查找的基本概念

查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找
查找结果分为两种：一是查找成功，即在数据集合中找到了满足条件的数据元素；二是查找失败
查找表：用于查找的数据集合称为查找表，由同一类型的数据元素组成，可以是数组、链表等数据类型
对查找表经常进行的操作一般有4种：
1. 查询某个特定的数据元素是否在查找表中
2. 检索满足条件的某个特定的数据元素的各种属性
3. 在查找表中插入一个数据元素
4. 从查找表中删除某个数据元素
静态查找表：若一个查找表的操作只涉及上述操作 1 和 2，则无须动态地修改查找表，此类查找表称为静态查找表
与此对应，需要动态地插入或删除的查找表称为动态查找表
适合静态查找表的查找方法有顺序查找、折半查找、散列查找等
适合动态查找表的查找方法有二叉排序树的查找、散列查找等
关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的
平均查找长度：在查找过程中，一次查找的长度是指需要比较的关键字次数
平均查找长度则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为 $A S L = \sum_{i = 1}^{n} P_{i} C_{i}$
其中 n 是查找表的长度； $P_{i}$ 是查找第 i 个数据元素的概率，一般认为每个数据元素的查找概率相等，即 $P_{i} = l / n$ ； $C_{i}$ 是找到第 i 个数据元素所需进行的比较次数
平均查找长度是衡量查找算法效率的最主要的指标

顺序查找和折半查找

顺序操作

一般线性表的顺序查找

其基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件

若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置

若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息


typedef struct {

    ElemType *elem;  // 从 1 开始存储

    int TableLen;  // 表的长度

} SSTable;



int Search_Seq(SSTable ST, ElemType key){

    ST.elem[0] = key;  // 哨兵，让查找不到时返回 0

    for(i = ST.TableLen; ST.elem[i] != key; --i);  // 从后向前查找

    return i;

}

对于有 n 个元素的表，定位第 i 个元素时，需进行 n - i + 1 次关键字的比较，即 $C_{i}$ = n - i + 1

查找成功时，平均长度为 $A S L_{成功} = \sum_{i = 1}^{n} P_{i} (n - i + 1)$ 当每个元素的查找概率相等，即 $P_{i} = \frac{1}{n}$ 有 $A S L_{成功} = \frac{n + 1}{2}$

查找不成功时，与表中各关键字的比较次数显然是 n + 1 次，从而顺序查找不成功的平均查找长度为 $A S L_{不成功} = n + 1$

通常查找表中记录的查找概率并不相等，若能预先得知查找概率，则应先对查找概率进行排序，按查找概率由大至小排列

顺序查找的缺点是当 n 较大时，平均查找长度较大，效率低；优点是对数据元素的存储没有要求，顺序存储或链式存储皆可。对表中记录的有序性也没有要求，无论记录是否按关键字有序，均可应用

注意：对线性的链表只能进行顺序查找

有序表的顺序查找

若在查找之前就已经知道表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度

查找思路：假设表是按关键字从小到大排列，查找顺序是从前往后，现在要查找 key，当第 i 个元素大于 key 是就可返回失败信息，因为第 i 即其以后的元素都大于 key，所以表中不存在 key

树中的圆形结点表示有序顺序表中存在的元素；树中的矩形结点称为失败结点，有 n + 1 个查找失败结点

在有序表的顺序查找中，查找成功的平均查找长度和一般线性表的顺序查找一样

查找失败时，到达失败结点时所查找的长度等于它上面的一个圆形结点的所在层数

查找不成功的平均查找长度在相等查找概率的情形下为 $A S L_{不成功} = \sum_{j = 1}^{n} q_{j} (l_{j} - 1) = \frac{1 + \dots + n + n}{n + 1} = \frac{n}{2} + \frac{n}{n + 1}$

其中， $q_{j}$ 是到达第 j 个失败结点的概率，在相等查找概率的情形下，它为 1 / (n + 1)； $l_{j}$ 是第 j 个失败结点所在的层数

