哈希函数与哈希表：散列设计、碰撞处理与一致性哈希

引言

哈希是「用空间换时间」的巅峰思想：一个 O(1) 的查找结构（哈希表）、一个能检验完整性的指纹（密码学哈希）、一个能扛节点增减的数据分布方案（一致性哈希）。但哈希也有两副面孔——快与安全用的完全不是同一类函数。本文把哈希表结构、碰撞处理、密码学哈希与一致性哈希串成一张图，讲清各自的设计目标与工程陷阱。

前置：/others-big-o-complexity-guide/（复杂度）、/others-uuid-identifier-design/（标识符与散列）、/others-data-compression-guide/（信息量与编码）。

目录

• 1. 哈希函数的两副面孔
• 2. 哈希表：O(1) 查找的代价与前提
• 3. 负载因子与扩容
• 4. 碰撞处理：链地址法与开放寻址
• 5. 哈希函数的质量：均匀性与雪崩效应
• 6. 密码学哈希：MD5、SHA-2 与冲突攻击
• 7. 密码存储：BCrypt 与加盐
• 8. 一致性哈希：节点增减不惊动全局
• 9. 布隆过滤器：空间极省的成员判断
• 10. 速查表与一句话记忆
• 延伸阅读

1. 哈希函数的两副面孔

1.1 非密码学哈希（数据结构用）

目标：快、均匀分布、雪崩适度
代表：Java HashMap 的 hashCode、MurmurHash、FNV
不在乎：被逆向、被构造碰撞

1.2 密码学哈希（安全用）

目标：不可逆、抗碰撞（找碰撞极难）、雪崩强
代表：SHA-2/3、SHA-256、BCrypt
在乎：抗攻击——攻击者能故意造碰撞来攻击

记忆：哈希有两副面孔——数据结构用「快且均匀」的散列（MurmurHash/FNV），安全用「抗碰撞不可逆」的密码学哈希（SHA-2/BCrypt）；把两者混用是常见事故。

2. 哈希表：O(1) 查找的代价与前提

2.1 结构

哈希表把 key 哈希成一个桶下标，直接定位到数组位置：

key → hash(key) → 桶号（对表长取模）→ 桶里存 value
理想：直接命中 → O(1)
现实：碰撞 → 桶内链/探测 → 退化

2.2 O(1) 的前提

# 1) 哈希函数均匀（桶分布平均）
# 2) 负载因子受控（见下）
# 3) key 不可变（变了就找不回原桶）
# 前提被破坏 → O(1) 退化成 O(n)（最坏全进一桶）

2.3 key 不可变是铁的约定

# 用可变对象当 key（如改过的 list）→ 哈希变了，查不到
# Java 用 final 字段做 hashCode、Python 要求 key 可哈希（不可变）

记忆：哈希表把 key 哈希成桶下标直接定位——O(1) 的前提是哈希均匀、负载因子受控、key 不可变；前提被破坏会退化成 O(n)。

3. 负载因子与扩容

3.1 负载因子定义

负载因子 α = 元素数 / 桶数
α 越大 → 碰撞越多 → 越慢
Java HashMap 默认 0.75：超过即扩容（重建哈希表、桶翻倍）

3.2 扩容的代价

# 扩容 = 新建更大的桶数组 + 全部元素重新哈希（rehash）
# 摊还分析：偶发 O(n) 扩容、总体平均 O(1) 插入
# 工程注意：扩容瞬间延迟尖峰（大表扩容会卡）

3.3 调负载因子的权衡

# α 调小 → 更快但更费内存
# α 调大 → 省内存但更慢
# 工程选型：内存敏感（大量 entry）用偏大 α，性能敏感用偏小 α

记忆：负载因子 = 元素数/桶数——超过阈值触发扩容（rehash 全部元素）；扩容偶发 O(n) 但摊还 O(1)；调 α 是内存与速度的权衡。

