哈希表与位图：冲突处理、HashMap 与空间优化

本文覆盖哈希表的核心原理（散列函数设计、冲突解决、装载因子）、Java HashMap 实现要点，以及布隆过滤器和位图两种空间高效的数据结构。

目录

章节	说明
散列表基础	散列思想、散列函数设计
冲突解决	开放寻址法 vs 链表法
装载因子与扩容	性能退化的关键指标
Java HashMap 原理	底层实现与优化
布隆过滤器	空间高效的概率型数据结构
位图	用比特位存储状态

散列表基础

散列表（Hash Table） 是数组的扩展，借助散列函数将键值映射为数组下标，利用数组 O(1) 随机访问的特性实现快速查找。

$$key \xrightarrow{hash(key)} 数组下标 \rightarrow 存取数据$$

为什么散列表这么快？ 本质上是用函数计算代替比较查找——不需要遍历，直接算出位置。代价是必须处理"两个不同 key 映射到同一下标"的冲突问题。

散列函数设计要求

1. 散列值是非负整数（对应数组下标）
2. 相同 key 映射到相同散列值（确定性）
3. 不同 key 尽量映射到不同散列值（完全无冲突几乎不可能，只能降低概率）

常见散列函数

类型	适用场景	特点
取模法 hash(key) = key % m	整数 key，m 取质数效果好	简单，m 为质数时分布均匀
乘法散列	均匀分布场景	对 m 不敏感
MD5/SHA	加密场景	安全性高，但性能低
MurmurHash	高性能非加密场景	分布均匀，速度快

冲突解决

不同 key 映射到同一下标时必须有策略处理冲突，主流方案有两种：

开放寻址法（Open Addressing）

冲突时在数组中重新探测空闲位置：

线性探测：依次往后找空位，hash(key)+1, hash(key)+2, ...

二次探测：步长变为平方，hash(key)+1², hash(key)+2², ...，减少聚集

双重散列：使用多个散列函数，第一个冲突换第二个，依次类推

// 删除操作注意：不能直接置空，需标记为 DELETED
// 否则查找时会误判为"链路断开，元素不存在"
enum SlotState { EMPTY, OCCUPIED, DELETED }

特点	说明
数据集中存储	对 CPU 缓存友好，查找连续内存
删除复杂	需特殊标记 DELETED，不能直接置空
装载因子不能太大	建议 < 0.7，否则探测次数急剧增加

链表法（Chaining）

每个槽位对应一条链表，冲突元素都追加到链表尾部。

散列表：
[0] → null
[1] → A → D → null
[2] → B → null
[3] → C → E → null

特点	说明
实现简单	链表操作直观，删除无需特殊标记
内存不连续	对缓存不友好
链表可升级	长链表可换成红黑树（Java HashMap Java 8+）

对比

维度	开放寻址法	链表法
内存利用率	高（无额外指针）	低（链表指针开销）
缓存友好性	好（数据紧凑）	差（指针跳跃）
适用场景	数据量小且可预估	数据量大或不可预估

装载因子与扩容

$$装载因子 = \frac{已填入元素个数}{散列表长度}$$

装载因子越大，冲突越多，性能越差（查找退化为 O(n)）。

方案	推荐装载因子阈值	原因
开放寻址法	< 0.7	探测次数随装载因子非线性增长
链表法	< 0.75（Java HashMap 默认）	链表平均长度约为 0.75

动态扩容

当装载因子超过阈值时，申请更大的数组（通常 2 倍），重新散列（rehash） 所有元素。

// Java HashMap 扩容触发条件
if (size > threshold) { // threshold = capacity * loadFactor
    resize(); // 容量翻倍，重新计算所有元素的位置
}

大规模扩容的问题：rehash 操作耗时较长，会造成短暂的性能抖动。可采用渐进式扩容：维护新旧两张表，每次查询时顺带迁移少量元素，分摊扩容开销。Redis 的字典扩容即采用此策略。

Java HashMap 原理

底层结构

Java 版本	底层结构	说明
Java 7 及之前	数组 + 链表	冲突元素挂链表
Java 8+	数组 + 链表 + 红黑树	链表过长时树化，O(n) → O(logn)

table[]
  [0] → null
  [1] → Node(k1,v1) → Node(k2,v2) → null    ← 链表
  [2] → TreeNode(k3,v3) → ...               ← 红黑树（链表过长时转换）

关键参数

参数	默认值	说明
初始容量	16	必须是 2 的幂次
装载因子	0.75	超过则扩容（threshold = 16 × 0.75 = 12）
树化阈值	8	链表长度超过此值且 table.length ≥ 64 时转红黑树
退树阈值	6	红黑树节点数低于此值退回链表

为什么容量必须是 2 的幂次？