注意：有序表的顺序查找和折半查找的思想是不一样的，且有序表的顺序查找中的线性表可以是链式存储结构

考点追踪：折半查找过程分析（2010、2015、2016、2017、2023、2024）

熟练掌握判定树的构造，判定树是平衡二叉树。2. 折半查找最多比较次数为 $⌈ \log_{2} (n + 1) ⌉$ 。3. 折半查找仅适用于有序顺序表，不适用于链表。4. 注意判定树路径的合法性。

折半查找

折半查找的定义

折半查找又称二分查找，它仅适用于有序的顺序表，不适合于链式存储结构

折半查找的基本思想（对于升序顺序表）：

从线性表的比较范围取中间元素与 key 比较
若相等，查找成功
若小于，把线性表的比较范围设置为前半部分
若大于，把线性表的比较范围设置为后半部分
重复，直到找到或者表范围为空为止


int Binary_Search(SeqList L, ElemType key){

    int low = 0, high = L.TableLen - 1, mid;  // low，hign 定义表范围

    while (low <= high) {  // 表范围里面有元素

        mid = (low + high) / 2;  // 取中间位置

        if (L.elem[mid] == key)

            return mid;  // 查找成功则返回所在位置

        else if (L.elem[mid] > key)

            high = mid - 1;  // 从前半部分继续查找

        else

            low = mid + 1;  // 从后半部分继续查找

    }

    return -1;  // 查找失败，返回 -1

}

折半查找的判定树

**折半查找的过程**可用二叉树排序树来描述，称为判定树

树中每个圆形结点表示一个记录，它的值为该记录的关键字值；树中最下面的叶结点都是方形的，它表示查找不成功的情况

折半查找取中可以是 $⌊ (l o w + h i g n) / 2 ⌋$ 或 $⌈ (l o w + h i g n) / 2 ⌉$ 这两种得出的判别树是不同的；前者右子树结点数必须大于等于左子树结点数且最多大一，而后者相反，下图的树是向下取整的树

从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点数

查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数

若有序序列有 n 个元素，则对应的判定树有 n 个圆形的非叶结点和 n + 1 个方形的叶结点

判定树是一棵平衡二叉树，用折半查找法查找到给定值的比较次数最多不会超过树的高度

折半查找的最少比较次数和最大比较次数差不会超过 1，故它的判定树内的高度差不会超过 1

等概率查找时，查找成功的平均查找长度为 $A S L = \frac{1}{n} \sum_{i = 1}^{n} l_{i} = \frac{1}{n} (1 \times 1 + \dots + h \times 2^{h - 1}) = \frac{n + 1}{n} \log_{2} (n + 1) - 1 \approx \log_{2} (n + 1) - 1$

其中 h 是树的高度且元素个数为 n 时树高 $h = ⌈ \log_{2} (n + 1) ⌉$ ；折半查找的最大比较次数为树高，最小比较次数为树高减 1

核心结论：折半查找判定树（2015、2017、2023）

结构：由于 $m i d = ⌊ (l o w + h i g h) / 2 ⌋$ ，判定树中对于任何结点，其左子树结点数 $n_{L}$ 和右子树结点数 $n_{R}$ 满足 $0 \leq n_{R} - n_{L} \leq 1$ 。

性质：判定树是平衡二叉树（AVL）。

高度：含有 $n$ 个结点的判定树高度 $h = ⌈ \log_{2} (n + 1) ⌉$ 。这也是查找成功时最大比较次数。

ASL：考试常考具体 $n$ 下的 $A S L_{成功}$ 和 $A S L_{不成功}$ ，务必手画判定树计算。

考点追踪：判定树的偏向（2024、2025 新焦点）

若 $m i d = ⌊ (l o w + h i g h) / 2 ⌋$ ，则左子树结点数 $\leq$ 右子树结点数 (偏右)。

