适用读者：会
HashMap但说不清"冲突怎么办""负载因子为什么是 0.75"的人。
前置：S03-B02。
实测环境：Python 3.12.3（自实现布隆过滤器）；实测日期 2026-11-05。
覆盖旧文：A-1502（哈希表，440 点）、A-1511（布隆过滤器，138 点）= 578 点。
覆盖扩展：E-S03-006（冲突处理）、E-S03-008（误判率公式）。
上一篇：S03-B03 · 栈与队列：只在一端操作的价值
下一篇：S03-B05 · 堆。
1. 一句话结论
哈希表的 O(1) 是"平均"且"有前提"的：哈希函数均匀 + 负载因子受控。布隆过滤器用"允许误判"换来了空间上的极致压缩。
| 结构 | 能力 | 代价 |
|---|---|---|
| 哈希表 | 精确查找/插入/删除 O(1) 平均 | 内存（存 key 与 value）+ 冲突处理 |
| 布隆过滤器 | 只判断"可能存在/一定不存在" | 误判（false positive）+ 不支持删除 |
2. 哈希表：冲突是必然的
把无限多 key 映射到有限多桶，冲突必然发生。两种主流处理：
| 策略 | 做法 | 优点 | 缺点 |
|---|---|---|---|
| 链地址（separate chaining） | 每个桶挂一个链表/红黑树 | 实现简单、删除方便 | 指针开销、cache 不友好 |
| 开放寻址（open addressing） | 冲突时按规则找下一个空位（线性/二次/双散列） | 无指针、cache 友好 | 删除要用"墓碑"；负载高时退化快 |
JDK 的 HashMap 是链地址 + 树化：链表长度 ≥ 8 且容量 ≥ 64 时转红黑树（防极端冲突导致 O(n)）。
2.1 负载因子为什么是 0.75
| 负载因子 | 冲突概率 | 空间 |
|---|---|---|
| 0.5 | 低 | 浪费一半 |
| 0.75 | 可接受 | 折中（JDK 默认） |
| 1.0+ | 明显升高 | 省空间但慢 |
判据：负载因子是"时间/空间"的旋钮，不是必须 0.75。已知元素数时，用 new HashMap<>(expectedSize / 0.75f + 1) 避免扩容。
3. 布隆过滤器：用误判换空间（实测 E-S03-008）
3.1 原理
用 m 个 bit + k 个哈希函数：插入时把 k 个位置置 1；查询时若 k 个位置全为 1 → "可能存在"；任一为 0 → "一定不存在"。
3.2 参数公式
m = -n · ln(p) / (ln2)² # n 元素数，p 目标误判率
k = (m/n) · ln2
3.3 实测
n = 10,000、目标误判 1%：
理论参数：m=95850 位, k=7, 占用 11.7 KB
实测：10 万次不存在查询，误判 957 次 → 误判率 0.9570%（理论 1.00%）
对比：Python set 存 1 万字符串约 512 KB（不含字符串本体）；布隆 11.7 KB
| 指标 | 布隆 | 精确集合 |
|---|---|---|
| 内存 | 11.7 KB | 512 KB（44×） |
| 误判 | 0.957% | 0 |
| 删除 | ❌ 不支持 | ✅ |
| 漏判（false negative） | 0（只要不误删） | 0 |
关键设计约束：布隆过滤器永远不能说"一定存在"，只能说"可能存在"。所以它只能放在"查库之前"做挡板（挡住 99% 的不存在请求），不能作为唯一判据。
4. 两者组合的经典架构
请求 → 布隆过滤器（快速否定）
│ 可能存在
▼
Redis / DB（精确判断）
| 收益 | 说明 |
|---|---|
| 挡住无效请求 | 缓存穿透防护（恶意查不存在 ID） |
| 内存便宜 | 千万级 key 只需几十 MB |
代价：布隆说不存在时可以直接拒；说存在时仍要查一次——它只是"过滤器"，不是"索引"。
5. 一致性哈希（E-S03-007，简述）
普通取模哈希 hash(key) % N 在节点增减时几乎全部 key 需要迁移。一致性哈希把节点与 key 都映射到一个环上，节点增减只影响邻近区间。
| 方案 | 扩容时迁移比例 |
|---|---|
| 取模 | 近乎 100% |
| 一致性哈希 | 约 1/N |
| 一致性哈希 + 虚拟节点 | 更均衡 |
用于：分布式缓存（S12）、分库分表（S11）。细节归那些系列。
6. 五个误区
| 误区 | 真相 |
|---|---|
| "哈希表查找永远 O(1)" | 平均是；最坏 O(n)（全冲突） |
| "负载因子越小越好" | 空间换时间，有成本 |
| "布隆过滤器能删除元素" | 标准布隆不支持（置 0 会影响其他元素） |
| "布隆说存在就一定存在" | 只说"可能存在"；误判率由 m/n/k 决定 |
| "哈希函数随便写就行" | 不均匀的哈希会退化成链表 |
7. 自检
- 链地址与开放寻址各自的适用场景？
- 负载因子 0.75 是怎么来的？什么时候该改？
- 给定 n=100 万、p=0.1%，算出 m 与 k 的量级。
- 为什么布隆过滤器不能作为唯一判据？
- 一致性哈希相比取模，扩容时迁移量降了多少？
8. 下一篇
S03-B05 · 堆：只要最大值，为什么要维护整棵树
哈希表解决"定位"，堆解决"取极值"。下一篇用实测说明：建堆为什么是 O(n) 而不是 O(n log n)（heapify 23.2 ms vs 逐个 push 68.2 ms），以及 Top-K 为什么比全排序快 15 倍。
本篇属于系列《S03 · 数据结构与算法》。旧文来源：A-1502/1511；扩展点 E-S03-006/007/008。布隆实测（11.7 KB / 0.957% 误判）为 2026-11-05。