使用位运算代替取模，大幅提升性能：

// 取模：index = hash % capacity  （慢，需要除法）
// 位运算：index = hash & (capacity - 1)  （快，仅当 capacity 为 2 的幂时等价）

当 capacity = 2^k 时，capacity - 1 的二进制为 k 个 1，hash & (capacity-1) 等价于取低 k 位，效果与取模相同但快得多。

put 流程

1. 计算 key 的 hash 值（高低位异或扰动，减少碰撞）
   hash = (h = key.hashCode()) ^ (h >>> 16)
2. 计算数组下标 index = hash & (n-1)
3. 若 table[index] 为空，直接插入
4. 若不为空，遍历链表/红黑树
   - key 相同（equals 为 true）：覆盖旧值
   - key 不同：追加到链表尾部 / 插入红黑树
5. 若链表长度 >= 8 且 table.length >= 64，转为红黑树
6. 若 size > threshold，触发扩容（容量翻倍，rehash）

为什么要做高低位异或扰动？ 直接用 hashCode() 的低位做下标，高位信息被丢弃，导致分布不均匀。异或扰动将高16位信息混入低16位，使散列更均匀。

布隆过滤器

布隆过滤器（Bloom Filter） 是一种概率型数据结构，用于判断某个元素是否可能存在于集合中。

核心权衡：用极小的内存换取"一定不存在"的确定性答案，以及"可能存在"的概率性答案（存在假阳性，不存在假阴性）。

原理

使用位数组 + 多个散列函数：

• 添加元素：将元素经过 k 个散列函数，分别映射到位数组的 k 个位置，全部置为 1
• 查询元素：检查 k 个位置是否全为 1
  • 全为 1：元素可能存在（有假阳性，因为这些位可能被其他元素置 1）
  • 有 0：元素一定不存在（无假阴性）

误判率公式

设位数组长度为 m，散列函数数量为 k，已插入 n 个元素：

$$P_{误判} \approx \left(1 - e^{-kn/m}\right)^k$$

最优散列函数数量 $k = \frac{m}{n} \ln 2$，此时误判率最低。

特性

特性	说明
空间效率	极高，比散列表小几十倍（每个元素约需 10 比特）
查询效率	O(k)，k 为 hash 函数数量，通常很小
误判率	存在假阳性，可通过增大位数组降低
删除	不支持（置 0 会影响其他共享该位的元素）
单侧误差	只高估不低估——"不存在"是确定的，"存在"是概率的

与 Count-Min Sketch 的相似性：布隆过滤器和 CMS 都具有单侧误差特性——只会高估，不会低估。布隆过滤器高估"存在"，CMS 高估"频次"。

应用场景

• 缓存穿透防护：快速判断 key 是否存在于数据库，过滤掉必然不存在的请求
• 网页爬虫 URL 去重：亿级 URL 用哈希表需要 GB 内存，布隆过滤器只需几十 MB
• 垃圾邮件过滤：快速判断邮件地址是否在黑名单中
• 分布式系统数据同步：快速判断某个 key 是否需要同步

位图

位图（Bitmap） 用每个比特位表示一个数据的状态（通常是存在/不存在），极度节省内存。

为什么需要位图？ 用 int[] 存状态，每个状态占 4 字节（32 位）；用位图，每个状态只占 1 位，节省 32 倍内存。

原理

// 存储 0~N 的整数是否存在，只需 N/8 字节
int[] bitmap = new int[N / 32 + 1]; // 每个 int 存 32 个状态

// 将数字 x 标记为存在
bitmap[x / 32] |= (1 << (x % 32));

// 查询数字 x 是否存在
boolean exists = (bitmap[x / 32] & (1 << (x % 32))) != 0;

// 清除数字 x 的标记
bitmap[x / 32] &= ~(1 << (x % 32));

内存对比

数据结构	存储 1 亿个整数的状态	查询复杂度
boolean 数组	约 100 MB	O(1)
int 数组（标记存在）	约 400 MB	O(1)
散列表（HashSet）	约 400 MB+	O(1)
位图	约 12.5 MB（1亿/8）	O(1)

局限性

• 只能表示整数（或可映射为整数的数据）
• 数据范围稀疏时浪费空间（如只有 1 和 10 亿两个数，需要 10 亿/8 ≈ 125 MB 的位图）
• 不能直接存储重复元素的计数（需改用计数位图，每个元素占多位）

应用场景

• 用户在线状态：userId 作为下标，1 位表示在线/离线
• 大集合交集/并集：两个位图做 AND/OR 位运算，极速求交并集
• 数据去重：配合布隆过滤器，先用布隆过滤器粗过滤，再用位图精确去重

参考资料

• 《数据结构与算法之美》— 18~22、45 章节