若 $m i d = ⌈ (l o w + h i g h) / 2 ⌉$ ，则左子树结点数 $\geq$ 右子树结点数 (偏左)。

判定树中的圆形结点代表查找成功，方形结点代表查找失败（对应顺序表中的外部区域）。

所以折半查找的时间复杂度为 $O (\log_{2} n)$ ，平均情况下比顺序查找的效率高

折半查找法仅适合于顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列

核心结论：折半查找 ASL 与判定树 (2025 重点)

ASL 成功： $\frac{1}{n} \sum (层数 \times 该层结点数)$ 。
ASL 失败： $\frac{1}{n + 1} \sum (对应失败结点父层数 \times 失败结点数)$ 。
判定树高度 $h$ ：含有 $n$ 个结点的判定树，最大比较次数为 $h = ⌈ \log_{2} (n + 1) ⌉$ 。
决策偏向：
- $m i d = ⌊ (l + h) / 2 ⌋$ ：左子树节点数 $\leq$ 右子树节点数（右偏）。
- $m i d = ⌈ (l + h) / 2 ⌉$ ：左子树节点数 $\geq$ 右子树节点数（左偏）。

提示：求二分法的平均查找长度不要套公式，直接画出判定树（注意 $n$ 是奇数还是偶数，偶数时注意 $m i d$ 取值偏向）。

分块查找

分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适合快速查找

分块查找的基本思想是：

将查找表分为若干子块
块内的元素可以无序，但块之间是有序的，如块一的元素小于块二等
建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列

分块查找的过程分为两步：

在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表
在块内顺序查找

分块查找的平均查找长度为索引查找和块内查找的平均长度之和，设索引查找和块内查找的平均查找长度分别为 $L_{I}$ ， $L_{S}$ ，则分块查找的平均查找长度为 $A S L = L_{I} + L_{S}$

将长度为 n 的查找表均匀地分为 b 块，每块有 s 个记录，在等概率情况下，若在块内和索引表中均采用顺序查找，则平均查找长度为 $A S L = L_{I} + L_{S} = \frac{b + 1}{2} + \frac{s + 1}{2} = \frac{s^{2} + 2 s + n}{2 s}$ 其中 $b = \frac{n}{s}$ ；若 $s = \sqrt{n}$ ，则平均查找长度取最小值 $\sqrt{n} + 1$

若对索引表采用折半查找时，则平均查找长度为 $A S L = L_{I} + L_{S} = ⌈ \log_{2} (b + 1) ⌉ + \frac{s + 1}{2}$

考点追踪：分块查找的效率设计（2025）

考试常考如何划分块大小以达到最优 ASL。当步长 $s = \sqrt{n}$ 时，ASL 取得最小值 $\sqrt{n} + 1$ 。

B 树和 B + 树

B 树及其基本操作

B 树的定义

B 树又称为多路平衡查找树，B 树中所有结点的孩子结点数的最大值称为 B 树的阶，通常用 m 表示

一个 m 阶 B 树或者为空树，或者为满足如下特性的 m 叉树：

树中每个结点至多有 m 棵子树（即至多含有 m - 1 个关键字）
若根结点不是终端结点，则至少含有两棵子树
除根结点之外的所有非叶结点至少有 $⌈ m / 2 ⌉$ 棵子树（即至少含有个 $⌈ m / 2 ⌉ - 1$ 关键字）
所有非叶结点的结构如下：
其中， $K_{i}$ 为结点的关键字，且满足 $K_{1} < \dots < K_{n}$ ； $P_{i}$ 为指向子树根结点的指针，且指针 $P_{i - 1}$ 所指子树中所有结点的关键字均小于 $K_{i}$ ， $P_{i}$ 所指子树中所有结点的关键字均大于 $K_{i}$ ； $⌈ m / 2 ⌉ - 1 \leq n \leq m - 1$ 中 n 为结点中关键字的个数
所有的叶结点都出现在同一层次上，并且不带信息（实际上这些结点不存在，指向这些结点的指针为空）

