为什么需要“扰动函数”？—— hash ^ (hash >>> 16)
HashMap中用 hash 方法计算哈希值：
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
之后用 hash & (length-1) 快速计算索引，计算索引时，本质是只保留hash的低 n 位，高位全部清零，此时如果hash的低位分布不均匀，会导致大量哈希冲突。
所以不能够单纯使用hashCode()作为hash值，例如：
- 假设
length = 16→ 只看低 4 位（& 15 = & 0b1111） - 若一批对象的
hashCode()低 4 位都是0000（比如连续递增 ID：1000, 1016, 1032…），它们会全部落到table[0]，退化成链表 → O(n) 查询！
所以就需要用(h = key.hashCode()) ^ (h >>> 16)“扰动”hashCode()值。也就是：
- 将
hashCode()的高 16 位异或到低 16 位 - 使得原本仅由低位决定的索引，现在高位也参与决策
- 提升低位的随机性，减少冲突
例如，假设hashCode()是：
h = 0b11001010 11110000 10101010 00000001 // 假设高 16 位有信息，低 16 位趋同
h >>> 16 = 0b00000000 00000000 11001010 11110000
h ^ (h >>> 16) = 0b11001010 11110000 01100000 11110001 // 低 16 位被“打散”
→ 即使原hashCode()低 4 位相同，扰动后大概率不同！
索引计算的巧妙设计
当HashMap扩容时（length → 2 * length），传统哈希表需要全部 rehash（重新计算每个 key 的hash % newLength），代价高。
但HashMap利用“2 的幂”特性，避免重新计算 hash。
原理
设旧容量oldCap = 2ⁿ，新容量newCap = 2ⁿ⁺¹ = 2 * oldCap
对任意 key，其旧索引为：oldIndex = hash & (oldCap - 1) = hash & (2ⁿ - 1)
新索引为：newIndex = hash & (newCap - 1) = hash & (2ⁿ⁺¹ - 1)
而2ⁿ⁺¹ - 1 = (2ⁿ - 1) | 2ⁿ → 即比旧掩码多了一个更高位的 1（第 n 位）。
因此：
- 若
hash的第 n 位是 0 →newIndex = oldIndex - 若
hash的第 n 位是 1 →newIndex = oldIndex + oldCap
结论：每个桶中的元素，扩容后只会落在两个位置之一：
- 原位置（
index） - 原位置 + 旧容量（
index + oldCap）
根据该逻辑，HashMap的扩容操作可以直接计算元素索引，无需重新计算。
举例
设旧容量oldCap = 8（0b1000），oldCap-1 = 7 = 0b0111
新容量newCap = 16（0b10000），newCap-1 = 15 = 0b1111
| hash (二进制) | oldIndex = hash & 7 | 第 3 位（从 0 起） | newIndex = hash & 15 |
|---|---|---|---|
...00101 |
101 & 111 = 5 |
0（第 3 位是 0） | 0101 & 1111 = 5 |
...10101 |
101 & 111 = 5 |
1（第 3 位是 1） | 1101 & 1111 = 13 = 5 + 8 |
→ 同一个旧桶table[5]中的元素，扩容后只去newTable[5]或newTable[5 + 8] = newTable[13]。
源码分析
resize()的实现如下：
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table; // 获取原来的数组 tableint oldCap = (oldTab == null) ? 0 : oldTab.length; // 获取数组长度 oldCapint oldThr = threshold; // 获取阈值 oldThrint newCap, newThr = 0;if (oldCap > 0) { // 如果原来的数组 table 不为空if (oldCap >= MAXIMUM_CAPACITY) { // 容量已达上限（1 << 30），后续只能链表冲突threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // 没超过上限，就扩充为原来的 2 倍oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 计算新的 resize 上限if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr; // 将新阈值赋值给成员变量 threshold@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 创建新数组 newTabtable = newTab; // 将新数组 newTab 赋值给成员变量 tableif (oldTab != null) { // 如果旧数组 oldTab 不为空for (int j = 0; j < oldCap; ++j) { // 遍历旧数组的每个元素Node<K,V> e;if ((e = oldTab[j]) != null) { // 如果该元素不为空oldTab[j] = null; // 将旧数组中该位置的元素置为 null，以便垃圾回收if (e.next == null) // 如果该元素没有冲突newTab[e.hash & (newCap - 1)] = e; // 直接将该元素放入新数组else if (e instanceof TreeNode) // 如果该元素是树节点((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 将该树节点分裂成两个链表else { // 如果该元素是链表Node<K,V> loHead = null, loTail = null; // 低位链表的头结点和尾结点Node<K,V> hiHead = null, hiTail = null; // 高位链表的头结点和尾结点Node<K,V> next;do { // 遍历该链表next = e.next;if ((e.hash & oldCap) == 0) { // 如果该元素在低位链表中if (loTail == null) // 如果低位链表还没有结点loHead = e; // 将该元素作为低位链表的头结点elseloTail.next = e; // 如果低位链表已经有结点，将该元素加入低位链表的尾部loTail = e; // 更新低位链表的尾结点}else { // 如果该元素在高位链表中if (hiTail == null) // 如果高位链表还没有结点hiHead = e; // 将该元素作为高位链表的头结点elsehiTail.next = e; // 如果高位链表已经有结点，将该元素加入高位链表的尾部hiTail = e; // 更新高位链表的尾结点}} while ((e = next) != null);if (loTail != null) { // 如果低位链表不为空loTail.next = null; // 将低位链表的尾结点指向 null，以便垃圾回收newTab[j] = loHead; // 将低位链表作为新数组对应位置的元素}if (hiTail != null) { // 如果高位链表不为空hiTail.next = null; // 将高位链表的尾结点指向 null，以便垃圾回收newTab[j + oldCap] = hiHead; // 将高位链表作为新数组对应位置的元素}}}}}return newTab; // 返回新数组
}
重点关注新数组 & 迁移数据：
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) { // 仅当非首次初始化才迁移for (int j = 0; j < oldCap; ++j) { // 遍历每个桶（bucket）Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null; // help GC...}}
}
oldTab[j] = null的作用是断开旧引用，避免内存泄漏。
之后会按节点类型分类迁移（核心）：
Case 1：单个节点
if (e.next == null)newTab[e.hash & (newCap - 1)] = e;
直接计算新位置：因newCap仍是 2 的幂，& (newCap-1)等价于% newCap
Case 2：红黑树节点（TreeNode）
else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
split()方法会将树节点分裂成两个链表。
Case 3：链表节点（关键）
else { // 链表Node<K,V> loHead = null, loTail = null; // 低位链Node<K,V> hiHead = null, hiTail = null; // 高位链Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {// 放入低位链（位置 j）if (loTail == null) loHead = e;else loTail.next = e;loTail = e;} else {// 放入高位链（位置 j + oldCap）if (hiTail == null) hiHead = e;else hiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}
}
(e.hash & oldCap) == 0的作用即判断该元素在低位链表中还是高位链表中。
前面分析过，设旧容量oldCap = 2ⁿ，新容量newCap = 2ⁿ⁺¹ = 2 * oldCap，则：
- 若
hash的第 n 位是 0 →newIndex = oldIndex - 若
hash的第 n 位是 1 →newIndex = oldIndex + oldCap
而注意到：
oldCap = 2ⁿ = 0b100...000 (第 n 位为 1，其余为 0)
所以hash & oldCap的结果：
- 非 0 ⇔
hash的第 n 位是 1 - == 0 ⇔
hash的第 n 位是 0
| 第 n 位 | 旧索引j |
新索引 |
|---|---|---|
| 0 | low n bits |
仍是low n bits → 位置j |
| 1 | low n bits |
1 << n + low n bits = oldCap + j → 位置j + oldCap |
因此：
loHead/loTail：第 n 位为 0 → 迁移到newTab[j]hiHead/hiTail：第 n 位为 1 → 迁移到newTab[j + oldCap]