查找算法

约 9604 字大约 32 分钟

2025-05-16

注

为了方便算法代码的书写，以下所有代码都是以int类型举例，重要的是算法的思想和性质。

什么是查找

查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。

查找的结果只能有两种，分别为查找成功和查找失败，前者表示在查找表中寻找到了满足条件的元素，后者表示没有在查找表中寻找到满足条件的元素。这里出现的查找表是用于查找的数据集合，其由同一类型的元素组成。

查找表有两种分类分别为：

静态查找表：对查找表只有查找操作，不存在修改元素的操作
动态查找表：对查找表有动态地插入和删除

静态查找容易理解，只存在查找操作而已，常见的静态查找算法有：折半查找、顺序查找、散列查找；动态查找值得说明一下，随着时间的流逝，数据集合中的数据会改变，因为动态查找提供了除查找操作外的插入、删除操作，为了保持查找的高效性，常见的动态查找算法有：二叉排序树的查找、散列查找。

我们查找是根据关键字来进行查找的，那什么是关键字呢？就是用于查找的“标志”，其必然是唯一的，比如要以学生的学号将班上的学生进行排序，这里的学号就是关键字。

评判查找算法效率的重要指标是什么，我们怎样知道该查找算法好不好呢？这个指标就是平均查找长度(ASL)。顾名思义，就是查找到目标元素需要查找的平均次数。

注意

比较次数通常指的是数据元素与目标值进行比较的次数。

ASL=\sum_{i=1}^nP_iC_i

$P_i$ 是查找元素i的概率， $C_i$ 是查找元素i的比较次数，ASL是一个查找算法不能不谈的重要性质。

顺序查找和折半查找

这两个算法是最“耿直”的查找算法了，十分易懂和直接。

顺序查找

顺序查找，显然说的是从一端到另一端依次查找，只要有目标元素就查找成功了，故顺序表和链表都可以使用该算法。

但是该线性表中的元素可能是有序的，也有可能是无序的，这两者的ASL是不同的，接下来一一说明。

一般线性表的顺序查找

为什么说是一般呢，这是因为不论是有序和无序都可以使用这个算法，但一般是给无序线性表使用的，因为有序线性表有自己更优秀的算法！

一般线性表的顺序查找算法

int normal_search(int arr[], int len, int goal){
    for (int i = 0; i < len; i++) {
        if (arr[i] == goal) {
            return i;
        }
    }
    return -1;
}

在这里还可以进行优化，使用哨兵模式，可以将内部的if判断条件全部省去！

原理是将目标元素放在线性表索引为0的位置上，然后从最后一个元素向前遍历，通过在for循环中的判断arr[i]!=goal（和上述的i < len一样的原理，在for循环中i++一次就会判断是否还小于len），遍历的元素是否为目标元素，其一定能在arr中遍历到goal，最后返回对应的索引，不过线性表中不存在时返回的是0。

对于一般线性表顺序查找的ASL分析，假设有n个元素，且每个元素的查找概率相同：

ASL_{查找成功}=\sum_{i=0}^{n-1}\frac{1}{n}(i+1)=\frac{n+1}{2}

ASL_{查找失败}=n

由上述的ASL表达式可知，ASL与n呈线性相关，在n很大时，顺序查找的效率很低，但其对元素的存储和有序性没有任何要求。需要注意的是链表只能进行顺序查找！

有序线性表的顺序查找

不难想到，如果线性表中的元素有序的话，在查找失败时就可直接返回，后续剩余元素的比较都不用进行，降低了查找失败的ASL。

什么时候是失败呢？如果线性表关键字按从小到大排序，查找值为goal，若i位置元素小于goal，且i+1位置大于goal，则失败了。因为i+1位置上的元素都大于goal了，此后的元素必定也大于goal。

有序线性表的顺序查找算法

int order_search_linear(int arr[], int len, int goal) {
    for (int i = 0; i < len; i++) {
        if (arr[i] == goal) {
            return i;
        } else if (arr[i] > goal) {
            return -1;
        }
    }
    return -1;
}

