ハッシュテーブルΩ（n^2）ランタイム？

Question

私はこれについて本当に混乱しています。教科書を読んで練習をしても、それはどのように機能するのですか？残念ながら、私は教授を見るために人で行くことはできず、（夏のオンラインコース、異なるタイムゾーン）連絡するのはやや難しいです。私はちょうどこの問題をどうやって理解するのであれば、「クリックする」ような気がします。教科書はハッシュ関数とランタイムを個別に詳細にしていますが、私はこの質問が私たちが学んだことの範囲外であると感じています。誰かが私を助けるかもしれない何かを指すことができるなら、それは素晴らしいことでしょう。

1）ハッシュテーブルT [0 .. メートルから1]にメートルキーを挿入する過程を検討メートルが素数である、と我々はアドレッシングオープン使用。我々が使用するハッシュ関数は、H（K、I）= メートル MOD（K + I）です。 メートルキーK1、K2 ... キロの例を与える、次の一連の操作は、Ω（N^2）時間がかかるように：

インサート（K1） 、（K2）を挿入し、...、（キロ）

を挿入し、私は挿入操作は（1）時間や、いくつかのケースでは、O（n）のOを取ることになっていることを理解しています。それをΩ（n^2）時間に変える鍵は、どのくらい正確に思いつきますか？私はこれを理解したいと思っています。教科書の章はシンプルで、私には意味があるので、私はいくつか大きなヒントを見逃しているように思います。質問には、mが重要であると述べられていますが、これは重要ですか？私はちょうど失われているし、Googleはかつて私を失敗させる。

Answer 1

ここでのキーワードは、ハッシュ衝突です：

ためにはハッシュ関数がうまく動作するように、あなたはエントリはに格納されているすべてのm可能な値を超えるよく分散されるように、特定の入力の値を必要とするためハッシュテーブルに要素が挿入された数のエントリがある場合、すべての要素がハッシュ値（またはその近く）に格納されることを期待できます（少量のプロービングが必要であることを意味します）。時限操作。

ハッシュ関数が毎回同じ値（衝突）にマップする入力値が異なる場合、挿入中に、プロービングステップは、以前に追加されたすべての要素をスキップし、要素あたりΩ平均してしたがって、私たちはΩ（n²）の実行時間を得る