這個(gè)程式主題是我這學(xué)期在大學(xué)裡遇到的，如果不是她，我想我不會(huì)遇到這個(gè)主題。我發(fā)現(xiàn)它很有趣，所以我嘗試根據(jù)我所理解的內(nèi)容製作一個(gè)教程，當(dāng)然它不會(huì)完整，只是涵蓋我認(rèn)為最有趣的點(diǎn)。在本文中，我們將探索 PHP 中的哈希表實(shí)現(xiàn)，用於儲(chǔ)存和組織足球運(yùn)動(dòng)員數(shù)據(jù)，並按進(jìn)球數(shù)進(jìn)行排序。

什麼是哈希表？

雜湊表是允許有效檢索資訊的資料結(jié)構(gòu)。由於它們?cè)诖蠖鄶?shù)搜尋和插入操作中具有恆定的平均時(shí)間性能，因此廣泛應(yīng)用於從資料庫(kù)到快取的各個(gè)程式設(shè)計(jì)領(lǐng)域。以及一個(gè)使用雜湊函數(shù)將鍵映射到數(shù)組中的位置的框架。當(dāng)我們想要儲(chǔ)存一個(gè)值時(shí)，我們使用雜湊函數(shù)來(lái)計(jì)算它應(yīng)該插入的位置。當(dāng)我們需要檢索這個(gè)值時(shí)，我們應(yīng)用相同的雜湊函數(shù)來(lái)快速找到它的位置。

哈希表的注意點(diǎn)

• 衝突：當(dāng)兩個(gè)不同的鍵產(chǎn)生相同的雜湊索引時(shí)，就會(huì)發(fā)生衝突。如果發(fā)生碰撞，我們的實(shí)作使用線性輪詢來(lái)尋找陣列中的下一個(gè)可用位置。
• 搜尋效能：為了使搜尋高效，雜湊函數(shù)均勻分佈資料非常重要。在此實(shí)作中，我們使用黃金常數(shù)作為雜湊函數(shù)的基礎(chǔ)，這是已知有助於均勻散射的方法。

執(zhí)行

1. 玩家等級(jí)

Player 類別代表每個(gè)球員，儲(chǔ)存他們的姓名和進(jìn)球數(shù)。

class Jogador
{
    private $nome = "";
    private $gols = 0;

    public function getNome()
    {
        return $this->nome;
    }

    public function setNome($nome)
    {
        $this->nome = $nome;
    }

    public function getGols()
    {
        return $this->gols;
    }

    public function setGols($gols)
    {
        if (is_numeric($gols) && $gols >= 0) {
            $this->gols = $gols;
        } else {
            throw new Exception("O número de gols deve ser um valor numérico e n?o negativo.");
        }
    }
}

2. 哈希表類

HashTable類別是主要的資料結(jié)構(gòu)，負(fù)責(zé)儲(chǔ)存玩家。它定義了輸入玩家和返回前 10 名得分手的方法。

哈希構(gòu)造函數(shù)和函數(shù)

建構(gòu)函式初始化儲(chǔ)存資料的數(shù)組，而雜湊方法則使用黃金常數(shù)計(jì)算索引。我選擇了乘法方法，因?yàn)樗苊饬藢?duì)錶大小中 2 的冪的擔(dān)憂。由於表大小是基於 CSV 檔案中的資料量，因此即使無(wú)法精確控製表大小，此選擇也有助於確保鍵的分佈更加均勻。

class Jogador
{
    private $nome = "";
    private $gols = 0;

    public function getNome()
    {
        return $this->nome;
    }

    public function setNome($nome)
    {
        $this->nome = $nome;
    }

    public function getGols()
    {
        return $this->gols;
    }

    public function setGols($gols)
    {
        if (is_numeric($gols) && $gols >= 0) {
            $this->gols = $gols;
        } else {
            throw new Exception("O número de gols deve ser um valor numérico e n?o negativo.");
        }
    }
}

帶有碰撞處理的插入

put 方法將 Player 物件插入表中。如果產(chǎn)生的索引已被佔(zhàn)用，我們將套用線性輪詢，直到找到空白位置。

class HashTable
{
    private $total_filme = 0;
    private $tabelaHas = [];

    public function __construct(int $max)
    {
        $this->total_filme = $max;
        $this->tabelaHas = array_fill(0, $max, null);
    }

    private function hash(int $numero_gols)
    {
        $a = 0.6180339887;
        $frac = $numero_gols * $a - floor($numero_gols * $a);
        return (int) ($this->total_filme * $frac);
    }

提取得分最高的 10 名球員

top10Gunners 方法以進(jìn)球數(shù)排序，並傳回前 10 名得分手。

    public function put(int $numero_gols, Jogador $jogador)
    {
        $posicao = $this->hash($numero_gols);

        for ($i = 0; $i < $this->total_filme; $i++) {
            $novaPosicao = ($posicao + $i) % $this->total_filme;

            if (is_null($this->tabelaHas[$novaPosicao])) {
                $this->tabelaHas[$novaPosicao] = $jogador;
                return;
            }
        }

        throw new Exception("Tabela hash está cheia. N?o foi possível inserir.");
    }

測(cè)試哈希表

以下是如何將玩家加入表中並取得前 10 名得分手的範(fàn)例：

    public function top10Artilheiros()
    {

        usort($this->tabelaHas, function ($a, $b) {

            if ($a->getGols() == $b->getGols()) {
                return 0;
            }

            return ($a->getGols() > $b->getGols()) ? -1 : 1;
        });

        $artilheiros = $this->tabelaHas;

        return array_slice($artilheiros, 0, 10);
    }

    public function getTabelaH()
    {
        return $this->tabelaHas;
    }
}

最後的考慮因素

此實(shí)作示範(fàn)如何建立具有碰撞處理功能的簡(jiǎn)單雜湊表以及如何在雜湊表中儲(chǔ)存物件（例如玩家）。以下是一些反思和改進(jìn)的要點(diǎn)：

• 碰撞解決：還有其他碰撞解決方法，例如二次探測(cè)和單獨(dú)鏈接，可以探索以提高性能。
• 調(diào)整大小：為了避免表滿，我們可以實(shí)現(xiàn)動(dòng)態(tài)調(diào)整大小機(jī)制。
• 替代雜湊函數(shù)：測(cè)試不同的雜湊函數(shù)可以提高稀疏性並減少衝突。

關(guān)注程式碼連結(jié)

以上是在 PHP 中實(shí)作哈希表來(lái)儲(chǔ)存巴西得分王數(shù)據(jù)的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！