在 PHP 中實作哈希表來儲存巴西得分王數據

這個程式主題是我這學期在大學裡遇到的，如果不是她，我想我不會遇到這個主題。我發現它很有趣，所以我嘗試根據我所理解的內容製作一個教程，當然它不會完整，只是涵蓋我認為最有趣的點。在本文中，我們將探索 PHP 中的哈希表實現，用於儲存和組織足球運動員數據，並按進球數進行排序。

什麼是哈希表？

雜湊表是允許有效檢索資訊的資料結構。由於它們在大多數搜尋和插入操作中具有恆定的平均時間性能，因此廣泛應用於從資料庫到快取的各個程式設計領域。以及一個使用雜湊函數將鍵映射到數組中的位置的框架。當我們想要儲存一個值時，我們使用雜湊函數來計算它應該插入的位置。當我們需要檢索這個值時，我們應用相同的雜湊函數來快速找到它的位置。

哈希表的注意點

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

執行

1. 玩家等級

Player 類別代表每個球員，儲存他們的姓名和進球數。

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類別是主要的資料結構，負責儲存玩家。它定義了輸入玩家和返回前 10 名得分手的方法。

哈希構造函數和函數

建構函式初始化儲存資料的數組，而雜湊方法則使用黃金常數計算索引。我選擇了乘法方法，因為它避免了對錶大小中 2 的冪的擔憂。由於表大小是基於 CSV 檔案中的資料量，因此即使無法精確控製表大小，此選擇也有助於確保鍵的分佈更加均勻。

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 物件插入表中。如果產生的索引已被佔用，我們將套用線性輪詢，直到找到空白位置。

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 方法以進球數排序，並傳回前 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;
    }
}

最後的考慮因素

此實作示範如何建立具有碰撞處理功能的簡單雜湊表以及如何在雜湊表中儲存物件（例如玩家）。以下是一些反思和改進的要點：

• 碰撞解決：還有其他碰撞解決方法，例如二次探測和單獨鏈接，可以探索以提高性能。
• 調整大小：為了避免表滿，我們可以實現動態調整大小機制。
• 替代雜湊函數：測試不同的雜湊函數可以提高稀疏性並減少衝突。

關注程式碼連結

以上是在 PHP 中實作哈希表來儲存巴西得分王數據的詳細內容。更多資訊請關注PHP中文網其他相關文章！