Chap9 词典

返回：0300 数据结构总目录 · 上一章：0308 Chap8 高级搜索树 · 下一章：0310 Chap10 优先级队列

1、学习目标

词典关注的是“按关键码查找、插入、删除词条”。前面 BST、AVL、B 树都能做词典，但本章的重点是：如果允许用散列思想，很多操作可以做到期望 O(1)。

模块	要掌握的内容
词典 ADT	`get`、`put`、`remove`、`contains`
散列表	桶数组、装填因子、冲突
哈希函数	除余法、MAD 法、字符串哈希
冲突处理	独立链、开放定址、线性试探、平方试探、双向平方试探、再散列
线性排序	桶排序、基数排序
拓展结构	跳表、位图、MD5 指纹

2、资料范围

PDF 课件	内容
`09.Dictionary.A.hashing.Call-by-value.pdf`	词典和散列思想入口
`09.Dictionary.B.hashing.principle.pdf`	散列基本原理
`09.Dictionary.C.Hashing.Hash-Function.pdf`	哈希函数设计
`09.Dictionary.D1.hashing.Collision-seperate_chaining.pdf`	独立链冲突处理
`09.Dictionary.D2.hashing.Collision-open_addressing.pdf`	开放定址冲突处理
`09.Dictionary.E.Bucketsort.pdf`	桶排序
`09.Dictionary.F.Radixsort.pdf`	基数排序
`09.Dictionary.XA1-XA2.Skiplist`	跳表
`09.Dictionary.XB1-XB4.Bitmap`	位图
`09.Dictionary.XC.Md5.pdf`	MD5 与指纹思想

3、词典 ADT

词典保存一组键值对：

1	Entry = (key, value)

常见操作：

操作	含义
`get(k)`	根据键 `k` 查找对应值
`put(k, v)`	插入或更新键值对
`remove(k)`	删除键为 `k` 的词条
`contains(k)`	判断关键码是否存在

词典和集合的区别是：集合只关心元素是否存在，词典还要保存与关键码绑定的值。比如符号表、缓存、路由表、单词频率表，本质上都可以看作词典。

4、散列表

散列表的基本想法：

1	key --hash(key)--> address

把关键码映射到数组下标，如果映射均匀，查找就不需要沿树或链表一步步比较。

关键指标：

名称	含义
桶数组	保存词条的底层数组
桶地址	`hash(key)` 映射出的数组位置
冲突	不同关键码映射到同一桶
装填因子	`λ = n / M`，元素数除以桶数
再散列	扩容后重新计算所有元素的位置

散列表的效率不是绝对 O(1)，而是依赖哈希函数、装填因子和冲突处理策略。最坏情况下所有元素落在同一桶，查找会退化。

5、哈希函数

好的哈希函数要尽量满足：

确定性：同一个 key 每次得到同一个地址。
高效性：计算不能太慢。
均匀性：尽量把关键码分散到各桶。
抗模式：输入有规律时也不集中。

5.1 除余法

1	h(key) = key mod M

M 常选素数，避免关键码规律和表长规律叠加后造成集中。

5.2 MAD 法

1	h(key) = (a * key + b) mod M

其中 a、b 用来打散关键码分布。它不是魔法，只是降低简单除余法遇到模式输入时的风险。

5.3 字符串哈希

字符串可以看作某个进制下的多项式：

1 2	s = "abc" hash(s) = a * R^2 + b * R + c

实际实现中会边扫描边累积：

size_t h = 0;
for (char c : s) {
    h = h * 131 + static_cast<unsigned char>(c);
}

字符串哈希要注意溢出、字符编码、大小写和模数选择。溢出不一定是错，很多实现会主动利用无符号整数自然回绕。

6、冲突处理

6.1 独立链

每个桶后面挂一个链表或小容器：

1	bucket[i] -> entry -> entry -> entry

优点是实现直接，删除方便；缺点是额外指针开销较大，缓存局部性一般。当装填因子较大时，每条链会变长，查找退化为链表扫描。

6.2 开放定址

所有词条都放在桶数组内部。若目标桶被占用，就按某种探测序列继续找空位。

