空のハッシュテーブルにn個の要素を挿入するランタイム

Question

人々は、ハッシュ表に入れるには償却済みのO（1）が必要だと言います。したがって、n個の要素を置くことはO（n）でなければなりません。ただし、回答者が言ったように、「予想される償却O（1）を満たすために必要なのは、衝突が発生したときにテーブルを展開し、新しいランダムハッシュ関数ですべてを再ハッシュすることだけです」と、nが大きい場合は当てはまりません;

では：ハッシュテーブルにn個の要素を挿入する平均実行時間はどのくらいですか？これはおそらく実装依存であることを理解しているので、あなたが話している実装のタイプを述べてください。

たとえば、（log n）等間隔の衝突があり、各衝突が解決するためにO（k）を取る場合（kはハッシュテーブルの現在のサイズ）、この再帰関係があります：

T(n) = T(n/2) + n/2 + n/2

（つまり、n / 2個の要素を挿入するのに時間がかかり、衝突が発生し、n / 2を解決してから、残りのn / 2個の挿入を衝突なしで実行します）。これはまだO（n）であるため、いやです。しかし、これは合理的ですか？

Answer 1

それは完全に、リハッシュがどれだけ効率的でないかにかかっています。具体的には、2回目にハッシュテーブルの予想サイズを適切に推定できる場合、ランタイムは引き続きO（n）に近づきます。効果的には、予想される順序を決定する前に、リハッシュサイズの計算の非効率性を指定する必要があります。

Answer 2

  

人々は、ハッシュ表に入れるには償却済みのO（1）が必要だと言います。

理論的な観点から、それは予想償却O（1）です。

ハッシュテーブルは、基本的に、クイックソートがランダム化アルゴリズムであるという意味で、ランダム化されたデータ構造です。ハッシュ関数をランダムに生成する必要があります。そうしないと、O（1）ではない病理学的入力が存在します。

動的完全ハッシュを使用して、予想される償却O（1）を実現できます。

>

私が最初に投稿した素朴なアイデアは、衝突ごとに新しいランダムハッシュ関数で再ハッシュすることでした。 （完全なハッシュ関数も参照してください）これに関する問題は、O（n ^ 2 ）誕生日の逆説からの空間。

解決策は、衝突用の2番目のテーブルを備えた 2つのハッシュテーブルを持つことです。 2番目のテーブルを再構築して、衝突を解決します。そのテーブルにはO（\ sqrt {n}）要素があるため、O（n）サイズになります。

実際には、入力が事前にランダム化されずにクイックソートされることが多いように、入力が病理学的であると想定できる（または気にしない）ため、固定ハッシュ関数を使用することがよくあります。

Answer 3

O（1）が言っているのは、操作が一定時間で実行されるということであり、データ構造内の要素の数に依存しない です。

簡単に言えば、これは、データ構造がどれほど大きくても同じコストを支払う必要があることを意味します。

実際には、これは、大量のデータを保存する必要がない場合、ツリーなどの単純なデータ構造が一般的に より効果的であることを意味します。私の経験では、最大で1k要素（32ビット整数）までのツリーが高速であることがわかり、ハッシュテーブルが引き継ぎます。しかし、いつものようにYMMW。

Answer 4

システムでいくつかのテストを実行するだけではどうですか？もしあなたがソースを投稿するなら、私たちは戻って私たちのシステム上でそれらをテストすることができ、私たちはこれを非常に有用な議論に形作ることができます。

アルゴリズムだけで実際にかかる時間は、実装ではなく環境によって決まります。ただし、ベンチマークサンプルが利用可能かどうかを確認できます。私のシステムで他に何が実行されているのか、現在どのくらいのRAMが空いているかなど、人々は知らないので、結果を投稿することに関する問題は役に立たないでしょう。広いアイデアしか持てません。これは、big-Oが提供するものとほぼ同じくらい優れています。