第7章查找这一章我每次讲算法课都会多停留十分钟。原因很简单代码量不大但思维的跳跃非常大。你上一秒还在学怎么在数组里暴力找一个数下一秒就要理解为什么一棵树能支撑起整个数据库的索引体系。很多人捧着教材读完觉得无非就是几种查找算法结果自己动手写二分查找时调了半小时死循环或者发现自己的哈希表越用越慢才知道这一章的真正分量。我打算把这一章完整拆开聊透查找到底在解决什么问题每种算法背后的代价是什么实际编码时教科书不会细讲的坑有哪些。如果你正在学数据结构、准备算法面试或者工作中需要设计数据检索方案这篇内容应该能给你一些参考。1. 先看整体查找算法到底在解决什么问题1.1 查找的本质是“快”不是“找得到”查找的定义可以写成给定一个包含n条记录的集合每条记录都有一个关键字根据给定的关键字找到匹配的记录或者返回不存在。这个定义看起来简单但核心不是“找得到”——遍历总能做到核心是“找得快”。数据规模很小的时候顺序查一遍也行数据量到百万、千万级快和慢的差距就是毫秒与秒级的差别。我习惯用书架上找一本书来类比。书架上的书没有整理过你只能一本一本翻这是顺序查找如果书按拼音排好序你可以先翻到中间比较一下书名再决定往前还是往后这是二分查找如果你给每本书编一个唯一编号把编号直接对应到一个具体的位置那就是哈希查找。三种方式对应不同的时间和空间准备没有绝对的好坏只有是否适合当前场景。教材里这一章通常会引入一个关键指标平均查找长度简称ASL。它衡量的是多次查找中平均要比较多少次。不要小看这个指标它决定了你选哪种算法。顺序查找的ASL是(n1)/2二分查找是log2(n1)-1哈希查找理想情况下是O(1)。但ASL只是理论值实际还要看数据分布、哈希冲突、额外空间和插入删除的代价。你得把这些放到一起权衡而不是看到一个O(1)就觉得哈希表天下无敌。1.2 三类查找算法对应三种数据形态顺着数据形态去理解查找算法可以分成三类静态查找、动态查找和哈希查找。静态查找针对“基本不变的数据集”数据在初始化后很少增删主要操作是查询典型代表是顺序查找、二分查找、分块查找。动态查找面对频繁插入、删除和查找的场景典型代表是二叉搜索树、平衡树、B树。哈希查找走的是另一条路不比较关键字本身而是通过哈希函数把关键字映射到存储位置让查找复杂度直接变成O(1)。这个分类能帮你快速做技术选型。比如你写一个小工具只需要在启动时加载一份固定的配置那用二分查找就足够了没必要引入复杂的树结构。如果你的业务是一个频繁增删的在线系统静态查找方案就不合适你得考虑动态查找或哈希表。教材把查找放在树之后、图之前也是有讲究的二叉搜索树本质上是把查找过程组织成树形结构而B树又为后面的文件存储和数据库打下基础。这一章就像一座桥把前面的线性结构、树结构串联起来也为后面的大型数据管理埋下伏笔。2. 三个基础算法顺序、二分、分块用到什么程度才算会2.1 顺序查找最简单反而容易被误用顺序查找的逻辑不用多讲从第一个元素遍历到最后一个相等就返回下标到头没有就返回不存在。时间复杂度是O(n)空间复杂度是O(1)。适用场景很明确数据量小、数据无序、存储结构是链表这类不支持随机访问的结构。我在实际工作中其实经常用到它比如从一组日志里找某个特定错误码日志量就几百条杀鸡不用牛刀。但顺序查找有几个容易忽略的细节。第一个是查找概率不均的时候可以把高概率的元素往前放这样可以明显降低平均查找长度。第二个是循环内判断条件的优化传统写法每次循环都要判断“是否越界”和“是否相等”两个条件如果用一个哨兵放在数组末尾就能省掉一半的越界判断。教科书上把这个叫哨兵顺序查找实现起来就是在数组最后预留一个位置把要查的关键字放进去循环里只判相等等找到再判断是不是那个预留位置。这种方法在现代编译器优化下收益没有早年那么明显但它体现了一个很重要的编程思想用冗余的哨兵来减少判断分支。这里也提醒一句在 Python 里写顺序查找时别傻傻地用 while 循环加下标直接用 enumerate 不仅可读性好性能也不差。但如果你真的在意性能又不能用内置函数可以试试哨兵技巧。不过大多数时候Python 内置的 in 操作符和 list.index() 底层都是 C 实现比自己写循环快得多。开发时优先用现成的高性能实现这是工程直觉不是偷懒。2.2 二分查找思路三分钟写对三小时二分查找看起来简单有序数组取中间值比较决定往左还是往右。但很多人第一次写都会死循环或者漏掉边界。根子在两个选择区间定义是左闭右闭还是左闭右开循环条件是 left right 还是 left right。这两个选择必须互相匹配一旦混用就会出问题。我自己的习惯是始终坚持左闭右开区间[left, right)初始条件 left0、rightlen(arr)循环条件 while left right查找区间不断收缩到空集时结束。用这个习惯写标准二分查找逻辑是这样def binary_search(arr, target): left, right 0, len(arr) while left right: mid left (right - left) // 2 if arr[mid] target: left mid 1 else: right mid return left if left len(arr) and arr[left] target else -1这里关键点在于当 arr[mid] target 时right 直接等于 mid而不是 mid - 1。因为左闭右开区间里right 处的元素本来就不在考虑范围内。mid 的计算用 left (right - left) // 2避免写成 (left right) // 2 导致整数溢出这在 C 和 Java 里不是玩笑。上面这个写法返回的是“第一个大于等于 target 的位置”所以最后要检查 left 是否越界且 arr[left] 是否等于 target。很多人背模板背不熟就是没有理解区间定义和返回条件之间的关系。二分查找的变体在面试里更常考第一个等于目标的元素、最后一个小于目标的元素、插入位置等等。我总结一个通用套路先确定你要找的是“范围内满足某个条件的最小/最大位置”再把这个条件写成一个布尔函数然后用二分去逼近。比如“第一个等于目标的下标”我们找的是满足 arr[mid] target 的最小位置最后判断 arr[left] 是否等于 target。这样把二分抽象成“在单调布尔序列上找第一个 True”比每一种变体都重新背模板要可靠得多。2.3 分块查找索引思想的起点分块查找是静态查找里容易被一笔带过但又非常有启发的算法。做法是把长度为 n 的表分成若干块块之间有序块内可以无序。查找时分两步先在索引表里用二分或顺序确定目标可能所在块再在块内进行顺序查找。复杂度介于顺序和二分之间假设块数为 b块内平均长度是 n/b查找长度大约是 log2(b1) (n/b)/2 1。虽然实际工程中你很少直接用它但它是一种非常朴素的“索引”思想后来数据库里的聚簇索引、非聚簇索引本质上都是“先查索引定位范围再查实际数据”。我第一次接触到分块查找时觉得有点鸡肋后来做一个报表系统数据由上游定时生成落库后只读但又不想引入完整的数据库索引。于是我在内存里按天分块块内按时间乱序块间按日期排序。查找某一天的数据时先二分定位到当天的块再在块里顺序找。虽然听着不够高端但效果很好查询速度和内存占用都在预期内。那一次经历让我意识到教材里每一种看似简单的算法背后都对应着某一类真实场景。不要觉得简单就没用要看它解决的是哪一类约束下的问题。3. 哈希查找想要O(1)可以但你要先接受几个代价3.1 哈希函数与哈希表的工作原理哈希查找的思路彻底转变不再比较关键字而是把关键字通过哈希函数计算得到一个整数值再用这个值模上表的容量得到的下标就是记录存储的位置。查找时用同样的哈希函数再算一次直接定位。理想情况下单次查找的时间复杂度是 O(1)这也是哈希表在现代编程语言里成为最常用数据结构之一的原因。哈希函数的选择很关键。最朴素的是取模hash(key) % capacity。这个方法的前提是 key 散列得足够均匀。对整数来说取模通常没什么问题对字符串来说简单把所有字符 ASCII 码相加取模很容易产生大量冲突比如 abc 和 bac 的 ASCII 码和是一样的。更通用的做法是用乘法哈希或者用语言标准库内置的哈希算法。比如 Python 的 hash() 函数和字典处理字符串时用的算法考虑了字节序列的各种特征就是为了让相近但不同的字符串尽量散列到不同位置。我在做模拟项目X时最开始图省事自己写了一个字符串哈希把字符串每个字符的码值乘以一个固定系数再累加然后取模。当时数据量小没什么感觉等数据量涨到几十万条某几个前缀相似的 ID 全部撞到了一起查找从 O(1) 退化成了 O(n)。后来我改成标准库的做法配合不同系数冲突率立刻降了下来。这件事给我的教训是日常业务开发里不要自己发明哈希函数优先用语言生态里被验证过的实现。学习时手搓一遍是无妨的但上线前一定要评估它的分布质量。3.2 冲突处理的两条路线拉链法与开放定址法哈希冲突无法避免只能缓解。处理冲突有两条主流路线拉链法和开放定址法。拉链法把哈希表每个槽位变成一条链表的头结点冲突的元素全部挂在同一个槽位下。查找时先定位槽位再在链表中顺序查找。这个方案简单直观负载因子元素个数 / 桶数可以超过 1缺点是大量冲突后链表会变长查找退化所以很多实现会在链表长度超过阈值时把链表转成树结构。Python 的字典在某些实现里采用开放寻址策略但拉链法仍是理解哈希表冲突的最佳入口。开放定址法不额外拉链冲突发生后按某种探测序列在表里继续找空位。线性探测最简单冲突了就往后一个一个找二次探测可以缓解“堆积”问题双重探测则用两个哈希函数决定步长。开放定址法的表不能太满负载因子一般控制在 0.7 以下否则查找性能会急剧下降删除时也不能直接删掉元素而要用“墓碑”标记否则会破坏探测链。它的优势是局部性好不需要链表节点内存紧凑。两种方法用表格对比一下对比项拉链法开放定址法实现难度较低较高尤其删除逻辑空间利用率允许超过1一般控制在0.7以下缓存友好度较差链表节点离散较好所有数据在数组中删除操作直接摘链需要墓碑标记适用场景通用哈希表内存受限、数据量可预估3.3 哈希查找实战中的几个隐藏坑先说说负载因子。哈希表的平均查找长度和负载因子强相关负载因子太高冲突变多性能下降太低空间浪费。工程上通常在负载因子超过 0.75 时扩容把桶数翻倍然后重新哈希所有已有元素。这个扩容是 O(n) 操作如果你能提前预估数据量最好直接给一个够大的初始容量避免频繁扩容。接着说删除。用开放定址法时删除一个元素如果直接把槽位清空会导致后续依赖该槽位探测的元素再也找不到。正确做法是把这个槽位标记为“已删除”的墓碑查询时遇到墓碑继续往后找插入时遇到墓碑可以复用。但如果墓碑太多又会拉长探测链这种时候最好做一次 rehash把表重新整理一遍。最后是键对象的可变性问题。如果你把一个对象当成哈希表的 key那这个对象的哈希值在存进去之后绝对不能变。否则查找时按新哈希值去定位会找不到这个对象而它在表里还占着一个位置。在 Java 里直接修改作为 key 的对象的字段就可能踩中这个坑在 Python 里如果自己定义了 class 并重写了hash和eq也必须保证这两个方法依赖的字段在对象生命周期内不可变。这个坑非常隐蔽一旦出现排查起来特别费劲。4. 动态查找从二叉搜索树到B树的演进逻辑4.1 二叉搜索树的构建与查找动态查找意味着数据会不断变化我们不能再寄希望于静态排序数组。二叉搜索树的定义很简单左子树的所有节点小于根节点右子树的所有节点大于根节点左右子树本身也是二叉搜索树。查找时从根节点开始目标比当前节点小就往左走比当前节点大就往右走直到找到或者走到空节点。用二叉树做查找的好处是插入和删除同样灵活。插入时按相同的比较路径走到一个空位把新节点挂上去删除稍微复杂要分三种情况叶子节点直接删只有一个孩子就用孩子顶上来有两个孩子则通常用中序后继节点顶替。这个算法写起来不难但我建议动手实现一次尤其是删除逻辑很多人在考试和面试里都会栽在这里。二叉搜索树的时间复杂度分析是这一章的重点。理想情况下树的高度是 log2(n)查找、插入、删除都是 O(log n)。但最坏情况下如果数据已经有序插入顺序恰好让它形成一条单链树的高度变成 n所有操作退化成 O(n)。也就是说二叉搜索树的复杂度并不稳定瓶颈在于树是否平衡。这也直接引出了平衡树的需求。4.2 平衡树的核心思想AVL与红黑树平衡树的作用是让树的高度尽量维持在 log n 级别。AVL 树是第一种被提出的平衡树它的定义是每个节点的左右子树高度差绝对值不超过 1这个差值叫平衡因子。插入或删除后如果某节点的平衡因子变成 -2 或 2就需要通过旋转来修复旋转分为左旋、右旋、左右双旋、右左双旋四种情况。AVL 树平衡性很严格所以查找性能非常稳定但代价是插入删除时可能需要多次旋转写起来也比较复杂。红黑树则牺牲了一部分严格平衡性来换取更低的调整代价。它用颜色标记节点通过一系列约束来保证任意路径的长度差不会超过两倍。换句话说它不追求完全平衡但保证树的高度依然是 O(log n)。红黑树的插入删除调整逻辑确实复杂我当年学的时候背了很多遍旋转和变色规则最后才发现最有效的记忆方式是画图把每一步的树形态画几遍比死记代码要牢固得多。实际工程里大部分语言标准库的有序映射和有序集合底层用的都是红黑树或者类似结构。我在学习这部分时并没有自己去实现一棵红黑树重点是理解它为什么存在、它和 AVL 树的取舍以及查找操作在平衡树里如何保证对数复杂度。如果你不是做底层基础设施开发不需要手写红黑树但你必须能在谈到查找这个话题时清楚地说出平衡树解决了什么、代价是什么。4.3 B树与B树面向磁盘的查找结构二叉搜索树和平衡树再好也有一个隐含前提所有操作在内存中完成。一旦数据量大到内存放不下必须把部分数据放在磁盘上情况就变了。磁盘的随机访问比内存慢好几个数量级减少访问次数成了第一目标。B 树正是为此设计的它不再是一个二叉树而是一个多叉树每个节点可以存储多个键值和多个孩子指针树的高度大幅降低。以一棵度为 100 的 B 树为例存储 100 万条数据树的高度可能只有 3 层甚至 2 层几次磁盘 I/O 就能完成查找。B 树是 B 树的变体它把真正的数据只放在叶子节点内部节点只存搜索键叶子节点之间通过指针串成链表。这样有两个好处内部节点能容纳更多键树更矮支持范围查询时找到起始叶子后顺着链表遍历即可效率非常高。数据库索引和文件系统索引普遍采用 B 树原因就在这里。我在第一次接触 B 树时很困惑为什么这么重要的结构数据结构教材里往往只是简单提一句。后来想明白了B 树虽然属于查找的内容但它已经贴近操作系统和数据库的领域需要结合磁盘页、缓存、页分裂等概念才能讲透。对初学者来说先理解“多叉树通过减少树高来减少磁盘 I/O”这个核心逻辑就够了具体实现细节可以在用到时再深入研究。5. 一个通讯录模块搞定查找算法的选型和实现5.1 一个真实场景的选型过程为了把前面这些算法串起来我设计一个模拟项目X某跨平台系统的通讯录模块需要支持按姓名查找联系人联系人数从几百人增长到几十万人同时支持频繁的增删改。需求看起来不复杂但选型时还是能看出门道。如果直接用一个有序数组加二分查找查找快但每插一条记录都要移动后面的元素插入成本太高显然不行。用二叉搜索树插入是方便了但万一联系人的插入顺序不巧树退化成链表查找性能就崩了。用平衡树各方面都行但实现成本高而且需要自己处理并发。用哈希表按姓名查找非常快插入删除也接近 O(1)但不支持范围查找和排序。综合来看常规做法是以姓名为 key用哈希表提供当项查询同时如果需要按姓氏前缀展示列表可以再加一个有序索引结构来配合。最终我选择了内置哈希表作为主索引复杂度可控代码也简洁。5.2 手写一个拉链法哈希表并实现查找为了讲清楚细节我手写一个简化版拉链法哈希表语言用 Python只保留核心功能。代码结构很简单底层是一个数组数组每个元素是一个链表头。插入时计算哈希值定位桶然后在链表中追加查找时定位桶遍历链表比较 key删除时遍历链表摘除节点。示例class LinkedHashTable: def __init__(self, capacity16): self.capacity capacity self.size 0 self.table [[] for _ in range(capacity)] def _hash(self, key): return abs(hash(key)) % self.capacity def set(self, key, value): index self._hash(key) bucket self.table[index] for i, (k, v) in enumerate(bucket): if k key: bucket[i] (key, value) return bucket.append((key, value)) self.size 1 if self.size / self.capacity 0.75: self._resize() def get(self, key): index self._hash(key) for k, v in self.table[index]: if k key: return v raise KeyError(key) def delete(self, key): index self._hash(key) bucket self.table[index] for i, (k, v) in enumerate(bucket): if k key: bucket.pop(i) self.size - 1 return raise KeyError(key) def _resize(self): old_table self.table self.capacity * 2 self.table [[] for _ in range(self.capacity)] self.size 0 for bucket in old_table: for k, v in bucket: self.set(k, v)这里用 Python 内置的 hash() 有两个坑一是字符串哈希在同一个进程内是稳定的但不同进程可能随机化如果你确实需要跨进程一致的哈希就不能用它要自己写确定性哈希二是取模时如果哈希值是负数取模结果可能是负数所以最好再取一次绝对值或者用 key 的二进制掩码方式。上面的代码用了 abs() 处理负数虽然 Python 的 % 对负数得到的也是非负余数但显式取绝对值会让意图更清楚。5.3 性能对比与结果分析写完基本功能后我用随机生成的联系人数据做了一组对比顺序查找和这个哈希表查找。数据量从 1000 涨到 10 万顺序查找的平均耗时几乎线性上涨10 万条时一次查找要几百微秒到数毫秒哈希表查找始终稳定在几十纳秒到一两百纳秒级别而且即使在负载因子接近 0.75、部分桶冲突达到十几个时也没有出现数量级退化。这说明哈希表的 O(1) 在工程上的确能兑现前提是哈希函数质量够、扩容策略正常。但我也把代码里故意改成弱哈希函数做了一次对比结果很有意思当所有 key 都容易被映射到同一个桶时插入后链表越来越长10 万条数据下查找性能退化到和顺序查找差不多甚至更差。这就验证了哈希函数的重要性O(1) 是理想情况的复杂度冲突不控制复杂度会退化。所以我在这个模拟项目X里最终没有自己实现哈希而是用语言内置的哈希表结构把精力放在业务逻辑上。如果你要学习手写一遍很有价值如果你要交付请相信成熟的内置实现。6. 常见坑与排查技巧这些我最少遇到三次6.1 查找相关的高频错误与定位方法先说二分查找的经典死循环。最常见的写法是 while left right 时某个分支里 right mid 而不是 right mid - 1导致区间不收缩无限循环。排查时最直接的办法是在循环里打印 left、right、mid 三个变量看看每次区间是否在缩小。如果区间长度不变说明边界更新写错了。哈希表的问题通常表现在“找不到某个元素”“明明存了却 get 不到”。这时候先检查 key 对象是否可变再检查hash和eq是否保持一致。一个容易犯的错误是重写了eq但没有重写hash导致两个逻辑上相等的对象哈希值不同放进哈希表后互相找不到。Python 里如果定义类时重写了eq默认hash会失效这点很多人不知道。二叉树查找的隐蔽错误更多。一个是插入时忘了维护父子指针另一个是删除有两个孩子节点的逻辑混乱。我建议调试时先把树的中序遍历打出来二叉搜索树的中序序列应当严格递增如果某次操作后不递增说明结构坏了。这个方法比单纯看结果输出要快得多毕竟查找操作通常不报错只有结果不对这才是最难处理的。6.2 考试与面试里最喜欢挖的坑二分查找的变形题目是面试高频。比如“在一个有序数组里查找第一个大于等于目标值的下标”很多人会背标准二分模板结果把边界条件写错。记住我前面说的把问题转换成“寻找满足条件的最小位置”的二分框架会稳很多。另一个高频坑是哈希表的负载因子比如“为什么哈希表扩容时通常翻倍而不是加 1”因为要保证取模运算的散列性还要控制重哈希成本翻倍配合素数桶数能让分布更均匀。红黑树在面试里通常不会让你手撕全部插入删除但可能会问它和 AVL 树有什么区别、为什么数据库不用红黑树而用 B 树。回答思路很简单AVL 严格平衡、查询快但调整成本高红黑树放宽平衡条件、调整成本低B 树适合磁盘是因为减少 IO 次数叶子链表支持范围查询。把这些讲清楚比背任何模板都管用。6.3 一份避坑清单写给正在学这一章的人第一不要背代码要背“选择”背后的理由。你只要想明白顺序查找适合无序小数据、二分查找适合有序静态数据、哈希表适合高频等值查询、平衡树适合有序动态数据你遇到问题时自然知道该用哪个自然就能写对。第二初期一定要多画图。二叉树旋转、哈希冲突链、B 树的分裂全靠想象很容易坚持不下去。画图不是为了交作业而是让大脑把抽象的指针关系转化成空间结构这是学习查找算法最划算的投入。第三善用语言内置库。学习阶段自己实现一遍是必要的但工作中优先用内置的字典、映射表、有序集合不要为了显得自己很懂底层就重复造轮子。能用成熟实现解决的问题不要自己制造复杂度。第7章查找我前前后后看了不下三遍每一遍的收获都不一样。第一遍学会了用二分替代遍历第二遍理解了哈希冲突和负载因子的意义第三遍才真正明白查找算法比拼的不是谁的复杂度更低而是谁能在数据的更新频率、访问模式、存储介质这些约束下找到最合适的平衡点。如果你也正在学这一章别急着刷题先把每一种算法放到真实场景里去想想它会怎么失效这样学到的东西才真正值钱。