ダブルハッシングを使用した2番目のケースの衝突の解決

Question

2番目の衝突のケースがある場合、これはどのように解決されますか？

IE：

のは、我々は数字の配列を持っているとしましょう：

[22、1、13、11、24、-1、-1、-1、-1、-1、 - 1] -1アレイ内の空示し

....

我々は

h1(key) = key % 11 
h2(key) = 7 - (key % 7) 

受け渡しを使用して33を挿入しようとした場合33で2を与え、配列位置2は既に占有されている（13で）。この衝突事件はどのように処理しますか？返されたmod値を再びh2に渡しますか？私はその値を@その配列値に置き換えますか？ （私は後者のケースではないと思う。）

編集：ダブルハッシュで

Answer 1

をH2に追加しました括弧、あなたに位置を計算：

pos = (h1 + i * h2) mod table_size 

をここにトリックがするまでiをインクリメントすることですハッシュテーブル内の空の位置が見つかる。したがって、計算は1回だけでなく、スロットが見つかるまで複数回実行されます。詳細は、Wikipedia articleを参照してください。

二重ハッシングと同様に非常に効率的なオープンアドレッシングの他の形式もあります。たとえば、cuckoo hashingとrobin-hood hashingです。