第11章散列表

导读

散列表（Hash Table）是一种支持高效插入、删除和查找的数据结构。在理想情况下，这些操作的时间复杂度均为O(1)。散列表的核心思想是使用哈希函数将关键字映射到数组下标，从而直接访问元素。

本章将详细介绍散列表的设计原理，包括哈希函数、冲突解决策略、开放寻址法和完全哈希等。我们还将讨论散列表的性能分析和实际应用。

核心概念详解

11.1 散列表的基本思想

直接寻址表：

假设关键字集合U = {0, 1, ..., m-1}，使用数组T[0..m-1]，T[k]存储关键字为k的元素。

优点：O(1)查找
缺点：当U很大但实际元素很少时，空间浪费严重

散列表：

当关键字集合U远大于实际存储的元素数n时，使用哈希函数h将U映射到{0, 1, ..., m-1}。

h: U → {0, 1, ..., m-1}
元素k存储在T[h(k)]
空间从O(|U|)降低到O(m)

11.2 哈希函数

好的哈希函数应具备的特性：

均匀分布：将关键字均匀映射到各个槽
计算高效：O(1)时间计算
确定性：相同关键字总是映射到相同位置

常用哈希函数：

除法哈希：

h(k) = k mod m

m应选择与2的幂无关的素数
例如：m = 701，适合存储约2000个元素

乘法哈希：

h(k) = ⌊m · (kA mod 1)⌋ = ⌊m · (kA - ⌊kA⌋)⌋

A为0到1之间的常数
Knuth建议A = (√5 - 1) / 2 ≈ 0.6180339887

全域哈希：

从一族哈希函数中随机选择一个，保证对任意两个不同关键字，碰撞概率≤1/m。

11.3 冲突解决：链接法

当两个关键字映射到同一位置时，发生冲突（Collision）。链接法（Chaining）将所有映射到同一位置的关键字存储在链表中。

插入：

将新元素插入到链表头部，O(1)

查找：

遍历链表查找关键字，最坏O(n)

删除：

找到元素后从链表中删除，O(1)（已知位置）

性能分析：

设α = n/m为装载因子（load factor）。

简单均匀散列假设：任何关键字等概率映射到任何位置
不成功查找的期望时间：Θ(1 + α)
成功查找的期望时间：Θ(1 + α)

当α = O(1)时（即n = O(m)），散列表操作期望时间为O(1)。

11.4 冲突解决：开放寻址法

开放寻址法（Open Addressing）将所有元素直接存储在散列表数组中，不使用链表。

探测序列：

查找关键字k时，依次检查位置h(k, 0), h(k, 1), h(k, 2), ...，直到找到k或遇到空槽。

线性探测：