方法	探测序列	特点
线性试探	`h(k), h(k)+1, h(k)+2...`	简单，但容易主聚集
平方试探	`h(k)+1^2, h(k)+2^2...`	缓解主聚集，但覆盖性要小心
双散列	`h1(k)+i*h2(k)`	分布更灵活，要求步长和表长互素

开放定址删除时不能直接清空，否则会截断后续探测链。常见做法是设置懒删除标记：

1
2
3

EMPTY：从未使用
DELETED：曾经使用，现已删除
OCCUPIED：正在使用

查找遇到 DELETED 要继续探测，遇到 EMPTY 才能确认不存在。

7、桶排序与基数排序

桶排序适合关键码范围较小或分布较均匀的场景。基本流程：

按关键码范围把元素放进不同桶。
桶内排序或直接计数。
按桶顺序收集结果。

当关键码是整数且范围不大时，可以退化为计数排序。

基数排序按位处理关键码：

1	个位 -> 十位 -> 百位 -> ...

若每一轮使用稳定排序，则最终整体有序。LSD 基数排序常从低位到高位，要求中间排序稳定；MSD 基数排序从高位开始，更像递归分桶。

8、跳表

跳表是在有序链表上增加多级索引：

Level 3:  1 ---------------- 17
Level 2:  1 ------ 9 ------- 17
Level 1:  1 -- 4 -- 9 -- 13 -- 17
Level 0:  1 2 4 6 9 11 13 17

查找从最高层开始，能往右就往右，不能往右就下移。插入时随机决定节点高度。

特点：

项目	说明
查找	期望 `O(log n)`
插入	期望 `O(log n)`
删除	期望 `O(log n)`
优点	实现比红黑树直观，区间遍历方便
代价	依赖随机层高，空间有冗余

9、位图

位图用一个 bit 表示一个整数是否出现：

1 2	bit[i] = 1 表示 i 存在 bit[i] = 0 表示 i 不存在

适合整数范围已知、数据规模大、只关心存在性的场景。比如一亿个非负整数去重，如果直接用布尔数组会浪费，位图可以把空间压缩到原来的八分之一左右。

常见操作：

void set(int x) {
    bits[x >> 3] |= 1 << (x & 7);
}

bool test(int x) {
    return bits[x >> 3] & (1 << (x & 7));
}

位图不适合保存附加值，也不适合范围极大但数据极稀疏的情况。

10、MD5 与指纹思想

MD5 在这里主要作为“指纹”的入口理解：把任意长度数据映射成固定长度摘要。

用于数据结构视角时，重点不是密码学细节，而是：

固定长度摘要方便比较。
微小输入变化会造成摘要明显变化。
摘要冲突理论上存在。
安全场景下 MD5 已不适合作为抗碰撞密码哈希。

在普通去重、缓存校验、文件快速比对里，指纹思想很常见；安全敏感场景要换更可靠的算法。

11、复杂度汇总

结构/算法	查找	插入	删除	备注
散列表期望	`O(1)`	`O(1)`	`O(1)`	依赖装填因子和哈希函数
散列表最坏	`O(n)`	`O(n)`	`O(n)`	极端冲突
跳表期望	`O(log n)`	`O(log n)`	`O(log n)`	随机化结构
位图	`O(1)`	`O(1)`	`O(1)`	只保存存在性
桶排序	`O(n+k)`	-	-	`k` 为桶数或关键码范围
基数排序	`O(d(n+k))`	-	-	`d` 为位数

12、易错点

易错点	修正
把散列表说成必然 `O(1)`	准确说是期望 `O(1)`
删除开放定址元素时直接置空	要用懒删除标记
忽视装填因子	装填因子过高会显著增加冲突
基数排序每轮不用稳定排序	LSD 基数排序必须保证每轮稳定
位图当词典用	位图只能表示存在性，不能保存值

13、复盘清单

检查项	状态
能解释词典 ADT 与集合的区别	待复盘
能说明装填因子对散列表效率的影响	待复盘
能比较独立链和开放定址	待复盘
能写开放定址查找和懒删除逻辑	待复盘
能解释桶排序、基数排序适用场景	待复盘
能手画跳表查找路径	待复盘
能用位图完成整数去重	待复盘