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

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

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

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

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

実裝

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 クラスは主要なデータ構(gòu)造であり、プレーヤーの保存を擔當します。選手を入力し、上位 10 人の得點者を返すメソッドを定義します。

ハッシュ コンストラクターと関數(shù)

コンストラクターはデータを格納する配列を初期化し、ハッシュ メソッドは黃金定數(shù)を使用してインデックスを計算します。テーブル サイズの 2 のべき乗に関する懸念を回避できるため、乗算方法を選択しました。テーブル サイズは CSV ファイル內(nèi)のデータ量に基づいているため、この選択により、テーブル サイズを正確に制御しなくても、キーをより均等に分散することができます。

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 メソッドは、ゴール數(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;
    }
}

最終的な考慮事項

この実裝では、衝突処理を備えた単純なハッシュ テーブルを作成する方法と、オブジェクト (プレーヤーなど) をハッシュ テーブルに保存する方法を示します。反省點と改善點をいくつか挙げます:

• 衝突解決: パフォーマンスを向上させるために検討できる二次プローブや個別のチェーンなど、他の衝突解決方法もあります。
• サイズ変更: テーブルがいっぱいになるのを避けるために、動的なサイズ変更メカニズムを?qū)g裝できます。
• 代替ハッシュ関數(shù): さまざまなハッシュ関數(shù)をテストすると、スパース性が向上し、衝突が軽減されます。

コードリンクをたどる

以上がPHP でハッシュ テーブルを?qū)g裝してブラジルの得點王データを保存するの詳細內(nèi)容です。詳細については、PHP 中國語 Web サイトの他の関連記事を參照してください。