每次判断都有三种可能，等于goal，大于goal，小于goal，等于的话就是查找成功，否则继续判断，这样可以将其抽象为一颗二叉树，该二叉树称为判定树。

矩形结点是虚拟的，也可以称为失败结点！

可知有序的线性表对应的查找成功ASL与一般的类似，不成功ASL更好一些：

ASL_{查找成功}=\frac{n+1}{2}

ASL_{查找不成功}=\frac{1+2+3+...+n+n}{n+1}=\frac{n}{2} + \frac{n}{n+1}

折半查找

折半查找需要利用有序和随机存取特性，故只能用于顺序存储结构的线性表！

通过不断缩小目的元素所在的区间，直到找到或达到结束条件为止。比如从1-5中查找2，首先对比1-5中间的元素，显然3大于2，故2只能在1-3之间，依次类推从而找到2。

折半查找算法

int binary_search(int arr[], int len, int goal){
    int low = 0;
    int high = len - 1;
    int mid;
    while(low <= high){
        mid = (high - low) / 2 + low;
        if(arr[mid] == goal){
            return mid;
        }
        else if (arr[mid] > goal){
            high = mid - 1;
        }
        else if (arr[mid] < goal){
            low = low + 1;
        }
    }
    return -1;
}

每次比较都是比较的区间中间元素，故可以将折半查找的判定树抽象为一颗平衡二叉树，任意一个结点的子树高度相差不会超过1。

因为整体呈树形，其查找的时间复杂度显然为 $O(log_2\,n)$

其对应的ASL为：

ASL_{查找成功}=\frac{1}{n}(1×1+2×2+...+h×2^{h-1})=\frac{n+1}{n}log_2(n+1)-1\approx log_2(n+1)-1

查找失败时的ASL根据之前比较的次数之和再除以整体的失败结点个数，上图的计算失败ASL如下：

ASL_{查找失败}=\frac{2×1+3×6}{7}=\frac{20}{7}

要查找在区间 $(11,14)$ 的失败结点，首先得比较上面的16、11、14，故比较次数为3，同一层的失败结点有6个，故为3×6，式子分子上的2×1类似！

分块查找

有没有办法将上面的算法综合一下呢？答案是有的，也就是分块算法。

通过一个索引数据结构快速找到对应区间，再从区间中查找目标元素，这就是该算法的基本思想。其和查字典的思想类似，先定位，再查找。

因为查找表中的元素被分为多个区间，且可以用区间内最大元素构造索引表，故区间之间元素需要有序（前一个区间内的最大值小于后一个区间的最小值），区间内元素无所谓。

用区间内最大元素构成索引表，若要查找的元素小于索引表中元素时，就从查找表对应的索引处开始查找元素。

如：要查找上图13元素，先从索引表中确定13小于16，其索引值为3，所以从查找表索引3开始查找，找到13结束。

显然，查找算法的ASL为查找索引表的ASL加上查找查找表的ASL。设：长度为n的查找表均匀分为b块，每块有s个记录，在等概率的条件下，在块内和索引表中都采用顺序查找，则：

ASL_{查找成功}=\frac{s+1}{2} + \frac{b+1}{2}

ASL_{查找失败}=\frac{b}{2}+s

在查找成功的情况下，若 $s=\sqrt n$ ，则平均查找成功长度有最小值 $\sqrt n + 1$ ，通过基本不等式可轻松得出。

虽然分块查找使用额外的存储空间存储索引表，查找索引表也增加了一定开销，但这样带来的提升也是不小的，更普遍的情况是带来性能的提升大于开销。这也是环绕计算机的一个核心优化手段——空间换时间！

因为需要快速定位到查找表中的位置，所以需要随机存取特性，故此算法只适用于顺序存储结构。

树形查找

为什么会出现树形查找呢？我们知道保持一颗优秀的二叉树可以使查找效率很高，因为此时无论是插入、查找、删除，其时间复杂度都为 $O(log_2n)$ 。

