PHP でハッシュテーブルを実装してブラジルの得点王データを保存する-PHPチュートリアル-php.cn

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

Barbara Streisand

リリース： 2024-11-08 08:03:01

オリジナル

385 人が閲覧しました

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

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

ログイン後にコピー