很多人在学数据结构的时候，会把"查找"这一章当成一堆零散算法的集合：顺序查找、折半查找、哈希、二叉排序树……背完ASL公式就扔到一边。但我在实际做开发之后回头看，这一章恰恰是全书最容易和工程经验挂钩的地方——你写的每一条SQL、每一次Map.get()、每一个索引设计，本质上都在做查找。这篇文章我想把第7章的脉络重新捋一遍，不只是讲"怎么做题"，也想讲清楚"这些算法为什么这么设计""真实项目里应该怎么选"，最后还会补上一些教材不写、但你在代码里迟早会踩的坑。

1. 先从根上理解：查找考的不是"找"，是"数据怎么组织"

1.1 最小模型：关键字、记录与"命中"

任何查找问题都可以抽成一个非常朴素的三件套：一堆数据、一条目标记录、一个用来判断"是不是它"的关键字。数据怎么摆、关键字怎么比，决定了查找是快还是慢。

举个例子，你现在有一张两万行的用户表，想查出某个用户名对应的注册时间。最直观的办法是从头到尾逐条比对，运气好第一条就命中，运气差要扫完两万条。当数据量涨到两千万条时，这个"挨个找"的方案就要扫几千万次，响应时间立刻变得不可接受。此时你是去优化"比较次数"还是去换一种数据组织方式？答案是后者，这才是查找章节真正要教的东西：同样的数据，换一种存放方式，查找的性能可以差出几个数量级。

只有把"查找"抽象成这样一个模型，你才能继续往下谈平均查找长度、谈不同结构之间的优劣。没有这个抽象，后面所有复杂算法的动机都不成立。

1.2 平均查找长度是照妖镜

衡量查找算法最核心的指标叫平均查找长度（ASL，Average Search Length），定义为查找过程中关键字比较次数的期望值，分为"查找成功"和"查找失败"两种。考试要你算ASL，工程上你要估算接口耗时，本质上用的是同一套方法。

举个例子，顺序查找在等概率的情况下，成功查找的平均比较次数是 (n+1)/2。这个公式怎么来的？一条一条找，第1条需要1次比较，第2条需要2次，……，第n条需要n次，加起来除以n，正好是(n+1)/2。而失败查找就比较惨烈了，你得完整扫完整个表才能确认不存在，所以要比较n+1次。

很多人在算ASL时会把"成功"和"失败"混在一起，这是做这章题目最冤枉的丢分点：成功ASL和失败ASL针对的是两种不同的查找过程，分母也不一定一样。成功ASL的分母是表中实际存在的记录数，失败ASL的分母是"可能失败的位置数"，这个概念在后面哈希表部分尤其重要。

1.3 三种基本存储形态决定了三类查找策略

数据在物理上怎么组织，直接决定了你能用哪种查找方法。大致可以分成三条路线：

• 顺序表：数据连续存放在内存里，支持随机访问。正因为能O(1)地跳到任意下标，折半查找这种需要"跳来跳去"的算法才成立。
• 链表：只能顺着指针走。不管你怎么折腾，想找中间元素必须从头遍历，所以链表上谈折半查找基本是无稽之谈。
• 散列/索引结构：数据与存储位置之间建立一个"映射函数"，目标是直接算出位置，一步到位。

后面的内容全部围绕这三条路线展开。每当你看到一道查找题，先别急着套算法，先问自己一句：数据现在是以什么形式存在的？这个前提直接决定答案。

2. 线性结构上的查找：顺序、折半与分块

2.1 顺序查找：不要小看挨个找

顺序查找是所有查找算法里最没有智商的方案，但从工程角度看，它有一个其他算法都比不了的优势：对数据组织没有任何额外要求。数组能找，链表也能找；有序行，无序也行；甚至你只有一张正在源源不断追加数据的日志表，没法建索引、没法排序，那顺序扫描就是唯一选择。

它的成功ASL是(n+1)/2，失败ASL是n+1，时间复杂度O(n)。表面上看，这是一个"慢"的算法，但"慢"不等于"没用"。很多分布式的日志检索、数据仓库的全表扫描，底层就是顺序查找的思路——因为没法对全量数据提前维护索引，只能靠并行扫描一堆数据分片来把时间压下来。所以不要带着鄙视链看顺序查找，它是兜底方案，是所有"更优方案"的比较基准。

