【数据结构复习之路】查找（严蔚敏版）万字详解

专栏：数据结构复习之路

复习完上面四章【线性表】【栈和队列】【串】【数组和广义表】【树和二叉树】【图】，我们接着复习查找，这篇文章我写的非常详细且通俗易懂，看完保证会带给你不一样的收获。如果对你有帮助，看在我这么辛苦整理的份上，三连一下啦。

一、查找的相关概念

二、静态查找表

2.1 顺序查找

查找效率分析：

2.2 折半查找

查找效率分析：

2.3 分块查找（索引查找）

查找效率分析：

2.4 总结

三、动态查找表

3.1 二叉排序树

二叉排序树的查找：

二叉排序树的插入：

二叉排序树的构造：

二叉排序树的删除：

查找效率分析：

3.2 平衡二叉树

平衡二叉树的插入：

3.3 B- 树

B-树的查找：

B-树的插入：

B-树的删除：

3.4 B+ 树

B+树的查找：

总结：

四、散列查找（哈希表）

4.1 哈希函数的构造方法

1. 除留余数法（最常用）

2. 直接定址法

3. 数字分析法（数字选择法）

4. 平方取中法（较常用）

5. 折叠法

6. 随机数法

4.2 处理冲突的方法

1、开放定址法

2、再散列法（再哈希法）

3、溢出区法

4、链地址法

4.3 哈希表的查找及其分析

结尾：

Reference

一、查找的相关概念

查找表：由同一类型的数据元素(或记录)构成的集合。（是一种统称，不是一种新的数据结构）

对查找表经常进行的操作为：

查找特定元素是否在查找表中；
检索（读取）查找表中某个元素的值；
查找失败时，将目标元素插入到查找表中；
查找成功时，将目标元素从查找表中删除。

静态查找表: 对查找表只进行前两种操作。

动态查找表：不仅限于前两种操作。

关键字：数据元素中某个数据项的值，用以标识一个数据元素，如果是唯一标识，则称为主关键字。比如你对应的学号。

查找是否成功：根据给定的值，在查找表中确定一个其关键字等于给定值的元素，如果表中存在这样元素，则称查找成功，否则，不成功。

除了时间复杂度之外，还有一种衡量查找算法好坏的方法。

几乎所有的查找算法执行过程中只做一件事，就是将表中元素逐一和目标元素做比较，因此比较次数的平均值（又称平均查找长度，简称 ASL）可以作为衡量查找算法好坏的依据。

一个查找算法的平均查找长度，可以借助下面的数学公式计算出来：

Pi：默认情况下表中各个元素被查找到的概率是相同的，为1/n。在某些特殊场景下，可能会指定表中各个元素被查找到的概率。

ASL 值越大，表明查找算法的性能越差，执行效率越低。

二、静态查找表

2.1 顺序查找

顺序查找，又叫 “ 线性查找 ”。通常用于线性表。

算法思想：从表的一端开始，逐个进行记录的关键字和给定值的比较。

//这里采用的动态数组
typedef struct {
    ElemType  * elem; //动态数组基址 
    int TableLen;   // 表长度
}SSTable;

顺序查找算法：

比如查找66是否存在于如下顺序表中（显然是查找失败的）

int Search_	Seq(SSTable ST , ElemType key)
{
    ST.elem[0] = key; //哨兵（0号位置存储） 
	int i;
	for (i = ST.TableLen ; ST.elem[i] != key ; --i);
	
	return i;//查找成功，则返回元素下标；查找失败，则返回0 
}

这种设置哨兵的写法，可以无需判断是否越界，效率比下面的算法更高。

int Search_	Seq(SSTable ST , ElemType key)
{
	int i;
	for (i = 0 ; i < ST.TableLen && ST.elem[i] != key ; ++i);
	
	return i == ST.TableLen ?  -1 : i;
}

查找效率分析：

假设每个记录的查找概率相等：Pi =1/n ，那么查找成功的ASL为：
查找不成功时，关键字的比较次数总是 n + 1 次。

我们大部分讨论查找成功时的平均查找长度和查找不成功时的比较次数。

但有些学校可能也会考察：查找不成功时的ASL，这里查找不成功的ASL恰好等于 n + 1，因为其查找失败的情况只有一种，因此概率为100%，之前共比较了n + 1次，所以ASL就为 n + 1。

通过熟练使用【查找判定树】，可以很容易求得一个查找算法的ASL。

顺序查找的优化：