h(k, i) = (h'(k) + i) mod m

优点：缓存友好
缺点：聚集（Clustering）——连续占用导致长探测序列

二次探测：

h(k, i) = (h'(k) + c₁·i + c₂·i²) mod m

减少一次聚集
但可能有二次聚集

双重散列：

h(k, i) = (h₁(k) + i·h₂(k)) mod m

使用两个独立的哈希函数
探测序列依赖于关键字，减少聚集

性能分析：

在简单均匀散列假设下：

不成功查找的期望探测次数 ≤ 1/(1-α)
成功查找的期望探测次数 ≤ (1/α)·ln(1/(1-α))

当α接近1时，性能急剧下降。

11.5 完全散列

完全散列（Perfect Hashing）使用两级散列结构，保证最坏情况下O(1)查找。

基本思想：

第一级：使用全域哈希将n个关键字映射到m个槽
第二级：每个槽使用独立的完全哈希函数，无冲突

构造：

第一级：m = n²，期望碰撞次数 < n/2
第二级：对于有s个关键字的槽，使用大小为s²的二级表
随机选择哈希函数直到无冲突

空间：O(n)

查找：O(1)最坏情况

构造：期望O(n)

11.6 散列表的动态扩展

当装载因子α超过阈值时，需要扩展散列表：

扩展过程：

创建大小为2m的新表

重新计算所有元素的哈希值

将元素插入新表

释放旧表

摊还分析：

单次扩展：O(n)
但扩展不频繁（每次容量翻倍）
摊还代价：O(1)

11.7 哈希函数的设计

字符串哈希：

hash(s) = (s[0]·p^(n-1) + s[1]·p^(n-2)) + ... + s[n-1]) mod m

p为素数（如31、37）
多项式滚动哈希

文件哈希：

MD5、SHA-1、SHA-256
用于文件完整性校验

一致性哈希：

分布式系统中的数据分片
最小化节点变化时的数据迁移

11.8 散列表的应用

1. 字典/映射：

键值对存储
O(1)查找、插入、删除

2. 集合：

快速成员测试
去重

3. 缓存：

LRU缓存
网页缓存

4. 数据库索引：

哈希索引
等值查询优化

5. 布隆过滤器：

空间高效的概率数据结构
快速判断元素是否"可能存在"

11.9 散列表的安全性

哈希碰撞攻击：

恶意构造输入导致大量碰撞
性能退化为O(n)
防御：使用随机化哈希函数

哈希泛洪攻击：

针对Web服务器的DoS攻击
防御：密钥哈希、限速

11.10 散列表与其他数据结构的比较

数据结构	查找	插入	删除	有序遍历
散列表	O(1)平均	O(1)平均	O(1)平均	不支持
二叉搜索树	O(log n)	O(log n)	O(log n)	支持
跳表	O(log n)	O(log n)	O(log n)	支持

重要知识点

知识点1：装载因子的影响

装载因子α = n/m决定了散列表的性能：

α小：空间浪费，但性能好
α大：空间高效，但碰撞多，性能差
通常保持α < 0.75

知识点2：简单均匀散列假设

简单均匀散列假设是分析散列表性能的基础：

任何关键字等概率映射到任何位置
实际中难以完全满足
全域哈希可以近似实现

知识点3：开放寻址法的删除

开放寻址法不能简单删除元素（会破坏探测序列）。解决方法：

标记删除（Tombstone）
重新哈希后续元素

知识点4：完全散列的构造

完全散列通过两级结构和随机化，保证无冲突。虽然构造是随机的，但期望时间O(n)，且可以验证。

知识点5：哈希函数的选择

好的哈希函数应该：

均匀分布
计算高效
抵抗碰撞攻击
适应数据特征

常见误区

误区1：散列表总是O(1)

散列表的平均情况是O(1)，但最坏情况可能退化为O(n)。选择合适的哈希函数和装载因子可以减少最坏情况的发生。

误区2：散列表可以存储有序数据

散列表不支持有序遍历。如果需要有序操作，应使用二叉搜索树或跳表。

误区3：哈希函数越复杂越好

复杂的哈希函数计算开销大。简单的哈希函数（如除法、乘法）在大多数场景下已经足够好。

误区4：散列表不需要调整大小

当装载因子过高时，散列表性能会下降。动态扩展是保持性能的关键。

误区5：开放寻址法比链接法好

两种方法各有优劣：

链接法：简单，支持α > 1
开放寻址法：缓存友好，但α必须 < 1

实践应用

应用1：编程语言中的字典/映射

大多数编程语言内置了散列表：

Python: dict
Java: HashMap
C++: unordered_map
JavaScript: Object/Map

应用2：数据库索引

数据库使用散列表加速等值查询：

哈希索引
内存表
查询缓存

应用3：编译器符号表

编译器使用散列表存储：

变量名到地址的映射
函数签名
宏定义

应用4：网络路由

路由器使用散列表进行：

路由表查找
ARP缓存
NAT转换表

应用5：布隆过滤器

布隆过滤器使用多个哈希函数实现空间高效的概率数据结构：

CDN缓存
数据库查询优化
网络爬虫去重

11.11 散列表的详细性能分析

链接法的详细分析：

在简单均匀散列假设下，每个关键字等概率映射到m个槽中的任何一个。设α = n/m为装载因子。

对于不成功查找，需要遍历整个链表。槽i中链表的期望长度为α，因此不成功查找的期望时间为Θ(1 + α)。

对于成功查找，情况略有不同。假设插入n个元素，第i个插入的元素查找时，链表中已有i-1个元素。其期望查找时间为1 + (i-1)/m。对所有元素取平均：

(1/n) · Σ(i=1 to n) (1 + (i-1)/m) = 1 + (n-1)/(2m) ≈ 1 + α/2

因此成功查找的期望时间为Θ(1 + α/2) = Θ(1 + α)。

开放寻址法的详细分析：

在简单均匀散列假设下，对于线性探测，不成功查找的期望探测次数约为(1/2)(1 + 1/(1-α)²)。当α = 0.5时约为2.5次，当α = 0.9时约为50.5次。

对于双重散列，不成功查找的期望探测次数约为-ln(1-α)/α。当α = 0.5时约为1.39次，当α = 0.9时约为2.56次。双重散列的性能明显优于线性探测。

装载因子的实际选择：

链接法：α可以大于1，但通常保持在1-2之间
开放寻址法：α必须小于1，通常保持在0.5-0.75之间
当α超过阈值时，进行rehash（扩展表并重新插入所有元素）

11.12 哈希函数的深入设计

字符串哈希的多种方案：

多项式滚动哈希是最常用的字符串哈希方法。对于字符串s = s₀s₁...sₙ₋₁：

h(s) = (s₀·p^(n-1) + s₁·p^(n-2) + ... + sₙ₋₁) mod m

其中p通常选择31、37或53等素数。这种哈希函数可以增量计算——当字符串窗口滑动时，可以在O(1)时间内更新哈希值。

FNV哈希：

FNV-1和FNV-1a是简单高效的非加密哈希函数：

hash = offset_basis
for each byte:
    hash = hash XOR byte
    hash = hash × FNV_prime

MurmurHash：

MurmurHash是一种高性能的非加密哈希函数，广泛用于哈希表实现。它通过混合（mixing）操作实现良好的分布特性，速度极快。

一致性哈希：

在分布式系统中，一致性哈希用于数据分片。将节点和数据都映射到一个哈希环上，数据分配给顺时针方向最近的节点。当节点增减时，只影响相邻节点的数据，最小化数据迁移。

11.13 布隆过滤器的深入分析

布隆过滤器是一种空间高效的概率数据结构，用于快速判断元素是否属于集合。

结构：

一个位数组（bit array）和k个独立的哈希函数。

插入：

对元素x，计算k个哈希值h₁(x), h₂(x), ..., hₖ(x)，将对应位设为1。

查询：

对元素x，检查h₁(x), h₂(x), ..., hₖ(x)对应的位是否全为1。如果全为1，元素"可能存在"；如果有0，元素"一定不存在"。

误判率分析：

设位数组大小为m，插入n个元素，使用k个哈希函数。某一位仍为0的概率为(1 - 1/m)^(kn) ≈ e^(-kn/m)。查询时所有k位都为1的概率（误判率）为：

(1 - e^(-kn/m))^k

最优的k值为(m/n)·ln2，此时误判率约为(0.6185)^(m/n)。

应用场景：

数据库查询优化：先检查布隆过滤器，避免不必要的磁盘读取
网络爬虫：URL去重
CDN缓存：快速判断内容是否可能已缓存
拼写检查：快速判断单词是否可能在词典中

11.14 散列表的并发安全

在多线程环境中使用散列表需要特殊处理：

ConcurrentHashMap：

Java的ConcurrentHashMap使用分段锁（Segment Locking）：

将表分成多个段（默认16个）
每个段有独立的锁
不同段的并发操作不冲突
读操作通常不需要加锁

线性哈希：

支持增量扩展的哈希方案，避免一次性rehash的大开销。扩展时只分裂一个桶，逐步完成表的扩展。

可扩展哈希：

使用目录（directory）实现动态扩展。目录大小按需增长，每次只分裂一个桶。

本章小结

本章深入介绍了散列表的设计、分析和应用。我们学习了：

基本思想：使用哈希函数将关键字映射到数组下标，实现O(1)查找。

哈希函数：除法哈希、乘法哈希、全域哈希、字符串哈希、一致性哈希等多种方案。

冲突解决：链接法（链表）和开放寻址法（线性探测、二次探测、双重散列），以及各自的性能分析。

性能分析：装载因子对性能的影响，简单均匀散列假设下的期望分析。链接法成功查找期望Θ(1+α)，双重散列优于线性探测。

完全散列：两级结构保证最坏情况O(1)查找。

高级主题：布隆过滤器的原理和误判率分析，并发安全的散列表实现。

应用：字典、集合、缓存、数据库索引、分布式系统等。

散列表是计算机科学中最重要的数据结构之一。深入理解其设计原理、性能特性和安全考量，对于编写高效、安全的代码至关重要。

关键术语

术语	英文	含义
散列表	Hash Table	基于哈希函数的数据结构
哈希函数	Hash Function	将关键字映射到槽的函数
冲突	Collision	不同关键字映射到同一槽
链接法	Chaining	使用链表解决冲突
开放寻址法	Open Addressing	在表中寻找空槽解决冲突
装载因子	Load Factor	α = n/m，表的填充程度
完全散列	Perfect Hashing	无冲突的两级散列
全域哈希	Universal Hashing	随机选择哈希函数

思考题

设计一个哈希函数，用于字符串关键字，并分析其分布特性。

比较链接法和开放寻址法在不同装载因子下的性能。

证明：在简单均匀散列假设下，n个元素全部映射到同一槽的概率为1/m^(n-1)。

设计一个支持O(1)摊还时间的动态散列表，包括插入、删除和扩展操作。

第11章 散列表

导读