在 PHP 中實作哈希表來儲存巴西得分王數據-php教程-PHP中文網

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

Barbara Streisand

發布： 2024-11-08 08:03:01

原創

383 人瀏覽過

Implementando uma Tabela Hash em PHP para Armazenar Dados de Artilheiros do Brasileirão

這個程式主題是我這學期在大學裡遇到的，如果不是她，我想我不會遇到這個主題。我發現它很有趣，所以我嘗試根據我所理解的內容製作一個教程，當然它不會完整，只是涵蓋我認為最有趣的點。在本文中，我們將探索 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;
    }
}

登入後複製