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

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

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

前回の記事に引き続き、テスト後に value1value2 が出力されます。

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

Echo $ht ->find('key12'); のとき、

が見つかりました出力値12値12。その理由は何ですか?

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

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

競合を解決するジッパー方法:

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

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

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

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

  <?PHP       Class HashNode{              Public $key;              Public $value;              Public $nextNode;              Public function__construct($key,$value,$nextNode = null){       $this ->key = $key;       $this ->value = $value;       $this ->nextNode = $nextNode;}}?>

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

Public function insert($key,$value){                            $index= $this -> hashfunc($key);                            //新建一个节点       if(isset($this->buckets[$index])){              $newNode = new HashNode($key,$value,$this->buckets[$index])              }else{                            $newNode = newHashNode($key,$value,null);                            }                            $this -> buckets[$index] = $newNode;//保存新节点                     }

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

1) ハッシュ関数を使用して、キーを計算する 単語のハッシュ値は、ハッシュ値を通じてハッシュ テーブル内の指定された位置を見つけるために使用されます。

2) この位置が既に別のノードによって占有されている場合は、新しいノードの $nextNode がこのノードを指すようにし、それ以外の場合は、新しいノードの $nextNode を null に設定します。

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

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

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

Public functionfind($key){                           $index = $this ->hashfunc($key);                           $current =$this->buckets[$index];                           while(isset($current)){//遍历当前链表                                  if($current->key== $key){  //比较当前节点的关键字                                         return$current -> value;//查找成功                                  }                                  $current =$current ->nextNode;  //比较下一个节点                           }                           Return null;  //查找失败               }

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

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

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

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

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