B 树的高度

B 树的高度不包含最后的不带任何信息的叶结点所处的那一层，有些书带了这一层

若 $n \geq 1$ 则对任意一棵包含 n 个关键字、高度为 h、阶数为 m 的 B 树：

在一棵高度为 h 的 m 阶 B 树中关键字的个数应满足 $n \leq (m - 1) (1 + \dots + m^{h - 1}) = m^{h} - 1$ ，就有 $h \geq \log_{m} (n + 1)$
其中 $m - 1$ 是结点中最大关键字数， $m^{h - 1}$ 是当前层最多的结点数
在一棵高度为 h 的 m 阶 B 树中关键字的个数应满足 $n + 1 \geq 2 (⌈ m / 2 ⌉)^{h - 1}$ ，就有 $h \leq \log_{⌈ m / 2 ⌉} ((n + 1) / 2) + 1$
要使 B 树最高，根据 B 树的定义：
1. 根结点只有一个结点，即根结点只有两个子树
2. 第三层至少有 $2 ⌈ m / 2 ⌉$ 个结点；其中 $⌈ m / 2 ⌉$ 是每个结点的最少子树
3. 第 h 层至少有 $2 ⌈ m / 2 ⌉^{h - 2}$ 个结点
4. 第 h + 1 层至少有 $2 ⌈ m / 2 ⌉^{h - 1}$ 个结点，对于关键字个数为 n 的 B 树，叶结点即查找不成功的结点为 n + 1
5. 又 h + 1 层是叶结点，就有 $n + 1 \geq 2 ⌈ m / 2 ⌉^{h - 1}$ ，即 $h \leq \log_{⌈ m / 2 ⌉} ((n + 1) / 2) + 1$
6. 注意： $n + 1 = 2 ⌈ m / 2 ⌉^{h - 1}$ 时是当前高度的最小结点情况
综上得到有 n 个关键字的 B 树最小高度为 $⌈ \log_{m} (n + 1) ⌉$ 最大高度为 $⌈ \log_{⌈ m / 2 ⌉} ((n + 1) / 2) ⌉ + 1$
计算关键字数量也可以把每一层结点数加起来乘最小关键字数 $1 + (⌈ m / 2 ⌉ - 1) (2 + 2 \sum_{i = 3}^{h} ⌈ m / 2 ⌉^{i - 2})$ 根结点关键字是 1

核心公式：m 阶 B 树的参数边界 (2012-2024 高频)

| 属性 | 根结点 | 非根分支结点 | 叶子结点 (外部) |

| :--- | :--- | :--- | :--- |

| 子树个数 $k$ | $[2, m]$ | $[⌈ m / 2 ⌉, m]$ | 0 |

| 关键字个数 $n$ | $[1, m - 1]$ | $[⌈ m / 2 ⌉ - 1, m - 1]$ | 0 |

高度 $h$ 与关键字 $n$ 的关系： $\log_{m} (n + 1) \leq h \leq \log_{⌈ m / 2 ⌉} (\frac{n + 1}{2}) + 1$ 。
失败结点数：一棵含有 $n$ 个关键字的 B 树必有 $n + 1$ 个叶子结点（外部结点）。

易错点：终端结点 vs 叶子结点

终端结点：B 树中最后一层“实”结点，包含关键字。

叶子结点：终端结点下方的 NULL 指针层，又称失败结点或外部结点。B 树高度计算通常不计这一层。

核心对比：B 树 vs B+ 树 (2020、2025)

关键字位置：B 树中关键字在全树各结点不重复；B+ 树中分支结点仅索引，关键字必在叶子节点出现。

数据关联：B 树所有结点带数据指针；B+ 树仅叶子结点带数据指针。

查询稳定性：B+ 树由于必到叶子，路径长度固定，查询更稳定。

