java - 为什么java.util.HashMap内部使用链表

Question

我对java.util.HashMap的概念理解如下:

1. 与其他 Map 实现相比，它的主要优点是恒定的查找时间(假设没有冲突)。因此，底层实现使用固定长度的数组 - 计算机科学中唯一具有 O(1) 查找的数据结构。

2. 用于存储映射条目的固定长度数组在实例化时初始化为给定大小，并随着映射大小的接近而扩展(扩展，我的意思是创建更大的数组并复制值)固定长度数组的长度。

3. 当将值放入 M​​ap 时，键值对将放入给定键的内部链表实现中。当发生冲突时，后续键值对将附加到列表中。

4. 从 Map 获取时，键的 hashCode() 用于派生内部链表实现的数组索引，如果列表大小为 1，则您可以获取值，或者迭代列表在每个元素的键上调用 equals() 直到找到您的值。

基于第2点，HashMap必须扩展一个数组，这个操作肯定是线性的。为什么它使用内部链表实现(O(n) 查找)来解决冲突？为什么它不使用 O(log n) 查找的数据结构(例如二叉树或红黑树)来提高性能？

Answer 1

http://openjdk.java.net/jeps/180

从 Java 8 开始，如果存在足够的冲突，HashMap 确实会回退到二叉树。