私は二重ハッシュをしようとしていますが、二重ハッシュ関数 h' を使用するとどうなるか混乱しています。
最初のハッシュ関数が衝突した場合、二次ハッシュ関数の値が最初のハッシュ関数の値に追加されますか?
私は多くの方法を試しましたが、これを理解することができませんでした.問題の問題は、次のリンクの画像です:
http://postimg.org/image/k6ko6e0gp/
これはダブルハッシュでどのように解決されますか? 配列にはすでに 3 つの要素があり、さらに 3 つを挿入する必要があります
ダブル ハッシングは、衝突 (複数のキーが 1 つのインデックスにハッシュされる) を解決する方法です。ダブルハッシュでは、2 つのハッシュ関数が使用されます。衝突が発生した場合、2 番目のハッシュ関数を使用して、キーを配置するための空のセルをテーブルで検索するステップ サイズを見つけます。このリンクは、考えられる衝突解決方法の概要を示しています。http://www.cs.utexas.edu/users/mitra/csSpring2016/cs313/lectures/hash.html
あなたの場合、添付された画像を確認した後、キー 16 がインデックス 6 の他のキーと衝突することは明らかであるため、2 番目のハッシュ関数を適用してステップ サイズを決定する必要があります。最初のハッシュのインデックスから、(ステップ サイズ) 番目の要素ごとに空のセルがチェックされます。空のセルが見つかると、そのセルにキーが配置されます。たとえば、最初のハッシュ インデックスが 0 で、ステップ サイズが 2 の場合、インデックス 0、2、4 .. をチェックする必要があります。場合によっては、空のセルを見つけるためにテーブルの先頭に戻る必要があることに注意してください。
したがって、添付の画像によると、キー 16 は 2 のステップ サイズを取得します。したがって、6 から、ステップ サイズ 2 で、次に使用可能なスロットはインデックス 1 であり、これは空いています :)
この場合、空のセルが見つからない場合、ハッシュ テーブルは新しい容量でサイズ変更されます。これは、テーブル内のすべての要素を再ハッシュする必要があるため、一般にコストのかかる操作である再ハッシュとして知られています。これは、テーブルが特定のサイズのしきい値に達した後に行われます。