Hash 全景：从 HashMap 到一致性哈希，一文吃透哈希核心

目录

1. 引子：一行索引代码里的秘密
2. Hash 基础：哈希函数、哈希表、桶与冲突
3. HashMap：哈希取模的单机极致优化
4. new HashMap<>(17) 到底会变成多少？
5. 分布式取模：当基数变成节点数
6. 一致性哈希：用“环”替代“除数”
7. 虚拟节点：解决数据倾斜
8. 一致性哈希的极简实现思路
9. 哈希算法家族：非加密、加密与一致性哈希
10. Hash 的典型应用
11. 工程中的坑：碰撞攻击、热点与数据倾斜
12. 收束：取模的破与立
13. 附：初始容量 17 速查

1. 引子：一行索引代码里的秘密

JDK 8 的 HashMap 源码中，putVal 有一行关键代码：

<span>if</span> ((p = tab[i = (n - <span>1</span>) & hash]) == <span>null</span>)

数组下标 i 由 (n - 1) & hash 得到。
当 n 是 2 的幂时，它等价于：

i = hash % n

但位运算比取模快得多。

这行代码背后藏着一个事实：

HashMap 本质上是在做哈希取模。

而这个设计会像涟漪一样扩散，最终引出一致性哈希这个分布式系统中的核心算法。

2. Hash 基础：哈希函数、哈希表、桶与冲突

2.1 哈希函数

哈希函数把任意长度的输入，映射成固定长度的输出：

hash(key) -> 固定长度整数

好的哈希函数通常追求：

• 确定性：同一个 key 每次哈希结果相同；
• 均匀性：结果尽量均匀分布在值域；
• 高效性：计算速度快；
• 抗碰撞性：不同 key 尽量不产生相同哈希值。

2.2 哈希表

哈希表利用哈希函数把 key 映射到数组下标：

key -> hash(key) -> index -> bucket

理想情况下，增删改查都是 O(1)。

2.3 桶是什么？

哈希表底层通常是一个数组。数组的每个下标位置，就叫一个“桶”（bucket）。

数组 table：

索引：   0     1     2     3     4     5     6     7
       +-----+-----+-----+-----+-----+-----+-----+-----+
       |     |     |  ●  |     |     |     |     |     |
       +-----+-----+-----+-----+-----+-----+-----+-----+
                    ↑
                 第 2 号桶

哈希函数决定 key 去哪个桶：

index = hash(key) % capacity;
<span>// 或 (capacity - 1) & hash</span>

capacity 是桶的数量，通常等于哈希表数组长度。

桶里放什么，取决于冲突处理方式：

Java HashMap 用的是链地址法。一个桶可以放一个元素，也可以放一条链表或一棵红黑树。

2.4 哈希冲突

不同 key 可能算出相同下标，这叫哈希冲突。

常见解决方案：

3. HashMap：哈希取模的单机极致优化

3.1 扰动函数：让低位更随机

HashMap 的 hash()：

<span>static</span> <span>final</span> <span>int</span> <span>hash</span><span>(Object key)</span> {
    <span>int</span> h;
    <span>return</span> (key == <span>null</span>) ? <span>0</span> : (h = key.hashCode()) ^ (h >>> <span>16</span>);
}

为什么要高 16 位异或低 16 位？

因为数组长度通常较小，(n - 1) 只保留 hash 的低几位。
如果不扰动，高位信息会被丢弃，大量 key 可能挤在少数桶里。

扰动让高位“下沉”参与索引计算，成本极低，效果显著。

3.2 容量为 2 的幂：取模变位运算

当 n = 2^k：

hash % n == hash & (n - <span>1</span>)

例如：

n = 32
n - 1 = 31 = 0b0001 1111

hash & 31 只保留低 5 位

所以容量必须是 2 的幂，否则不能用 & 替代 %。

3.3 扩容：只多查一位

容量从 n 翻倍到 2n，索引计算从：

hash & (n - <span>1</span>)

变成：

hash & (2n - <span>1</span>)

本质上只是多考察 hash 的某一个二进制位。

• 这一位为 0：元素留在原下标；
• 这一位为 1：元素移到“原下标 + 旧容量”。

JDK 8 的 resize() 正是利用这一点，把链表拆成低位链和高位链，避免重新计算 hash。

3.4 树化

当链表长度达到 8，且数组长度达到 64，链表转为红黑树，查询从 O(n) 降到 O(log n)。

