ハッシュテーブルに入れるには、償却された O(1) が必要だと人々は言います。したがって、n 個の要素を配置することは O(n) でなければなりません。ただし、回答者が言ったように、「予想される償却された O(1) を満たすために必要なのは、テーブルを拡張し、衝突が発生したときに新しいランダム ハッシュ関数を使用してすべてを再ハッシュすることだけです。」
では、ハッシュ テーブルに n 個の要素を挿入する平均実行時間は? これはおそらく実装に依存していると思いますので、どのタイプの実装について話しているのかを述べてください。
たとえば、(log n) 個の等間隔の衝突があり、各衝突の解決に O(k) かかる場合 (k はハッシュテーブルの現在のサイズ)、次の再帰関係が得られます。
T(n) = T(n/2) + n/2 + n/2
(つまり、時間をかけて n/2 要素を挿入すると、衝突が発生し、解決に n/2 がかかり、衝突なしで残りの n/2 挿入が行われます)。これでも O(n) になってしまいます。しかし、これは合理的ですか？
それは、再ハッシュがどれほど非効率的であるかに完全に依存します。具体的には、ハッシュテーブルの予想サイズを 2 回目に適切に見積もることができたとしても、ランタイムは O(n) に近づきます。実際には、予想される順序を決定する前に、再ハッシュ サイズの計算がどれほど非効率的であるかを指定する必要があります。
ハッシュテーブルに入れるには、償却された O(1) が必要だと人々は言います。
理論的な観点からは、償却された O(1)が期待されます。
クイックソートがランダム化されたアルゴリズムであるのと同じ意味で、ハッシュ テーブルは基本的にランダム化されたデータ構造です。ハッシュ関数をランダムに生成する必要があります。そうしないと、O(1) ではない病理学的入力が存在します。
動的完全ハッシュを使用して、予想される償却 O(1) を実現できます。
私が最初に投稿した単純なアイデアは、衝突ごとに新しいランダム ハッシュ関数で再ハッシュすることでした。(完全ハッシュ関数も参照してください) これに関する問題は、誕生日のパラドックスから、これには O(n^2) スペースが必要なことです。
解決策は、2 つのハッシュ テーブルを用意し、2 つ目のテーブルを衝突用にすることです。その 2 番目のテーブルを再構築することで衝突を解決します。そのテーブルには O(\sqrt{n}) 要素が含まれるため、O(n) サイズになります。
実際には、入力を事前にランダム化せずにクイックソートすることがよくあるように、入力が病的であると想定できる (または気にしない) ため、固定ハッシュ関数を使用することがよくあります。
O(1) が言っているのは、操作が一定時間で実行され、データ構造内の要素の数に依存しないということだけです。
簡単に言えば、これは、データ構造がどれほど大きくても、同じコストを支払わなければならないことを意味します。
実際には、これは、多くのデータを保存する必要がない場合、ツリーなどの単純なデータ構造が一般的により効果的であることを意味します。私の経験では、最大 1,000 個の要素 (32 ビット整数) までツリーが高速であることがわかり、その後はハッシュ テーブルが引き継がれます。でも相変わらずのYMMW。
システムでいくつかのテストを実行してみませんか? ソースを投稿していただければ、私たちのシステムに戻ってテストすることができ、非常に有益な議論になる可能性があります。
実装だけでなく、アルゴリズムが実際にかかる時間を決定するのは環境でもあります。ただし、ベンチマーク サンプルが利用可能かどうかを調べることはできます。私のシステムで他に何が実行されているか、現在どれだけの RAM が空いているかなどがわからないため、結果を投稿することの問題は役に立ちません。広い考えを持つことしかできません。そして、それはbig-Oがあなたに与えるものとほぼ同じです.