PHP がハッシュの競合をどのように解決するかについて話し合う

プログラミングにおいて、ハッシュ テーブルは非常に便利なデータ構造です。要素の検索と挿入は O(1) 時間で実行できますが、ハッシュ関数はハッシュ衝突を引き起こす可能性があります。これは、2 つの異なるキー値が同じインデックスにマップされている場合に発生する問題です。この記事では、ハッシュ衝突の問題を解決するいくつかの方法と、それらを PHP で実装する方法を検討します。

1. チェーン アドレス方式
   チェーン アドレス方式は、ハッシュの競合を解決するための最も簡単で一般的な方法の 1 つです。チェーン アドレス方式では、各ハッシュ テーブル スロットはリンク リストを指し、各ノードにはキーと値のペアが含まれます。ハッシュの衝突が発生すると、リンクされたリストのその位置に新しい要素が追加されます。要素を探すときは、リンクされたリストをたどってノードを見つけるだけです。

PHP では、配列を使用してチェーン アドレス メソッドを実装できます。たとえば、次は簡単な実装です:

class Hashtable {
    private $table = array();
  
    public function put($key, $value) {
        $hash = $this->hashFunction($key);
        if (!isset($this->table[$hash])) {
            $this->table[$hash] = array();
        }
        foreach ($this->table[$hash] as &$v) {
            if ($v['key'] == $key) {
                $v['value'] = $value;
                return;
            }
        }
        $this->table[$hash][] = array('key' => $key, 'value' => $value);
    }
  
    public function get($key) {
        $hash = $this->hashFunction($key);
        if (isset($this->table[$hash])) {
            foreach ($this->table[$hash] as $v) {
                if ($v['key'] == $key) {
                    return $v['value'];
                }
            }
        }
        return null;
    }
  
    private function hashFunction($key) {
        return crc32($key); // 简单的哈希函数
    }
}

この例では、ハッシュ テーブル クラス Hashtable を定義します。 crc32 ハッシュ関数を使用して各キーのハッシュ値を計算し、キーと値のペアを 2 次元配列に格納します。要素を検索または挿入する必要がある場合、まずそのハッシュ値を計算し、次にハッシュ値が存在する場所がすでに存在するかどうかを確認します。存在しない場合は、新しいリストを作成し、その要素をリストに追加します。位置がすでに存在する場合は、リストを反復処理し、キーに対応する要素を見つけて、値を置き換えます。この実装は非常に単純ですが、ハッシュ テーブルのサイズが大きくなると、リンク リストの長さが非常に長くなり、検索の効率に影響を与える可能性があります。

2. オープン アドレッシング メソッド
   オープン アドレッシング メソッドは、ハッシュ衝突を解決するもう 1 つの方法です。オープン アドレッシングでは、ハッシュの衝突が発生した場合、リンク リストに新しい要素を追加するのではなく、元の位置から空きスロットを探し続け、最初に使用可能な位置に要素を挿入します。この方法の利点は、リンク リストを必要とせず、メモリ使用量を削減できることです。

PHP では、配列を使用してオープン アドレッシングを実装できます。たとえば、簡単な実装を次に示します。

class Hashtable {
    private $table = array();
  
    public function put($key, $value) {
        $i = $this->hashFunction($key);
        $j = $i;
        do {
            if (!isset($this->table[$j])) {
                $this->table[$j] = array('key' => $key, 'value' => $value);
                return;
            }
            if ($this->table[$j]['key'] == $key) {
                $this->table[$j]['value'] = $value;
                return;
            }
            $j = ($j + 1) % count($this->table);
        } while ($j != $i);
    }
  
    public function get($key) {
        $i = $this->hashFunction($key);
        $j = $i;
        do {
            if (isset($this->table[$j])) {
                if ($this->table[$j]['key'] == $key) {
                    return $this->table[$j]['value'];
                }
            } else {
                return null;
            }
            $j = ($j + 1) % count($this->table);
        } while ($j != $i);
        return null;
    }
  
    private function hashFunction($key) {
        return crc32($key); // 简单的哈希函数
    }
}

