這個編程主題是我這學期在大學里遇到的，如果不是她，我想我不會遇到這個主題。我發(fā)現(xiàn)它很有趣，所以我嘗試根據(jù)我所理解的內(nèi)容制作一個教程，當然它不會完整，只是涵蓋我認為最有趣的點。在本文中，我們將探索 PHP 中的哈希表實現(xiàn)，用于存儲和組織足球運動員數(shù)據(jù)，并按進球數(shù)對其進行排序。

什么是哈希表？

哈希表是允許有效檢索信息的數(shù)據(jù)結(jié)構(gòu)。由于它們在大多數(shù)搜索和插入操作中具有恒定的平均時間性能，因此廣泛應(yīng)用于從數(shù)據(jù)庫到緩存的各個編程領(lǐng)域。以及一個使用哈希函數(shù)將鍵映射到數(shù)組中的位置的框架。當我們想要存儲一個值時，我們使用哈希函數(shù)來計算它應(yīng)該插入的位置。當我們需要檢索這個值時，我們應(yīng)用相同的哈希函數(shù)來快速找到它的位置。

哈希表的注意點

• 沖突：當兩個不同的鍵生成相同的哈希索引時，就會發(fā)生沖突。如果發(fā)生碰撞，我們的實現(xiàn)使用線性輪詢來查找數(shù)組中的下一個可用位置。
• 搜索性能：為了使搜索高效，哈希函數(shù)均勻分布數(shù)據(jù)非常重要。在此實現(xiàn)中，我們使用黃金常數(shù)作為哈希函數(shù)的基礎(chǔ)，這是一種已知有助于均勻散射的方法。

執(zhí)行

1. 玩家等級

Player 類代表每個球員，存儲他們的姓名和進球數(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類是主要的數(shù)據(jù)結(jié)構(gòu)，負責存儲玩家。它定義了輸入玩家和返回前 10 名得分手的方法。

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

構(gòu)造函數(shù)初始化存儲數(shù)據(jù)的數(shù)組，而哈希方法則使用黃金常量計算索引。我選擇了乘法方法，因為它避免了對表大小中 2 的冪的擔憂。由于表大小基于 CSV 文件中的數(shù)據(jù)量，因此即使無法精確控制表大小，此選擇也有助于確保鍵的分布更加均勻。

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 對象插入表中。如果生成的索引已被占用，我們將應(yīng)用線性輪詢，直到找到空位置。

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 方法按進球數(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.");
    }

測試哈希表

以下是如何將玩家添加到表中并獲取前 10 名得分手的示例：

    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;
    }
}

最后的考慮因素

此實現(xiàn)演示了如何創(chuàng)建具有碰撞處理功能的簡單哈希表以及如何在哈希表中存儲對象（例如玩家）。以下是一些反思和改進的點：

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

關(guān)注代碼鏈接

以上是在 PHP 中實現(xiàn)哈希表來存儲巴西得分王數(shù)據(jù)的詳細內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！