「Java 工兵连」第 2 篇，讲 HashMap——用得最多、被问得最狠的一个类。网上讲它的文章汗牛充栋，但大多从源码第一行讲到最后一行，看完记不住。这篇换个打法：只讲两个自适应机制——扩容和树化，讲完你能回答三个问题：为什么容量必须是 2 的幂？扩容时为什么不用重新计算 hash？树化阈值为什么偏偏是 8？

一、先建直觉：按尾号分房的宿舍楼

把 HashMap 想成一栋宿舍楼：

• 容量 capacity = 房间数（默认 16）；
• hash 定位 = 学号尾号决定住哪个房间：index = hash & (capacity - 1)；
• 拉链 = 尾号相同的室友住同一间，先来的挨个排（链表）；
• 扩容 resize = 楼里总人数超过「房间数 × 0.75」，整栋搬去房间数翻倍的新楼，所有人重新分房；
• 树化 treeify = 某个房间挤进 8 个人，这个房间改建成一棵有排序的「单元楼」（红黑树），找人从逐个问变成折半找。

map.put(k, v) 背后就是这套流程：算 hash → 定房间 → 空房直入 / 同 key 覆盖 / 否则挂链或上树 → 总数超阈值就整栋搬家。

二、地基：为什么容量恒为 2 的幂

这是全文最值钱的一个知识点，两个原因：

其一，取模变位与。 当 n 是 2 的幂时，hash % n 等价于 hash & (n - 1)。取模要走除法，位与只是一条与门指令——高频操作里这个差距是真金白银。所以 new HashMap<>(10) 实际拿到的是 16（tableSizeFor 把你给的数向上取成最近的 2 的幂）。

其二，hash 的低位就是房间号。 n-1 是一串连续的 1（容量 16 → 掩码 1111），「取尾号」这个动作天然成立，这也为扩容的精妙技巧埋了伏笔。

但这带来一个隐患：只有低位参与分房，高位变化全被浪费。于是 JDK 8 的扰动函数登场：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 高 16 位异或进低 16 位
}

高 16 位与低 16 位异或一次，让高位信息也参与「定尾号」，碰撞概率显著下降（顺带：null key 的 hash 是 0，所以它永远住 0 号房）。

三、扩容：一次只看一个 bit

触发条件先说准：是 size（元素总数）超过 threshold = capacity × 0.75，不是某个桶挤了。负载因子 0.75 是空间与时间的折中——太低浪费房间，太高链子长。

JDK 7 的扩容很朴素：新表建好，每个元素重新计算 index，一个个搬。JDK 8 的实现是全文最漂亮的一步棋——扩容后根本不用重算 hash，每个元素只看一个 bit：

容量从 n 翻倍到 2n，掩码从 n-1 多出一位（比如 0111 → 1111）。对旧表同一个桶里的元素，旧的低位完全不变，唯一的问题是新增的那一位是 0 还是 1：

• 新增位是 0 → 留在原索引；
• 新增位是 1 → 挪到 原索引 + 旧容量 oldCap。

对应源码就是一句 hash & oldCap 的判断（见图：桶 0 的链分家，一部分留 0 号房，一部分去 4 号房）。旧桶一条链，新表两条链，顺序保持不变，还能保持局部性。这个优化把 rehash 从「逐个重算」降成「逐个看一位」，是读 JDK 源码最值得驻足的一段。

四、树化：阈值 8 不是拍脑袋，是泊松分布

链表查找是 O(n)，恶意构造的 key 可以让大量元素挤进同一个桶，把 HashMap 拖成 O(n) 的慢速结构（历史上真实发生过 hash 碰撞 DoS 攻击）。JDK 8 的答案就是树化，但注意双门槛：

1. 桶内节点数 ≥ 8（TREEIFY_THRESHOLD）；
2. 数组容量 ≥ 64（MIN_TREEIFY_CAPACITY）——不满足时优先扩容而不是树化。房间太少时，「搬家」比「改建单元楼」便宜得多。