この例では、別のハッシュ テーブル クラス Hashtable を定義します。このクラスは crc32 ハッシュ関数を使用して各キーのハッシュ値を計算し、キーと値のペアは次の場所に保存されます。一次元配列。要素を検索または挿入する必要がある場合、まずそのハッシュ値を計算し、その位置から配列の走査を開始します。位置が空の場合は、その位置に新しい要素を挿入します。位置がすでに占有されている場合は、空いている位置が見つかるまで、または配列全体を走査するまで、配列の走査を続けます。この実装の欠点の 1 つは、ハッシュ テーブルのサイズが大きくなると、ストレージを再割り当てし、既存の要素を新しい配列にコピーする必要があることです。

3. ダブルハッシュ法
   ダブルハッシュ法は、ハッシュが衝突した場合に新しい位置を見つけるために、ハッシュ関数を通じて一連のハッシュ値を生成する方法です。ダブルハッシュでは、2 つの異なるハッシュ関数を使用して各キーのハッシュ値を計算し、ハッシュ値のシーケンスに従って空の位置を見つけます。複数のハッシュ関数を使用すると、ハッシュの衝突の数が減り、検索効率が向上します。

PHP では、配列を使用して二重ハッシュを実装できます。たとえば、これは簡単な実装です:

class Hashtable {
    private $table = array();
  
    public function put($key, $value) {
        $i = $this->hashFunction1($key);
        $j = $this->hashFunction2($key);
        $k = $i;
        do {
            if (!isset($this->table[$k])) {
                $this->table[$k] = array('key' => $key, 'value' => $value);
                return;
            }
            if ($this->table[$k]['key'] == $key) {
                $this->table[$k]['value'] = $value;
                return;
            }
            $k = ($k + $j) % count($this->table);
        } while ($k != $i);
    }
  
    public function get($key) {
        $i = $this->hashFunction1($key);
        $j = $this->hashFunction2($key);
        $k = $i;
        do {
            if (isset($this->table[$k])) {
                if ($this->table[$k]['key'] == $key) {
                    return $this->table[$k]['value'];
                }
            } else {
                return null;
            }
            $k = ($k + $j) % count($this->table);
        } while ($k != $i);
        return null;
    }
  
    private function hashFunction1($key) {
        return crc32($key);
    }
  
    private function hashFunction2($key) {
        return ((int)(crc32($key) / count($this->table)) + 1) % count($this->table);
    }
}

この例では、別のハッシュ テーブル クラス Hashtable を定義します。これは 2 つのハッシュ関数を使用して各キーのハッシュ値を計算し、キーと値のペアを一次元配列。要素を検索または挿入する必要がある場合、まずそのハッシュ値を計算し、最初のハッシュ値を初期位置として使用し、2 番目のハッシュ値を使用して各検索のステップ サイズを計算します。位置が空の場合は、その位置に新しい要素を挿入します。位置がすでに占有されている場合は、空いている位置が見つかるまで、または配列全体を走査するまで、配列の走査を続けます。この実装の利点の 1 つは、2 つの異なるハッシュ関数を使用するとハッシュの衝突の数を減らすことができ、2 番目のハッシュ関数を使用すると「クラスタリング」状況の発生を減らすことができることです。

結論
PHP でのハッシュ テーブルの実装は、楽しくて役に立つ演習です。コードの実装中に、ハッシュの競合を解決するために一般的に使用される 3 つの方法、つまりチェーン アドレス方法、オープン アドレス方法、およびダブル ハッシュ方法が確認されました。各方法には長所と短所があるため、現在のアプリケーション シナリオに最も適した方法を選択する必要があります。

最後に、ハッシュ テーブルは検索および挿入操作では非常に効率的ですが、ハッシュ テーブルの負荷率が高すぎるとパフォーマンスが急激に低下することに注意する必要があります。したがって、要素を挿入するときに負荷係数をチェックし、必要に応じてメモリを再割り当てして、ハッシュ テーブルの効率的な動作を確保する必要があります。

以上がPHP がハッシュの競合をどのように解決するかについて話し合うの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。