[解決済み] Javaのハッシュマップ検索は本当にO(1)なのか？

質問

SOで、Javaのハッシュマップとその O(1) ルックアップに時間がかかる。なぜそうなのか、誰か説明してください。これらのハッシュマップが、私が買ってきたどのハッシュアルゴリズムとも大きく異なっていない限り、衝突を含むデータセットが常に存在するはずです。

その場合、ルックアップは O(n) ではなく O(1) .

なのか、誰か説明してください。 は O(1)であるとすれば、それをどのように達成するのか？

どのように解決するのですか？

HashMapの特徴は、例えばバランス木と違って、その挙動が確率的であることだ。 このような場合、通常、最悪の事態が発生する確率という観点から複雑さを語るのが最も有用である。 ハッシュ・マップの場合、それはもちろん、マップがどれだけ完全であるかということに関して、衝突が発生する場合です。 衝突の発生確率を見積もるのはとても簡単です。

p <サブ 衝突 = n / 容量

つまり、それなりの数の要素を持つハッシュマップでも、少なくとも1回は衝突が発生する可能性が高いということです。 ビッグ・オー表記を使えば、もっと説得力のあることができる。任意の固定定数kについて、次のことを観察してください。

O(n) = O(k * n)

この特徴を利用して、ハッシュマップの性能を向上させることができるのです。 代わりに、最大で2回の衝突が起こる確率を考えることもできる。

p <サブ 衝突×2 = (n / 容量) ²

これはかなり低くなりましたね。 1つの余分な衝突を処理するコストはBig Oのパフォーマンスとは無関係なので、実際にアルゴリズムを変更せずにパフォーマンスを向上させる方法を見つけたのです これを一般化すると

p <サブ 衝突 x k = (n / 容量) ^k

そして、任意の数の衝突を無視することができ、考慮した以上の衝突が発生する可能性は限りなく低くなります。 正しいkを選択することによって、アルゴリズムの実際の実装を変更することなく、任意の小さなレベルまで確率を得ることができます。

このことを、ハッシュマップのアクセス数はO(1)であると言っています。 高い確率で