如果数组长度小于 64，优先扩容，而不是树化。

3.5 负载因子

HashMap 默认负载因子是 0.75。

• 太低：浪费空间；
• 太高：冲突多，查询慢。

阈值 threshold = capacity * loadFactor。
元素数量超过阈值，就扩容。

4. new HashMap<>(17) 到底会变成多少？

HashMap 要求数组长度必须是 2 的幂。
传入 17，会被 tableSizeFor 向上取到最近的 2 的幂：

17 -> 32

所以：

如果你问的是“hash 值会设置多少”，那要注意：

• hash() 的输出只取决于 key 的 hashCode()；
• 初始容量影响的是索引计算时的模数基数；
• 你传 17，它偏要给你 32，因为只有 2 的幂才能让 % 变成 &，才能让扩容只多查一位。

5. 分布式取模：当基数变成节点数

把 HashMap 的逻辑搬到分布式缓存：

nodeIndex = hash(key) % N;

N 是节点数量。

当 N 固定时，它工作得很好：均匀、简单、无额外元数据。

但节点数一变，问题爆发。

假设 3 台缓存服务器，6 个 key：

现在加一台节点，节点数从 3 变成 4，取模基数变成 4：

6 个 key 全部迁移。

这就是普通取模的致命问题：

节点数量一变，几乎所有 key 的归属都会改变。

迁移比例约为：

N / (N + 1)

从 3 台扩到 4 台，迁移约 75%；
从 10 台扩到 11 台，迁移约 90.9%。

这意味着：加一台机器，几乎全部缓存失效，请求穿透到数据库，可能引发缓存雪崩。

问题根源在于：

基数一变，所有映射关系同时断裂。

HashMap 用“容量总是 2 的幂”把断裂限制在“只多查一位”，但分布式节点数不可能永远是 2 的幂。

6. 一致性哈希：用“环”替代“除数”

6.1 核心思想

一致性哈希不再对节点数量取模，而是对固定的哈希空间取模。

把 0 ~ 2^32 - 1 首尾相接成一个环。
节点和数据都映射到环上，数据顺时针找到的第一个节点，就是归属节点。

规则是：

node = 从 hash(key) 的位置顺时针找到的第一个节点;

这个规则里没有 N。
节点数量变了，只是环上多了或少了几个点，规则本身不变。

6.2 节点怎么上环？

节点用 IP 或 IP:端口 做哈希：

hash("节点A") = 100
hash("节点B") = 300
hash("节点C") = 600

环上的顺序是：

0 -> A(100) -> B(300) -> C(600) -> 回到 0

数据也用同样的哈希函数映射到环上。

举例：

6.3 加节点时发生了什么？

现在加入节点 D，假设：

hash("节点D") = 200

环上的顺序变成：

0 -> A(100) -> D(200) -> B(300) -> C(600) -> 回到 0

原来 hash 在 100 到 300 之间的数据，顺时针第一个是 B。
现在 100 到 200 之间的数据，顺时针第一个变成了 D。

所以：

新节点 D 只接管它前一个节点到它之间的那一段数据。

其他数据完全不动。

如果节点数从 3 变成 4，新节点期望接管约：

1 / (N + 1)

也就是约 1/4，即 25%。

对比普通取模：

6.4 为什么它有效？

关键区别在于：映射规则是否依赖节点数量。

普通取模：

hash(key) % N

规则里有 N，所以 N 一变，规则就变了。

一致性哈希：

从 <span>hash</span>(key) 顺时针找第一个节点

规则里没有节点数量。
节点数量只影响环上有哪些点，不影响“顺时针找第一个”这个规则。

所以它把“规则”和“节点数量”解耦了。

6.5 节点下线时呢？

节点下线时，它负责的数据会交给环上顺时针的下一个节点。

比如 B 下线，原来归 B 的数据会顺时针找到 C，归 C。
生产环境通常还要配合数据复制，避免某个节点下线后数据丢失或压力全压到下一个节点。

7. 虚拟节点：解决数据倾斜

如果只有 3 个物理节点，它们在环上可能分布很不均匀。

比如：

A 在 100
B 在 120
C 在 600

那么从 120 到 600 这一大段数据，都会归 C。
C 压力远大于 A 和 B，这就是数据倾斜。

解决办法：虚拟节点。

不再让一个物理节点只在环上占一个点，而是给它生成多个虚拟身份：