这里引入的树形查找就是为了构造并保持这种优秀的二叉树结构！其最基本的结构就是二叉排序树，在二叉排序树之后的所有的树形查找都是在此基础上添加了部分限制形成的。

因为树形查找是一种动态查找，故在此还需讨论结点的插入与删除操作。

二叉排序树（BST）

定义：是一颗空树，或者满足下列性质的二叉树：
若左子树非空，则左子树上所有结点的值均小于根结点的值
若右子树非空，则右子树上所有结点的值均大于根结点的值
左右子树也分别为一颗二叉树

意思就是左小右大，根据这个性质可知根结点为中间值，且用中序遍历二叉排序树可以得到一个递增的有序序列。

BST的查找

根据性质不难得出，查询从根结点开始，若根结点不为空，则用其值与目标元素比较，若相等，则查找成功；若小于，则查找右子树；否则，则查找左子树，其余结点与根结点操作类似。

显然可知，此操作为一个递归操作！

BST的递归查找算法

/*
 * 传入BST的根结点和目的元素
 */
int recursion_search(bst_tree_node *tree, int goal){
    if(tree == NULL){
        return 0;
    }
    if(tree->data == goal){
        return 1;
    }
    else if(tree->data < goal){
        return recursion_search(tree->right, goal);
    }
    else{
        return recursion_search(tree->left, goal);
    }
}

BST的插入

对于动态查找表，可以进行插入操作，因为插入后仍需保持原本的性质，所以需要在查找失败后进行插入，若BST中本来就有要插入的元素，则什么操作都不会执行。

由上述可知，插入的位置一定是在最后一个失败结点的左或右孩子位置。

BST的插入算法

BST的删除

对于BST的删除也要注意不能破坏其性质，其可以分为3种情况！

删除的结点为叶子结点，显然删除后没有任何影响，直接删除则可（轻如鸿毛）；
删除的结点有一颗子树，删除后，只需要用其子树的根结点替代被删除的结点则可（父债子偿）；
删除的结点有两颗子树，删除后，只需要用直接后继或者直接前驱替代该结点则可，然后就转换为了前两种情况（斗转星移）。

这三种情况十分容易理解，故不再赘述。

BST的条件是最宽松的，以至于可能导致其退化为链表，导致 $ASL_{查找成功}=\frac{n+1}{2}$ ，也有可能是十分理想的情况，左右子树高度相差不超过1，也就是平衡二叉树，其 $ASL$ 与树高 $O(log_n)$ 成正比。

BST的ASL计算是得根据具体的BST形状用ASL计算公式计算的。

BST和折半查找类似，平均时间性能也差不多，但BST的形状会因为关键字的插入顺序不同而不同，折半查找不会，其判定树是唯一的。而且BST是一种动态查找表，折半查找是静态的，所以BST的插入、删除操作十分容易实现，时间复杂度为 $O(log_2n)$ ，若折半查找也存在插入、删除操作，时间复杂度就为 $O(n)$ ，因为其“牵一发要动全身”。

平衡二叉树（AVL）

上面的BST条件太宽松了，所以会导致退化到链表，若在BST性质的基础上再加上一些限制条件，则就可以避免这种退化现象的发生，故引出平衡二叉树的定义

在二叉树的定义基础上再添加一条：任意结点的左、右子树高度差的绝对值不超过1，这个绝对值称为平衡因子。

AVL的本质仍是一颗BST！

上图结点中的值为该结点的平衡因子。

AVL的插入

和BST类似，首先也得找到最后一个失败结点，然后插入到其左或右孩子结点上，但这时候就不能直接“跑路”了，还需要确保其仍是一颗AVL，若不是了，则要经过一系列操作让其变为一颗AVL，操作的对象为最小不平衡子树，也就是让从插入结点位置向上找到的第一个平衡因子大于1的结点作为最小不平衡子树的根结点。

若添加后仍是AVL就好办，不需要任何操作，但若不是AVL了，就有4种情况，分为对应着4种操作：

操作的最小不平衡子树的根结点为 A。