4. 碰撞处理：链地址法与开放寻址

4.1 链地址法（Separate Chaining）

同桶的元素串成链表/树：

桶 3: → (key1, val1) → (key2, val2)
实现简单、α 可超过 1、适合频繁删除
Java 用链表→树（桶长超过 8 转红黑树）优化最坏

4.2 开放寻址（Open Addressing）

碰撞就往下一个空位放：

线性探测：桶 → 桶+1 → 桶+2 …
二次探测/双重散列：步长用另一个哈希
不用指针、缓存友好、α 必须 < 1
删除麻烦（要标记 tombstone）、最坏退化更严重

4.3 选型

# 通用内存哈希表：链地址（实现简单、伸缩灵活）
# 高并发/缓存友好：开放寻址（如 Google dense_hash_map）
# 语言内置：Python dict / Java HashMap 内部已帮你选好

记忆：碰撞处理两条路——链地址法同桶串链表（实现简单、α 可超 1、Java 桶长超 8 转树）、开放寻址往后找空位（缓存友好、α 须 <1、删除麻烦）；语言内置的 dict/HashMap 已替你选好。

5. 哈希函数的质量：均匀性与雪崩效应

5.1 好哈希的三个指标

5.2 为什么「简单取模」不够

key % 100 看着没问题，但：
  - 规律 key（偶数、自增）会扎堆进同桶
  - 需要"打散"：用乘法/移位混合（MurmurHash/FNV）
  - 好哈希让"看似接近的 key"分布得毫无规律

5.3 测试哈希质量

# 简单检验：塞 10 万个 key，看各桶计数方差
# 方差越小越好；目标碰撞率远低于随机猜测
# 安全哈希要更强：差分攻击下仍稳定

记忆：好哈希三指标——均匀（桶分布平均）、雪崩（输入微变输出大变）、快；「key % 100」这类朴素取模会遭规律 key 扎堆，用乘法/移位混合的 MurmurHash/FNV 打散。

6. 密码学哈希：MD5、SHA-2 与冲突攻击

6.1 演进线

MD5：快但已被"构造碰撞"攻破 → 不再用于安全
SHA-1：同 MD5，理论碰撞已公开
SHA-2（SHA-256/512）：目前安全主流
SHA-3：设计全新，未来储备

6.2 为什么「构造碰撞」可怕

# 密码学哈希的要求：找两个不同输入使哈希相同要"指数级难"
# MD5 已能做到"秒级造碰撞"——恶意文件可以伪装成合法文件
# 用途红线：下载校验可用（防传输损坏），防篡改不行（防恶意构造）

6.3 正确的用法

# 完整性校验（防误传）：MD5/SHA-256 都行
# 安全（防恶意构造/签名/证书）：SHA-256+，绝不用 MD5
# 且要配合信任链，哈希本身不是安全保证

记忆：密码学哈希的演进是「碰撞越来越难构造」——MD5/SHA-1 已能被构造碰撞（恶意伪装），SHA-2 是安全主流；MD5 只配做防误传的校验，安全场景（签名/证书/防篡改）必须 SHA-256+。

7. 密码存储：BCrypt 与加盐

7.1 为什么不能直接存 SHA-256(密码)

# SHA 太快：GPU 每秒可试数十亿次，穷举弱密码几分钟
# 无盐：相同密码得到相同哈希 → 彩虹表/批量破解
# 正确方案：慢哈希 + 盐

7.2 BCrypt/Argon2 的要点

加盐：每个用户随机盐，存进结果（salt 无需保密）
慢：故意迭代/内存昂贵，让穷举成本暴涨
BCrypt：经典慢哈希（cost 因子控制慢度）
Argon2：内存难型（抗 GPU 专用硬件），现代推荐

7.3 实践要点

# 盐：随机、每用户不同、长度足够
# cost：随硬件提升逐步调大
# 验证：比较时用"慢比较"（防时序攻击）
# 迁移：老哈希（MD5 存密码）要计划迁移到 BCrypt/Argon2

