PHP でハッシュ テーブルを実装してブラジルの得点王データを保存する

このプログラミングのトピックは私が今学期大学で出会ったもので、彼女がいなかったらこのトピックに出会うことはなかったと思います。面白かったので、理解した内容をチュートリアルにしてみました。もちろん完全ではありませんが、最も興味深かった点だけを取り上げています。この記事では、サッカー選手のデータをゴール数順に並べて保存および整理するための、PHP でのハッシュ テーブルの実装について説明します。

ハッシュテーブルとは何ですか?

ハッシュ テーブルは、情報を効率的に取得できるようにするデータ構造です。これらは、ほとんどの検索および挿入操作で平均時間のパフォーマンスが一定であるため、データベースからキャッシュに至るまで、プログラミングのさまざまな分野で広く使用されています。そして、ハッシュ関数を使用してキーを配列内の位置にマップするフレームワークです。値を保存したい場合は、ハッシュ関数を使用して値を挿入する位置を計算します。この値を取得する必要がある場合、同じハッシュ関数を適用してその位置をすばやく見つけます。

ハッシュテーブルの注意点

• 衝突: 2 つの異なるキーが同じハッシュ インデックスを生成すると、衝突が発生します。私たちの実装では、衝突が発生した場合に、線形ポーリングを使用して配列内の次に利用可能な位置を見つけます。
• 検索パフォーマンス: 検索を効率的に行うためには、ハッシュ関数がデータを均等に分散することが重要です。この実装では、ハッシュ関数の基礎として 黄金定数 を使用します。これは、均一な散乱に役立つことが知られている方法です。

実装

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 中国語 Web サイトの他の関連記事を参照してください。