范围查询：B+ 树叶子结点有横向指针连成链表，更直观高效。

B 树的查找

从磁盘上把结点加载进内存
在结点内对关键字进行比较，使用二分查找或顺序查找
如果查找成功就返回关键字对应的信息
如果查找失败，就拿对应的指针信息回到第一步加载进内存
对应的指针是指，若 $K_{i - 1}$ < k < $K_{i}$ 那么指针就是 $P_{i - 1}$ ，否则就是 $P_{i}$
如果查找到叶结点（NULL）时，说明树中没有对应的关键字，查找失败

B 树的插入

先定位，使用查找找到最下层的非叶结点
把 key 插入，查看该结点的大小是否等于 $m$ ，若小于 m 插入结束
若大于等于 m，就进行分裂操作，分裂完了由于给父结点加了个关键字，所以父结点可能也要分裂
1. 从中间位置 $⌈ m / 2 ⌉$ 将该结点的关键字分为两个部分
2. 创建一个新结点存放右边部分的内容
3. 中间结点插入父结点假设是 $K_{i}$ 位置，父结点的 $P_{i}$ 指向新结点

B 树的删除

查找要删除的关键字所在的位置
如果要删除的关键字不在最底层，那么就拿后继或前驱代替，现在就变成删除最底层
如果删除关键字后结点内关键字 $\geq ⌈ m / 2 ⌉$ ，则不需要调整，删除完成
如果小于，就先看兄弟结点有没有 $\geq ⌈ m / 2 ⌉$ ，有就向他借一个，删除完成
1. 这里假设是右兄弟，左兄弟类似
2. 从父结点拿一个结点下来，用右兄弟最小的关键字代替
如果兄弟也没有的借，那就合并，合并会拿父结点一个关键字，导致父结点也可能需要调整（第三步开始）
1. 就拿自己和兄弟以及一个父结点的关键字合并
2. 这里要注意调整子树的指针位置

B + 树的基本概念

B + 树是应数据库所需而出现的一种 B 树的变形树

一棵 m 阶的 B + 树需满足下列条件：

每个分支结点最多有 m 棵子树（孩子结点）
非叶根结点至少有两棵子树，其他每个分支结点至少有 $⌈ m / 2 ⌉$ 棵子树
结点的子树个数与关键字个数相等
叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，相邻叶结点按大小顺序相互链接起来
所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针

m 阶的 B + 树与 m 阶的 B 树的主要差异如下:

关键字对应的子树不一样，B + 树每个关键字对应一棵子树；B 树子树的数量是关键字的数量加一
根结点和非根内部结点的关键字个数不一样，B + 树是 $⌈ m / 2 ⌉ \leq n \leq m$ ；B 树是 $⌈ m / 2 ⌉ - 1 \leq n \leq m - 1$
在 B + 树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中不含有该关键字对应记录的存储地址
在 B + 树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中
而在 B 树中，叶结点（最外层内部结点）包含的关键字和其他结点包含的关键字是不重复的

通常在 B + 树中有两个头指针：一个指向根结点，另一个指向关键字最小的叶结点

可以对 B + 树进行两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找

B + 树的查找、插入、删除操作和 B 树的基本类似，只是在查找时，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，直到叶结点上的该关键字为止

核心对比：B 树 vs B+ 树 (2020、2025)

关键字位置：B 树中关键字在全树各结点不重复；B+ 树中分支结点仅索引，关键字必在叶子节点出现。

数据关联：B 树所有结点带数据指针；B+ 树仅叶子结点带数据指针。

查询稳定性：B+ 树由于必到叶子，路径长度固定，查询更稳定。

范围查询：B+ 树叶子结点有横向指针连成链表，更直观高效。

重点：B 树与 B+ 树的“关键字与子树”对应关系

B 树： $k$ 个关键字对应 $k + 1$ 个子树。

B+ 树： $k$ 个关键字对应 $k$ 个子树。