【1】如果使表中元素有序，那么可以缩减查找不成功的ASL。

比如查找表有序存放：7 13 19 29 37 43

那么其生成的查找判定树为：

图中粉色结点属于：查找失败的情况

对于上图，其查找成功的ASL为：

因为上图共有 n + 1种查找失败的情况，并且假设对于每个查找失败的情况等概率发生。

那么查找失败的ASL 为：

【查找判定树总结】

【2】若各个关键字被查找的概率不同，可按被查概率降序排列，那么可以缩减查找成功时的ASL

当然上述优化只能减少部分比较次数，但是顺序查找算法的时间复杂度还是：O（n），并不能实现质的飞跃。

2.2 折半查找

折半查找，又称 “ 二分查找 ”，仅适用于有序的顺序表。顺序表有随机查找访问的特性，而链表没有（比如访问mid中间元素，你通过链表存储，只能循环遍历找）

找到了目标元素 33，二分查找算法执行结束。

//折半查找算法
int Search_Bin(SSTable ST, keyType key) {
    int low = 0; // 初始状态 low 指针指向第一个关键字
    int high = ST.length - 1; // high 指向最后一个关键字
    int mid;
    while (low <= high) {
        mid = (low + high) / 2; // int 本身为整形，所以向下取整
        if (ST.elem[mid].key == key) // 如果 mid 指向的同要查找的相等，返回 mid 所指向的位置
        {
            return mid;
        }
        else if (ST.elem[mid].key > key) // 如果mid指向的关键字较大，则更新 high 指针的位置
        {
            high = mid - 1;
        }
        // 反之，则更新 low 指针的位置
        else {
            low = mid + 1; //既然mid即其以下的元素都不可能为key，所以low就从mid + 1往上找
        }
    }
    //未在查找表中找到目标元素，查找失败
    return -1;
}

查找效率分析：

折半查找判定树的构造：

对序列不断求出mid（向下取整），然后分层。

比如查找表存储的元素序列为：

所以根据其【查找判定树】，容易得：

在不考虑失败结点，一个折半查找判定树有如下性质：

如果mid是向下取整，那么右子树结点数 - 左子树结点数 = 0或1
如果mid是向上取整，那么左子树结点数 - 右子树结点数 = 0或1
折半查找判定树是平衡的二叉排序树
若查找表有n个关键字，则失败结点有n+1个
树高h = $\left \lfloor log_{2}n \right \rfloor+1$ （不包含失败结点）

【总结】

二分查找算法的时间复杂度为O(logn)，平均查找长度为：

这个ASL对应的是查找成功的ASL，如果你能画出【二分查找的判定树】，那么这个公式还是建议别去记，因为 $log_{2}(n+1)$ 不好开出来！

⚠️注意：折半查找的速度不一定比顺序查找更快，比如要查找的元素刚好是第一个元素，那么肯定是顺序查找先查找到啊。

2.3 分块查找（索引查找）

条件：块内无序，块间有序

ElemType List[listLength];//原顺序表实际存储元素（没分块前）
typedef struct{
	ElemType maxValue; //每个分块中的最大值
	int low , high; //每个每块在原顺序表中对应的前后边界
} Index[Klength]; //分块后，存储每个分块的数组（也叫索引表）

查找过程：先确定待查记录所在块（顺序或折半查找），再在块内查找（顺序查找）。

【1】比如在块间和块内都顺序查找：先依次对比10、20。当对比30时，发现22小于30，就进入其对应的【low，high】分块中，依次对比27，22，最后查找到22。

【2】比如在块间折半查找，块内顺序查找：

当最后折半查找：low > high时，此时折半查找退出，就以low对应的分块去进行顺序查找，因为最终 low 左边的分块（high）一定小于查找目标，high 右边的分块(low)一定大于查找目标.

⚠️注意：low超出了索引表范围，那么一定是查找失败的。

查找效率分析：

每个元素被查概率一般都是等概率的： $\frac{1}{n}$ ，所以关键是求得找到每个元素需比较次数：

查找失败的情况太复杂了，所以一般不会考察。

如果每个分块都是等长的，那么就能推导出它的ASL公式：

若将长度为 n 的表均分成 b 块，每块含 s 个记录 (b = n / s)；并设表中每个记录的查找概率相等，则每块查找的概率为 1/b,块中每个记录的查找概率为 1/s。

显然 $n^{\frac{1}{2}}+1$ 比单纯的顺序查找好，但比单纯的折半查找差！

