1. 查找为什么值得单独拎出来做一章很多人学数据结构学到查找这一章会有点“轻敌”——前面链表、树、图都啃下来了查找不就是在一个集合里找个数吗我一开始也这么想直到有次做日志分析要从几千万条记录里按时间戳定位某一段随手写了个线性扫描跑一次要等好几分钟才意识到查找这块的水比想象中深得多。查找的本质是在一个数据集合里定位目标元素的位置或者判断它是否存在。听起来简单但“怎么找”直接决定了程序的快慢。同样是在100万个数据里找一个值线性查找平均要比较50万次而用哈希表可能一次就命中用平衡树也就20次左右。这个差距在数据量小的时候感觉不出来一旦上了规模就是秒级和分钟级的区别。这一章要解决的核心问题就三个第一有哪些查找方法它们各自的适用场景是什么第二每种方法背后的数据结构是怎么组织的为什么这样组织能加速查找第三实际写代码时怎么根据数据的特点有序还是无序、静态还是动态、内存放不放得下选对方法。适合谁来参考呢如果你正在准备考试、复习数据结构这篇可以帮你把散落的知识点串成一条线如果你是刚入行的开发者想搞清楚实际项目里该用哪种查找方案这里面的对比和踩坑经验应该对你有用。我会尽量把每个概念讲透不堆公式多用类比和实际场景来说明。2. 线性表的查找从顺序查到分块查的进化逻辑2.1 顺序查找最笨但最通用的兜底方案顺序查找就是从表的一端开始逐个比较直到找到目标或者扫完整个表。它的代码简单到不需要解释def sequential_search(arr, target): for i in range(len(arr)): if arr[i] target: return i return -1时间复杂度是O(n)最好情况第一个就命中最坏情况要找n次。很多人觉得这方法太low但它的优势在于对数据没有任何要求。不需要有序不需要额外空间链表也能用数据动态增删也不影响。实际开发里当数据量不大比如几百条或者数据本身无序且只查一次顺序查找反而是最省事的选择。有个细节值得注意如果数据是有序的顺序查找可以提前终止。比如在升序数组里找5扫到7的时候就知道后面不可能有了直接返回不存在。这个优化在目标值偏小的时候能省不少时间但最坏情况还是O(n)。提示顺序查找的哨兵优化——在数组末尾放一个等于目标值的哨兵可以省去每次循环判断是否越界虽然只是常数级优化但在底层代码里很常见。2.2 折半查找有序带来的指数级加速折半查找二分查找的前提是数据必须有序。思路是每次拿中间元素和目标比较根据大小关系砍掉一半的搜索区间。def binary_search(arr, target): low, high 0, len(arr) - 1 while low high: mid (low high) // 2 if arr[mid] target: return mid elif arr[mid] target: low mid 1 else: high mid - 1 return -1时间复杂度O(log n)。100万个数据最多比较20次这个效率提升是巨大的。但它的限制也很明显数据必须有序而且得是顺序存储数组因为要随机访问中间元素。链表就不行链表找中间元素本身就要O(n)。折半查找的边界条件特别容易写错。我见过太多人栽在low high还是low high、mid 1还是mid这些细节上。一个实用的记忆方法是把区间定义成左闭右闭即[low, high]那么循环条件就是low high更新时low mid 1、high mid - 1这样逻辑最自洽。还有个坑mid (low high) // 2在low和high都很大时可能溢出。虽然Python不会但在C/C/Java里要注意改成mid low (high - low) // 2更安全。2.3 分块查找顺序和折半的折中艺术分块查找索引顺序查找把数据分成若干块块内无序但块间有序。比如数据分成三块第一块所有元素都小于第二块第二块都小于第三块。查找时先用折半查找定位目标可能在哪个块再在块内顺序查找。这种方法的性能介于顺序和折半之间。假设n个元素分成b块每块s个元素平均查找长度大约是(b1)/2 (s1)/2。当s √n时取得最小值√n 1。也就是说10000个数据分块查找平均只要约101次比较比顺序查找的5000次好太多又不像折半查找那样要求全局有序。分块查找的实际价值在于数据动态变化时维护成本低。折半查找要求全局有序插入一个元素可能要移动大量数据分块查找只需要保证块间有序插入时找到对应块塞进去就行块内顺序无所谓。这种特性在数据库索引、文件系统里都有应用。3. 树表查找让动态数据也能高效查找3.1 二叉排序树动态查找的起点二叉排序树BST的定义是左子树所有节点小于根右子树所有节点大于根。查找时从根开始比根小往左走比根大往右走。class TreeNode: def __init__(self, val): self.val val self.left None self.right None def bst_search(root, target): while root: if root.val target: return root elif root.val target: root root.right else: root root.left return NoneBST的好处是插入和删除不用像数组那样搬移元素动态性很好。但它的致命问题是可能退化成链表。如果按顺序插入1,2,3,4,5BST就变成一条向右的链查找退化成O(n)。这就引出了平衡树的概念。3.2 平衡二叉树与红黑树给BST上保险平衡二叉树AVL树要求任意节点左右子树高度差不超过1通过旋转操作在插入删除时维持平衡保证树高始终是O(log n)。红黑树则放松了平衡条件用颜色标记和旋转来维持“近似平衡”换取了更少的旋转次数插入删除性能更好。实际开发里红黑树比AVL树更常见。Java的TreeMap、C的std::map底层都是红黑树。为什么因为红黑树的平衡条件没那么严格插入删除时旋转次数少综合性能更优。AVL树适合查找远多于插入删除的场景。这里有个容易混淆的点平衡树的查找、插入、删除都是O(log n)但常数因子不同。红黑树的查找可能比AVL树多比较几次因为树高可能略高但插入删除更快。选哪个取决于你的操作比例。3.3 B树与B树磁盘时代的查找利器前面说的树都是内存里的节点存一个元素。但磁盘I/O慢得离谱一次磁盘读取可能要几毫秒而内存访问只要几十纳秒。如果树高是20就要20次磁盘I/O完全不可接受。B树的核心思想是一个节点存多个元素比如一个节点存100个元素那100万个数据树高只有3层3次磁盘I/O就够了。B树在B树基础上改进所有数据都在叶子节点非叶子节点只存索引叶子节点用链表串起来。这样范围查询特别方便——找到起点后顺着链表扫就行。MySQL的InnoDB引擎用的就是B树索引。为什么不用B树因为B树的非叶子节点不存数据同样大小的节点能存更多索引项树高更低而且叶子链表让范围查询和全表扫描更高效。树类型查找复杂度插入删除适用场景BST平均O(log n)最坏O(n)O(log n)~O(n)教学、简单场景AVL树O(log n)O(log n)旋转多查找远多于增删红黑树O(log n)O(log n)旋转少通用动态查找B/B树O(log n)O(log n)磁盘存储、数据库索引4. 散列表查找用空间换时间的极致玩法4.1 哈希函数把任意数据映射成固定范围的下标散列表哈希表的思路是通过一个哈希函数把关键字直接映射成数组下标理想情况下一次就能定位。比如除留余数法H(key) key % pp通常取小于表长的最大质数这样分布更均匀。哈希函数的设计目标有两个计算要快分布要均匀。计算快好理解分布均匀是为了减少冲突。如果所有key都映射到同一个下标哈希表就退化成链表了。常见的哈希函数有直接定址法、数字分析法、平方取中法、折叠法等实际工程里用的最多的是除留余数法和乘法散列法。注意哈希函数没有“最好”的只有“最适合当前数据分布”的。比如关键字都是手机号取后四位就比取前四位好因为前几位重复度高。4.2 冲突处理开放定址 vs 链地址法冲突是指两个不同的key映射到了同一个下标。处理方法主要有两类开放定址法冲突了就按某种规则找下一个空位。线性探测是挨个往后找简单但容易产生“堆积”——连续的位置都被占满后续查找要探测很多次。平方探测是跳着找能缓解堆积但可能探测不到所有位置。再散列是用第二个哈希函数再算一次。链地址法每个下标挂一个链表冲突的元素都塞进链表。Java的HashMap用的就是链地址法当链表长度超过8时转成红黑树兼顾了效率和最坏情况。class HashTable: def __init__(self, size16): self.size size self.table [[] for _ in range(size)] def _hash(self, key): return hash(key) % self.size def insert(self, key, value): idx self._hash(key) for i, (k, v) in enumerate(self.table[idx]): if k key: self.table[idx][i] (key, value) return self.table[idx].append((key, value)) def search(self, key): idx self._hash(key) for k, v in self.table[idx]: if k key: return v return None链地址法的装载因子元素个数/表长可以大于1而开放定址法必须小于1。实际工程里链地址法更常用因为删除操作简单不会像开放定址法那样需要特殊标记。4.3 装载因子与再哈希性能拐点在哪里装载因子α 元素个数 / 表长。α越大冲突概率越高查找越慢。开放定址法下α接近1时性能急剧下降链地址法下α1时平均查找长度约1.5还能接受。一般当α超过0.75时就该扩容了。扩容就是新建一个更大的表把所有元素重新哈希进去。这个过程是O(n)的但摊还到每次插入上还是O(1)。Java的HashMap默认装载因子就是0.75初始容量16每次扩容翻倍。这里有个实操经验如果能预估数据量初始化时直接指定合适的容量避免多次扩容。比如你知道要存1000个元素初始容量设20482的幂方便位运算取模装载因子0.5左右性能最好。5. 查找算法的选型实战没有最好只有最合适5.1 按数据特征选有序性、动态性、存储介质选查找方法先问三个问题第一数据有序吗有序优先考虑折半查找或树结构无序只能顺序查找或哈希。第二数据动态变化吗频繁插入删除用树或哈希静态数据用折半查找或分块。第三数据在内存还是磁盘内存用红黑树或哈希磁盘用B树。举个例子配置项查找数据量小几百条加载后不变用折半查找最合适——有序数组二分定位代码简单。用户会话管理频繁增删数据量中等用哈希表——O(1)查找删除方便。数据库索引数据量大存在磁盘用B树——树高低范围查询快。5.2 按操作比例选查多写少还是查写均衡如果查找操作占90%以上AVL树或有序数组折半查找更优因为查找路径短。如果插入删除也很频繁红黑树或哈希表更合适。有个反直觉的结论哈希表并不总是最快的。当数据量很小比如少于50个顺序查找可能比哈希表快因为哈希函数计算和冲突处理有开销而顺序查找的循环在现代CPU上跑得飞快。我实测过在32个元素的数组里找一个值顺序查找平均比哈希表快20%左右。5.3 一个真实场景的选型推演假设要做一个实时日志检索系统日志按时间戳追加写入支持按时间范围查询。数据量每天千万级保留7天。分析数据按时间天然有序追加写入不修改历史数据查询主要是范围查询。选什么哈希表范围查询不支持排除。红黑树内存放不下7天的数据排除。B树完美匹配。按时间戳建B树索引叶子节点链表支持高效范围扫描数据落磁盘内存只缓存索引节点。这就是为什么时序数据库底层大多用类似B树或LSM树的结构。选型的核心不是比哪个算法“高级”而是看哪个最贴合数据的访问模式。6. 那些年我在查找上踩过的坑6.1 二分查找的边界死循环刚学二分查找时我写过这样的代码while low high: mid (low high) // 2 if arr[mid] target: low mid else: high mid看起来没问题但当low 0, high 1时mid 0如果arr[0] targetlow mid 0区间没变死循环。正确写法应该是low mid 1。这个坑的本质是区间收缩必须保证每次至少排除一个元素。6.2 哈希表扩容时的性能抖动有次做在线服务用哈希表缓存用户数据平时响应时间1ms。某天用户量突增哈希表触发扩容单次请求耗时飙到200ms导致超时报警。原因是扩容时重新哈希所有元素数据量大时耗时明显。解决办法渐进式扩容。扩容时保留新旧两个表每次操作顺便迁移一部分数据把O(n)的扩容成本摊到多次操作里。Redis的字典就是这么做的。6.3 有序数组插入的隐藏成本有段时间我特别喜欢用有序数组折半查找觉得查找O(log n)很优雅。直到有个场景要频繁插入数据每次插入都要移动后面所有元素O(n)的插入成本把查找省下的时间全吃回去了整体性能还不如直接用链表顺序查找。这个教训让我明白查找效率不能孤立看要和增删改一起算总账。数据结构的选择是全局优化不是局部最优。6.4 字符串哈希的分布陷阱做关键词统计时我用hash(key) % size做哈希函数结果发现某些前缀相同的字符串大量冲突。原因是Python的字符串哈希对相似字符串产生的哈希值也相似取模后容易撞车。改进方法是加一个扰动hash(key) ^ (hash(key) 16)再取模让高位参与运算分布更均匀。Java的HashMap就是这么干的。7. 把查找知识串成一张网学完这一章我建议你脑子里有一张决策树数据无序且量小顺序查找数据有序且静态折半查找数据动态变化红黑树数据在磁盘B树追求O(1)且能接受空间开销哈希表。但更重要的是理解每种方法背后的权衡。折半查找用“有序”换“log n”哈希表用“空间”换“O(1)”B树用“节点存多个元素”换“低树高”。没有免费的午餐每个优势背后都有代价。我在实际项目里最常用的组合是小数据用有序数组二分中等数据用哈希表大数据用数据库索引。偶尔遇到特殊场景比如需要按范围遍历才会考虑跳表或B树。最后分享一个练习方法拿一个真实的数据集比如一份CSV文件分别用顺序查找、折半查找、哈希表、二叉搜索树实现同一个查询功能对比它们的耗时和内存占用。跑一遍下来你对这些算法的理解会比看十遍书都深。