在数据库索引中，B+ 树因其叶子结点构成有序链表，更适合 范围查询（Range Query）。

散列表

散列表的基本概念

在前面介绍的线性表和树表的查找中，查找方法建立在“比较”的基础上，查找的效率取决于比较的次数

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为 Hash(key) = Addr，这里的地址可以是数组下标、索引或内存地址等
散列函数可能把两个或以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词
设计得好的散列函数应尽量减少这样的冲突；由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法
散列表：根据关键字而直接进行访问的数据结构，散列表建立了关键字和存储地址之间的一种直接映射关系

理想情况下，对双链表进行查找的时间复杂度为 O(1)，即与表中元素的个数无关

散列函数的构造方法

在构造散列函数时，必须注意以下几点：

散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围
散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生
散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址

在不同的情况下，不同的散列函数具有不同的性能，因此不能笼统地说哪种散列函数最好

在实际选择中，采用何种构造散列函数的方法取决于关键字集合的情况，但目标是为了尽量降低产生冲突的可能性

直接定址法

直接取关键字的某个线性函数值为散列地址，散列函数为 H(key) = key 或 H(key) = a × key + b，其中 a 和 b 是常数

这种方法计算最简单，且不会产生冲突，它适合关键字的分布基本连续的情况

若关键字分布不连续，则会造成存储空间的浪费

除留余数法

这是一种最简单、最常用的方法，假定散列表表长为 m，取一个不大于 m 但最接近或等于 m 的质数 p

利用散列函数 H(key) = key % p，把关键字转换成散列地址

除留余数法的关键是选好 p，使得通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性

为什么 p 是质数：因为质数因子最少，冲突较少；如 6 还有因子 2，因子的列 2, 4, 6, 8, 10, 12 冲突比较大

数字分析法

设关键字是 r 进制数（如十进制数），而 r 个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等

而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址

这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数

数值分析法就是有一堆有规律的数字，我们可以根据这个规律思考一个散列函数

平方取中法

这种方法取关键字的平方值的中间几位作为散列地址，具体取多少位要视实际情况而定

这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀

适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数

如 3586 的平方 12859396 我们可以取中间的 59 作为散列地址

处理冲突的方法

用 $H_{i}$ 表示处理冲突中第i次探测得到的散列地址，假设得到的另一个散列地址 $H_{1}$ 仍然发生冲突，只得继续求下一个地址 $H_{2}$ ，以此类推，直到 $H_{k}$ 不发生冲突为止，则 $H_{k}$ 为关键字在表中的地址

开放地址法

所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放

其数学递推公式为 $H_{i} = (H (k e y) + d_{i}) % m$ 其中 m 表示散列表表长， $d_{i}$ 为增量序列

取定某一增量序列后，对应的处理方法就是确定的，其中增量序列有以下4种取法：

线性探测法

当 $d_{i} = 0, 1, \dots, m - 1$ 时，称为线性探测法

这种方法的特点是：冲突发生时，顺序查看表中下一个单元，直到找出一个空闲单元或查遍全表

线性探测法可能使第 i 个散列地址的同义词存入第 i + 1 个散列地址

这样本应存入第 i + 1 个散列地址的元素就争夺第 i + 2 个散列地址的元素的地址

从而造成大量元素在相邻的散列地址上“聚集”起来，大大降低了查找效率

平方探测法

当 $d_{i} = 0^{2}, 1^{2}, - 1^{2}, \dots, k^{2}, - k^{2}$ 时，称为平方探测法，其中 k ≤ m / 2，散列表长度 m 必须是一个可以表示成 4k + 3 的素数，又称二次探测法

平方探测法是一种较好的处理冲突的方法，可以避免出现“聚集”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元

再散列法

当 $d_{i} = H a s h_{2} (k e y)$ 时，称为再散列法，又称双散列法

