据我所知，在 java 中实现的 HashMap 中 put/get 操作的最坏情况是 o(n)。
在为我正在从事的项目研究有效的数据结构时，我在这里看到一个人的评论，他说在 Java 8 JDK 中，这些操作的 HashMap 复杂度是 O(logn)，但我不能'找不到关于它的文档。 这是真的吗？所以我可以信赖它？
如果这是真的，它是如何实现的？ 我的猜测是 HashMap 中的每个“单元格”都是作为平衡树实现的。
最佳答案
没错。从 Java 8 开始，如果单个哈希桶包含 8 个或更多对象，则该位置的链表将转换为树(红黑平衡树)。
上面有一篇文章here . OpenJDK JEP 是 here .
有趣的是......这个O(logn) 依赖于实现了comparable 的对象。所以从技术上讲，您是正确的，只要您只将 comparable 对象放在 map 中即可。如果您不这样做，那么它将返回到普通的旧链表和 O(n)。
关于java - 在 java 8 jdk 中放置/获取 HashMap 复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37282837/