操作は O(1) であるとよく言われますHashMap get/put。ただし、これはハッシュの実装によって異なります。デフォルトのオブジェクト ハッシュは、実際には JVM ヒープ内の内部アドレスです。O(1) であると主張するだけで十分でしょうかget/put?
使用可能なメモリも別の問題です。Javadoc から理解したところによると、HashMap負荷係数は 0.75 である必要があります。JVM に十分なメモリがなく、負荷係数が制限を超えた場合はどうなるでしょうか?
つまり、O(1) は保証されていないようです。これは理にかなっていますか、それとも何か見落としているのでしょうか?
ベストアンサー1
それは多くのことに依存します。いつものO(1)、それ自体は定数時間で計算できる適切なハッシュですが、計算に長い時間がかかるハッシュもあります。そしてハッシュ マップ内に同じハッシュ コードを返す項目が複数ある場合は、各項目を呼び出し、一致するものを見つけるためにgetそれらを反復処理する必要があります。equals
最悪の場合、HashMap同じハッシュ バケット内のすべてのエントリを調べるため (たとえば、すべてのエントリが同じハッシュ コードを持つ場合)、検索には O(n) の時間がかかります。幸い、私の経験では、この最悪のシナリオは現実にはあまり発生しません。したがって、O(1) が保証されるわけではありませんが、通常、どのアルゴリズムとデータ構造を使用するかを検討する際には、これを想定する必要があります。
JDK 8 では、HashMapキーを比較して順序付けできる場合、密集したバケットはツリーとして実装されるように調整されており、同じハッシュ コードを持つエントリが多数ある場合でも、複雑さは O(log n) になります。もちろん、等価性と順序付けが異なるキー タイプがある場合は、問題が発生する可能性があります。
そして、ハッシュ マップ用のメモリが足りない場合は、問題が発生します... ただし、これは使用するデータ構造に関係なく当てはまります。