需要使用两个散列函数，当通过第一个散列函数 H(key) 得到的地址发生冲突时，则利用第二个散列函数 $H a s h_{2} (k e y)$ 计算该关键字的地址增量

它的具体散列函数形式为 $H_{i} = (H (k) + i \times H a s h_{2} (k e y)) % m$ 初始探测位置 $H_{0} = H (k e y) % m$ ，i 是冲突的次数，初始为 0

在再散列法中，最多经过 m - 1 次探测就会遍历表中所有位置，回到 $H_{0}$ 位置

伪随机序列法

当 $d_{i}$ = 伪随机数序列时，称为伪随机序列法

要删除一个元素时，可给它做一个删除标记，进行逻辑删除，因为删除后可能会影响相同散列地址的查找

但这样做的副作用是：执行多次删除后，表面上看起来散列表很满，实际上有许多位置未利用，因此需要定期维护散列表，要把删除标记的元素物理删除

拉链法

对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识

假设散列地址为 i 的同义词链表的头指针存放在散列表的第 i 个单元中，因而查找、插入和删除操作主要在同义词链中进行

拉链法适用于经常进行插入和删除的情况

考点追踪：散列表查找效率影响因素（2010、2011、2018、2019、2022、2023、2024）

ASL 主要取决于装填因子 $α$ ，而非简单的 $n$ 。2. 开放定址法删除需打标记，否则会截断查找路径。3. 散列函数选择不当会导致“聚集”现象。4. 熟练掌握 ASL_成功和 ASL_失败的计算。

散列查找及性能分析

散列查找过程

散列表的查找过程与构造散列表的过程基本一致

对于一个给定的关键字 key，查找的操作如下：

根据散列函数可以计算出其散列地址 Addr = Hash(key)
检测查找表中地址为 Addr 的位置上是否有记录，若无记录，返回查找失败
若有记录，比较它与 key 的值，若相等，则返回查找成功标志，否则执行步骤 4
用给定的处理冲突方法计算“下一个散列地址”，并把 Addr 置为此地址，转入步骤 2

注意：要保证在插入时的散列函数运行结果与查找时散列函数的运行结果一致

性能分析

查找成功的平均查找长度：每个关键字的比较次数的和 / 关键字总数

查找失败的平均查找长度：根据散列函数，计算每个查找失败的比较次数的和 / 失败的次数

对同一组关键字，设定相同的散列函数，则不同的处理冲突的方法得到的散列表不同，它们的平均查找长度也不同

从散列表的查找过程可见：

虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需要以平均查找长度作为衡量散列表的查找效率的度量
散列表的查找效率取决于三个因素：散列函数、处理冲突的方法、装填因子
散列表的装填因子一般记为 α，定义为一个表的装满程度，即 $α = \frac{表中记录数 n}{散列表长度 n}$

散列表的平均查找长度依赖于散列表的装填因子 α，而不直接依赖于 n 或 m

直观地看，α 越大，表示装填的记录越“满”，发生冲突的可能性越大，反之发生冲突的可能性越小

散列表例题

将关键字序列 (7, 8, 30, 11, 18, 9, 14) 散列存储到散列表中。散列表的存储空间是一个下标从 0 开始的一维数组，散列函数为 $H (k e y) = (k e y \times 3) M O D 7$ ，处理冲突采用线性探测再散列法，要求装填（载）因子为 0.7

由装填因子 0.7 和数据总数 7，得一维数组大小为 7 / 0.7 = 10，数组下标为 0 ~ 9
根据散列函数和线性探测再散列法，构造出散列表：
查找 18 时，对 18 进行散列函数得 54 % 7 = 5，而和 5 比较不是，根据线性探测与 6 比较不是，最后与 7 比较查找成功，中间共比较了 3 次
查找成功的平均长度是每个关键字查找时的比较次数和除以关键字数，即 (1 + 2 + 1 + 1 + 1 + 3 + 3) / 7 = 12 / 7
查找失败的比较次数是，假如从 0 开始查找到 2 查找失败共比较了 3 次；从 2 开始查找到查找失败比较了 1 次
查找失败的平均长度是散列函数值域的查找失败的比较次数和除以散列函数值域数，即 (3 + 2 + 1 + 2 + 1 + 5 + 4) / 7 = 18 / 7

