第 7 章 · 查找

「在数据里找东西」是这个行业每天发生最多次的操作,本章把三种查找策略放在一起比较:顺序查找(老实人,什么都能找)、二分查找(讲究人,要数据先排好)、哈希表(赌徒,用空间赌 O(1))。第 1 章埋的几个伏笔在这里全部兑现:二分是 O(log n) 的标本,哈希表的「摊还 O(1)」和「最坏 O(n)」的赌局要亲手摸一遍装载因子才能体会。

7.1 二分查找:一半一半地丢

顺序查找没什么可讲的(什么都能找,O(n)),二分才是主菜。前提苛刻而明确:有序 + 随机访问(链表跳不到中间,出局)。每次比对,丢掉错误的一半:

int bsearch(const int *a, int n, int k) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // 防溢出写法,别写 (lo+hi)/2
        if (a[mid] == k) return mid;
        else if (a[mid] < k) lo = mid + 1;   // k 在右半
        else hi = mid - 1;                   // k 在左半
    }
    return -1;
}

千万数据 24 次比对封顶。三个工程细节,每个都是真 bug 的产地:mid 用 lo + (hi-lo)/2 防 lo+hi 整型溢出(2005 年起,JDK 的二分实现因为这个 bug 静默运行了近十年才被数学教授发现);边界用 lo <= hi 配 mid±1(保证区间严格收缩不死循环);找到就返回,但很多变体要「第一个 ≥ k 的位置」(lower_bound),那种版本返回的是 lo 而不是 -1,区间开闭约定变了,全套条件跟着变。二分的思想远比代码值钱:答案具有单调性,就能二分——「最小的满足条件的速度」「最大的可行装载量」,把问题参数化后都能二分,这是竞赛和工程里最常用的降维手段之一。

7.2 哈希表:把键变成数组下标

哈希表的想法豪迈:不比较、直接算。用哈希函数把键变成数组下标,查找一步到位:

int h(int key) { return key % M; }        // 除留余数法,M 取素数

M 取素数是为了让规律输入(全是偶数、全是 10 的倍数)尽量散开。数学上冲突不可避免(鸽巢原理:键的空间比桶多,必有两键同桶),全部智慧花在两件事:散得匀(哈希函数)、撞了怎么办(冲突处理)。

7.3 冲突处理:链地址 vs 开放定址

链地址法:每个桶挂一条链表(第 2 章的链表原样复用),撞了的键全挤在一条链上:

typedef struct Node { int key, val; struct Node *next; } Node;
Node *bucket[M];

void put(int key, int val) {
    int i = h(key);
    Node *n = malloc(sizeof *n);
    n->key = key; n->val = val;
    n->next = bucket[i];
    bucket[i] = n;                        // 头插
}

简单、不怕满、删除干净(摘链即可),Java 的 HashMap 长期是这个流派(链长了还会转红黑树,把最坏 O(n) 兜底成 O(log n),第 5 章的伏笔在这里收)。

开放定址法:不用链,撞了就在数组里另找空位(线性探测:挨个往后挪)。省指针、内存连续、缓存友好(第 12 章会讲这多重要),但两个软肋:删除要留「墓碑」(直接置空会截断后续探测链);装载因子(元素数/桶数)超过 0.7 后探测链急剧变长,性能断崖,必须及时扩容再散列(第 1 章摊还分析的应用)。Python 的 dict、Redis 的字典就是这条路线(后者还有渐进式 rehash 的巧思:扩容时新旧两张表并存,每次操作搬一点,把「搬家卡顿」摊平)。

	链地址	开放定址
内存	数组 + 离散节点	一整块数组,连续
删除	摘链,干净	要墓碑标记
装载因子上限	可以大于 1	建议不超过 0.7
缓存友好度	差(链表跳)	好

7.4 赌局结算:什么时候 O(1) 会输

哈希表的平均 O(1) 是赌出来的,输法有三种,每种都值得排进你的排查清单:

键分布规律 + 坏哈希函数:攻击者故意构造全撞一个桶的键(哈希碰撞 DoS,2011 年真实打瘫过多家网站),防御是加随机盐的哈希函数。
装载因子失控:链地址长成千节点链,每次「O(1)」实为 O(n);监控桶均长(或直接用语言库的自动扩容)。
需要有序操作:哈希表天生无序,「按范围取键」「取最大键」要全扫;那时用第 5 章的平衡树或第 9 章将提到的 B+ 树。C++ 的 map(树)与 unordered_map(哈希)就是这两种世界观并列在标准库里。

一张决策表收束:数据只查一次,顺序查找(别折腾);静态有序、查很多次,二分(排序一次 O(n log n),之后每次 O(log n));键值动态增删查,哈希表;既要快查又要有序,平衡树/跳表(第 11 章)。

常见错误

二分写成死循环。区间收缩不严格(lo = mid 这种),区间卡在两格反复横跳。记住配对规则:mid±1 与 lo <= hi 同进退。
哈希函数只对 int 有效就用在字符串上。字符串要逐字节累积(如 djb2:h = h*33 + c),直接 key % M 在指针上做没意义。
开放定址删除不留墓碑。中间一个空位截断探测链,后面的键「消失」(实际还在别的桶里),查找变错,这类 bug 报告往往只是「偶尔找不到」。

练习

实现:lower_bound(返回第一个 ≥ k 的下标,不存在返回 n),用 5 组边界数据(空表、单元素、全小于 k、全大于 k、k 恰在边界)验证你的实现。
手算:桶数 M=7,键 {12, 5, 19, 26, 33, 40}(全 % 7),链地址下每条链长多少?平均查找长度算出来,再改 M=13 重算,体会装载因子。
动手:实现线性探测哈希表,插入 0.7M 个键后连续查找 10 万次计时;再插入到 0.95M 重测,亲测性能悬崖。
思考:数据库第 9 章说索引默认用 B+ 树而不用哈希,列出至少三条理由;再想一个「数据库里确实该用哈希」的场景(提示:等值的内存表)。