为什么阈值是 8？JDK 源码注释里给过答案：在负载因子 0.75、hash 足够随机的前提下，单个桶的节点数近似服从参数 0.5 的泊松分布，桶内出现 8 个节点的概率约为 0.00000006——亿分之六。换句话说：正常数据几乎不会树化；树化发生，基本说明 hash 质量出了问题（坏 hashCode、或有人恶意碰撞）。树是保命手段，不是日常形态。扩容把长链拆开后，节点数低于 6（UNTREEIFY_THRESHOLD）就退回链表——留 2 的余量防止在阈值附近反复横跳。

五、一桩旧案：JDK 7 头插成环

老面试题，但值得每个写并发代码的人真正理解。JDK 7 扩容搬家用头插法（新元素插链头，图省事）。两个线程同时扩容时，线程交错执行可能把链表指针接成环——之后任何 get() 落到这个桶，遍历就永远出不来：CPU 100%，服务假死。

JDK 8 做了两层修复：改尾插法（保持顺序，配合上面的分流逻辑）；树化让长链有了兜底。但注意——HashMap 依然不是线程安全的，修复的是「扩容成环」这一种死法，并发写还有丢失更新等别的死法。并发场景的答案始终是 ConcurrentHashMap（工兵连后面单开一篇讲它的分段锁到 CAS 的演进）。

六、生产实践：三个动作

1. 能预估容量就别让它半路搬家。 已知要装 1000 个元素：

// 不好：默认 16 → 陆续扩容 6 次（16→32→…→1024）
Map<String, User> m = new HashMap<>();

// 好：一步到位。1000 / 0.75 ≈ 1334 → tableSizeFor 取 2048
Map<String, User> m = new HashMap<>((int) (1000 / 0.75f) + 1);

// 或者直接用 Guava，免去心算
Map<String, User> m2 = Maps.newHashMapWithExpectedSize(1000);

扩容是全量搬运，大 Map 在高峰期触发一次，就是一次可感知的停顿——初始化时多写一个数字，是最便宜的优化。

2. key 的 hashCode 要稳定且分散。 可变对象做 key 是自埋雷：字段变了导致 hashCode 变化，元素在桶里「失踪」（还在 Map 里，但 get 不到）。用不可变对象或只取不可变字段。

3. 迭代中修改要当心。 for (String k : map.keySet()) 期间做结构性修改（put/remove），下一轮 next() 抛 ConcurrentModificationException（fail-fast，靠 modCount 计数）。正确姿势是迭代器自己的 remove()，或 removeIf()。

老兵点评

1. HashMap 的设计哲学是「为正常数据优化，为异常数据兜底」。泊松分布算出的 8、扩容优先于树化、树化后又允许退化——每个数字背后都是「常见路径极致快，罕见路径不出事」的取舍。读集合源码，读的就是这种分层防御。
2. 别把「2 的幂」当成八股，它是整套机关的齿轮。位与定位、扩容看一个 bit、树化退化，全部咬合在「容量恒为 2 的幂」这个前提上。理解了这点，上面的每个「为什么」都不用背。
3. 面试讲 HashMap 的段位差：初级背「数组+链表+红黑树」；中级讲扰动函数和负载因子；高级讲 hash & oldCap 分流和泊松分布——读完这篇，你直接在高级那一档。

带走三句话

1. 容量恒为 2 的幂：取模变位与，扩容只看新增的一个 bit——留原位，或挪「原位 + oldCap」。
2. 超过四分之三就搬家（threshold = capacity × 0.75），同屋八个且楼够六十四才上树——树化是亿分之六概率的保命手段，不是常态。
3. 并发读写的答案永远是 ConcurrentHashMap——JDK 8 修的是「成环」，不是「不安全」。

---

本篇是「Java 工兵连」第 2 篇。→ 上一篇：第 1 篇 · 线程池：别再 Executors 了 ｜ 继续阅读：第 3 篇 · volatile 不是锁。