Javaで実装されたHashMapの複雑さをput/get jdk

Question

限り、Javaで実装されたHashMapのput/get操作の最悪のシナリオはo（n）です。

プロジェクトの効率的なデータ構造を研究しています。私はここで、Java 8ではJDKのHashMapの複雑さはO（logn）ですが、それについてのドキュメントは見つかりません。 本当ですか、私はそれに頼ることができますか？

本当に真実なら、それはどのように実装されていますか？ 私の推測では、HashMap内の各 "セル"はバランスのとれたツリーとして実装されています。

Answer 1

これは正しいです。 Java 8以降、単一のハッシュバケットに8つ以上のオブジェクトが含まれている場合、その場所のリンクリストはツリー（赤黒のバランスのとれたツリー）に変換されます。

記事はhereです。 OpenJDK JEPはhereです。

しかし、このO(logn)は、comparableを実装したオブジェクトに依存します。だから、技術的には、あなたは正しく、あなたがマップにcomparableオブジェクトを置く限りです。もしそうでなければ、普通の古いリンクリストに戻り、O(n)に戻ります。