在实际写代码时，顺序查找还有一个容易忽略的优化：把目标关键字当作"哨兵"放在表的末尾，这样每次循环都不需要额外判断"下标是否越界"，比较次数没变，但分支减少了，数据量大时也能省下不少时间。这种小技巧在算法竞赛和底层库实现里很常见，是典型"不求复杂度变好、只求常数变小"的思路。

2.2 折半查找：O(log n)的前提条件与边界魔鬼

折半查找（也叫二分查找）是线性结构查找里最重要的一个算法。它有一个硬性前提：数据必须存储在顺序表上，并且按关键字有序。存储前提前面说过，支持随机访问才能跳。有序前提则是二分策略正确性的根基。

它的核心思想是每次把查找区间切成两半，用中间位置的关键字和目标比，小了去左半边，大了去右半边。理想情况下，每次排除一半的数据，复杂度O(log n)，n=100万时最多比较20次，比顺序查找的50万次平均比较有数量级的优势。

把查找过程画成二叉树，你会看到一棵判定树，树的高度就是最大比较次数。比如7个有序元素的判定树，第一层1个结点，第二层2个，第三层4个，树高3层，成功ASL=(1×1+2×2+4×3)/7=17/7≈2.43。这个值和log2(8)-1=2非常接近，说明二分查找确实把"比较次数"压到了对数级别。

但二分查找的代码非常容易写错，我见过太多人在边界条件上翻车。这里必须说几个关键点：

• 循环条件用low <= high，退出时low和high的交叉位置就是目标应该插入的位置；
• 计算中间点要用low + (high - low) / 2，不要用(low + high) / 2，因为两个大整数相加可能溢出；
• 每次移动边界时，low = mid + 1或high = mid - 1，而不是low = mid，否则会出现死循环。

我个人的习惯是先写出判定树，在心里过一遍mid取到哪里、数组下标是否越界，再写循环。这个习惯帮我挡掉过很多次线上事故。

2.3 分块查找：静态数据里的折中方案

分块查找（索引顺序查找）是顺序查找和折半查找之间的一个折中方案：把数据分成若干块，块与块之间按最大值有序，块内可以完全无序。另外维护一个索引表，记录每块的最大关键字和块的起始位置。

查找过程分两步：先在索引表里定位目标可能存在的块，这一步可以用顺序查找，也可以对索引表做二分；再在块内做顺序查找。比如n=9，分成3块每块3个元素，索引表用顺序查找时，成功ASL=(3+1)/2+(3+1)/2=4；如果索引表用二分查找，块间部分会降到约1.6，整体ASL约3.6。

分块查找最大的价值在于它引入了"索引"的概念：建立一个规模较小的索引结构，先查索引缩小范围，再深入数据本身。数据库的聚簇索引、文件系统的多级目录，玩的都是这个思路。理解分块查找，你就理解了为什么"加一层索引"能解决很多性能问题。它牺牲了额外的索引存储空间，换来比全表扫描低得多的查找成本。

3. 哈希查找：空间换时间的极致，也是选择题的重灾区

3.1 散列函数：均匀、快速、少冲突

哈希（散列）查找的核心思想是算，不是找：通过一个散列函数，把关键字直接映射成存储地址。理想情况下，你要查的元素存在哪个位置，一算便知，时间复杂度接近O(1)。

散列函数常见的设计方法有直接定址法、除留余数法、数字分析法、平方取中法等。考试里出现频率最高的是除留余数法：H(key) = key % p，其中p是一个不大于哈希表长m的质数（或素数）。为什么强调p要选质数？假设表长是10，关键字全是10的倍数，那无论除几，结果都挤在0上，冲突会非常严重。选质数就是为了尽量避免这种由于关键字分布规律带来的"成族冲突"。

一个合格的散列函数要满足三件事：均匀（各位置被映射到的概率尽量一致）、快速（函数计算本身不能太复杂）、少冲突（不同关键字尽量映射到不同位置）。但"少冲突"是理想，实际中冲突不可能完全避免，所以下一节的内容就来了。

