PHP コアテクノロジーとベストプラクティス間のハッシュテーブルの競合_PHP チュートリアル

PHPコアテクノロジーとベストプラクティス間のハッシュテーブルの競合

PHPコアテクノロジーとベストプラクティス間のハッシュテーブルの競合

前回の記事に続き、テスト後、value1value2を出力します

。

$ht->insert('key12','value12');

Echo $ht ->find(‘key12’);,

value12value12 が出力されていることがわかります。これはなぜですか?

この問題はハッシュテーブルの競合と呼ばれます。挿入は文字列であるため、文字列の ASIIC コードを追加するアルゴリズムが使用されます。この方法では競合が発生します。 key12とkey1のハッシュ値を出力すると、両方とも8であることがわかります。つまり、value1とvalue12はハッシュテーブルの9番目の位置に同時に格納されている（インデックスは0から始まる）ので、 value1 の値は value12 によって上書きされます。

競合を解決するために一般的に使用される方法は、オープン アドレス指定方法とジッパー方法です。ジッパーは理解しやすいため、この記事ではジッパー方式を使用して競合の問題を解決します。

競合を解決するための Zip メソッド:

その方法は、同じハッシュ値キーノードをすべて同じリンクリスト内でリンクすることです。

ジッパーメソッドは、リンクされたリスト内の同じハッシュ値を持つキーノードを接続します。その後、要素を検索するときに、リンクされたリスト内の各要素のキーワードが検索されたキーワードと等しいかどうかを比較する必要があります。が等しい、we を検索する要素。

ノードはキーワード（キー）とデータ（値）を保存し、同じハッシュ値を持つノードを記録する必要があるためです。したがって、この情報を保存する HashNode クラスを作成します。

HashNode の構造は次のとおりです:

リーリー

HashNode には、$key、$value、$nextNode の 3 つの属性があります。 $key はノードのキー、$value はノードの値、$nextNode は同じハッシュ値を持つノードへのポインタです。次に、挿入方法を次のように変更します:

リーリー

変更された挿入アルゴリズムのフローは次のとおりです:

1) ハッシュ関数を使用してキーワードのハッシュ値を計算し、ハッシュ値を介してハッシュ テーブル内の指定された位置を特定します。

2) この位置がすでに他のノードによって占められている場合は、新しいノードの $nextNode をこのノードにポイントし、それ以外の場合は新しいノードの $nextNode を null に設定します。

3) 新しいノードをハッシュ テーブルの現在の場所に保存します。

これらの 3 つの手順の後、同じハッシュ値を持つノードが同じリンク リストに接続されます。

それに応じて、検索アルゴリズムは次の形式に変更されます:

リーリー

変更された検索アルゴリズムのプロセスは次のとおりです:

1) ハッシュ関数を使用してキーワードのハッシュ値を計算し、ハッシュ値を介してハッシュ テーブル内の指定された位置を特定します。

2) 現在のリンク リストを走査し、リンク リスト内の各ノードのキーを比較し、キーが等しいかどうかを確認します。それらが等しい場合、検索は成功します。

3) リンクされたリスト全体にキーワードが見つからない場合、検索は失敗します。

テスト後、競合の問題はジッパー方式を使用して解決されました。

http://www.bkjia.com/PHPjc/984758.htmlwww.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/984758.html技術記事 PHP のコア技術とベストプラクティスのハッシュテーブルの競合 前回の記事の続きですが、テスト後、 $ht-insert(key12,value12); とすると value1value2 が出力されます。