2.4 总结

三、动态查找表

3.1 二叉排序树

typedef struct BSTNode{
	int key;
	struct BSTNode *lchild , *rchild;
}BSTNode , *BSTree;

对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

二叉排序树的查找：

因为左子树节点值 < 根结点值 < 右子树结点值。

所以，若树非空，目标值与根结点的值比较：

若相等，则查找成功
若小于根结点，则在其左子树上查找，否则在其右子树上查找

查找成功，返回结点指针；查找失败，返回NULL

比如在如下二叉排序树中查找元素32：

非递归代码：

BSTNode *BST_Search(BSTree T , int key)
{
	while (T != NULL && key != T->key)
	{
		if (key < T->key) T = T->lchild;
		else T = T->rchild;
	}
	return T;
}

递归代码：

BSTNode* BST_Search(BSTree T, int key) {
    if (!T || key == T->key) {
        return T;
    }
    else if (key < T->key) {
        return BST_Search(T->lchild, key);
    }
    else {
        return BST_Search(T->rchild, key);
    }
}

二叉排序树的插入：

若原二叉排序树为空，则直接插入结点；否则，若关键字 k 小于根结点值，则插入到左子树，若关键字 k 大于根结点值，则插入到右子树。

比如在如下二叉排序树中插入元素30：

⚠️注意：新插入的结点一定是叶子结点！

int BST_Insert(BSTree &T , int k)
{
	if (T == NULL)
	{
		T = (BSTNode *)malloc(sizeof(BSTNode));
		T->key = k;
		T->lchild = T->rchild = NULL;
		return 1;//插入成功 
	}
	else if (k == T->key){ //树中存在相同关键字的结点，则插入失败 
		return 0;         
	}
	else if (k < T->key)
	{
		return BST_Insert(T->lchild , k);
	} 
	else {
		return BST_Insert(T->rchild , k);
	}
}

二叉排序树的构造：

利用BST_Insert ( )函数，可以实现二叉排序树的构造：

void Create_BST(BSTree &T , int str[] , int n)
{
	T = NULL;
	int i = 0;
	while (i < n)
	{
		BST_Insert(T , str[i]);
		i++;
	}
}

二叉排序树的删除：

删除二叉排序树中已有的元素Z，必须确保整棵树还是一棵二叉排序树。

1、Z 是叶子结点：可以直接摘除，整棵树还是二叉排序树。如下图删除21和65。

2、若结点 Z 只有一棵左子树或右子树，则让 Z 的子树成为 Z的父结点的子树，代替Z的位置。如下图删除13和60。

3、若结点Z有左、右两棵子树，则令Z的直接后继（或直接前驱）代替Z，然后从二叉排序树中删除这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。

那么删除下图的50，就有两种情况：

令Z的直接后继代替Z （Z的直接后继就是在树与二叉树那一章讲：线索二叉树找前驱和后继）：Z的后继就是Z的右子树中最左下结点P

令Z的直接前驱代替Z （Z的直接前驱就是在树与二叉树那一章讲：线索二叉树找前驱和后继）：Z的前驱就是Z的左子树中最右下结点P

算法代码：

/*
若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点，
并返回TRUE;否则返回FALSE
*/
bool DeleteBST(BSTree &T, int key){
	if(!T){
		return false; 
	}else{
		if(key == T->data){ //找到关键字等于key的数据元素
			return Delete(T);
		}else if(key < T->data){
			return DeleteBST(T -> lchild, key);
		}else{
			return DeleteBST(T -> rchild, key);
		}
	}
}

//实现删除 p 结点的函数
bool Delete(BSTree &p)
{
    BSTNode* q = NULL, s = NULL;
    //情况 1，结点 p 本身为叶子结点，左、右孩子也为 NULL，在第2种情况会一同处理 
    //情况 2,结点 p 只有一个孩子
    if (!(p->lchild)) { //左子树为空，只需用结点 p 的右子树根结点代替结点 p 即可；
        q = p;
        p = p->rchild;
        free(q);
    }
    else if (!(p->rchild)) {//右子树为空，只需用结点 p 的左子树根结点代替结点 p 即可；
        q = p;
        p = p->lchild;
        free(q);
    }
    //情况 3，结点 p 有两个孩子
    else {
        q = p;
        s = p->lchild;
        //遍历，找到结点 p 的直接前驱，最终 s 指向的就是前驱结点，q 指向的是 s 的父结点
        while (s->rchild)
        {
            q = s;
            s = s->rchild;
        }
        //直接改变结点 p 的值
        p->data = s->data;
        //删除 s 结点
        //如果 q 和 p 结点不同，删除 s 后的 q 将没有右子树，因此将 s 的左子树作为 q 的右子树
        if (q != p) {
            q->rchild = s->lchild;
        }
        //如果 q 和 p 结点相同，删除 s 后的 q（p） 将没有左子树，因此将 s 的左子树作为 q（p）的左子树
        else {
            q->lchild = s->lchild;
        }
        free(s);
    }
    return true;
}

