gil*_*gil 1 java data-structures
据我所知,在java中实现的HashMap中put/get操作的最坏情况是o(n).
在研究我正在研究的项目的高效数据结构时,我在这里看到了一个评论,在java 8 JDK中,那些操作的HashMap复杂性是O(logn),但我找不到文档关于它.这是真的,所以我可以依靠它吗？
如果这真的是事实,它是如何实现的？我的猜测是HashMap中的每个"单元格"都是作为平衡树实现的.
And*_*dyN 7
那是对的.从Java 8开始,如果单个散列桶包含8个或更多对象,则该位置的链表将转换为树(红黑平衡树).
有一个关于它的文章在这里.OpenJDK JEP就在这里.
有趣的是......虽然这O(logn)依赖于实现的对象comparable.从技术上讲,只要您只comparable在地图中放置对象,就是正确的.如果你不这样做,那么它将回到普通的旧链表和O(n).
O(logn)
comparable
O(n)
归档时间：
9 年，12 月 前
查看次数：
256 次
最近记录：