查找与哈希表
这一讲只保留基础内容:先学会用 ASL 衡量查找, 再掌握顺序、折半、插值三种查找, 最后理解哈希表的构造、冲突和装填因子。
10.1 查找的基本概念与 ASL
10.1.1 什么是查找表
查找表是同一类型元素的集合。按操作分两类:
- 静态查找表:只查询,不修改;
- 动态查找表:允许插入和删除。
存储结构决定能用哪种查找方法。
10.1.2 关键字:主关键字与次关键字
主关键字能唯一标识一个元素,如学号、身份证号; 次关键字可能重复,如姓名、班级。 主关键字查找的结果唯一,次关键字可能查到一组元素。
10.1.3 ASL 的定义与公式
平均查找长度 ASL 衡量“平均要比较几次”。
设查找第 i 个元素的概率是 p_i、比较次数是 c_i:
等概率时退化为 (1/n)Σc_i。
失败 ASL 则把所有失败情形按等概率求平均。
10.1.4 查找算法的评价维度
比较查找方法时看五点:时间复杂度、空间复杂度、对存储结构的要求、 是否支持插入删除、适用场景。
10.2 顺序查找
10.2.1 一句话本质与扫描方向
从表的一端开始,逐个比较;找到就成功,扫完就失败。 不需要有序,数组和链表都能用。可以从前往后、从后往前,或加哨兵。
10.2.2 成功 ASL
按 1 基位置计算,第 i 个元素要比较 i 次,等概率下:
10.2.3 失败 ASL:n 还是 n+1?
无序表朴素写法失败时比较 n 次;
带哨兵写法多比较一次,是 n+1 次。
差别来自“哨兵算不算一次比较”的约定。
10.2.4 链式存储上的顺序查找
链表只能顺序查找,ASL 与顺序表相同; 指针跳转和缓存不友好,实际常数更大。
10.2.5 优缺点、场景与简单实现
优点:无前提、实现简单;缺点:平均 O(n)。
适合小表、无序表、链表和流式数据。
#include <iostream>
#include <vector>
using namespace std;
/* ---------- 朴素版:0 基,从前往后扫 ---------- */
// 成功:第 i 个元素比较 i+1 次,等概率 ASL = (n+1)/2
// 失败:扫完 n 个元素,比较 n 次
int seqSearchPlain(const vector<int>& a, int key) {
for (int i = 0; i < (int)a.size(); ++i)
if (a[i] == key) return i;
return -1;
}
/* ---------- 带哨兵版:1 基,从后往前扫 ---------- */
// a[1..n] 存数据,a[0] 放哨兵;找不到时一定在 a[0] 停下
// 成功:从后往前比较 n-i+1 次;失败:n+1 次(含哨兵)
int seqSearchSentinel(vector<int>& a, int key) {
int n = (int)a.size() - 1;
a[0] = key;
int i = n;
while (a[i] != key) --i; // 不需要判断 i >= 1
return i; // i == 0 表示失败
}
int main() {
vector<int> v = {17, 25, 39, 42, 58, 66, 73};
cout << seqSearchPlain(v, 39) << "\n"; // 2
cout << seqSearchPlain(v, 100) << "\n"; // -1
vector<int> w(1, 0); // w[0] 是哨兵位
for (int x : v) w.push_back(x);
cout << seqSearchSentinel(w, 39) << "\n"; // 3
cout << seqSearchSentinel(w, 100) << "\n"; // 0,失败
return 0;
}
10.3 折半查找
10.3.1 前提条件与本质
每次拿区间中点与 key 比较,一次砍掉一半候选区间。 两个硬前提:必须有序、必须能随机访问(顺序存储)。 链表不能折半查找。
10.3.2 三步走
- 取当前区间的中点
mid; - 若
a[mid] == key,查找成功; - 若
a[mid] < key,去右半区间;否则去左半区间。区间为空则失败。
10.3.3 为什么是 O(log n)
每比较一次,候选区间大约减半。
从 n 个元素开始,最多折半 ⌈log2 n⌉ 次就会缩到 1 个;
所以比较次数是对数级。
10.3.4 折半查找的局限
- 插入、删除要搬移元素,代价
O(n); - 要求整块连续内存,磁盘上不友好;
- 只能判断“在不在”,不支持范围查询和前驱后继。
10.4 插值查找
10.4.1 按比例取中点
在区间两端值不同、数据近似均匀时,可以按 key 在值域中的比例取 mid,而不是固定取中点:
均匀分布时平均很快(约 O(log log n));
分布严重不均时会退化到 O(n),所以前提是“数据比较均匀”。
10.5 哈希表
10.5.1 一句话本质与核心术语
哈希表用哈希函数 H(key) 直接把关键字算成地址,跳过逐个比较。
要掌握三个词:哈希函数、冲突、装填因子 α = n/m。
10.5.2 六种哈希函数
常见构造方法:直接定址、除留余数、数字分析、平方取中、折叠、随机数。
最常用的是除留余数法:H(k) = k mod p,
p 通常取不大于表长的最大质数。
10.5.3 冲突处理:链地址法
哈希表只存每个桶的头指针,落到同一地址的元素挂成一条链表。 插入用头插法,删除摘链即可;查找时先算地址,再在链表里找。 它适合冲突较多、又需要频繁删除的场景。
10.5.4 再哈希法与公共溢出区
再哈希法准备多个哈希函数,冲突就换一个函数再算; 公共溢出区则把所有冲突元素统一放到另一张表里。 两者都能减少主表拥挤,但实现和空间代价不同。
10.5.5 装填因子 α
n 是哈希表中实际存了多少个元素;m 是哈希表有多少个桶(槽位)。
装填因子 α = n/m,表示平均每个桶里装了多少个元素。
例如 m = 11 个桶、n = 7 个元素,则
α = 7/11 ≈ 0.64,平均每桶约 0.64 个元素;
若 n = 22,则 α = 2,平均每桶挂 2 个元素。
链地址法允许 α > 1,因为一个桶可以挂多个结点。
在“哈希函数把元素均匀撒开”的前提下,链地址法的平均查找代价是
Θ(1 + α):先花 O(1) 算地址,
再在长度约为 α 的链上查找。因此:
- 若
α被控制在一个固定的常数上界内(如α ≤ 1或α ≤ 2), 平均查找是O(1),与元素总数n无关; - 若桶数
m固定、元素数n不断增长,α会随之变大, 平均链长变长,查找就不再是O(1); - “常数”不等于“很小”:
α = 100仍是常数级,但平均要扫约 100 个结点, 实际会很慢。工程上控制α是为了控制实际常数。
所以更准确的说法是:在哈希均匀且 α 有固定上界时,链地址法的期望查找代价是
O(1 + α) = O(1)。
不能简单说“α 在常数附近就一定 O(1)”,还要看哈希是否均匀、这个常数有多大。
10.6 查找方法总览
| 方法 | 前提 | 成功 ASL | 插入 / 删除 | 适用场景 |
|---|---|---|---|---|
| 顺序查找 | 无 | (n+1)/2 | 容易 | 小表、无序、链表 |
| 折半查找 | 有序 + 顺序存储 | 约 log2 n | 要搬移 | 静态表、查多改少 |
| 插值查找 | 有序 + 数据均匀 | 均匀时很快 | 要搬移 | 近似均匀的有序表 |
| 哈希表 | 好的哈希函数 | 期望 O(1) | 容易 | 频繁查找、插入、删除 |
一句话选型:小表随便扫;静态有序表用折半;数据均匀可试插值; 追求平均常数时间就用哈希。