[解決済み] HashMapのget/putの複雑さ

質問

私たちは、よく次のように言います。 HashMap get/put の演算はO(1)です。しかし、それはハッシュの実装に依存する。デフォルトのオブジェクトハッシュは、実際にはJVMヒープ内の内部アドレスである。と主張するのは良いのだろうか？ get/put はO(1)なのでしょうか？

利用可能なメモリも問題です。javadocsから理解しているように HashMap ロードファクターは0.75であるべきです。もし、JVMに十分なメモリがなく、ロードファクターが制限を超えたらどうなりますか？

ということは、O(1)は保証されないようですね。それとも何か見落としているのでしょうか？

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

それは多くのことに依存します。それは 通常 まともなハッシュならO(1)で、それ自体は一定時間ですが、計算に長い時間がかかるハッシュもありえます。 そして ハッシュマップの中に同じハッシュコードを返す項目が複数ある場合。 get を呼び出すと、それらを繰り返し実行する必要があります。 equals をそれぞれ使って、一致するものを探します。

最悪の場合 HashMap は、同じハッシュバケツ内のすべてのエントリを走査するため（たとえば、それらがすべて同じハッシュコードを持つ場合）、O(n)のルックアップが発生します。幸いなことに、私の経験では、そのような最悪のシナリオは現実にはあまり出てきません。しかし、どのアルゴリズムやデータ構造を使うかを検討する際には、通常、O(1)を仮定すべきなのです。

JDK8では HashMap が調整され、キーが順序を比較できる場合、密に配置されたバケツはツリーとして実装され、同じハッシュコードのエントリーがたくさんあったとしても、その複雑さは O(log n) となります。もちろん、等値性と順序性が異なるキータイプがある場合には、問題が発生する可能性があります。

そうそう、ハッシュマップに十分なメモリがないと大変なことになるけど、これはどんなデータ構造を使っても同じことだね。