面试题：Java中HashMap如何处理哈希冲突

Question

在Java的HashMap中，当不同的键计算出相同的哈希值时，即发生哈希冲突，请问HashMap是如何处理这种情况的？并且说明在JDK 1.7和JDK 1.8中处理方式有何不同。

Answer 1

1. HashMap处理哈希冲突的方式

在Java的HashMap中，当发生哈希冲突时，使用链地址法（Separate Chaining）来处理。即每个哈希值对应的位置是一个链表（JDK 1.7）或链表+红黑树（JDK 1.8及之后），当不同键计算出相同哈希值时，这些键值对会被存储在这个链表或树结构中。

2. JDK 1.7和JDK 1.8处理方式的不同

• JDK 1.7：
  • 采用数组 + 链表的结构。当哈希冲突发生时，新的元素会被插入到链表的头部（头插法）。这种方式在频繁插入元素时，如果哈希冲突较多，链表可能会变得很长，导致查找效率降低，时间复杂度为O(n)，其中n为链表长度。
• JDK 1.8：
  • 采用数组 + 链表 + 红黑树的结构。当链表长度超过阈值（默认为8）且数组长度大于等于64时，链表会转化为红黑树。这样在查找元素时，时间复杂度从链表的O(n)变为红黑树的O(log n)，提高了查找效率。新元素插入时采用尾插法，避免了JDK 1.7头插法在多线程环境下可能产生链表成环的问题。