3.2 处理冲突：线性探测、平方探测与链地址法的取舍

当两个关键字算出同一个地址时，就需要处理冲突。教材里给的方法主要分两类：

开放定址法的思路是：冲突了？那就往下一个空闲位置放。具体又分线性探测法、平方探测法（二次探测法）和伪随机探测法。

• 线性探测：冲突后依次探测下一个位置(H(key)+i) % m，i=1,2,3,...。问题非常明显——容易产生聚集现象，一旦某一段被占满，后续的关键字会像排队一样挤在一起，查找失败的代价大幅上升。
• 平方探测：探测序列变成(H(key) + i^2) % m，能有效缓解线性探测的聚集问题，但有个前提，表长必须取适合的质数，否则可能探测不全所有位置。

链地址法则简单粗暴：每个哈希表位置不存数据，而是存一条链表的头指针，冲突的元素链在后面。查找时要沿着链表往后扫，但每个链子通常都很短，所以整体仍然很快。工程上最常用的是链地址法的变体——每个桶放一个链表，链表过长时再升级为树结构，这是很多哈希表实现处理"极端冲突"的办法。

链地址法还有一个好处：删除元素特别方便，直接把结点从链表里摘掉就行。而开放定址法删除时要小心，不能直接置空，否则会把后面探测路径中断掉，通常得打一个"已删除"标记。这一点我在纸上推演时觉得无所谓，写代码才发现非常烦人。

3.3 装填因子α才是哈希的"命门"

开始讲哈希表时，很多人误以为"冲突处理方式决定了性能上限"，其实真正决定哈希查找性能的是一个看似不起眼的参数：装填因子 α = 表中记录数 / 表长。

为什么说它是命门？因为哈希表的ASL并不直接依赖记录数n，而是依赖α。α越大，表越满，冲突概率越高，查找代价上升；α越小，表越空，冲突少，但空间浪费严重。教材给过线性探测法成功查找的近似ASL：1/2 * (1 + 1/(1-α))，链地址法成功查找的近似ASL：1 + α/2。你把这个近似公式带进去算一下就会发现，同样是链地址法，α从0.5涨到0.9，ASL从1.25涨到1.45，其实还能接受；但线性探测在α接近0.9时已经明显恶化了。

所以工程上的哈希表基本都会做一件事：扩容。当α超过某个阈值（常见的是0.75），就把表扩大一倍，把所有元素重新散列一遍。很多人对扩容有疑虑："扩容要重新插入所有元素，那不是O(n)吗？"没错，但均摊到每次插入上，代价仍然很低。这是理解哈希表工程实现的关键。

3.4 一个典型题目的完整ASL计算

