面试题：Java中JDK 8前后HashMap结构变化的主要体现

Question

请阐述在JDK 8前后，Java的HashMap在数据结构方面发生了哪些主要变化？这些变化对HashMap的性能有何影响？

Answer 1

JDK 8 前后HashMap数据结构的主要变化

1. 链表转红黑树
   • JDK 8之前：HashMap内部数据结构主要是数组加链表。当发生哈希冲突时，新的元素以链表的形式追加到冲突位置。链表的查找时间复杂度在最坏情况下为O(n)，n为链表长度。
   • JDK 8之后：当链表长度超过阈值（默认为8）且哈希表容量大于64时，链表会转化为红黑树。红黑树是一种自平衡的二叉查找树，查找、插入和删除操作的时间复杂度在最坏情况下为O(log n)，n为树中节点的数量。
2. 数组扩容方式
   • JDK 8之前：采用旧容量*2的方式进行扩容。重新计算每个元素在新数组中的位置，需要遍历旧数组的每个元素并重新计算哈希值和索引位置。
   • JDK 8之后：仍然是旧容量*2的扩容方式，但优化了重新计算元素位置的方法。通过观察发现，扩容后元素要么在原位置，要么在原位置加上旧容量的位置，这样可以减少重新计算哈希值的开销。

这些变化对HashMap性能的影响

1. 查找性能提升
   • 在哈希冲突较少，链表较短时，链表和红黑树的查找性能相近。但当链表长度较长时，JDK 8中红黑树结构的HashMap查找性能有显著提升，从最坏情况下的O(n)提升到O(log n)。
2. 插入和删除性能
   • 插入：在链表较短时，链表插入性能较好，因为不需要维护树的平衡。但当链表较长转化为红黑树后，插入时虽然需要维护树的平衡，但整体插入性能在大量数据且哈希冲突较多时更优，避免了链表过长导致的性能急剧下降。
   • 删除：与插入类似，在链表较短时链表删除性能较好，但在大量数据且哈希冲突较多时，红黑树结构的删除性能相对稳定，不会像链表那样随着长度增加而性能急剧恶化。
3. 扩容性能优化 JDK 8优化的扩容计算位置方法减少了重新计算哈希值的开销，使得扩容操作在大规模数据下性能有所提升，降低了扩容时的时间复杂度。