很多人在学数据结构的时候会把查找这一章当成一堆零散算法的集合顺序查找、折半查找、哈希、二叉排序树……背完ASL公式就扔到一边。但我在实际做开发之后回头看这一章恰恰是全书最容易和工程经验挂钩的地方——你写的每一条SQL、每一次Map.get()、每一个索引设计本质上都在做查找。这篇文章我想把第7章的脉络重新捋一遍不只是讲怎么做题也想讲清楚这些算法为什么这么设计真实项目里应该怎么选最后还会补上一些教材不写、但你在代码里迟早会踩的坑。1. 先从根上理解查找考的不是找是数据怎么组织1.1 最小模型关键字、记录与命中任何查找问题都可以抽成一个非常朴素的三件套一堆数据、一条目标记录、一个用来判断是不是它的关键字。数据怎么摆、关键字怎么比决定了查找是快还是慢。举个例子你现在有一张两万行的用户表想查出某个用户名对应的注册时间。最直观的办法是从头到尾逐条比对运气好第一条就命中运气差要扫完两万条。当数据量涨到两千万条时这个挨个找的方案就要扫几千万次响应时间立刻变得不可接受。此时你是去优化比较次数还是去换一种数据组织方式答案是后者这才是查找章节真正要教的东西同样的数据换一种存放方式查找的性能可以差出几个数量级。只有把查找抽象成这样一个模型你才能继续往下谈平均查找长度、谈不同结构之间的优劣。没有这个抽象后面所有复杂算法的动机都不成立。1.2 平均查找长度是照妖镜衡量查找算法最核心的指标叫平均查找长度ASLAverage Search Length定义为查找过程中关键字比较次数的期望值分为查找成功和查找失败两种。考试要你算ASL工程上你要估算接口耗时本质上用的是同一套方法。举个例子顺序查找在等概率的情况下成功查找的平均比较次数是 (n1)/2。这个公式怎么来的一条一条找第1条需要1次比较第2条需要2次……第n条需要n次加起来除以n正好是(n1)/2。而失败查找就比较惨烈了你得完整扫完整个表才能确认不存在所以要比较n1次。很多人在算ASL时会把成功和失败混在一起这是做这章题目最冤枉的丢分点成功ASL和失败ASL针对的是两种不同的查找过程分母也不一定一样。成功ASL的分母是表中实际存在的记录数失败ASL的分母是可能失败的位置数这个概念在后面哈希表部分尤其重要。1.3 三种基本存储形态决定了三类查找策略数据在物理上怎么组织直接决定了你能用哪种查找方法。大致可以分成三条路线顺序表数据连续存放在内存里支持随机访问。正因为能O(1)地跳到任意下标折半查找这种需要跳来跳去的算法才成立。链表只能顺着指针走。不管你怎么折腾想找中间元素必须从头遍历所以链表上谈折半查找基本是无稽之谈。散列/索引结构数据与存储位置之间建立一个映射函数目标是直接算出位置一步到位。后面的内容全部围绕这三条路线展开。每当你看到一道查找题先别急着套算法先问自己一句数据现在是以什么形式存在的这个前提直接决定答案。2. 线性结构上的查找顺序、折半与分块2.1 顺序查找不要小看挨个找顺序查找是所有查找算法里最没有智商的方案但从工程角度看它有一个其他算法都比不了的优势对数据组织没有任何额外要求。数组能找链表也能找有序行无序也行甚至你只有一张正在源源不断追加数据的日志表没法建索引、没法排序那顺序扫描就是唯一选择。它的成功ASL是(n1)/2失败ASL是n1时间复杂度O(n)。表面上看这是一个慢的算法但慢不等于没用。很多分布式的日志检索、数据仓库的全表扫描底层就是顺序查找的思路——因为没法对全量数据提前维护索引只能靠并行扫描一堆数据分片来把时间压下来。所以不要带着鄙视链看顺序查找它是兜底方案是所有更优方案的比较基准。在实际写代码时顺序查找还有一个容易忽略的优化把目标关键字当作哨兵放在表的末尾这样每次循环都不需要额外判断下标是否越界比较次数没变但分支减少了数据量大时也能省下不少时间。这种小技巧在算法竞赛和底层库实现里很常见是典型不求复杂度变好、只求常数变小的思路。2.2 折半查找O(log n)的前提条件与边界魔鬼折半查找也叫二分查找是线性结构查找里最重要的一个算法。它有一个硬性前提数据必须存储在顺序表上并且按关键字有序。存储前提前面说过支持随机访问才能跳。有序前提则是二分策略正确性的根基。它的核心思想是每次把查找区间切成两半用中间位置的关键字和目标比小了去左半边大了去右半边。理想情况下每次排除一半的数据复杂度O(log n)n100万时最多比较20次比顺序查找的50万次平均比较有数量级的优势。把查找过程画成二叉树你会看到一棵判定树树的高度就是最大比较次数。比如7个有序元素的判定树第一层1个结点第二层2个第三层4个树高3层成功ASL(1×12×24×3)/717/7≈2.43。这个值和log2(8)-12非常接近说明二分查找确实把比较次数压到了对数级别。但二分查找的代码非常容易写错我见过太多人在边界条件上翻车。这里必须说几个关键点循环条件用low high退出时low和high的交叉位置就是目标应该插入的位置计算中间点要用low (high - low) / 2不要用(low high) / 2因为两个大整数相加可能溢出每次移动边界时low mid 1或high mid - 1而不是low mid否则会出现死循环。我个人的习惯是先写出判定树在心里过一遍mid取到哪里、数组下标是否越界再写循环。这个习惯帮我挡掉过很多次线上事故。2.3 分块查找静态数据里的折中方案分块查找索引顺序查找是顺序查找和折半查找之间的一个折中方案把数据分成若干块块与块之间按最大值有序块内可以完全无序。另外维护一个索引表记录每块的最大关键字和块的起始位置。查找过程分两步先在索引表里定位目标可能存在的块这一步可以用顺序查找也可以对索引表做二分再在块内做顺序查找。比如n9分成3块每块3个元素索引表用顺序查找时成功ASL(31)/2(31)/24如果索引表用二分查找块间部分会降到约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) % mi1,2,3,...。问题非常明显——容易产生聚集现象一旦某一段被占满后续的关键字会像排队一样挤在一起查找失败的代价大幅上升。平方探测探测序列变成(H(key) i^2) % m能有效缓解线性探测的聚集问题但有个前提表长必须取适合的质数否则可能探测不全所有位置。链地址法则简单粗暴每个哈希表位置不存数据而是存一条链表的头指针冲突的元素链在后面。查找时要沿着链表往后扫但每个链子通常都很短所以整体仍然很快。工程上最常用的是链地址法的变体——每个桶放一个链表链表过长时再升级为树结构这是很多哈希表实现处理极端冲突的办法。链地址法还有一个好处删除元素特别方便直接把结点从链表里摘掉就行。而开放定址法删除时要小心不能直接置空否则会把后面探测路径中断掉通常得打一个已删除标记。这一点我在纸上推演时觉得无所谓写代码才发现非常烦人。3.3 装填因子α才是哈希的命门开始讲哈希表时很多人误以为冲突处理方式决定了性能上限其实真正决定哈希查找性能的是一个看似不起眼的参数装填因子 α 表中记录数 / 表长。为什么说它是命门因为哈希表的ASL并不直接依赖记录数n而是依赖α。α越大表越满冲突概率越高查找代价上升α越小表越空冲突少但空间浪费严重。教材给过线性探测法成功查找的近似ASL1/2 * (1 1/(1-α))链地址法成功查找的近似ASL1 α/2。你把这个近似公式带进去算一下就会发现同样是链地址法α从0.5涨到0.9ASL从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}表长m13散列函数H(key)key%13用线性探测法处理冲突计算查找成功时的ASL。先把每个关键字的散列地址算出来然后逐个插入19%136无冲突比较1次14%131无冲突比较1次23%1310无冲突比较1次1%131冲突线性探测到2比较2次68%133无冲突比较1次20%137无冲突比较1次84%136冲突探测到7被20占、8比较3次27%131依次探测2、3、4比较4次55%133依次探测4、5比较3次11%1311无冲突比较1次10%1310冲突探测11被11占、12比较3次79%131依次探测2到9比较9次。成功找完所有12个关键字的总比较次数是 11121134313930成功ASL30/122.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(n2)近似公式。这意味着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树索引磁盘IO友好范围查询顺畅高频精确查找、内存容量允许哈希表平均O(1)但注意扩容和控制α数据动态插入删除、保持有序遍历平衡树AVL/红黑树有序性保持得好范围遍历方便缓存淘汰、排行榜等特殊场景哈希链表组合兼顾O(1)定位和顺序维护注意这张表有一列很容易被人忽略空间成本。哈希需要额外的桶和可能的内存浪费B树需要大量索引结点折半查找则完全不需要额外内存。如果你的数据量小到可以在内存里全量装下但内存又很紧张那一个有序数组加二分查找往往比你去搞一棵树和一个哈希表更划算。5.2 工程实现里那些教材没写的细节教材教算法但工程里写代码会遇到很多教材不会提的细枝末节。我挑几个印象最深的第一个是哈希函数的输入类型问题。很多教材只讨论整数关键字但真实项目里关键字经常是字符串、复合对象。你会遇到一个很现实的问题直接把字符串的hashCode拿来用分布很可能不理想。这时候要给散列函数补一些位运算把高位信息混到低位里否则哈希表的很多桶可能是空的而另一些桶挤成一堆装填因子明明不高性能却已经烂了。第二个是二分查找的适用场景比想象中窄。工程上索引结构大多是B树或者哈希表很少有人手动搞二分查找因为维护一个动态有序数组的代价太高。但反过来在一次性加载全部配置、运行期只读这种场景里有序数组加二分查找的性能不但优秀而且内存效率极高。我见过某个配置服务就是这么干的启动时加载几千条配置排序一次之后每次查找都是log级别的耗时比拍脑袋上一套缓存简单多了。第三个是扩容和抖动问题。哈希表扩容在并发场景下特别容易出问题——扩容过程中所有线程都尝试rehash如果没处理好轻则性能剧烈波动重则数据错乱。这也是为什么真实系统里哈希表要么做分段、要么在扩容时加锁。这类工程细节教材不会考但做线上系统一定会遇到。5.3 高流量场景下哈希表劣化的真实经历最后讲一个我印象很深的排查经历。某次接手一个内部查询服务接口平时响应都是个位数毫秒某天突然有人反馈某些key的查询要几百毫秒甚至超时。一开始我以为是数据量涨了导致机器扛不住看了监控发现CPU不高、内存也充足非常诡异。后来把调用链打成火焰图才发现热点全在哈希表里——不是哈希表本身慢了而是某个类别下的key数量特别大且它们的散列结果高度集中在少数的桶里。当桶里的链表变得很长查找从O(1)退化成了O(n)。那时候才意识到教科书里讲的冲突极端情况不是理论是真实会在生产环境出现的。后续的修复方案也不难换一个分布更均匀的散列函数同时给底层哈希表加上桶内元素超过阈值时自动转为树结构的机制。修复之后那些极端key的查询时间立刻降了下来。这件事给我的教训是学查找算法时公式要背但更重要的是建立起数据结构决定性能上限的敏感度。当系统出现莫名性能问题时最先怀疑的往往不是机器而是数据组织方式。回头再看第7章你会发现这一章的每一节都不是孤立的。顺序查找是最朴素的基线分块查找引入了索引思想哈希利用散列函数把定位变成计算BST和AVL让动态数据保持有序B树把这一切扩展到海量数据和磁盘场景。每套方案都有自己的适用边界没有银弹。能把选型时知道自己在为什么买单这层功夫练出来这一章才算真正学会了。
很多人在学数据结构的时候会把查找这一章当成一堆零散算法的集合顺序查找、折半查找、哈希、二叉排序树……背完ASL公式就扔到一边。但我在实际做开发之后回头看这一章恰恰是全书最容易和工程经验挂钩的地方——你写的每一条SQL、每一次Map.get()、每一个索引设计本质上都在做查找。这篇文章我想把第7章的脉络重新捋一遍不只是讲怎么做题也想讲清楚这些算法为什么这么设计真实项目里应该怎么选最后还会补上一些教材不写、但你在代码里迟早会踩的坑。1. 先从根上理解查找考的不是找是数据怎么组织1.1 最小模型关键字、记录与命中任何查找问题都可以抽成一个非常朴素的三件套一堆数据、一条目标记录、一个用来判断是不是它的关键字。数据怎么摆、关键字怎么比决定了查找是快还是慢。举个例子你现在有一张两万行的用户表想查出某个用户名对应的注册时间。最直观的办法是从头到尾逐条比对运气好第一条就命中运气差要扫完两万条。当数据量涨到两千万条时这个挨个找的方案就要扫几千万次响应时间立刻变得不可接受。此时你是去优化比较次数还是去换一种数据组织方式答案是后者这才是查找章节真正要教的东西同样的数据换一种存放方式查找的性能可以差出几个数量级。只有把查找抽象成这样一个模型你才能继续往下谈平均查找长度、谈不同结构之间的优劣。没有这个抽象后面所有复杂算法的动机都不成立。1.2 平均查找长度是照妖镜衡量查找算法最核心的指标叫平均查找长度ASLAverage Search Length定义为查找过程中关键字比较次数的期望值分为查找成功和查找失败两种。考试要你算ASL工程上你要估算接口耗时本质上用的是同一套方法。举个例子顺序查找在等概率的情况下成功查找的平均比较次数是 (n1)/2。这个公式怎么来的一条一条找第1条需要1次比较第2条需要2次……第n条需要n次加起来除以n正好是(n1)/2。而失败查找就比较惨烈了你得完整扫完整个表才能确认不存在所以要比较n1次。很多人在算ASL时会把成功和失败混在一起这是做这章题目最冤枉的丢分点成功ASL和失败ASL针对的是两种不同的查找过程分母也不一定一样。成功ASL的分母是表中实际存在的记录数失败ASL的分母是可能失败的位置数这个概念在后面哈希表部分尤其重要。1.3 三种基本存储形态决定了三类查找策略数据在物理上怎么组织直接决定了你能用哪种查找方法。大致可以分成三条路线顺序表数据连续存放在内存里支持随机访问。正因为能O(1)地跳到任意下标折半查找这种需要跳来跳去的算法才成立。链表只能顺着指针走。不管你怎么折腾想找中间元素必须从头遍历所以链表上谈折半查找基本是无稽之谈。散列/索引结构数据与存储位置之间建立一个映射函数目标是直接算出位置一步到位。后面的内容全部围绕这三条路线展开。每当你看到一道查找题先别急着套算法先问自己一句数据现在是以什么形式存在的这个前提直接决定答案。2. 线性结构上的查找顺序、折半与分块2.1 顺序查找不要小看挨个找顺序查找是所有查找算法里最没有智商的方案但从工程角度看它有一个其他算法都比不了的优势对数据组织没有任何额外要求。数组能找链表也能找有序行无序也行甚至你只有一张正在源源不断追加数据的日志表没法建索引、没法排序那顺序扫描就是唯一选择。它的成功ASL是(n1)/2失败ASL是n1时间复杂度O(n)。表面上看这是一个慢的算法但慢不等于没用。很多分布式的日志检索、数据仓库的全表扫描底层就是顺序查找的思路——因为没法对全量数据提前维护索引只能靠并行扫描一堆数据分片来把时间压下来。所以不要带着鄙视链看顺序查找它是兜底方案是所有更优方案的比较基准。在实际写代码时顺序查找还有一个容易忽略的优化把目标关键字当作哨兵放在表的末尾这样每次循环都不需要额外判断下标是否越界比较次数没变但分支减少了数据量大时也能省下不少时间。这种小技巧在算法竞赛和底层库实现里很常见是典型不求复杂度变好、只求常数变小的思路。2.2 折半查找O(log n)的前提条件与边界魔鬼折半查找也叫二分查找是线性结构查找里最重要的一个算法。它有一个硬性前提数据必须存储在顺序表上并且按关键字有序。存储前提前面说过支持随机访问才能跳。有序前提则是二分策略正确性的根基。它的核心思想是每次把查找区间切成两半用中间位置的关键字和目标比小了去左半边大了去右半边。理想情况下每次排除一半的数据复杂度O(log n)n100万时最多比较20次比顺序查找的50万次平均比较有数量级的优势。把查找过程画成二叉树你会看到一棵判定树树的高度就是最大比较次数。比如7个有序元素的判定树第一层1个结点第二层2个第三层4个树高3层成功ASL(1×12×24×3)/717/7≈2.43。这个值和log2(8)-12非常接近说明二分查找确实把比较次数压到了对数级别。但二分查找的代码非常容易写错我见过太多人在边界条件上翻车。这里必须说几个关键点循环条件用low high退出时low和high的交叉位置就是目标应该插入的位置计算中间点要用low (high - low) / 2不要用(low high) / 2因为两个大整数相加可能溢出每次移动边界时low mid 1或high mid - 1而不是low mid否则会出现死循环。我个人的习惯是先写出判定树在心里过一遍mid取到哪里、数组下标是否越界再写循环。这个习惯帮我挡掉过很多次线上事故。2.3 分块查找静态数据里的折中方案分块查找索引顺序查找是顺序查找和折半查找之间的一个折中方案把数据分成若干块块与块之间按最大值有序块内可以完全无序。另外维护一个索引表记录每块的最大关键字和块的起始位置。查找过程分两步先在索引表里定位目标可能存在的块这一步可以用顺序查找也可以对索引表做二分再在块内做顺序查找。比如n9分成3块每块3个元素索引表用顺序查找时成功ASL(31)/2(31)/24如果索引表用二分查找块间部分会降到约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) % mi1,2,3,...。问题非常明显——容易产生聚集现象一旦某一段被占满后续的关键字会像排队一样挤在一起查找失败的代价大幅上升。平方探测探测序列变成(H(key) i^2) % m能有效缓解线性探测的聚集问题但有个前提表长必须取适合的质数否则可能探测不全所有位置。链地址法则简单粗暴每个哈希表位置不存数据而是存一条链表的头指针冲突的元素链在后面。查找时要沿着链表往后扫但每个链子通常都很短所以整体仍然很快。工程上最常用的是链地址法的变体——每个桶放一个链表链表过长时再升级为树结构这是很多哈希表实现处理极端冲突的办法。链地址法还有一个好处删除元素特别方便直接把结点从链表里摘掉就行。而开放定址法删除时要小心不能直接置空否则会把后面探测路径中断掉通常得打一个已删除标记。这一点我在纸上推演时觉得无所谓写代码才发现非常烦人。3.3 装填因子α才是哈希的命门开始讲哈希表时很多人误以为冲突处理方式决定了性能上限其实真正决定哈希查找性能的是一个看似不起眼的参数装填因子 α 表中记录数 / 表长。为什么说它是命门因为哈希表的ASL并不直接依赖记录数n而是依赖α。α越大表越满冲突概率越高查找代价上升α越小表越空冲突少但空间浪费严重。教材给过线性探测法成功查找的近似ASL1/2 * (1 1/(1-α))链地址法成功查找的近似ASL1 α/2。你把这个近似公式带进去算一下就会发现同样是链地址法α从0.5涨到0.9ASL从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}表长m13散列函数H(key)key%13用线性探测法处理冲突计算查找成功时的ASL。先把每个关键字的散列地址算出来然后逐个插入19%136无冲突比较1次14%131无冲突比较1次23%1310无冲突比较1次1%131冲突线性探测到2比较2次68%133无冲突比较1次20%137无冲突比较1次84%136冲突探测到7被20占、8比较3次27%131依次探测2、3、4比较4次55%133依次探测4、5比较3次11%1311无冲突比较1次10%1310冲突探测11被11占、12比较3次79%131依次探测2到9比较9次。成功找完所有12个关键字的总比较次数是 11121134313930成功ASL30/122.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(n2)近似公式。这意味着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树索引磁盘IO友好范围查询顺畅高频精确查找、内存容量允许哈希表平均O(1)但注意扩容和控制α数据动态插入删除、保持有序遍历平衡树AVL/红黑树有序性保持得好范围遍历方便缓存淘汰、排行榜等特殊场景哈希链表组合兼顾O(1)定位和顺序维护注意这张表有一列很容易被人忽略空间成本。哈希需要额外的桶和可能的内存浪费B树需要大量索引结点折半查找则完全不需要额外内存。如果你的数据量小到可以在内存里全量装下但内存又很紧张那一个有序数组加二分查找往往比你去搞一棵树和一个哈希表更划算。5.2 工程实现里那些教材没写的细节教材教算法但工程里写代码会遇到很多教材不会提的细枝末节。我挑几个印象最深的第一个是哈希函数的输入类型问题。很多教材只讨论整数关键字但真实项目里关键字经常是字符串、复合对象。你会遇到一个很现实的问题直接把字符串的hashCode拿来用分布很可能不理想。这时候要给散列函数补一些位运算把高位信息混到低位里否则哈希表的很多桶可能是空的而另一些桶挤成一堆装填因子明明不高性能却已经烂了。第二个是二分查找的适用场景比想象中窄。工程上索引结构大多是B树或者哈希表很少有人手动搞二分查找因为维护一个动态有序数组的代价太高。但反过来在一次性加载全部配置、运行期只读这种场景里有序数组加二分查找的性能不但优秀而且内存效率极高。我见过某个配置服务就是这么干的启动时加载几千条配置排序一次之后每次查找都是log级别的耗时比拍脑袋上一套缓存简单多了。第三个是扩容和抖动问题。哈希表扩容在并发场景下特别容易出问题——扩容过程中所有线程都尝试rehash如果没处理好轻则性能剧烈波动重则数据错乱。这也是为什么真实系统里哈希表要么做分段、要么在扩容时加锁。这类工程细节教材不会考但做线上系统一定会遇到。5.3 高流量场景下哈希表劣化的真实经历最后讲一个我印象很深的排查经历。某次接手一个内部查询服务接口平时响应都是个位数毫秒某天突然有人反馈某些key的查询要几百毫秒甚至超时。一开始我以为是数据量涨了导致机器扛不住看了监控发现CPU不高、内存也充足非常诡异。后来把调用链打成火焰图才发现热点全在哈希表里——不是哈希表本身慢了而是某个类别下的key数量特别大且它们的散列结果高度集中在少数的桶里。当桶里的链表变得很长查找从O(1)退化成了O(n)。那时候才意识到教科书里讲的冲突极端情况不是理论是真实会在生产环境出现的。后续的修复方案也不难换一个分布更均匀的散列函数同时给底层哈希表加上桶内元素超过阈值时自动转为树结构的机制。修复之后那些极端key的查询时间立刻降了下来。这件事给我的教训是学查找算法时公式要背但更重要的是建立起数据结构决定性能上限的敏感度。当系统出现莫名性能问题时最先怀疑的往往不是机器而是数据组织方式。回头再看第7章你会发现这一章的每一节都不是孤立的。顺序查找是最朴素的基线分块查找引入了索引思想哈希利用散列函数把定位变成计算BST和AVL让动态数据保持有序B树把这一切扩展到海量数据和磁盘场景。每套方案都有自己的适用边界没有银弹。能把选型时知道自己在为什么买单这层功夫练出来这一章才算真正学会了。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