查找效率分析：

含有 n 个结点的二叉排序树的平均查找长度和树的形态有关：

对于图1，显然查找成功的ASL为：

ASL = （1 * 1 + 2 * 2 + 4 * 3 + 1 * 4）/ 8 = 2.625

对于图2，显然查找成功的ASL为：

ASL = （1 * 1 + 2 * 2 + 1 * 3 + 1 * 4 + 1 * 5 + 1 * 6 + 1 * 7）/ 8 = 3.75

因此对于相同序列的元素可以构造多种二叉排序树，但是观察上图，我们发现，仅仅当该二叉排序树对应的树高越低时，才可能减少ASL。

也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同（ $\left \lfloor log_{2}n \right \rfloor+1$ ），那么查找的时间复杂也就为O(logn)，近似于折半查找。而图二这种不看21的话，查找时间复杂度为O(n)，这等同于顺序查找。

3.2 平衡二叉树

平衡二叉树：树上任一结点的左子树和右子树的深度之差的绝对值不超过1。

好处：搭配二叉排序树可以达到更高的搜索效率！

结点的平衡因子 = 左子树高 - 右子树高 = -1或0或1

typedef struct AVLNode{
	int key;
	int balance;//平衡因子 
	struct AVLNode *lchild , *rchild;
}AVLNode , *AVLTree;

需要注意的是：我们以后讨论的平衡二叉树大多数都是建立在二叉排序树基础之上的。

但平衡二叉树不一定都是在二叉排序树的基础上研究，如一年考研题只让判断，看平衡因子就好。

平衡二叉树的插入：

如果在一棵 AVL 树中插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡。

我们称此调整平衡的过程为平衡旋转：

【1】 LL 平衡旋转：