RR（左单旋操作）：新结点在 A 的右孩子的右子树上插入，A 的右孩子为 B，则需要将 B 代替 A 作为根结点，A 作为 B 的左孩子，B 原本的左子树作为 A 的右子树
LL（右单旋操作）：新结点在 A 的左孩子的左子树上插入，A 的左孩子为 B，则需要将 B 代替 A 作为根节点，A 作为 B 的右孩子，B 原本的右子树作为 A 的左子树
RL（右左双旋操作）：新结点在 A 的右孩子的左子树上插入，A 的右孩子为 B，B 的左子树的根结点为 C，则需要先将 C 进行右旋操作，让 C 代替 B 的位置，然后再对 C 进行左旋操作，代替 A 的位置
LR（左右双旋操作）：新结点在 A 的左孩子的右子树上插入，A 的左孩子为 B，B 的右子树的根结点为 C，则需要先将 C 进行左旋操作，让 C 代替 B 的位置，然后再对 C 进行右旋操作，代替 A 的位置

因为AVL的旋转操作较为简单，故单旋和多旋各举一个例子。

AVL的删除

删除过程的前半部分和BST的删除完全一样，后半部分调整和AVL的插入调整类似。

首先先删除目的元素，删除后和插入一样，可能导致不再满足AVL的性质，若为不满足AVL性质的情况，则需要进行旋转操作。

从删除结点w位置往上找，一个平衡因子大于1的结点作为最小不平衡子树的根结点z，y为z的最高子树根结点，x为y的最高子树根结点，接下来就和AVL插入操作后的调整一样了，看x在z的什么位置，就对应什么操作，这里就不再赘述了，需要注意的一点是旋转操作会传播，调整后可能又会破坏AVL的性质，所以可能又会调整，甚至调整至根结点，导致树高减一。

AVL的查找

和BST的查找完全一样，只不过AVL不会出现BST那样的极端情况（退化为链表），查找效率比BST好，为 $O(log_2n)，$ 除此之外，AVL还多出了一些性质：

设 $n_h$ 为深度为h的AVL中含有的最少结点数

则有 $n_0=0,n_1=1,n_2=2,n_3=4,...,n_h=n_{h-2}+n_{n-1}+1$ 。

使用该结论，可以很快得出高为h的AVL含有最少的结点数为多少，还可以得出含有结点数为n的AVL高最大为多少。

红黑树（RBT）

在 AVL 中插入或者删除一个结点后，会频繁地调整全树整体的拓扑结构，这样的代价是很大的，究其原因还是条件太过严格，故为了减小消耗，引入条件稍微宽松的红黑树。

RBT：可以是一颗空树或者满足以下条件的二叉树：
每颗结点要么是红色的，要么是黑色的
根节点是黑色的
叶结点（虚构的外部结点，NULL 结点）都是黑色的
不存在两个相邻的红结点
满足 BST 结点值的关系
每个结点到任意叶子结点的简单路径上，所含有的黑色结点数相同

引入虚拟结点的原因是为了保证内部结点左右孩子不为空。

红黑树有个 黑高（bh） 属性。

黑高定义：从某结点出发（不包含该结点）到达一个叶子结点的任意一个简单路径上的黑色结点个数。

根据RBT的定义，可以得出一些好用的结论：

从根到叶结点的最长路径不大于最短路径的2倍
有n个内部结点的RBT的高度 $h\le 2log_2(n+1)$
RBT插入的结点初始为红色

分析：

第一个结论：在最短时，路径上的所有结点都为黑色，而最长时，是红黑相间的，故最长的路径不会超过最短的路径 2 倍
第二个结论：因为在 $bh = h_b$ 时，RBT 的最少内部结点数 $n=2^{h_b}-1$ 个，又因为 RBT 的 $h\le2h_b$ ，故在 RBT 的内部结点树高为 $h$ 时有： $n \ge 2^{\frac{h}{2}} - 1$ ，化简后可得
第三个结论：插入时着红色更为方便，若父结点为黑色就不用进行额外的操作，但插入的结点若初始着为黑色，则不管怎样都会破坏RBT的性质

