解刨HashMap的put流程 ＜二＞ JDK 1.8
好的，我们接着 HashMap 的put流程往下讲）。第一步已经计算出了 Key 的哈希值，第二步是 “计算元素的存储索引（即确定放在数组的哪个桶中）”。这一步是连接哈希值与实际存储位置的关键，核心目标是：将第一步计算出的哈希值（32 位整数，范围极大）“映射” 到数组的有效索引范围内（0 ~ 数组容量 - 1）。
一、核心操作：index = hash & (n - 1)
计算索引的公式非常简单：
int index = hash & (n - 1);
其中：
hash：第一步通过扰动函数处理后的哈希值（32 位整数）；n：当前 HashMap 数组的容量（如初始容量 16，扩容后 32、64 等，始终是 2 的幂）；n - 1：容量减 1（因n是 2 的幂，所以n-1的二进制一定是 “全 1”，如 n=16 时，n-1=15→二进制1111）。
二、为什么这样计算？
这个公式的设计有两个核心目的：确保索引有效和保证分布均匀，且依赖于 “n是 2 的幂” 这个前提。
1. 确保索引一定在数组范围内
数组的索引必须是0 ~ n-1之间的整数（否则会数组越界）。
由于n是 2 的幂，n-1的二进制是 “全 1”（如 n=8→n-1=7→111），任何整数与 “全 1” 做&运算，结果只会保留该数的低k位（k是n的幂次，如 n=8 是 2³，保留低 3 位），因此结果必然在0 ~ n-1范围内。
举例：
n=8（2³），n-1=7（111）：
- 任意哈希值（如
10010110）与111做&运算：10010110 & 00000111 = 00000110（十进制 6）→ 索引 = 6（在 0~7 范围内）。
2. 等价于取模运算，但效率更高
当n是 2 的幂时，hash & (n-1) 与 hash % n（取模运算）的结果完全相同，但位运算&的执行效率远高于取模运算%（计算机处理位运算更直接）。
举例：
n=16（2⁴），hash=20：
20 & 15 = 4（20 的二进制10100& 15 的01111=00100）；20 % 16 = 4（结果相同）。
3. 结合扰动函数，让索引分布更均匀
第一步的扰动函数已经让哈希值的高低位混合，增加了随机性。而n-1的 “全 1” 特性，能让哈希值的每一位都参与索引计算（不会浪费任何一位的特征），进一步减少不同哈希值映射到同一索引的概率（即减少哈希冲突）。
反例：如果n不是 2 的幂（如 n=10），则n-1=9（二进制1001），此时&运算只会用到哈希值的第 0 位和第 3 位，其他位的特征被忽略，会导致大量不同的哈希值映射到相同索引（冲突剧增）。
第二步的核心是通过hash & (n-1)计算索引，它依赖于两个关键设计：
n是 2 的幂：保证n-1是 “全 1” 二进制，确保索引有效且与取模结果等价；- 位运算
&：比取模运算更快，且能充分利用哈希值的每一位特征。
这一步将大范围的哈希值 “压缩” 到数组的有效索引范围内，同时通过均匀分布减少冲突，为后续的元素插入和查询效率奠定基础。