面试必问 HashMap，但你真的理解它的进化机制吗？从数组 + 链表到红黑树，JDK 8 的这次升级解决了什么问题？

一、HashMap 的数据结构演进

  • 1.1 JDK 7：数组 + 单向链表
  • 1.2 JDK 8：数组 + 链表 + 红黑树
  • 1.3 为什么需要红黑树——哈希碰撞攻击

二、put() 方法源码全解析

  • 2.1 hash() 扰动函数——为什么是 (h ^ h>>>16)
  • 2.2 定位桶位置——(n-1) & hash
  • 2.3 链表插入——尾插法（JDK 8）vs 头插法（JDK 7）
  • 2.4 树化条件——链表长度 ≥ 8 且桶数量 ≥ 64
  • 2.5 扩容条件——负载因子 0.75

三、红黑树的树化与退树化

  • 3.1 treeifyBin()——链表转红黑树
  • 3.2 红黑树的 5 条性质
  • 3.3 putTreeVal()——红黑树节点的插入与平衡
  • 3.4 untreeify()——节点数 ≤ 6 时退化为链表

四、扩容机制 resize()

  • 4.1 扩容时机——size > threshold
  • 4.2 容量翻倍——2 的幂次方的意义
  • 4.3 rehash——(e.hash & oldCap) == 0 判断高位
  • 4.4 JDK 7 的 rehash——重新计算 hash & (newCap - 1)
  • 4.5 JDK 8 的优化——高低位链表拆分

五、并发问题

  • 5.1 JDK 7 的并发扩容死循环——头插法导致的环形链表
  • 5.2 JDK 8 的并发问题——数据覆盖、size 不准确
  • 5.3 为什么 ConcurrentHashMap 是替代方案

六、为什么容量必须是 2 的幂次方

  • 6.1 (n-1) & hash 替代取模运算
  • 6.2 扩容时的高低位判断优化

七、性能优化建议

  • 7.1 初始化容量预估——避免频繁扩容
  • 7.2 负载因子的取舍——0.75 的由来
  • 7.3 作为缓存时的内存占用估算
  • 7.4 key 的 hashCode() 设计——避免碰撞

八、总结

  • HashMap 的设计精髓——空间换时间
  • 与 TreeMap / LinkedHashMap 的对比