注意：查找失败要计算的仅仅只是散列函数的值域位置

核心避坑：散列表查找失败 $ASL$ 计算 (2025 绝杀)

线性探测法：分母是散列函数的模数 $p$ （或表长 $m$ ），查找时需持续到第一个 NULL。

拉链法：分母是模数 $p$ 。分子是每个地址对应的链表长度之和。

装填因子 $α$ ：它是衡量散列表性能的最核心因素。

核心结论：散列表效率双杀 (ASL_成功 vs ASL_失败)

装填因子 $α = n / m$ ： $α$ 越大，冲突越多，效率越低。

ASL 成功：基于插入过程，求所有已存入元素比较次数的平均值。

ASL 失败：

线性探测：计算从每个 $H (k e y)$ 可能的入口出发，到遇到第一个“空位”所需的比较次数。

拉链法：计算每个入库链表的长度，不包含空链。注意考纲有时定义空位置也算 1 次比较。

聚集现象：由处理冲突方法（如线性探测）引起。平方探测法和双散列法可有效缓解。

采用链地址解决冲突的话，平均查找长度也差不多，都是比较次数的和除以关键字数

但有时空指针也算比较次数，有时空指针不算比较次数，因题而异

归纳总结

本章的核心考查点是求平均查找长度（ASL)，以度量各种查找算法的性能

查找算法本身依托于查找结构，查找结构又是由相同数据类型的记录或结点构成的，故最终落脚于数据结构类型的区别

不管是何种查找算法，其平均查找长度的计算公式都是一样的

查找成功的平均查找长度 $A S L_{成功} = \sum_{i = 1}^{n} p_{i} c_{i}$

查找失败的平均查找长度 $A S L_{失败} = \sum_{i = 1}^{n} q_{i} c_{i}$

若综合考虑，即 $\sum_{i = 1}^{n} p_{i} + \sum_{i = 1}^{n} q_{i} = 1$ ，若所有元素查找概率相等，则有 $p_{i} = q_{i} = \frac{1}{2 n + 1}$ ；若分开考虑，即 $\sum_{i = 1}^{n} p_{i} = 1$ ， $\sum_{i = 1}^{n} q_{i} = 1$ ，若所有元素查找概率相等，则有 $p_{i} = \frac{1}{n}$ ， $q_{i} = \frac{1}{n + 1}$

虽然综合考虑更为理想，但在实际应用中多数是分开考虑的，因为对于查找不成功的情况，很多场合下没有明确给出，往往会被忽略掉。不过读者仍要注意的是，这两种考虑的计算结果是不同的，考试中一定要仔细阅读题目的要求，以免失误

查找的基本概念 ​

顺序查找和折半查找 ​

顺序操作 ​

一般线性表的顺序查找 ​

有序表的顺序查找 ​

折半查找 ​

折半查找的定义 ​

折半查找的判定树 ​

分块查找 ​

B 树和 B + 树 ​

B 树及其基本操作 ​

B 树的定义 ​

B 树的高度 ​

B 树的查找 ​

B 树的插入 ​

B 树的删除 ​

B + 树的基本概念 ​

散列表 ​

散列表的基本概念 ​

散列函数的构造方法 ​

直接定址法 ​

除留余数法 ​

数字分析法 ​

平方取中法 ​

处理冲突的方法 ​

开放地址法 ​

线性探测法 ​

平方探测法 ​

再散列法 ​

伪随机序列法 ​

拉链法 ​

散列查找及性能分析 ​

散列查找过程 ​

性能分析 ​

散列表例题 ​

归纳总结 ​