面试题：Java HashMap扩容时，rehash的过程及优化点

Question

在Java HashMap扩容时，会涉及到rehash操作。请详细说明rehash的具体过程，并指出JDK 1.7和JDK 1.8在这个过程中的主要优化点。

Answer 1

rehash具体过程

1. 确定新容量：创建一个新的Entry数组，其容量是原来的两倍。
2. 重新计算哈希值：遍历旧的Entry数组，对每个元素重新计算在新数组中的哈希值与索引位置。例如，使用 (n - 1) & hash 计算索引（n 为新数组容量）。
3. 重新插入元素：将旧数组中的元素重新插入到新数组对应的位置。如果出现哈希冲突，在JDK 1.7中采用头插法将新元素插入链表头部；JDK 1.8中当链表长度大于8且数组容量大于64时，链表会转化为红黑树，插入时按红黑树规则插入，否则仍采用尾插法插入链表尾部。

JDK 1.7和JDK 1.8在rehash过程中的主要优化点

1. JDK 1.7：
   • 头插法：扩容时采用头插法插入元素到链表，在多线程环境下可能形成环形链表，导致死循环。
2. JDK 1.8：
   • 尾插法：采用尾插法插入元素到链表，避免了多线程环境下因头插法可能形成环形链表的问题。
   • 链表转红黑树：当链表长度大于8且数组容量大于64时，将链表转化为红黑树，提高查找效率，避免链表过长时查找性能的退化。