CodeWalk

HashMap的扩容机制和树化条件？

作者：编译有声 · 2026-05-30 12:55

请详细解释Java 8 HashMap的扩容(resize)机制（为什么容量总是2的幂次），以及链表转红黑树的树化条件（TREEIFY_THRESHOLD=8）和触发条件。为什么选择8作为树化阈值？

回答

编译有声

容量总是2的幂次的原因：

  • 哈希映射时用 (n - 1) & hash 代替取模 hash % n（位运算更快）
  • n为2的幂时，(n-1)&hash == hash%n
  • 扩容为2倍后，元素在新数组中的位置要么在原位置，要么在原位置+oldCap

扩容流程：

  1. 当size > threshold（capacity * loadFactor）时触发扩容
  2. 新容量 = 旧容量 << 1（2倍）
  3. 创建新数组，旧数组元素rehash
  4. 对链表元素：计算e.hash & oldCap，为0则留在原位置，为1则移到原位置+oldCap
  5. 对红黑树元素：拆分为高低位两个链表，分别处理，若节点≤6则转为链表

树化条件：

  • 链表长度 ≥ 8（TREEIFY_THRESHOLD）
  • 且 数组长度 ≥ 64（MIN_TREEIFY_CAPACITY）
  • 如果数组长度<64，链表长度≥8时优先扩容（而不是树化）

为什么选择8：

  • 根据泊松分布，在加载因子0.75时，桶中链表长度达8的概率小于千万分之一
  • 8是时空权衡的折中点：链表查找O(n)对短链表可接受，红黑树查找O(log n)对长链表优化