在java 8 jdk中放置/获取HashMap复杂性

Question

据我所知,在java中实现的HashMap中put/get操作的最坏情况是o(n).

在研究我正在研究的项目的高效数据结构时,我在这里看到了一个评论,在java 8 JDK中,那些操作的HashMap复杂性是O(logn),但我找不到文档关于它.这是真的,所以我可以依靠它吗？

如果这真的是事实,它是如何实现的？我的猜测是HashMap中的每个"单元格"都是作为平衡树实现的.

Answer 1

那是对的.从Java 8开始,如果单个散列桶包含8个或更多对象,则该位置的链表将转换为树(红黑平衡树).

有一个关于它的文章在这里.OpenJDK JEP就在这里.

有趣的是......虽然这O(logn)依赖于实现的对象comparable.从技术上讲,只要您只comparable在地图中放置对象,就是正确的.如果你不这样做,那么它将回到普通的旧链表和O(n).