hashtable - ダブルハッシュ関数でオープンアドレスの過酷なテーブル全体を埋める

Question

素数に基づくオープン アドレス ハッシュで、ハッシュ テーブル内のすべてのエントリをダブル ハッシュで埋めることができますか?

Answer 1

些細なことですが、はい。ハッシュ テーブルにnバケットがある場合は、n要素を挿入するだけです。

二重ハッシュ プローブ シーケンスは、すべてのバケットにヒットするように設計する必要があります (そうでない場合は、スキームの欠陥になります)。特に、これは、2 番目のハッシュ関数が 0 mod n に評価されてはならないことを意味します。これは、それ以外の場合は 0 になる場合に、強制的に 1 にすることで保証できます。