在 Java 后端开发面试或源码阅读中，HashMap 永远是避不开的核心。很多人能熟练地背出它的扩容阈值、红黑树化条件，但当深入到源码底层，看到诸如 e.hash & (newCap - 1) 和 e.hash & oldCap 这样的位运算时，往往会陷入沉思。
一、 起源：为什么数组长度必须是 2 的次幂？
在散列表中，为了让数据均匀分布，最直观的想法是对哈希值进行取模（求余数）：
$$\text{索引位置} = \text{hash} \pmod{\text{Capacity}}$$然而，在 CPU 的底层底层执行中，除法和取模（%）是非常昂贵的算术操作（可能需要几十个时钟周期）。为了追求极致的性能，底层的数论定理为我们提供了一个完美的替代方案：
数学定理：当容量 $C$ 是 $2$ 的次幂（$2^n$）时，对于任意整数 $H$，满足：
$$H \pmod C \equiv H \ \& \ (C - 1)$$
位运算（&）在 CPU 中只需要 1 个时钟周期！为了享受到这个性能红利，HashMap 在源码中将容量死死限制为 2 的次幂：
// 默认初始容量 16 (2的4次方)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
裁剪器的魔术：hash & (newCap - 1)
以容量 16 为例，16 - 1 = 15（二进制：0000 1111）。任何 Hash 值与 15 进行 & 运算，高位都会被无情“抹零”，只有最后 4 位被保留下来：
e.hash : 1010 0101 (某个对象的Hash值)
& 15 (16-1): 0000 1111
-------------------------------
结果 : 0000 0101 (十进制的 5，即数组索引)
裁剪出来的结果范围绝对在 0 ~ 15 之间，在数学上完全等同于取模，速度却快了成百上千倍。
二、 进阶：扩容时的核心优化 e.hash & oldCap
当 HashMap 触发扩容（resize()）时，原数组中的链表节点面临着重新分配（Rehash）。在 JDK 7 中，程序需要对每个节点重新进行一次上面提到的计算，不仅耗时，在多线程下还容易形成死循环。
JDK 8 引入了一个极其巧妙的判断：(e.hash & oldCap) == 0。
1. 搬家还是留守？
扩容是翻倍的。比如旧容量 oldCap = 16（二进制 0001 0000），新容量 newCap = 32。
- 容量为 16 时，看的是二进制的低 4 位。
- 容量为 32 时，看的是二进制的低 5 位。
也就是说，决定一个节点扩容后去哪里的，仅仅取决于它 Hash 值多出来的左边那 1 位（二进制的第 5 位）是 0 还是 1。
2. 精准的按位照准
oldCap（16）的二进制刚好是 0001 0000，除了第 5 位是 1，其余全为 0。
因此，e.hash & oldCap 就像是一把精准的手电筒，只照看新增的这一位：
- 结果 == 0：说明新增的那一位是 0。扩容后重新计算位置，它依然会留在原下标位置（归为低位链表）。
- 结果 != 0：说明新增的那一位是 1。扩容后它的新位置必然是 原下标 + oldCap（归为高位链表）。
假设节点 A 和 B 之前都在下标 5：
节点 A 的 Hash: ...0000 0101 -> A & 16 = 0 -> 留守原位（下标 5）
节点 B 的 Hash: ...0001 0101 -> B & 16 = 16 (非0) -> 搬家（5 + 16 = 下标 21）
三、 总结：HashMap 扩容全景流程
基于上述的高低位拆分优化，HashMap 的 put 与 resize 流程变得无比丝滑。
1. Put 方法核心步骤
- 计算哈希：利用扰动函数
(h = key.hashCode()) ^ (h >>> 16)将高位特征混合到低位。 - 定位桶位：通过
hash & (capacity - 1)快速定位。 - 解决冲突：桶为空直接放入；不为空则遍历链表或红黑树。若链表长度 $\ge 8$ 且数组长度 $\ge 64$ 则触发树化。
- 检查扩容：当元素总量超过阈值（
capacity * loadFactor）时，启动resize()。
2. Resize 扩容数据迁移步骤
graph TD
A[开始扩容 resize] --> B["创建新数组 newTable, 容量翻倍"]
B --> C[遍历旧数组的每个桶位]
C --> D{桶位节点类型?}
D -- 单节点 --> E["重新计算索引: e.hash & (newCap - 1)
放入新数组"]
D -- 红黑树 --> F[调用 split 拆分树]
D -- 链表 --> G{"判断 (e.hash & oldCap) == 0"}
G -- 是 --> H["归入低位链表
位置不变: newTable[原位置]"]
G -- 否 --> I["归入高位链表
搬家: newTable[原位置 + oldCap]"]
E --> J{是否遍历完?}
F --> J
H --> J
I --> J
J -- 否 --> C
J -- 是 --> K[扩容完成]
结语：工程美学的最高体现
HashMap 的设计者 Joshua Bloch 等大牛，通过强制容器大小为 2 的次幂 这一空间规律，成功用 位运算 换取了时间的极致性能。
从 & (cap - 1) 的精简截取，到 & oldCap 的高低位完美拆分，HashMap 的源码向我们展示了什么是真正的计算机工程美学——将严谨的数学定理，转化为压榨硬件底层的极致武器。