RBT的插入

仍然是需要找到要插入的位置，插入后结点初始为红色，若父结点为黑色，显然还保持着RBT的性质，直接结束，若父结点为红色，则需要通过旋转+变色进行调整，使其满足RBT的性质。

具体怎样操作呢？插入位置若为根结点则直接插入并将插入结点再次染色为黑色则可；若插入结点位置的父结点为黑色，仍保持RBT性质，直接结束；若插入结点位置的父结点为红色，则要看插入结点的叔结点，根据叔结点的颜色又将该情况分为两类：

叔结点为黑色：看插入结点的位置位于爷结点的何处，以确定采用何种旋转操作，旋转操作和AVL一样，染色只在LL或RR操作时进行，将最小方的父结点和爷结点染成相反的颜色则可
叔结点为红色：这个简单，将插入结点的叔结点、父结点、爷结点染成相反的颜色，然后将爷结点视为新结点继续调整，直至满足RBT性质

RBT的删除

B树和B+树

对于B树和B+树，重点掌握B树，B+是B树的一种变体，它们都是专门为优化磁盘或其他外部存储设备操作而设计的数据结构。

B树及其基本操作

B 树的定义：为空树或者满足以下性质的 m 叉树：
树中每个结点最多有 m 个子树，最多有 m - 1 个关键字
若树中不是只有一个根结点，则根结点至少有 2 颗子树，至少有 1 个关键字
除了根结点外，其余的内部结点至少有 $⌈\frac{m}{2}⌉$ 颗子树，至少有 $⌈\frac{m}{2}-1⌉$ 个关键字
每个结点中都是由关键字和指向子树根结点的指针构成，满足广义上的左小右大
所有叶子结点都在同一层上（所有结点的平衡因子为0），并且不存在信息（视其为折半查找判定树中的失败结点，其并不存在，是虚构的，也就是外部结点）

平衡查找树

平衡查找树是一种自平衡的、有序的树形数据结构，用于高效存储和检索数据。它在动态插入、删除操作后能自动调整结构，确保最坏情况下的时间复杂度保持为 O(log n)

常见的平衡查找树有：AVL、RBT、B 树。对于不同的平衡查找树会有不同的约束条件！

简单解释一下：

对于 AVL ，约束条件是任意一颗结点的左右子树高度差不能相差 1；对于这里的 B 树，约束条件是每个结点的子树高度相同，结点关键字个数和子树个数限制。

使用场景：

文件系统：早期的一些文件系统（如 NTFS）中，B 树被用于文件索引，但现代文件系统更多地倾向于 B+ 树
MongoDB 的索引： NoSQL 数据库 MongoDB 的默认索引就是 B 树结构。由于 MongoDB 是文档型数据库，其索引可能需要支持更灵活的数据结构，B 树在这种场景下有其优势。当查询单个确切的值且数据可能在任何层级时，B 树理论上可能比 B+ 树少一次 I/O（如果数据恰好在内部节点被找到）

B树的查找

和 BST 的查找类似，只不过每个结点内部是多个关键字构成的有序表，换句话说，就是BST只有两个分支，而B树有多个分支。

因为 B 树常存储在磁盘上，所以在查找关键字时，需要将磁盘上的结点调入内存，然后在内存中采用顺序查找或者折半查找查找目的元素，若目标元素在该结点中，则返回查找成功，否则根据内存中结点的信息调入合适的下一个B树结点，以此类推，故目标结点在 B 树上的层数决定了 B 树的查找效率（因为磁盘上查找需要进行缓慢的IO操作）。

查找的过程：先查找根结点，若在根结点中找到了目标元素，则返回查找成功，否则到满足条件的子树中去找（和 BST 一样，只不过多了几个分支罢了），一直到找到目标元素或者找到叶子结点为止。

B树的高度

设：一颗关键字个数为 $n(n\ge1)$ ，高度为 $h$ ，阶数为 $m$ 的 B 树，则：