节点A -> A#1, A#2, A#3 ...
节点B -> B#1, B#2, B#3 ...
节点C -> C#1, C#2, C#3 ...

这些虚拟节点分别哈希到环上。
数据落到哪个虚拟节点，就路由到对应的物理节点。

虚拟节点把每个物理节点“打散”成很多小段，整体分布就均匀了。

经验值：每个物理节点配 100 到 200 个虚拟节点。
但不是越多越好，虚拟节点越多，环的元数据和路由表也越大。

8. 一致性哈希的极简实现思路

用 TreeMap 存环：

TreeMap<Long, Node> ring = <span>new</span> <span>TreeMap</span><>();

<span>// 节点上环</span>
ring.put(hash(<span>"nodeA"</span>), nodeA);
ring.put(hash(<span>"nodeB"</span>), nodeB);
ring.put(hash(<span>"nodeC"</span>), nodeC);

<span>// 查找归属</span>
<span>Long</span> <span>keyHash</span> <span>=</span> hash(key);
Map.Entry<Long, Node> entry = ring.ceilingEntry(keyHash);
<span>if</span> (entry == <span>null</span>) {
    entry = ring.firstEntry(); <span>// 绕回环起点</span>
}
<span>Node</span> <span>target</span> <span>=</span> entry.getValue();

虚拟节点就是往 ring 里放更多：

hash(nodeId + <span>"#"</span> + i)

核心查找逻辑就是：

• ceilingEntry：找第一个大于等于 keyHash 的节点；
• 找不到就取 firstEntry，形成环。

9. 哈希算法家族：非加密、加密与一致性哈希

9.1 非加密哈希

追求速度和均匀性：

• MurmurHash
• xxHash
• CityHash
• CRC32
• Java hashCode()

适合：HashMap、分片、布隆过滤器、一致性哈希。

9.2 加密哈希

追求抗碰撞、单向性：

• MD5
• SHA-1
• SHA-256
• SHA-3

适合：数字签名、文件校验、密码存储、区块链。

但 MD5、SHA-1 已不推荐用于安全场景。

9.3 一致性哈希常用算法

早期常用 MD5，后来多用 MurmurHash、xxHash，因为更快且分布足够均匀。

10. Hash 的典型应用

10.1 布隆过滤器

用多个哈希函数把元素映射到位数组。

特点：

• 判断“不存在”一定准确；
• 判断“存在”可能有假阳性；
• 不支持删除，计数布隆过滤器可删除。

应用：缓存穿透、URL 去重、垃圾邮件判断。

10.2 分库分表

dbIndex = hash(userId) % dbCount;

但扩容时同样面临取模迁移问题。
所以很多系统改用一致性哈希或预分片。

10.3 哈希索引

数据库可用哈希索引做等值查询，但不支持范围查询。

10.4 去重与秒传

文件哈希作为唯一标识，实现秒传、去重。

10.5 负载均衡

一致性哈希常用于：

• Redis Cluster
• Memcached 客户端分片
• Dubbo 负载均衡
• Nginx upstream hash
• CDN 节点调度

10.6 校验与签名

MD5、SHA 用于文件完整性校验、数字签名。

11. 工程中的坑：碰撞攻击、热点与数据倾斜

11.1 HashDoS

攻击者构造大量哈希碰撞的 key，让哈希表退化成链表，CPU 飙升。

Java 8 用红黑树缓解。
有些语言引入随机哈希种子。

11.2 负载因子

HashMap 默认 0.75：

• 太低：浪费空间；
• 太高：冲突多，查询慢。

11.3 热点 Key

即使哈希均匀，某些 key 访问量极高，也会打爆单节点。
需要本地缓存、热点探测、key 打散。

11.4 数据倾斜

一致性哈希中，虚拟节点不足会导致倾斜。
需要增加虚拟节点或使用带权重的哈希环。

12. 收束：取模的破与立

HashMap 教给我们：

取模本身没有错，错的是让映射规则依赖于一个会变的数。

一致性哈希做的，就是把那个会变的数从“规则内部”挪到“规则外部”——环不变，规则不变，变的只是环上多了或少了几个点。

从 HashMap 的桶到分布式系统的哈希环，取模的破与立贯穿始终。

13. 附：初始容量 17 速查

Map<String, String> map = <span>new</span> <span>HashMap</span><>(<span>17</span>);

本文为原创技术整理，如果对你有帮助，麻烦点赞，收藏。