面试题：Java中HashMap的扩容机制是怎样的

Question

请详细阐述Java中HashMap在什么情况下会进行扩容，扩容的具体过程是怎样的，包括扩容前后元素位置的变化原理。

Answer 1

HashMap扩容的情况

当HashMap中的元素数量（size）达到了负载因子（loadFactor）与容量（capacity）的乘积时，就会触发扩容。即 size >= threshold，其中 threshold = loadFactor * capacity 。

扩容的具体过程

1. 创建新的数组：
   • 新的容量是原容量的2倍。例如原容量为16，新容量就是32。
   • 创建一个新的 Node<K,V>[] 数组，其大小为新的容量。
2. 重新计算元素位置并迁移：
   • 遍历旧数组的每一个桶（bucket）。
   • 对于每个桶中的链表或红黑树中的元素，重新计算其在新数组中的位置。

扩容前后元素位置的变化原理

假设原容量为 oldCap，新容量为 newCap（newCap = oldCap * 2）。

• 对于链表中的元素：
  • 元素的哈希值不变，重新计算在新数组中的索引位置 index = hash & (newCap - 1)。
  • 由于新容量是原容量的2倍，所以新的索引位置要么与原索引位置相同，要么是原索引位置加上原容量。
  • 例如，原容量 oldCap = 16，哈希值 hash = 10，原索引位置 index1 = 10 & (16 - 1) = 10。新容量 newCap = 32，新索引位置 index2 = 10 & (32 - 1) = 10，保持不变；若哈希值 hash = 26，原索引位置 index1 = 26 & (16 - 1) = 10，新索引位置 index2 = 26 & (32 - 1) = 26，即原索引位置加上原容量（10 + 16 = 26）。
• 对于红黑树中的元素：
  • 同样重新计算索引位置，然后将红黑树中的节点拆分到新数组的对应桶中。如果拆分后节点数量小于 TREEIFY_THRESHOLD（默认为6），红黑树会退化为链表。