第 10 讲

查找与哈希表

这一讲只保留基础内容:先学会用 ASL 衡量查找, 再掌握顺序、折半、插值三种查找, 最后理解哈希表的构造、冲突和装填因子。

预计 70 分钟 前置:数组、循环、简单的对数概念 关键词:ASL · 折半 · 插值 · 哈希 · 装填因子

10.1 查找的基本概念与 ASL

10.1.1 什么是查找表

查找表是同一类型元素的集合。按操作分两类:

存储结构决定能用哪种查找方法。

10.1.2 关键字:主关键字与次关键字

主关键字能唯一标识一个元素,如学号、身份证号; 次关键字可能重复,如姓名、班级。 主关键字查找的结果唯一,次关键字可能查到一组元素。

10.1.3 ASL 的定义与公式

平均查找长度 ASL 衡量“平均要比较几次”。 设查找第 i 个元素的概率是 p_i、比较次数是 c_i:

ASL成功 = Σ pi ci

等概率时退化为 (1/n)Σc_i。 失败 ASL 则把所有失败情形按等概率求平均。

10.1.4 查找算法的评价维度

比较查找方法时看五点:时间复杂度、空间复杂度、对存储结构的要求、 是否支持插入删除、适用场景。

10.2 顺序查找

10.2.1 一句话本质与扫描方向

从表的一端开始,逐个比较;找到就成功,扫完就失败。 不需要有序,数组和链表都能用。可以从前往后、从后往前,或加哨兵。

10.2.2 成功 ASL

按 1 基位置计算,第 i 个元素要比较 i 次,等概率下:

ASL成功 = (1 + 2 + … + n) / n = (n + 1) / 2

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 三步走

  1. 取当前区间的中点 mid;
  2. 若 a[mid] == key,查找成功;
  3. 若 a[mid] < key,去右半区间;否则去左半区间。区间为空则失败。

10.3.3 为什么是 O(log n)

每比较一次,候选区间大约减半。 从 n 个元素开始,最多折半 ⌈log2 n⌉ 次就会缩到 1 个; 所以比较次数是对数级。

10.3.4 折半查找的局限

10.4 插值查找

10.4.1 按比例取中点

在区间两端值不同、数据近似均匀时,可以按 key 在值域中的比例取 mid,而不是固定取中点:

mid = low + (key − a[low]) / (a[high] − a[low]) × (high − low)

均匀分布时平均很快(约 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,表示平均每个桶里装了多少个元素。

α = n / m   n = 元素个数,m = 桶的个数

例如 m = 11 个桶、n = 7 个元素,则 α = 7/11 ≈ 0.64,平均每桶约 0.64 个元素; 若 n = 22,则 α = 2,平均每桶挂 2 个元素。 链地址法允许 α > 1,因为一个桶可以挂多个结点。

在“哈希函数把元素均匀撒开”的前提下,链地址法的平均查找代价是 Θ(1 + α):先花 O(1) 算地址, 再在长度约为 α 的链上查找。因此:

所以更准确的说法是:在哈希均匀且 α 有固定上界时,链地址法的期望查找代价是 O(1 + α) = O(1)。 不能简单说“α 在常数附近就一定 O(1)”,还要看哈希是否均匀、这个常数有多大。

10.6 查找方法总览

方法前提成功 ASL插入 / 删除适用场景
顺序查找无(n+1)/2容易小表、无序、链表
折半查找有序 + 顺序存储约 log2 n要搬移静态表、查多改少
插值查找有序 + 数据均匀均匀时很快要搬移近似均匀的有序表
哈希表好的哈希函数期望 O(1)容易频繁查找、插入、删除

一句话选型:小表随便扫;静态有序表用折半;数据均匀可试插值; 追求平均常数时间就用哈希。