HashMapget/put操作はO（1）であると言っています。しかし、それはハッシュ実装に依存します。デフォルトのオブジェクトハッシュは、実際にはJVMヒープの内部アドレスです。 get/putがO（1）であると主張するのに十分ですか？HashMap get/put複雑度
利用可能なメモリは別の問題です。私がjavadocsから理解しているように、HashMapload factorは0.75でなければなりません。 JVMに十分なメモリがなく、load factorが制限を超えたらどうなりますか？
O（1）は保証されていないようです。それは意味をなさないか、私は何かを逃していますか？
多くのことに依存します。 通常は O（1）、それ自体は一定の時間です...しかし、あなたは計算に長い時間がかかるハッシュを持つことができます。とハッシュマップに複数のアイテムがある場合同じハッシュコードgetは、一致するものを見つけるためにそれらのそれぞれにequalsを呼び出すことを反復処理する必要があります。最悪の場合
、HashMap起因同じハッシュバケット内のすべてのエントリを歩いにO（n）のルックアップを有する（例えば、それらはすべて同一のハッシュコードを持っている場合）。幸いにも、その最悪のシナリオは、私の経験では実際の生活では非常に頻繁に現れません。だから、O（1）は確かに保証されていませんが、通常、どのアルゴリズムやデータ構造を使用するかを検討するときに想定する必要があります。
JDK 8でHashMapが調整されているため、キーを並べ替えることができれば、密集したバケットがツリーとして実装されるため、同じハッシュコードを持つエントリがたくさんあっても、複雑さはO（log n）です。もちろん、等価性と順序が異なるキータイプを使用している場合は、問題が発生する可能性があります。
はい、ハッシュマップのメモリが不足していると困ってしまいますが、それはどのようなデータ構造を使っても同じです。
@marcog：あなたは*単一検索*のO（n log n）と仮定しますか？それは私にはうんざりです。もちろん、ハッシュ関数と等価関数の複雑さに依存しますが、マップのサイズに依存する可能性は低いです。 –
@marcog：あなたは何をO（n log n）と仮定していますか？ n個のアイテムの挿入？ –
それを忘れてしまった。これは、関連する質問の不一致からの少しの悪化です。私はばかげているだけです。あなたの答えはこの質問のために素晴らしいです。良い答えは+1 – marcog
デフォルトのハッシュコードがアドレスであるかどうかわかりません - 以前はハッシュコード生成のためのOpenJDKソースを読んでいましたが、もう少し複雑なことを覚えています。おそらく良い流通を保証するものではないでしょう。しかし、これはある程度のことですが、ハッシュマップのキーとして使用するクラスはほとんどありません。デフォルトのハッシュコードを使用します。これらのクラスは独自の実装を提供します。
これに加えて、HashMapはハッシュマップを使用する前にそのハッシュを攪拌し、単語全体からエントロピーをボトムビットにミックスし、これは、最も巨大なハッシュマップを除いてすべてのものに必要な場所です。それは、特に自分自身ではできないハッシュを扱うのに役立ちますが、私はあなたがそれを見る一般的な事例は考えられません。
最後に、テーブルが過負荷になると、パラレルリンクリストのセットに縮退し、パフォーマンスはO（n）になります。具体的には、横断されるリンクの数は平均して負荷率の半分になります。
Dammit。私は、これを携帯電話のタッチスクリーンで反転させなければならないとしたら、Jon Sheetを打つことができたと信じています。それにはバッジがありますよね？ –
ハッシュマップは平均でO(n/m)であり、nがアイテム数であり、mがサイズであることが既に説明されています。原則として、すべてがクエリー時間がO(n)の単一リンクリストに崩壊する可能性があることも言及されています。 （これは、ハッシュの計算が一定時間であることを前提としています）。
しかし、頻繁に言及されていないのは、確率が少なくとも1-1/nであるため（1000アイテムが99.9％の確率で）、最大のバケットはO(logn)以上で埋められません。したがって、2分探索木の平均複雑度にマッチする。 （定数は良いですが、より厳しい境界は(log n)*(m/n) + O(1)です）。
この理論上の制約に必要なのは、合理的に優れたハッシュ関数を使用することです（ウィキペディア：Universal Hashingを参照してください）。これは簡単にa*x>>mとすることができます。もちろん、ハッシュ値を与える人はあなたのランダム定数をどのように選択したのか分かりません。
TL; DR：非常に高い確率では、ハッシュマップの最悪の場合のゲット/プットの複雑さはO(logn)です。
（これはランダムデータを前提としていないことに注意してください。確率は純粋にハッシュ関数の選択から生まれます） –
ハッシュマップのルックアップの実行時の複雑さに関しても同じ質問があります。それは一定の要因が落とされることになっているので、それはO（n）のように見えます。 1/mは一定の係数であり、従って、O（n）を残して落とされる。 – nickdu
ハッシュマップ操作は、hashCodeの実装に依存します。理想的なシナリオでは、すべてのオブジェクト（ハッシュ衝突なし）にユニークなハッシュコードを提供する良いハッシュ実装を言えば、ベスト、最悪および平均のケースシナリオはO（1）になります。 hashCodeの悪い実装が常に1を返し、ハッシュ衝突を伴うハッシュを返すシナリオを考えてみましょう。この場合、時間の複雑さはO（n）になります。
メモリについての質問の2番目の部分に来ると、はいメモリの制約がJVMによって処理されます。
償却された複雑さの概念を調べたいと思うかもしれません。例えば、ここを参照してください：stackoverflow.com/questions/3949217/time-complexity-of-hash-table最悪の複雑さは、ハッシュテーブルの最も重要な尺度ではありません –
修正 - それは_amortized_ O（1） - それを忘れることはありませんあなたはこれらの種類の質問をしません:) –