這個(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ù)對(duì)其進(jìn)行排序。

什么是哈希表？

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

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

• 沖突：當(dāng)兩個(gè)不同的鍵生成相同的哈希索引時(shí)，就會(huì)發(fā)生沖突。如果發(fā)生碰撞，我們的實(shí)現(xiàn)使用線性輪詢來查找數(shù)組中的下一個(gè)可用位置。
• 搜索性能：為了使搜索高效，哈希函數(shù)均勻分布數(shù)據(jù)非常重要。在此實(shí)現(xiàn)中，我們使用黃金常數(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類是主要的數(shù)據(jù)結(jié)構(gòu)，負(fù)責(zé)存儲(chǔ)玩家。它定義了輸入玩家和返回前 10 名得分手的方法。

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

構(gòu)造函數(shù)初始化存儲(chǔ)數(shù)據(jù)的數(shù)組，而哈希方法則使用黃金常量計(jì)算索引。我選擇了乘法方法，因?yàn)樗苊饬藢?duì)表大小中 2 的冪的擔(dān)憂。由于表大小基于 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 對(duì)象插入表中。如果生成的索引已被占用，我們將應(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 方法按進(jìn)球數(shù)對(duì)表格進(jìn)行排序，并返回前 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;
    }
}

最后的考慮因素

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

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

關(guān)注代碼鏈接

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