记忆：密码存储用慢哈希+盐——SHA 太快禁用于密码、无盐会被彩虹表批量破解；BCrypt 用 cost 控慢度、Argon2 抗 GPU，盐随机每用户不同且无需保密；老系统要计划迁移。

8. 一致性哈希：节点增减不惊动全局

8.1 朴素取模的问题

数据按 hash(key) % N 分到 N 个节点
节点从 N 变 N+1 → 几乎所有数据的归属都变 → 大量迁移/缓存全失效

8.2 一致性哈希

把 key 与节点都映射到同一个环上，key 顺时针找第一个节点：

hash 环: [0 .. 2^32)
节点 A/B/C 各落在环上一个点
key 从自己的哈希点顺时针走到第一个节点 → 归属
新增节点 D：只影响 D 逆时针到下一节点之间那一段的 key
→ 迁移量从 O(N) 降到 O(1/N)，其余不动

8.3 虚拟节点

# 问题：节点少时环上分布不均 → 负载倾斜
# 解决：每个物理节点映射成环上多个虚拟点
# 虚拟节点让分布均匀，也能按权重（大节点多虚拟点）

记忆：一致性哈希把 key 与节点都放到环上、key 顺时针找节点——节点增减只影响局部区间（迁移从 O(N) 降到 O(1/N)）；虚拟节点解决少节点分布不均并支持按权重。

9. 布隆过滤器：空间极省的成员判断

9.1 原理

多个独立哈希把位置标记为 1，判断时全 1 才「可能存在」：

插入：把 k 个哈希对应的位都置 1
查询：k 个位全 1 → "可能在"（有误判率）
      有任一位为 0 → "一定不在"
特点：空间省、误判单向（绝不漏判、偶尔误报）

9.2 工程应用

# 缓存穿透防护：不存在的数据先过布隆过滤器，挡住恶意 key
# 爬虫去重：URL 是否访问过（可容忍少量误判）
# 数据库/存储：磁盘块是否存在（LevelDB 用它）

9.3 参数权衡

# 误判率 p、元素数 n、位数 m、哈希数 k 的关系
# 想低误判：多给位（m 大）与适当 k（约 m/n · ln2）
# 不可删除（删位会误删其他元素）——需要删除用计数布隆

记忆：布隆过滤器用 k 个哈希位标记存在性——「一定不在」绝对可靠、「可能在」有误判率；防缓存穿透、爬虫去重、磁盘块索引都用它；不可删除是它的边界。

10. 速查表与一句话记忆

一句话记忆：哈希的两副面孔要分清——数据结构用快而均匀的散列（MurmurHash/FNV，看均匀性与雪崩），安全用抗碰撞的密码学哈希（SHA-2 签名防篡改、BCrypt/Argon2 慢哈希+盐存密码，MD5 只配防误传）；哈希表的 O(1) 建立在均匀哈希+负载因子受控（超 0.75 扩容 rehash）+ key 不可变三条前提上，碰撞用链地址（同桶链，Java 桶长超 8 转树）或开放寻址（往后找空位，α 须 <1）；分布式扩容别用朴素取模，用一致性哈希（key 与节点共置一环、增减只迁移局部、虚拟节点均衡负载）；缓存穿透防护用布隆过滤器（位图+多哈希，「一定不在」可靠、「可能在」可误报）——「快哈希管结构、慢哈希管安全、环哈希管分布、位图管判存」各司其职。

延伸阅读

• /others-big-o-complexity-guide/ — 复杂度与摊还分析
• /others-uuid-identifier-design/ — 标识符设计与散列
• /others-data-compression-guide/ — 信息量与编码
• /others-diff-patch/ — 哈希校验与完整性
• 数据库专题 — 索引与分库分表
• MurmurHash 介绍
• 一致性哈希详解