面试题：Java中HashMap在JDK1.7和JDK1.8底层实现有哪些主要区别

Question

请阐述Java中HashMap在JDK1.7和JDK1.8版本下，底层数据结构、插入元素过程以及扩容机制等方面存在的主要差异。

Answer 1

底层数据结构

• JDK1.7：HashMap底层是数组 + 链表结构。数组的每个元素是一个链表的头节点，链表用来解决哈希冲突。
• JDK1.8：底层结构在JDK1.7基础上新增了红黑树。当链表长度大于阈值（默认为8）且数组长度大于等于64时，链表会转换为红黑树，以提高查找效率。

插入元素过程

• JDK1.7：
  1. 计算key的hash值，通过与数组长度取模确定插入位置。
  2. 如果该位置为空，直接插入新元素。
  3. 如果该位置已有元素，遍历链表，若找到相同key的元素则替换其value，否则将新元素插入到链表头部（头插法）。
• JDK1.8：
  1. 同样计算key的hash值并确定插入位置。
  2. 若该位置为空，直接插入。
  3. 若该位置元素为链表节点，遍历链表，若找到相同key的元素则替换value；若未找到，将新元素插入到链表尾部（尾插法），当链表长度大于8且数组长度大于等于64时，将链表转换为红黑树。
  4. 若该位置元素为红黑树节点，按红黑树规则插入新节点。

扩容机制

• JDK1.7：
  • 扩容条件：当HashMap中元素个数超过loadFactor * capacity（默认loadFactor为0.75）时进行扩容。
  • 扩容方式：扩容时创建一个新的更大的数组，然后将旧数组中的所有元素重新计算哈希值并插入到新数组中，即所谓的“重新散列”，这个过程比较耗时。
• JDK1.8：
  • 扩容条件与JDK1.7相同。
  • 扩容方式优化：在扩容时，会对每个链表或红黑树进行拆分，部分节点位置不变，部分节点位置发生变化，减少了重新计算哈希值的次数，提高了扩容效率。对于链表，根据节点的hash值和旧数组长度判断节点在新数组中的位置是否改变，位置不变的节点仍留在原位置链表，位置改变的节点移动到新位置链表；对于红黑树，同样按上述规则拆分，若拆分后节点数小于6，则将红黑树转换回链表。