ハッシュの意味での（衝突の）クラスタリングは何ですか？

Question

線形プロービングの主な問題はクラスタリングです。多くの連続する要素がグループを形成し、空きスロットを見つけたり、要素を検索する時間がかかり始めます。

なぜグループから連続する要素&空きスロットを見つける時間にどのように影響しますか？

Answer 1

ハッシュ関数の出力は、100個の文字列を200個の "ピジョンスロット"にランダムに散らばっていると言います。衝突の場合、すなわちすでに占有されているスロットの場合、線形スキャンは、次の占有されていないスロットを探索し、直ちに少なくとも2つのグループを作る（2つのグループを接続することもできる）。線形プロービングでは、クラスタに衝突が発生したときに、そのクラスタを元の位置がクラスタ内のどこにあってもよい新しいキーで追加します。

多くの高速ハッシュ関数を評価するには、キーを均等に分配しないという問題があります。また、入力データが均等に分布していない場合、これらの2つの現象はお互いを強調し、線形プロービングの場合、かなりの量のキーをクラスタリングする可能性があります。事実上、これは挿入だけでなく、O（1）の代わりにO（n）の問題を検索するでしょう。

Answer 2

常に連続する要素がクラスタを形成する場合。

Condictory例

はあなたが100エントリのハッシュテーブルがあるとしますと、ハッシュ関数は次のとおりです。

h(x) = x mod 100; 

は、あなたが要素を挿入言う：

948,748,172,973,473,572,72 

クラスターが形成され

クラスタ1：948(position 48),748(position 49)（が明確要素が連続していない）

クラスタ2：172(position 72),973(position 73),473(position 74),572(position 75),72(position 76)（明確要素連続していません）。

YESは、クラスタリングはlinear probingに、我々は原因のクラスタに起因するクラスタに、リニアスキャンは、より多くの時間がかかりますので、非常に次の空きスロットを見つけるために、ハッシュテーブルをスキャンするために形成され、空きスロットを見つけるための時間に影響を及ぼししかし、それはリニアスキャンの場合にのみ、の衝突のためです。