第 11 讲 · 查找、索引与散列

查找是根据关键字确定记录是否存在以及所在位置。若查找表只读，称静态查找表；若还要插入和删除，称动态查找表。结构的选择取决于数据是否有序、是否频繁变化、能否随机访问，以及可用空间。

平均查找长度

平均查找长度（ASL）是关键字比较次数的期望：

ASL=\sum_{i=1}^{n}p_i c_i,

其中 $p_i$ 是查找第 $i$ 个记录的概率， $c_i$ 是对应比较次数。查找失败也可以单独计算失败 ASL。

顺序查找

从头逐个比较，不要求有序，也适用于链表。等概率成功查找平均比较约 $(n+1)/2$ 次，时间 $O(n)$ 。设置哨兵可以减少循环内的边界判断，但不会改变数量级。

折半查找

折半查找要求数据有序且可随机访问。每次比较中间元素：相等则成功；目标较小就在左半区继续；较大就在右半区继续。

循环不变量是：若目标存在，它一定仍在闭区间 [low, high] 中。使用闭区间时循环条件为 low <= high，更新应写 high = mid - 1 或 low = mid + 1。

每次把候选规模约减半，因此最坏比较次数为 $O(\log n)$ 。有序链表虽有次序，却不能 $O(1)$ 找中间结点，不适合普通折半查找。

课件还把插值查找和 Fibonacci 查找列作延伸。它们仍以有序顺序表为前提，只是选择分割位置的规则不同：插值查找根据关键字在端点值之间的比例估计位置，数据近似均匀时可能很快；Fibonacci 查找用 Fibonacci 数划分区间。两者都没有改变“缩小候选区间”的基本思想，也不能替代对使用条件的判断。

索引

索引表把关键字或关键字范围映射到基本数据的位置。

稠密索引：每条记录都有索引项；
分块索引：每块一项，先定位块，再在块内查找；
多级索引：索引本身再建立索引，形成树形结构；
倒排索引：从词项映射到含该词的记录集合。

索引以额外空间和更新成本换取更小的查找范围。

B-树与 B+树

磁盘访问比内存比较昂贵得多，多路查找树让一个结点保存多个关键字和孩子，从而降低树高。

B-树的关键字和记录可以分布在各层；B+树把完整记录集中在叶层，内部结点只作索引，叶结点按次序相连。B+树适合范围查询，因为找到范围起点后可以沿叶链顺序扫描。

课程材料把它们作为树形索引的基本认识，重点是理解“用更高分支因子减少外存层数”，而不是死背某一种阶数定义。

散列查找

散列函数 $H(k)$ 直接把关键字映射到有限地址。理想情况下查找不必与许多记录比较，平均接近 $O(1)$ 。

不同关键字可能得到同一地址，这叫冲突。好的散列函数应覆盖全部关键字、计算简单，并让结果尽量均匀。

开放地址法

发生冲突后，在表内按探测序列寻找下一个空位。线性探测简单，但容易形成连续聚集；二次探测减少主聚集，却必须配合合适表长和探测约定。

开放地址删除不能简单清空单元，否则会截断其他元素的查找路径，通常要设置“已删除”标记。

链地址法

让每个散列地址指向一条链，所有同地址记录放入该链。它不产生表内聚集，删除方便，表长也不必严格容纳所有记录，但结点需要指针空间。

装填因子

\alpha=\frac{\text{实际记录数}}{\text{散列表容量}}

反映表的拥挤程度。对开放地址法， $\alpha$ 越接近 1，探测通常越长；链地址法可以允许 $\alpha>1$ ，但平均链长会增加。

怎样选择

条件	更合适的方法
数据很少或完全无序	顺序查找
静态有序数组	折半查找
动态有序集合	平衡搜索树
外存大数据和范围查询	B/B+ 树索引
精确关键字、追求平均常数时间	散列表

不存在脱离使用条件的“最快查找”。散列表不维持顺序，折半查找不适合频繁插入的数组，树结构的性能又取决于是否平衡。