若要使该 B 树的高最大，则每个结点中的关键字数要最少，子树个数也要最少。每个结点的关键字最少为 $⌈\frac{m}{2} - 1⌉$ ，子树最少为 $⌈\frac{m}{2}⌉$ ，故有 $n+1\ge 2×⌈\frac{m}{2}⌉^{h-1}$ ，所以可以得到： $h\le log_{⌈\frac{m}{2}⌉}((\frac{n+1}{2})+1）$
若要使该 B 树的高最小，则每个结点中的关键字数要最多，子树个数也要最多。每个结点的关键字最多为 $m-1$ ，子树个数最多为 $m$ ，故有 $n\le m^h-1$ ，所以可以得到： $h\ge log_m(n+1)$

最终得到 h 的取值范围为：

log_m(n+1)\le h\le log_{⌈\frac{m}{2}⌉}((\frac{n+1}{2})+1)

B树的插入（分裂）

B树的插入一定是在终端结点中，原理和BST的插入一致，但B 树的插入比 BST 的插入复杂得多，因为将关键字插入到终端结点后可能导致不在满足 B 树的性质，因为除根结点外每个结点关键字个数最多有 $m-1$ 个，所以插入结点后可能会违背了这条性质，此时需要进行调整！

设插入的结点为 w

首先需要找到关键字插入的终端结点，如果在对应的终端结点中插入新结点后其关键字数仍小于等于 $m-1$ ，则结束；

否则先将关键字插入，再将该终端结点从 $⌈\frac{m}{2}⌉$ （结点中第 1 个关键字的位置为 1 ，以此类推）处分裂，左侧关键字保留在该终端结点中，右侧关键字放到一个新的结点中，终端结点中 $⌈\frac{m}{2}⌉$ 处的关键字提高到父结点中，若父结点被提入一个关键字后又破坏了最多关键字的性质，则重复此过程，直到满足B树性质为止，最多提升到根结点，使得树高增加 1。

B树的删除（合并）

因为除根节点外每个结点的关键字个数最少要有： $⌈\frac{m}{2}-1⌉$ 个，所以如果删除结点后违背了这条性质就需要进行调整！

当删除的关键字 k 不在终端结点时，在将 k 删除后会使用 k 的前驱结点或者后继结点进行补充，故最终可以将删除关键字的后果转移到终端结点上，我们就只用讨论在终端结点上删除的可能了。

若删除终端结点上的关键字后，被删的终端结点中关键字数仍然大于等于 $⌈\frac{m}{2}-1⌉$ ，则直接结束。
若删除终端结点上的关键字后，被删的终端结点中关键字数小于 $⌈\frac{m}{2}-1⌉$ ，但是兄弟结点（左右都行）的关键字数大于 $⌈\frac{m}{2}-1⌉$ ，也就是说有兄弟“够借”，就会先从父结点中拿一个关键字到删除关键字的终端结点中，然后再从兄弟那拿一个关键字到父结点中（注意兄弟结点和父结点拿的关键字）
若删除终端结点上的关键字后，被删的终端结点中关键字数小于 $⌈\frac{m}{2}-1⌉$ ，但是兄弟结点（左右都行）的关键字数小于等于 $⌈\frac{m}{2}-1⌉$ ，也就是说所有兄弟都“不够借”，则将该终端结点的关键字删除后，让这个终端结点合并一个兄弟结点+父结点中的一个关键字进行合并（注意父结点选择的关键字）

同样的，在取了父结点中的一个关键字后可能会造成父结点不满足性质，还是使用合并的方法进行处理，直到满足性质（最多将 B 树根结点删除，使得树高减少 1）。

设有一个 3 阶 B 树，我们对其进行插入和删除操作，看看会怎样调整

B+树及其基本操作

B+树：是应数据库所需而诞生的一种 B 树的变形树，一颗 m 阶的 B+树应满足下列条件：
每个分支结点最多有 m 颗子树
非叶根结点至少有 2 颗子树，其余分支结点至少有 $⌈\frac{m}{2}⌉$ 颗子树
结点的子树棵数和关键字个数相等
所有叶子结点中包含全部关键字以及只想相应记录（一般指数据存储的磁盘地址）的指针，叶子结点中将关键字有序排列，并且相邻叶子结点按大小顺序相互连接起来（支持顺序查找）
所有分支结点中仅包含它各个子结点中关键字最大值以及指向子结点的指针

使用场景：

关系型数据库索引：这是 B+ 树最主要、最广泛的应用场景。几乎所有的关系型数据库（如 MySQL 的 InnoDB 存储引擎、Oracle、SQL Server 等）都使用 B+ 树作为其底层索引结构。这是因为数据库查询中频繁涉及： 精确查找： WHERE id = 123； 范围查找： WHERE price BETWEEN 100 AND 200，WHERE name LIKE 'A%'；排序： ORDER BY column； 全表扫描：在某些情况下，通过遍历叶子节点链表比其他方式更高效；
文件系统：许多现代文件系统（如 Linux 的 Ext4、ReiserFS 等）也广泛使用 B+ 树来组织文件和目录的索引。这是因为文件系统也需要高效地查找文件、遍历目录内容和进行范围操作（比如查找某个日期范围内的文件）

B+树中的所有分支结点仅其索引作用，只存在对应子树的最大关键字和指向该子树的指针，不存在记录的地址，故一个磁盘块可以存储更多的关键字信息，使得磁盘 IO 操作次数更少，查找速度更快！

查找有两种方式：其一是从根结点开始的多路查找；其二是从关键字最小的节点开始在链表上顺序查找。

B树和B+的差异

B树，其中结点含有n个关键字，其会有n+1个分支，但B+树不是，结点中含有n个关键字，其只会有n个分支
B树，每个结点中的关键字个数范围是更严苛的
B+树中，叶结点包含信息，分支结点只起索引作用
B+树既可以树形查找又可以顺序查找，其最下方是一条链表。

散列表

在之前学习的查找都是基于关键字的比较的，那我们能不能像访问数组一样直接的访问想要查询的关键字呢？

答案是肯定，这一节要学习的散列表就实现了这种功能，使用散列函数将要查找的关键字映射为存储的地址，就可以通过存储地址直接访问到。

散列表的基本概念

散列函数（哈希函数）：将查找表中的关键字映射为该关键字对应的地址的函数
散列表：根据关键字而直接进行访问的数据结构，也就是建立了关键字和存储地址之间的一种直接映射关系
冲突：散列函数将两个或两个以上的不同关键字映射到同一地址
同义词：发生冲突的不同关键字

因为可以直接访问关键字的存储地址，故使用散列表进行查找的理想时间复杂度为： $O(1)$ 。

散列函数的构造方法

构造哈希函数是非常重要的，一个优秀的哈希函数会让“冲突”次数大大减少，相反地，一个差的哈希函数会让冲突充满整个映射过程！一般来说有以下 4 种构造方法：

直接定址法：取关键字的某个线性函数值为散列地址： $Hash(key)=a*key+b$ 。这种设计方法不会发生冲突，但如果 key 之间相差太多会造成空间的浪费。
除留余数法：取一个小于且最接近查找表长度 m 的质数 p，并使用后面的公式进行映射： $Hash(key)=key \% p$ 。使用这种方案可以尽可能地减少发生冲突的概率。
数字分析法：数字分析法适用于关键字本身由多位数字或字符组成的情况。其核心思想是分析关键字的各位分布规律，选取分布较为均匀的若干位作为散列地址。举个例子：假设关键字是 8 位十进制数字（如学号），统计发现前 3 位是学校编号（所有关键字相同），中间 2 位波动较小，后 3 位随机分布。则可直接取后 3 位作为散列地址
平方取中法：平方取中法通过将关键字平方后取中间几位作为散列地址。目的是利用平方运算扩大关键字的差异，使散列地址分布更均匀。举个例子：关键字为 123，散列地址需要 2 位，123 平方后的值为：15129，我们就可以取 51 作为该关键字的散列地址。

ok，在解决了怎样构造哈希函数后，我们来说说怎样处理“冲突”吧！

处理冲突的方法

但是散列表也不全是优点，在数据量大并且哈希函数取得不好的情况下，会经常发生“冲突”！

那怎样解决这个问题呢？在这里会介绍和。

开放地址法可以分为多种，但都是围绕着增量序列展开的！

开放地址法中又可以分为 4 种具体的实现方式。

线性探测法： $d_i$ 以线性增长（ $d_i=1,2,3...,m-1$ ）的方式探测对应的地址是否存在关键字，只要表没有被填满就一定可以找到一个没有存储关键字的地址。其缺点也很大，可能会让本该在第 i 个散列地址的元素存到第 i+1 个散列地址，本该在 i+1 地址的元素又存到了 i+2 个散列地址，以此类推，造成大量的元素在相邻的散列地址上“聚集”起来，使得查找效率大大降低！
平方探测法： $d_i$ 以平方增长（ $d_i=1^2,-1^2,2^2,-2^2...,k^2,-k^2$ ）的方式探测，需要散列表长度 m 必须为可以表示为 $4*k+1$ 的素数。这种方式可以解决上面方法存在的“堆积”问题，缺点是不能探测所有的元素，但至少可以探测一半的元素。
双散列法：需要使用两个散列函数，当通过第一个散列函数发生“冲突”时，则利用第二个散列函数计算 $d_i$ ,其散列函数为： $H_i=(Hash_1(key)+i*Hash_2(key))\%m$ ，其中 i 为发生冲突的次数，初始值为 0。
伪随机序列法： $d_i$ 为伪随机序列。

在使用开放地址法时，不能随意地物理删除表中的已有元素，因为在查找时是遇到满足条件的元素或者为空时结束，如果物理删除了某个元素则可能导致查找中断！解决方式是：使用一个删除标记进行逻辑删除，这样做的副作用是空间利用率会下降；在多次的逻辑删除后，虽然散列表看起来比较满，但是有许多空间并没有被真正地利用。

计算查找失败的平均查找长度时，要注意余得多少，查找失败的个数就为多少，而且需要特别注意逻辑删除！

链表法

因为可能有多个关键字会被映射到同一个存储地址，故可以将这些“同义词”用一个链表连起来！

这样散列表中存储的就为指向存入元素的指针了。

举个例子：关键字序列为{12，24，1，2，3}，散列函数为：Hash(key)=key%12。

因为是链表，所以非常适合插入、删除操作多的情况。

散列查找及性能分析的应用

查找过程：和构造类似，也是通过散列函数，传入要查找的关键字计算出散列地址。

检查地址上是否存储有记录，若没有记录则查找失败；若有记录且关键字相同则返回查找成功；若有记录但是关键字不相同，则需要根据给定的处理冲突方法进行探测。

影响散列表查找效率的因素：散列函数、处理冲突的方法、装填因子。

装填因子：一般定义为α，用于形容一个散列表的装满程度。

α=\frac{表中的记录数}{散列表长度}

散列表的平均查找长度（ASL）依赖是α 而不是“表中的记录数”或“散列表长度”，使两者的共同作用！

当然α 越大表示散列表越“满”，此时就更容易发生冲突，故需要制定在α 大于多少时对散列表进行扩容！

更新日志

2025/6/24 14:06

查看所有更新日志

51d1d-docs:数据结构-查找算法补充散列表查找失败ASL计算🚀于 2025/6/24
9427a-docs:数据结构-查找算法-除RBT的删除外，所有整理完毕🚀于 2025/6/24
f105f-docs:数据结构-查找算法-散列表构造函数🚀于 2025/6/22
58cb1-docs:数据结构-查找算法🚀于 2025/6/22
5d706-docs:数据结构-查找算法🚀于 2025/6/22
18b39-docs:数据结构-查找算法🚀于 2025/6/21

版权所有

版权归属：代码・生活・THINKING

许可证：署名 4.0 国际 (CC-BY-4.0)