本書CLRS によるアルゴリズムの紹介では、各キーのプローブ シーケンスが m! <0,1,2,...m-1> の順列。次に、この本は 3 つのスキームを紹介します。
これらすべての前述の手法は、各キー k に対して <<0,1,2,...m-1> の順列であることを保証します。しかし、m^2 を超える異なるプローブ シーケンスを生成できるものはないため、均一ハッシュの仮定を満たすものはありません。ダブル ハッシングはプローブ シーケンスの数が最も多く、最良の結果が得られるようです。
プローブ配列の最大数が必要なのはなぜですか? プローブ配列が最小の場合、最高のパフォーマンスが得られませんか? ここで欠けている基本事項がいくつかあると確信しています。プローブとプローブ配列の間で混乱していると思います。
ここでの主なアイデアは、大きな数 (または基本的には数で表さfれる s の可能性があります) をより扱いやすい小さな数にマップする関数が必要だということです。これらの小さい数値は通常、配列内のインデックスとして直接使用されるため、によって保証される
一定のアクセス時間を取得できます。
この関数は通常、ハッシュ関数です。
ここでの問題は、大きなスペースから小さなスペースに移動するため、衝突が発生することになります (アクセス時間の保証に影響します)。
衝突に対処する方法については (使用するハッシュ関数を既に決定していると仮定して)、さまざまなアプローチがあり、そのうちの 3 つについて言及されています。 StringO(1)HashTablef
Linear Probingは、空のセルが見つかるまで基本的に配列を順番に検索する最も単純な衝突解決戦略です。これを実装するのは簡単ですが、hashtable.
要約すると、同じハッシュを持つ両方のアイテムが衝突するだけでなく、別の場所で衝突するアイテムもあるという事実により、パフォーマンスが低下します。
Quadratic ProbingLinear元のプローブ ポイントよりもさらにセルを占有しようとすることで、改善を試みます。大幅に改善されますLinear Probingが、二次クラスタリングが導入されます (同じハッシュ プローブを持つ要素は、配列内の同じ代替位置にもなります)。
Double Hashingさらに改善されQuadratic Probing、理論的には（私が思うに）線形と同じ数またはプローブを持つはずです。
二重ハッシングは最大数のプローブ シーケンスを持ち、最良の結果をもたらすようです...なぜ最大数のプローブ シーケンスが必要なのですか?
はい、理論的にはその方が良いですQuadratic。ここで IMO が意味するのは、プローブする場所が最も離れているため、(元のバケットよりも) 別の場所にある同じハッシュまたは異なるハッシュの要素間の衝突を排除することです。