HashMap底层讲解

首先HashMap是初始容量为 16，负载因子为 0.75，则扩容阈值为 16 × 0.75 = 12。当存入第 13 个元素时，HashMap 就会触发扩容。
当触发扩容时，HashMap 的容量会扩大为当前容量的两倍。例如，容量从 16 增加到 32，从 32 增加到 64 等。数组长度一定是 2 的幂

问题：为什么数组长度一定是 2 的幂？

这是为了用位运算代替取模运算，提升性能。

1

hash % length == hash & (length - 1)   // 前提：length 是 2 的幂

• % 是耗性能的除法操作
• & 是非常快的位运算
• 所以为了高性能，HashMap 规定数组长度只能是 2 的幂，这样 & 操作就相当于 %
  因为只用了 hash 的低位，如果很多 key 的低位部分相同（比如都以 0 结尾、或者 hashCode 差异集中在高位），就会被分配到同一个桶中，发生严重冲突！
  所以才引入了“扰动函数”：

1

hash = h ^ (h >>> 16)

h是key.hashCode()得到的，在经过上面的运算之后，把高位的信息混进了地位，减少了分布不均匀的情况

右移高位 + 异或：让高位参与进低位的计算

• h >>> 16：把哈希值的高 16 位移到低位。
• h ^ (h >>> 16)：将原始值和高位部分做 按位异或，等于把高位的信息折叠混进低位。
  这样一来，即便多个 key 的 hashCode() 低位相同，但如果高位不同，最终 hash() 的值也会不同，从而分散到不同的桶中。

✅ 举个例子：

假设两个 key 的 hashCode() 是：

原始 hashCode 的低 16 位完全一样：0x0001，最终用来计算桶位置时结果会一样（冲突！）。
现在看扰动函数：

h ^ (h >>> 16)

• A: 0x12340001 ^ 0x1234 = 0x12341235
• B: 0x56780001 ^ 0x5678 = 0x56785679

扰动后，它们的低位已经不一样了 → 可以分配到不同的桶，冲突减少了！

问题：HashMap 是怎么根据哈希值的低位来分配桶的？

✅ 第一步：桶的结构

HashMap 的底层结构是一个数组 + 链表（或红黑树）：

1

Node<K,V>[] table; // 本质是一个数组，每个元素就是一个“桶”

数组长度是 2 的幂，比如 16、32、64……（默认初始容量为 16）。

✅ 第二步：桶的下标是怎么计算的？

桶的下标，也就是哈希值对应的桶的位置，是通过下面这个公式计算的：

1

int index = (table.length - 1) & hash;

• hash：是经过扰动函数处理后的哈希值。
• table.length - 1：是一个掩码（mask），比如：
  • 如果数组长度是 16，则掩码为 0b0000_1111（即 15）。
  • 如果数组长度是 32，则掩码为 0b0001_1111（即 31）。

这个 & 操作就相当于：

只保留 hash 的低几位，用作数组下标

🧠 举个例子：

1
2
3
4

hash = 0b1010_0110_1010_1111_1101_0100_1100_1010   // 假设扰动后的哈希值
table.length = 16  // => table.length - 1 = 15 = 0b0000_0000_0000_0000_0000_0000_0000_1111

index = hash & 0b1111 = 0b1010 = 10

所以这个 key 最终被映射到数组的第 10 个桶中。

✅ 为什么只保留低位就能定位桶？

• 因为桶的数量（table.length）是 2 的幂，比如 2⁴ = 16。
• 所以桶的下标只需要 4 位（二进制）来表示。
• 使用 (table.length - 1) & hash 就能直接取出哈希值的低 4 位作为下标。

这是一个比 % 更快的方式。

📌 总结图示：

💡 常见误区

很多人以为“HashMap 根据 hash 值来分配桶”，其实更准确地说：它是根据 hash 值的低位来定位桶的。
这就是为什么哈希值低位分布不均时，冲突会非常严重 —— 所以才要用扰动函数混合高位。

元素搬迁

rehashing 细节

按照我们的思维，每一个元素应该是重新 hash 一个一个搬迁过去。

在 1.7 的时候就是这样实现的，然而 1.8 在这里做了优化，关键点就在于数组的长度是 2 的次方，且扩容为 2 倍。

因为数组的长度是 2 的 n 次方，所以假设以前的数组长度（16）二进制表示是 010000，那么新数组的长度（32）二进制表示是 100000，这个应该很好理解吧？

它们之间的差别就在于高位多了一个 1，而我们通过 key 的 hash 值定位其在数组位置所采用的方法是 (数组长度-1) & hash。我们还是拿 16 和 32 长度来举例：

16-1=15，二进制为 001111

32-1=31，二进制为 011111

所以重点就在 key 的 hash 值的从右往左数第五位是否是 1，如果是 1 说明需要搬迁到新位置，且新位置的下标就是原下标+16（原数组大小），如果是 0 说明吃不到新数组长度的高位，那就还是在原位置，不需要迁移。

所以，我们刚好拿老数组的长度（010000）来判断高位是否是 1，这里只有两种情况，要么是 1 要么是 0 。

扩容后，HashMap 多了一位用于分桶，所以只要那一位是 1，就说明这个 key 应该去“新增加的桶”。

为什么 HashMap 中桶位置计算要用 (length - 1) & hash，而不是直接用 length & hash？

✅ 一句话解释：

因为只有当 数组长度是 2 的幂 时，length - 1 才能构造出一个全是 1 的掩码，从而提取出 哈希值的低位。

🔍 举个例子直观理解：

假设数组长度是 16：

1
2

length       =  16    = 0b0001_0000
length - 1   =  15    = 0b0000_1111

如果写：

1

index = hash & length

就等于：

1

index = hash & 0b0001_0000 // 只有第 5 位能参与计算

➡️ 只看了一位！几乎所有 hash 都会落到几个固定的位置，极其不均匀，导致严重哈希冲突！

而如果你写：

1
2

index = hash & (length - 1)
       = hash & 0b0000_1111  // 看的是低 4 位

➡️ 这样 hash 的低位能平均分布在 0 ~ 15 共 16 个桶中，非常均匀！

📌 为什么这样做只有在 2 的幂下才成立？

我们来看几个例子：

可以看出：

length - 1 恰好是一个连续的低位全 1 掩码，可以保留 hash 的低位，实现高效分桶！

🔁 反例：如果不是 2 的幂会怎样？

比如数组长度是 10（不是 2 的幂）：

• length - 1 = 9 = 0b1001，掩码不连续！

• hash & 0b1001 结果会跳跃分布，桶分布非常不均匀！

所以 HashMap 强制数组长度只能是 2 的幂，就是为了让 (length - 1) 变成理想的掩码。