若在 C 的左子树的左子树上插入结点A，使 C 的平衡因子从 1 增加至 2，需要进行一次顺时针旋转。 (以 B 为旋转轴）

例如下题：以B为轴，对A做了一次单向右旋平衡旋转。

40既然已经替代了30的位置，那么30就只能成为40的左孩子结点了。

【2】RR 平衡旋转：

若在 A 的右子树的右子树上插入结点C，使 A 的平衡因子从 -1 改变为 -2，需要进行一次逆时针旋转。(以 B 为旋转轴）

例如：以B为轴，对A做了一次单向左旋平衡旋转。

【3】 LR 平衡旋转：

若在 C 的左子树的右子树上插入结点B，使 C 的平衡因子从 1 增加至 2，需要先对A进行逆时针旋转，再对C进行顺时针旋转。 (以插入的结点 B 为旋转轴）

简化 tips：

直接将A和B、A和C之间的连线剪断，那么A和C就要往下面掉，那么自然就成为了B的左、右孩子结点。超级好记！

例题： 把40和60、40和80的连线剪断，那么40和80往下掉，成为了60的左、右孩子结点，而60原来的左、右子树被占了位置，就要分别重新连在40和80上，如下图：

【4】 RL 平衡旋转：

若在 A 的右子树的左子树上插入结点B，使 A 的平衡因子从 -1 改变为 -2，需要先对C进行顺时针旋转，再对A进行逆时针旋转。(以插入的结点 B 为旋转轴）

简化 tips:

和LR的tips一样，将A和C、C和B的连线剪断，往下掉，那么自然就成为了B的左、右孩子结点。超级好记！

例题：和LR解法几乎完全一样，就不多阐述了。

综合上面，可以尝试做一下这道题：

例：请将下面序列构成一棵平衡二叉排序树： (13, 24, 37, 90, 53)，

答案：

过程：这里将37、90、53调成为平衡子树后，24就自然而然恢复平衡了！因此如果有多个结点不满足平衡性质，优先调整最小不平衡子树！

3.3 B- 树

B- 树（也叫B树）是一种平衡的多路查找树，它在文件系统中很有用。B-树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。如下图5阶B-树：

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

树中每个结点至多有m棵子树，即至多含有m - 1个关键字。
若根结点不是终端结点，则至少有两棵子树。
除根结点外的所有非叶结点至少有⌈ m / 2 ⌉棵子树，即至少含有⌈ m / 2 ⌉ − 1 个关键字。
所有的叶子结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）
所有非叶子结点的结构如下：

⚠️注意：大部分学校算B-树的高度不包括叶子结点！

B-树的最小高度：
问题：含n个关键字的m阶B-树，最小高度是多少？

解析：让每个结点尽可能的满，有 m - 1个关键字，m个分叉。

那么对于第一层的关键字数为：（m - 1）* 1

对于第二层的关键字数为：（m - 1）* m

对于第三层的关键字数为：（m - 1）* ( $m^{2}$ )

因此归纳得：

$n <= (m-1)(1 + m +m^{2}+m^{3}+....+m^{h-1}) = m^{h}-1$

所以：

$h >= log_{m}(n+1)$

B-树得最大高度：

让各层得分叉尽可能的少，即根结点只有2个分叉，其他结点只有⌈ m / 2 ⌉个分叉。

那么第一层的结点数：1

第二层的结点数：2

第三层的结点数：2 * ⌈ m / 2 ⌉

第h层的结点数： $2 * (\left \lceil m/2 \right \rceil^{h-2})$

第h + 1层共有叶子结点数： $2 * (\left \lceil m/2 \right \rceil^{h-1})$

又由于：n个关键字的B树必有n + 1个叶子结点，则有：

$n+1>=2 * (\left \lceil m/2 \right \rceil^{h-1})$

所以：

$h<=(log_{\left \lceil m/2 \right \rceil}\frac{n+1}{2})+1$

B-树的查找：

从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找两个过程交叉进行。

若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；

若查找不成功，则返回插入位置。

B-树的插入：

通过B-树的查找，找出插入该关键字key的最底层中的某个终端结点(在B树中查找key时,会找到表示查找失败的叶结点,这样就确定了最底层非叶结点的插入位置)

⚠️注意：插入位置一定是最低层中的某个终端结点。

分裂的方法：在插入key后的原结点，若导致其原结点关键字数超过上限

$(\left \lceil m/2 \right \rceil-1<=n<=m-1)$ ，则从中间位置⌈ M / 2 ⌉将其中的关键字分为两部分（这里的M是该结点插入后所含关键字数），左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置⌈ M / 2 ⌉ 的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B-树高度增1。

例如：在下面的3阶的B-树上依次插入结点30、26、85和7的插入过程。

因为是3阶B-树，所以每个结点关键字数： 1 <= n <= 2

【1】插入30，不需要分裂

【2】插入26，需要分裂1次。

【3】插入85，需要分裂两次。

【4】插入7，需要分裂三次，高度还会+1。

B-树的删除：

相较于B-树的插入，B-树的删除就复杂多了，其实也说不上什么复杂，只是考虑的情况比较多了。

【1】若被删除的关键字在终端结点，且删除后，该结点的关键字数没有低于下限 $\left \lceil m/2 \right \rceil-1$ 。那么可以直接删除该关键字。比如删除下图中70：

【2】若被删除的关键字在非终端结点，则用其直接前驱或直接后继来代替被删除的关键字。这和二叉排序树的删除几乎一样：

采用其直接前驱替代：当前关键字左侧指针所指子树中 “ 最右下 ” 的元素，比如删除上图的80，过程如下图：
采用其直接后继替代：当前关键字右侧指针所指子树中 “ 最左下 ” 的元素，比如删除上图的77，过程如下图：

观察上面的操作我们发现，对非终端结点关键字的删除，相当于也是转化为对终端结点的删除操作。

【3】若被删除的关键字在终端结点，且删除后，该结点的关键字数低于下限 $\left \lceil m/2 \right \rceil-1$ 。那么就要向左兄弟（或右兄弟）借一个结点过来（前提你借完后，你的兄弟的关键字数不能低于下限）。

这个借法我俗称为：父子换位法，即爸爸当儿子，儿子当爸爸（非官方描述）

右兄弟很宽裕，可以借，比如删除上图中的38：49原先是爸爸，然后变儿子；70原先是儿子然后变爸爸。
左兄弟很宽裕，可以借，比如删除上图中的90：

【4】若被删除的关键字在终端结点，如果左、右兄弟都不够借，那么就只能和其右兄弟（或左兄弟）合并，但其父节点的分支数要减1了，那么又只能再从父结点中取一个关键字与其再次合并。

如果合并完后，其父节点的关键字数低于下限 $\left \lceil m/2 \right \rceil-1$ ，那么就要将该父节点继续与其右兄弟（或左兄弟）合并.........

$\left \lceil m/2 \right \rceil$

3.4 B+ 树

B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用（并没有存储关键字对应记录的存储地址）。而B树的非叶结点都包含了关键字对应记录的存储地址。这也使得在相同磁盘含量下，B+树的非叶结点含有的关键字数比B树多（因为B+树不存储关键字对应的存储地址），从而使得B+树的阶更大，树更矮。这样的话，当我们查询时，访问次数会更少，查找会更快，这也是B+树具有更广泛的应用的一个原因！

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

每个分支结点最多有m棵子树（孩子结点）
非叶根结点至少有两棵子树，其他每个分支结点至少有 $\left \lceil m/2 \right \rceil$ 棵子树
每个结点的子树个数与其关键字个数相等
所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接;

看到这里有疑惑很正常，下面我将会对比B-树，讲解它们各自的特点：

【考点】 B- 树 VS B+ 树

【1】

B-树：每个结点的子树个数比其关键字个数多 1
B+树：每个结点的子树个数与其关键字个数相等

【2】

B-树：根结点的关键字数： $n\in[1 , m-1]$
B-树：其他结点的关键字数： $n\in [\left \lceil m/2 \right \rceil-1,m-1]$
B+树：根结点的关键字数： $n\in[2 , m]$
B+树：其他结点的关键字数： $n\in [\left \lceil m/2 \right \rceil,m]$

【3】

B-树：各结点中包含的关键字是不重复的
B+树：叶结点包含全部关键字，非叶子结点中出现过的关键字也会出现在叶子结点中

【4】

B-树：结点中包含了关键字对应的记录的存储地址
B+树：叶子结点包含信息，所有非叶子结点仅起索引作用，非叶子结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址

B+树的查找：

对应B+树可以进行两种查找运算：一种是从最小关键字起的顺序查找（从底层的叶子结点）；

另一种是从根结点开始，进行随机查找。

顺序查找：比如查找8

随机查找：比如查找9，通过红线路径。

⚠️注意：B+树中，无论查找成功与否，最终一定都要走到最下面一层结点（不然你怎么拿到关键字对应的记录的存储地址呢！）

总结：

四、散列查找（哈希表）

以上讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，并且查找过程是：给定值依次和关键字集合中各关键字进行比较。

散列表（Hash Table），又称为哈希表。是一种数据结构，特点：数据元素的关键字与其存储地址直接相关。

记录的关键字与记录在表中的存储位置之间存在一种对应（函数）关系。若记录的关键字为 key，记录在表中的位置（称为哈希地址）为 f (key)，则称此函数 f (x) 为哈希函数（散列函数）。

由于哈希函数是一个映像，因此，在一般情况下，很容易产生“冲突”现象，即：key1 $\neq$ key2，而 f (key1) = f (key2)。这种具有相同函数值的关键字称为同义词。

因此：在构造这种哈希表时，除了需要选择一个 “好” 的哈希函数之外；还需要找到一种“处理冲突”的方法。这里我用拉链法(下文会讲解)处理上述题目的 “冲突”，即把所有 “同义词”存储在一个链表中。通过这个题，把哈希表要涉及的ASL和装填因子讲解一下：

【1】查找长度就是ASL里面的 $C_{i}$ ，即在查找运算中，需要对比关键字的次数。

14的查找长度为：1
1的查找长度为：2
27的查找长度为：3
79的查找长度为：4
68的查找长度为：1
55的查找长度为：2
其他同理..............

注意如果查找21，其21 % 13 = 8，映射在H(8），此时H(8）为NULL，根本就没有关键字，更别谈对比次数了。所以21的查找长度为：0（具体还是以大家学校的要求为定吧）。如果查找66，其66 % 13 = 1，映射在H(1)，此时H(1)不为NULL，那么对比14、1、27、79。共需对比4次关键字才能发现查找失败，因此66的查找长度为：4。

因此该查找表的查找成功的ASL为：

$ASL=\frac{1*6+2*4+3 +4}{12}=1.75$

显然通过ASL我们可以观察到，对于不产生冲突的关键字，我们查找长度为1，对于产生冲突的关键字，如14、1、27、79，随着其冲突越多，查找长度越大，其ASL越高，查找效率越低。

但这也比顺序查找 $\frac{12 + 1}{2} = 6.5$ 好太多了！

查找失败的ASL为：

$ASL = \frac{0 +4+0+2+0+0+2+1+0+0+2+1+0}{13}=0.92$

装填因子 $\alpha$ = 表中记录数 / 散列表长度。（后续还会介绍）

该查找表的装填因子刚好是其查找失败的ASL值

4.1 哈希函数的构造方法

对数字关键字可有下列构造方法：

若是非数字关键字，则需先对其进行数字化处理。

1. 除留余数法（最常用）

假定散列表表长为m ，取一个不大于 m 但最接近或等于m 的质数 p ，利用以下公式把关键字转换成散列地址。散列函数为：即 H(key) = key % p， p <= m。

质数又称素数，指除了1和此整数自身外，不能被其他自然数整除的数。

特点：简单，可与下述几种方法结合使用。p 的选取很重要，p 选的不好，容易产生同义词。

2. 直接定址法

哈希函数为关键字的线性函数:

H(key) = key 或者 H(key) = a * key + b

其中a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

例如：存储一个班级的学生信息，班内学生学号为：（1120112176 ~ 1120112205），那么可以将哈希函数定为：

H(key) = key - 1120112176，那么在查找表中就为：

3. 数字分析法（数字选择法）

构造：取关键字的若干位或其组合作哈希地址。

适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况，若更换了关键字，则需要重新构造新的散列函数。

例如：当手机号码为关键字时，其11位数字是有规则的，此时是无需把11位数值全部当做散列地址，这时我们给关键词抽取，将这几位抽取出来的分布较为均匀的若干位作为散列地址。比如手机号码后4位（出现机会较为均匀）作为哈希地址。

4. 平方取中法（较常用）

构造：以关键字的平方值的中间几位作为哈希地址。

求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。

原因：图中很明显可以看到红框圈出的计算过程，基本都受到整个关键字中各位的影响。因此算出的这几位结果可以作为散列地址。

⚠️注意：具体取多少位，还是要视题意为准，这里只是说明取中间几位的原因！

例如：要存储整个学校的学生信息，以“身份证号”作为关键字设计散列函数。

5. 折叠法

构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位，最后一部分的位数可以不同）做哈希地址。

适于关键字位数很多，且每一位上数字分布大致均匀情况。

6. 随机数法

构造：取关键字的随机函数值作哈希地址，即： H(key) = Random(key)

其中，Random 为伪随机函数。

适于关键字长度不等的情况。

4.2 处理冲突的方法

“处理冲突”的实际含义是：为产生冲突的地址寻找另一个哈希地址。

1、开放定址法

当发生冲突时，在冲突位置的前后附近寻找可以存放记录的空闲单元。用此法解决冲突，要产生一个探测序列，沿着此序列去寻找可以存放记录的空闲单元。最简单的探测序列产生方法是进行线性探测，即当发生冲突时，从发生冲突的存储位置的下一个存储位置开始依次顺序探测空闲单元。

为产生冲突的地址 H(key) 求得一个探查地址序列：

H0, H1, H2, …, Hs 1≤s≤m - 1

其中： $H_{i}$ = ( H(key) + di ) % m . i =1, 2, …, s

m 为哈希表的表长。di为增量序列。

沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中。

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

【1】线性探测法

增量序列：di = 1, 2, 3, …, m-1

即发生冲突时，每次往后探测相邻的下一个单元是否为空。

如下题：

当加入关键字1时，和H[1]发生冲突，因此根据 (1 + 1) % 16 = 2，而由于和H[2]无冲突，所以

H[2] = 1。所以如图：

然后依次再加入：68、20、84、27、55、11、10、79。最终结果如图：

首先先来看一下各元素的查找长度：

所以查找成功的ASL为：

对于查找失败的情况为13种，因为可能映射到：0 ~ 12

但要注意的是：上面介绍拉链法时，对于如果映射到结点值为NULL的查找失败情况的查找长度为0。但是对于线性探测，这里如果映射到结点值为空的查找失败情况的查找长度应为1。

比如，12的查找长度为2，需要依次对比10，和一个空值（可以理解为一个事先初始化的值，比如一开始整个数组初始化为0，所以要计算它的对比次数）。

因此上述查找失败的ASL为：

显然线性探测法很容易造成同义词、非同义词的 “ 聚集（堆积）”现象，严重影响查找长度，比如查找元素79需要对比9次，而对于查找失败的结点，比如查找40，需要对比13次。虽然这种处理冲突的方法并不是很理想，但是考试特别喜欢考察，必须要重点掌握！

【2】平方探测法

增量序列：di = 1², -1², 2², -2², 3², …, ±k² (k <= m/2)

当加入6时，根据散列函数应放到H[6]，当加入19时，和6发生冲突，所以根据根据平方探测法，应将19放到H[7]，当加入32时发生冲突，根据平方探测法：（6 +( $-1^{2}$ )）%27 = 5，所以放到H[5]。

当加入45时发生冲突，根据平方探测法：（6 +( $2^{2}$ )）% 27 = 10，所以放到H[10]。

当加入58时发生冲突，根据平方探测法：（6 +( $-2^{2}$ )）% 27 = 2，所以放到H[2]。

当加入71时发生冲突，根据平方探测法：（6 +( $3^{2}$ )）% 27 = 10，所以放到H[15]。

当加入45时发生冲突，根据平方探测法：（6 +( $-3^{2}$ )）% 27 = 24【除-1余数24】，所以放到H[24]。

所以最终结果为：

很明显，平方探测法比起线性探测法更不易产生 “聚集（堆积）”的问题。

最后再了解一个非重点的小坑：

散列表长度 m 必须是一个可以表示成：4*k + 3 的素数，才能探测到所有位置！！

【3】伪随机序列法

di = 伪随机数序列。

这种考试无法考察，hh~

⚠️注意：采用 “开放定址法”时，删除结点不能简单地将被删除的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径，可以做一个 “删除标记”，进行逻辑删除！

2、再散列法（再哈希法）

方法：构造若干个哈希函数，当发生冲突时，计算另一个哈希地址，

即：Hi = RHi(key) i =1, 2, …, k 。其中：RHi 是不同的哈希函数。

特点：不易产生“聚集”，但计算时间增加。

3、溢出区法

除基本的存储区外（称为基本表），另外建立一个公共溢出区（称为溢出表），当发生冲突时，记录可以存入这个公共溢出区。

4、链地址法

方法：将所有关键字为同义词的记录存储在一个单链表（同义词子表）中，并用一维数组存放头指针。这就是开头就介绍的处理冲突的方法，简单明了！

4.3 哈希表的查找及其分析

哈希查找过程仍是一个给定值与关键字进行比较的过程，评价哈希查找效率仍要用 ASL。

决定哈希表查找的ASL的因素：

选用的哈希函数
选用的处理冲突的方法
哈希表饱和的程度：装载因子 $\alpha$ = 表中记录数(n) / 散列表长度(m)

当哈希函数和处理冲突的方法确定后：

哈希表的平均查找长度是 $\alpha$ 的函数，而不是 n 的函数。

—— 这是哈希表所特有的特点。

一道有趣的题：

这题如果直接利用上面讲的性质，很容易就给套进去了。这题重在审题，题目说了：是这种堆积现象的出现，带来的直接影响对象是谁？

说明，在这之前散列函数、处理冲突的方法、表中记录数n和散列长度m都可以假设是确定的！

装填因子 $\alpha$ = 表中记录数(n) / 散列表长度(m)。这就相当空间利用率（定值），这种堆积现象对它没有直接影响。所有排除C

存储效率和装填因子直接相关，也相当于空间利用率（定值），所有排除A。

显然对散列函数，没有影响，排除A。

而为什么平均查找查找长度会受到直接影响呢，因为这种现象的产生正是这种散列方式处理冲突的弊端，这种堆积的产生直接影响对象就是会使查找一个元素的比较次数增加（这在开放地址法已介绍）。如果这种堆积现象减少（比如给定插入的元素比较特殊，或者将线性探测换成平方探测）那么其对于的ASL都会减小。

因此综上所述，选择D。

结尾：

最后，非常感谢大家的阅读。我接下来还会更新排序，如果本文有错误或者不足的地方请在评论区(或者私信)留言，一定尽量满足大家，如果对大家有帮助，还望三连一下啦！

新的一年，提前祝大家2024新年快乐！哈哈，干杯~

我的个人博客，欢迎访问 !

Reference

【1】严蔚敏、吴伟民：《数据结构（C语言版）》

【2】b站：王道数据结构