光说公式容易虚，我们算一道比较典型的题目。设关键字序列为{19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，表长m=13，散列函数H(key)=key%13，用线性探测法处理冲突，计算查找成功时的ASL。

先把每个关键字的散列地址算出来，然后逐个插入：

• 19%13=6，无冲突，比较1次；
• 14%13=1，无冲突，比较1次；
• 23%13=10，无冲突，比较1次；
• 1%13=1，冲突，线性探测到2，比较2次；
• 68%13=3，无冲突，比较1次；
• 20%13=7，无冲突，比较1次；
• 84%13=6，冲突，探测到7（被20占）、8，比较3次；
• 27%13=1，依次探测2、3、4，比较4次；
• 55%13=3，依次探测4、5，比较3次；
• 11%13=11，无冲突，比较1次；
• 10%13=10，冲突，探测11（被11占）、12，比较3次；
• 79%13=1，依次探测2到9，比较9次。

成功找完所有12个关键字的总比较次数是 1+1+1+2+1+1+3+4+3+1+3+9=30，成功ASL=30/12=2.5。你可以对比一下，如果数据能均匀散列，每个关键字都在自己的初始地址上，ASL就是1；因为冲突，平均代价到了2.5。这个例子同时演示了两个关键意识：先算初始地址、再模拟探测过程；每个关键字的比较次数是从"它的初始位置"出发到"实际落位"所经历的探测步数。

4. 树形查找：让动态数据集保持"有序且平衡"

4.1 二叉排序树：插入、查找、删除全流程

二叉排序树（BST）的核心定义很简单：左子树所有结点的关键字小于根结点，右子树所有结点的关键字大于根结点，且左右子树也分别是二叉排序树。这个结构有个特性——中序遍历得到一个升序序列，所以它本质上是一个"动态维护有序集"的工具。

插入操作不复杂：从根开始，比当前结点小就往左走，大就往右走，走到空位就挂上新结点。查找同理。真正麻烦的是删除，分三种情况：

• 删除叶子结点：直接摘掉，不影响树结构；
• 删除只有一个孩子的结点：让孩子顶替自己的位置；
• 删除有两个孩子的结点：这是最关键的场景，通常用它的直接前驱或直接后继来替换它。直接后继就是右子树中最小的结点，也就是右子树一路向左走到最底部的那个节点；直接前驱是左子树中最大的结点，即左子树一路向右走到最底部的节点。

为什么必须用前驱/后继替换？因为只有这样才能保持"左小右大"的性质不被破坏。稍微练过一道题就会发现，很多人在这一步忘记"替换后要递归处理前驱/后继的删除"，导致树中出现重复结点或者丢失子树。

BST的致命弱点是它可能长歪。如果按有序序列依次插入，BST会退化成一条链表，查找复杂度从O(log n)恶化到O(n)。这也是AVL树、红黑树这些平衡结构存在的根本原因。

4.2 AVL平衡调整：LL、RR、LR、RL的识别和旋转

AVL树给BST加了一个平衡条件：任意结点的左、右子树高度差绝对值不超过1，这个高度差称为平衡因子。一旦某次插入后打破了平衡，就需要通过旋转来恢复。

四种失衡情况必须熟练掌握，只看名字也能猜个大概：

• LL型：插到了某个失衡结点的左孩子的左子树。解决办法是右旋一次，把左孩子提上来当根。
• RR型：插到了右孩子的右子树。解决办法是左旋一次。
• LR型：插到了左孩子的右子树。先对左孩子做一次左旋，把它变成LL型，再对失衡结点做一次右旋。
• RL型：插到了右孩子的左子树。先对右孩子做一次右旋，再对失衡结点做一次左旋。

每次旋转后，要重新计算涉及的几个结点的平衡因子。这里我说一个容易让人晕的地方：旋转操作只改变局部位置，不会破坏BST的"左小右大"性质。因为旋转的本质是把孩子提上来、自己退下去，所有子树的相对大小关系不变。做题时如果你觉得旋转后顺序乱了，多半是把"谁左谁右"搞混了，可以拿三个结点画一张小图验证。

含n个结点的AVL树，最大深度约1.44log2(n+2)（近似公式）。这意味着AVL的查找复杂度能稳定保证在O(log n)。但代价是插入和删除时可能需要多次旋转，所以AVL一般用于"查找频率远高于插入删除"的场景。而红黑树放宽了平衡限制，插入删除代价更低，因此被大量用在通用容器的底层实现里。

4.3 从内存到磁盘：为什么大场面需要B树和B+树

AVL和BST解决的是内存场景的问题，但数据量一旦大到要放磁盘，问题就变了。磁盘访问一次的时间大概是内存访问的几十万倍，所以你必须把"比较次数"换成"磁盘访问次数"来优化。B树和B+树就是为这个场景设计的多路平衡查找树。

先看B树的几个硬性规定（设阶数为m）：

• 每个结点最多有m棵子树、m-1个关键字；
• 根结点至少有两棵子树；
• 除根以外，所有非叶结点的子树个数至少是⌈m/2⌉，意思是每个结点最少半满；
• 所有叶子结点在同一层，保证树高绝对平衡。

因为一个结点能装很多关键字，B树的树高远低于BST。假设一个磁盘页能存几百个关键字，几百万条数据可能只要三四层的树就能索引完，每次查找只读几次磁盘，这是BST做不到的。

B+树在B树基础上做了两处关键改动：内部结点不保存记录数据，只做索引；所有关键字和数据都落在叶子结点上，并且叶子结点用指针链成有序链表。这两个改动带来三个好处：

• 内部结点能存更多关键字，进一步降低树高；
• 范围查询非常自然——从最小关键字顺着叶子链表往后扫即可，不需要反复回溯到上层；
• 所有查找都必须走到叶子结点，每次查找的路径长度稳定，更利于预测IO开销。

所以在真实的数据库索引、文件系统索引里，B+树几乎是标配。你说它是"查找章节的尽头"也不为过：从线性表到哈希，再到平衡树、B+树，这条线就是"如何在大规模数据上快速定位"这个问题的完整答案链。

5. 实际项目中的查找选型：复杂度之外的教训

5.1 不同场景的算法选型速查

学了这么多算法，落到实际项目里该怎么选？我先给一张我常用的速查表，它比任何概念都直接：

注意，这张表有一列很容易被人忽略：空间成本。哈希需要额外的桶和可能的内存浪费；B+树需要大量索引结点；折半查找则完全不需要额外内存。如果你的数据量小到可以在内存里全量装下，但内存又很紧张，那一个有序数组加二分查找，往往比你去搞一棵树和一个哈希表更划算。

5.2 工程实现里那些教材没写的细节

教材教算法，但工程里写代码会遇到很多教材不会提的细枝末节。我挑几个印象最深的：

第一个是哈希函数的"输入类型"问题。很多教材只讨论整数关键字，但真实项目里关键字经常是字符串、复合对象。你会遇到一个很现实的问题：直接把字符串的hashCode拿来用，分布很可能不理想。这时候要给散列函数补一些位运算，把高位信息混到低位里，否则哈希表的很多桶可能是空的，而另一些桶挤成一堆，装填因子明明不高，性能却已经烂了。

第二个是二分查找的适用场景比想象中窄。工程上索引结构大多是B+树或者哈希表，很少有人手动搞二分查找，因为维护一个动态有序数组的代价太高。但反过来，在"一次性加载全部配置、运行期只读"这种场景里，有序数组加二分查找的性能不但优秀，而且内存效率极高。我见过某个配置服务就是这么干的，启动时加载几千条配置，排序一次，之后每次查找都是log级别的耗时，比拍脑袋上一套缓存简单多了。

第三个是扩容和抖动问题。哈希表扩容在并发场景下特别容易出问题——扩容过程中所有线程都尝试rehash，如果没处理好，轻则性能剧烈波动，重则数据错乱。这也是为什么真实系统里哈希表要么做分段、要么在扩容时加锁。这类工程细节教材不会考，但做线上系统一定会遇到。

5.3 高流量场景下哈希表劣化的真实经历

最后讲一个我印象很深的排查经历。某次接手一个内部查询服务，接口平时响应都是个位数毫秒，某天突然有人反馈某些key的查询要几百毫秒甚至超时。

一开始我以为是数据量涨了导致机器扛不住，看了监控发现CPU不高、内存也充足，非常诡异。后来把调用链打成火焰图，才发现热点全在哈希表里——不是哈希表本身慢了，而是某个类别下的key数量特别大，且它们的散列结果高度集中在少数的桶里。当桶里的链表变得很长，查找从O(1)退化成了O(n)。那时候才意识到，教科书里讲的"冲突极端情况"不是理论，是真实会在生产环境出现的。

后续的修复方案也不难：换一个分布更均匀的散列函数，同时给底层哈希表加上"桶内元素超过阈值时自动转为树结构"的机制。修复之后，那些极端key的查询时间立刻降了下来。这件事给我的教训是：学查找算法时，公式要背，但更重要的是建立起"数据结构决定性能上限"的敏感度。当系统出现莫名性能问题时，最先怀疑的往往不是机器，而是数据组织方式。

回头再看第7章，你会发现这一章的每一节都不是孤立的。顺序查找是最朴素的基线，分块查找引入了索引思想，哈希利用散列函数把定位变成计算，BST和AVL让动态数据保持有序，B+树把这一切扩展到海量数据和磁盘场景。每套方案都有自己的适用边界，没有银弹。能把"选型时知道自己在为什么买单"这层功夫练出来，这一章才算真正学会了。