数据结构与算法（C语言版）P11——查找

1、查找的基本概念

从着一章节开始学习查找，

查找时属于数据的运算里面的知识。

数据的元素包括：查找、排序、插入、删除、修改等。

问题一：那里查找？

首先要清楚，是在哪里进行查找操作？是在线性表中找？还是在树中找呢？还是在图中找呢？

都不是，是在一个叫做查找表中进行查找的。

那什么是查找表呢？

__查找表：是由同一类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着__松散的关系，因此查找表是一种应用灵便的结构。

__问题二：__什么是查找？

​ 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录。

__关键字：__用来标识一个数据元素（或记录）的某个数据项的值。

• 主关键字：可以唯一标识一个记录的关键字的主关键字。
• 次关键字：反之，用以识别若干记录的关键字是次关键字。

__问题三：__查找是否成功？

根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。

• 若查找表存在这样一个记录，则称“查找成功”。
  • 那就给出整个记录信息，或指示该记录在查找表中的位置。
• 否则称“查找不成功”
  • 查找结果给出“空记录”，或“空指针”。

问题四：查找的目的？

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

• 查询某个“特定的”数据元素是否在查找表中。
• 检索某个“特定的”数据元素的各种属性。
• 查找没有此数据，就在查找表中插入一个数据元素。
• 删除查找表中的某个数据元素。

_查找表的分类：

• 静态查找表：仅作“查询”（检索）操作的查找表。

• 动态查找表：

  • 作“插入”和“删除”操作的查找表。

    有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素，此类表为动态查找表。

问题五：如何评价查找算法？

查找算法的评价指标：关键字的平均比较次数，也称__平均查找长度。__

简称ASL（Average Search Length）。

以上ASL是关键字比较次数的期望值。

问题六：查找过程中我们要研究什么？

查找的方法取决于查找表的结构，即表中数据元素是__依何种关系组织在一起的。__

由于对查找表来说，在集合中查询或检索一个“特定的”数据元素时，若无规律可循，只能对集合中的元素一一遍历直至找到为止。

而这样的“查询”和“检索”显然效率不高，但是它恰恰又是任何计算机应用系统中使用频度都很高的操作，因此__设法提高查找表的查找效率__，是本章讨论问题的出发点。

为提高查找效率，一个办法就是在构造查找表时，在集合中的数据元素之间认为的加上某种确定的约束关系。

2、线性表的查找

2.1、顺序查找（顺序查找）

2.1.1、算法讨论

应用范围：

• 顺序表或线性表表示的__静态查找表。__

• 表内元素之间__无序__。

数据元素类型定义：

typedef struct
{
    KeyType key;          //关键字域
    ...                   //其它域
}ElemType;

顺序表结构类型定义

typedef struct
{
    ElemType* R;
    int length;         //表长
}SSTable;

SSTable ST;             //定义顺序表ST

那顺序查找，就是在顺序表ST中查找值为key的数据元素。

例如：

要想查找元素13，我们可以从头开始比较，也可以从尾部开始比较。

常规的算法：

int Search_Seq(SSTable ST, KeyType key)
{
    for(int i = ST.length; ST.R[i].key != key; --i)
    {
        if (i<=0)
        {
            break;
        }
    }
    if (i>0)
    {
        return i;
    }
    else
    {
        return 0;
    }
}

这里看到以上查找算法，没执行一次循环都要进行两次比较，一次ST.R[i].key != key比较，一次i<=0比较。

那有没有更好一点的算法呢？由，如下。

改进的方法：

把待查关键字key存入表头（哨兵，监视哨），从后往前逐个比较，可免去查找过程中每一步都要检测是否查找完毕。

例如要在以下数组中查找key=60的元素：

那改进的算法如下：

int Search_Seq(SSTable ST,KeyType key)
{
    ST.R[0].key = key;      //将key就放在数组下标为0的位置处
    for(int i = ST.length; ST.R[i].key != key; i--);   //如果从下标1~11中的某个位置找了，就直接返回下标
    return i;      //这里代表没有找到key，就返回key本身的下标0。
}

可以看到这里每次循环只需要比较ST.R[i].key != key。

那当ST.length较大时，此改进的算法优势会更大，并且此改进能使进行一次查找所需的平均时间几乎减少一半。

2.1.2、算法效率分析

分析这个算法的时间复杂度：

int Search_Seq(SSTable ST,KeyType key)
{
    ST.R[0].key = key;      //将key就放在数组下标为0的位置处
    for(int i = ST.length; ST.R[i].key != key; i--);   //如果从下标1~11中的某个位置找了，就直接返回下标
    return i;      //这里代表没有找到key，就返回key本身的下标0。
}

比较次数与key位置有关：

• 查找第i个元素，需要比较n-i+1次。
• 查找失败，需比较n+1次。

那查找成功时的平均查找长度：

ASL = (1/n) * ∑(n-i+1) = (1+2+…+n)/n = (n+1)/2。

所以算法的时间复杂度：O(n)，空间复杂度：O(1)。

2.1.3、顺序查找的特点

优点：算法简单，逻辑次序无要求，且不同存储结构均使用。

缺点：ASL太长，事件效率太低。

2.2、折半查找（二分查找）

二分法适用的条件：所查找的数据是有序的，什么有序的？就是1 2 3 45 6 7 8 9 10 11…这样的。

并且只能查一个元素。

折半查找算法：

• 设表长为n。left，right，mid分别为指向待查元素所在区间的上界、下界和中点，key为给定的要查找的值。
• 初始时，令right=0，high=n-1，mid=[(left+right) / 2]（取整）。
• 让key和mid指向的记录比较
  • 若key==mid，则查找成功。
  • 若key<mid，则right = mid-1。
  • 若key>mid，则left=mid+1。
• 重复以上操作，直至left>right时，查找失败。

2.2.1、二分法查找代码实现（非递归）

#include <stdio.h>
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int k = 7;                //需要查找的元素
	int sz = sizeof(arr) / sizeof(arr[0]);
	int left = 0;            //最左边元素的下标
	int right = sz - 1;      //最右边元素的下标
	while (left <= right)
	{
		//int mid = (left + right) / 2;    //这样如果数据非常庞大时有可能存在溢出
        int mid = left + (right-left) / 2;         //建议这样写   
		if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			printf("找到了，下标是：%d\n", mid);
			break;
		}
	}
	if (left > right)
	{
		printf("没有找到");
	}


	return 0;
}



//这个利用数学知识就是log2   n=32

//也就是说我有2**32的数，也只需要查找32次。

优化：int mid = (left + right) / 2; 这一行代码是有些不妥当的，如果left和right数字非常的庞大，以至于int类型无法承载，那就会导致溢出的问题。
我们可以这样做：int mid = left + (right-left) / 2;

2.2.2、折半查找的性能分析

首先来看时间复杂度：

我们以如下例子说明：

如果想找下标为4，key=21的值，需要几次呢？

直接分析不太好分析，既然我们使用的是折半查找法，每一次比较后都会排除一半的可能性。

所以我们可以将此数组的信息，转为二叉树：

通过此二叉树，如果想要匹配到key=21，需要经过6结点、3结点、4结点。那可以发现：

• 如果能匹配到，那比较次数=路径上的结点数=3，换句话说就是比较次数=结点的层数=3。

​ 而无论如何比较次数<=树的深度。

​ 而树的深度=
（[3.14]=3)。

• 但如果匹配不到：比较次数=路径上的内部结点数。

平均查找长度ASL（成功时）：

设表n=2^h - 1（n为结点个数，即为数组长度，h为深度），则h=log2 (n+1)，此时，判定树为深度=h的满二叉树，且表中每个记录的查找概率相等：Pi=1/n。

所以ASL推导过程：

那此算法的数量级，也就是时间复杂度：O(log2 n)。

__折半查找优点：__效率比顺序查找高。

折半查找缺点：只适用于__有序表，且限于__顺序存储结构（对线性链表无效）。

2.3、分块查找

2.3.1、算法分析

条件：

• 将表分成几块，且表或者有序，或者分块有序；若i<j，则第j块中所有记录的关键字均大于第i块中的最大关键字。
• 2、建立索引表，每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序。

如下图：其中第二块中最小值比第一块的每一个值都大，同理其中第三块中最小值比第二块的每一个值都大。

查找过程：

• 先确定待查记录所在块（使用顺序或折半查找）。
• 再在块内查找（使用顺序查找）。

分块有序，块内无序。

举了例子：查找key=38。

首先看索引表，确定key的范围在那个块中。

索引表中第一块max=22，第二块max=48，第三块max=86。

所以确定了要查的key在第二块中。

然后在使用顺序查找进行匹配。

2.3.2、性能分析

我们也可以看出，分块查找分两部分：

• 在索引中查找。
• 在块中查找。

所以分块查找的ASL=Lb+Lw

• Lb：对索引表查找的ASL。
• Lw：对块内查找的ASL。

因为索引表是有序的，所以索引表的ASL和折半查找的ASL一样。

同理，块内是无序的，所以块内查找的ASL和顺序查找的ASL一样。

那ASL=Lb+Lw=ASL(折半查找)+ASL(顺序查找)，如下：

【说明】：s为每块内部的记录个数，n/s即块的数目。

又因为折半查找的的时间复杂度为O(log2 n)，顺序查找的时间复杂度为O(n)，所以分块查找的ASL，介于折半查找和顺序查找之间，并且分块查找ASL的更贴近于折半查找ASL。

下面我们通过一个例子，来验证以上结论。

例：当n=9，s=3时。

• 分块查找ASL=log2 (9/3 + 1) + 3/2=2+1.5=3.5
• 折半查找ASL=log2 9=3.1
• 顺序查找ASL=(9+1)/2=5

可以看到分块查找的效率确实在折半查找和顺序查找之间，并且更贴近于折半查找。

分块查找的优缺点：

• 优点：插入和删除比较容易，无需进行大量移动。
• 缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。
• 使用情况：如果线性表既要快速查找又经常动态变化，则可采用分块查找。

2.4、顺序查找、折半查找、分块查找三者对比

	顺序查找	折半查找	分块查找
ASL	最大（效率最慢）	最小（效率最快）	中间（效率中间）
表结构	适用于有序表、无序表	适用于有序表	分块有序、块内无序
存储结构	顺序表、线性链表	顺序表	顺序表、线性链表

3、树表的查找

上面学习了顺序查找法，其中折半查找法效率最高，但是折半查找法有个缺点，就是当表插入、删除操作频繁时，为维护表的有序性，需要移动表中很多记录。这样以来会影响效率。

那有没有那个查找算法既能达到折半查找法的效率，又能解决折半查找的不足之处呢？

有！这就是接下来要学习的树表的查找。

可以改用动态查找表——几种特殊的树。

这里先简单说一下：所谓动态查找表，就是表结构在查找过程中动态生成。

对于给定值key：

• 若表中存在，则成功返回。
• 否则，插入关键字等于key的记录。

根据用途的差别，特殊的树可以有多种选择：

• 二叉排序树
• 平衡二叉树
• 红黑树
• B树
• B-树
• B+树
• 键树

这里重点学习：二叉排序树和平衡二叉树。

3.1、二叉排序树

3.1.1、二叉排序树的定义及性质

__二叉排序树（Binary Sort Tree）：__又称二叉搜索树、二叉查找树。

定义：

二叉排序树或是空树，或是满足如下性质的二叉树：

• 若其左子树非空，则左子树上所有结点的值均小于根节点的值。
• 若其右子树非空，则右子树上所有结点的值均小于根节点的值。
• 其左右子树本身又各是一棵二叉排序树。

如下图：

那现在思考一下：中序遍历上面的二叉排序树，结果有什么规律？

遍历结果：3 12 24 37 45 53 61 78 90 99。

可以看到遍历结果，中序二叉树排序树后，数据是__递增有序__的。

为什么中序遍历，就会出现如此现象呢？

一部分是二叉排序树的特性，另一部分是中序遍历的特性。就是从左节点–>根节点–>右节点。

__二叉排序树的性质：__中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排序的__递增有序__序列。

3.1.2、二叉排序树查找—递归算法

步骤：

• 若查找的关键字等于根节点，成功。
• 否则：
  • 若小于根节点，查其左子树。
  • 若大于根节点，插旗右子树。
• 在左右子树上的操作类似。

比如要查找key=105。首先105不等于122，并且小于122，所以去122的左子树继续查找。之后遇见99，105等于99，且大于99，所以继续去99的右子树查找，发现105小于100，所以继续去110的左子树查找，发现查找成功。

二叉排序树的存储结构

typedef struct
{
    KeyType key;             //关键字项
    InfoType a;              //其它数据域
}ElemType;

typedef struct BSTNode
{
    ElemType data;          //数据域
    struct BSTNode *lchild,*rchild      //左右孩子指针
}BSTNode,*BSTree;

算法思想：

• 若二叉排序树为空，则查找失败，返回指针。
• 若二叉排序树非空，将给定值key与根节点的关键字T->data.key进行比较：
  • 若key等于T->data.key，则查找成功，返回根节点地址；
  • 若key小于T->data.key，则进一步查找左子树；
  • 若key大于T->data.key，则进一步查找右子树；

代码

BSTree SearchBST(BSTree T,keyType key)
{
    //二叉排序树为空，或者是直接查找到了根节点，就返回T
    if ((!T) || key==T->data.key)
    {
        return T;
    }
    else if(key<T->data.key)
    {
        return SearchBST(T->lchild,key);        //在左子树中继续查找
    }
    else
    {
        return SearchBST(T->rchild,key);        //在右子树中继续查找
    }
}

3.1.3、二叉排序树的算法分析

我们先来个例子：

二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。

所以，比较关键字次数 == 此结点所在层次数。

而我们需要考虑悲观预期，也就是最多的比较次数。

而，最多的比较次数 == 树的深度。

但是树的形态不同所引起的效率就不同，我们来看：

同样是数据值一样的结点，但是所构成树的形态不同，其ASL值是不一样的。

无论哪一种二叉排序树，

• 最好的情况就是左边的情况：O(log2 n)。
• 最坏的情况就是右边的情况，n个结点，位于n层，那就意味着，需要一个一个的比较，那这就退化成了顺序查找法：O(n)。

所以最终得出结论：

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

最好情况：时间复杂度为O(log2 n)。

最坏情况：时间复杂度为O(n)。

__问题：__如何提高形态不均衡的二叉排序树的查找效率？

解决办法：做“平衡化”处理，即尽量让二叉树的形状均衡。

那二叉树的形状均衡就称作：平衡二叉树。

3.1.4、二叉排序树操作—插入、生成

先看个例子：在以下二叉排序树中，插入数值。

• 插入40，是37的右孩子。
• 插入50，是53的左孩子。

插入操作步骤：

• 若二叉排序树为空，则插入结点作为根结点插入到空树中。
• 否则，继续在其左，右树上查找。
  • 树中已有，不在插入。
  • 树种没有
    • 查找直至某个叶子结点的左子树或右子树为空为止，则插入，并插入结点应为该叶子节点的左孩子和右孩子。

【注意】：插入的元素一定在叶子结点上。

学习完二叉排序树的插入，我们再来学习二叉排序树的生成。

二叉排序树生成的步骤：从空树出发，经过一系列的查找，插入操作之后，可生成一棵二叉排序树。

例：设查找的关键字序列为：{45，24，53，45，12，24，90}

可生成二叉排序树如下：

将无序序列变为有序序列的过程：将一个无序序列通过构造二叉排序树，然后通过中序遍历，就将无序序列变为一个有序序列。

构造树的过程就是对无序序列继续宁排序的过程。

插入的结点均为叶子节点，故无需移动其它结点。相当于在有序序列上插入记录而无需移动其它记录。

但是要注意，关键字的输入顺序不同，建立的将会是不同的二叉树排序树。

例，如下：

3.1.5、二叉排序树操作—删除

从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删除该结点，并且__还应保证删除后所得的二叉树任然满足二叉树排序树的性质不变。__

由于中序遍历二叉排序树可以得到一个递增有序的序列。那么，在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。

那如果删去一个结点还需要保持是递增有序序列，需要考虑两点：

• 将因删除结点而断开的二叉链表重新链接起来。

• 防止重新链接后树的高度增加。

删除结点需要分类讨论：

• 被删除的结点是叶子节点：直接删除该结点。然后将其双亲结点中相应指针域的值置为为NULL。

• 被删除的结点只有左子树或者只有右子树：用其左子树或者右子树替换它（结点替换）。然后将其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。

  

• 被删除的结点既有左子树，又有右子树，如下：

  

  这里有两种方法：

  • __方法一：__以其中序前趋值替换（值替换），然后再删除该前趋结点。前趋是左子树中最大的结点。

    以上面二叉排序树再说一下，如何找结点50的前趋。其实很好想50的前趋就是比50值小并且是最接近50的。那肯定就是50这个结点左子树中最大的一个结点值，就是40。还有一种方法可以找到50的前趋，先把二叉排序树右中序遍历出来：20、30、32、35、40、50、80、85、88、90。这样就能直接找到50的前趋是40了。

    如下删除：

    

  • __方法二：__以其中序后继值替换（值替换），然后再删除该后继结点。前趋是右子树中最小的结点。

    这里找后继结点不在赘述，和上面找前趋结点一样。

    

这里我们再来看个示例：

首先可以把78的值替换为65，但是这个方案不太好。为什么呢？因为65替换了78，这个二叉排序树的深度没有改变，这样回影响效率。

那我们再来看看使用78的后继81来看，这里有个难点，如果使用81，那就需要移动81，又因为81还有个右子树88，所以需要先解决移除结点，并且此结点只有右子树的情况，那直接把81的值替换为88，然后再把78的主替换为81。这样也使得二叉排序树的深度降低，使得效率提升。

3.2、平衡二叉树

3.2.1、平衡二叉树的定义

前面二叉排序树有个问题：如何提高形态不均衡的二叉排序树的查找效率？

解决办法：做"平衡化"处理，即尽量让二叉树的形态均衡！

这种"平衡化"就是__平衡二叉树（balanced binary tree）。__

平衡二叉树的：

• 又称__AVL__树（Adelson-Velskii and Landis）。
• 一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：
  • 左子树与右子树的高度只差的绝对值小于等于1。
  • 左子树和右子树也是平衡二叉排序树。

平衡二叉树首先需要满足二叉排序树。

平衡二叉树是在二叉排序树的基础上定义的。

为了方便起见，给每个结点附加一个数字，给出__该结点左子树与右子树的高度差__。这个数字称为结点的__平衡因子（BF）。__

平衡因子 = 结点左子树的高度 - 结点右子树的高度

根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是-1，0，1。

下面我们来看几个例子：

那既然有不平衡的二叉树，就需要想办法让它变为平衡的。

对于一个有n个结点的AVL树，其高度保持在O(log2 n)数量级，ASL也保持在O(log2 n)量级。

3.2.2、平衡调整方法

当我们在一个平衡二叉排序树上插入一个结点时，有可能导致_失衡__，即出现平衡因子绝对值大于1的结点，如：2，-2。

下面看个例子：

由于60的插入，使得53的平衡因子为-2。所以此时插入了一个结点，使得此平衡二叉树不在平衡了。

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

那如果插入一个结点造成多个子树失衡呢？如下：

可以发现结点7和结点16的平衡因子都不对。那这个时候怎么办呢？

规定：当不止一个失衡节点时，为最小失衡子树的根节点。

什么意思呢？画图解释：

其中有平衡调整有四种类型。

3.2.2.1、四种调整类型总览

A：失衡结点。

B：A结点的孩子，C结点的双亲。

C：插入新节点的子树。

调整原则：

• 降低高度。
• 保持二叉排序树性质。

3.2.2.2、类型一（LL型）

调整规则：

• B结点带左子树α一起上升。
• A结点称为B结点的右孩子。
• 原来B结点的右子树β作为A的左子树。

示例：

3.2.2.3、类型二（LR型）

​

调整规则：

• C结点穿过A、B结点上升（直接将C拿出来）。
• B结点成为C的左孩子，A结点成为C的右孩子。
• 原来C结点的左子树β作为B的右子树。
• 原来C结点的右子树γ作为A的左子树。

示例：

3.2.2.4、类型三（RL型）

调整规则：

• 9结点单独拿出来。
• 7作为9的左子树，11作为9的右子树。
• 8作为7的左子树。

3.2.2.5、类型四（RR型）

调整规则：

• B结点带右子树β以前上升。
• A结点称为B的左孩子。
• 原来B结点的左子树α作为A的右子树。

示例：

3.2.2.6、例题

输入关键字序列：{16，3，7，11，9，26，18，14，15}

给出构造AVL树的步骤：

至此AVL树构造完毕。

平衡二叉树如下：

4、散列表（哈希表）

4.1、散列表引入

__基本思想：__记录的存储位置与关键字之间存在对应关系。

对应关系————bash函数

Loc(i)=H(keyi)

什么是存储位置与关键字之间存在对应关系呢？

我们来看几个例子：

例子一：

__例子二：__数据元素序列{21，23，39，9，25，11}，若规定每个元素k的存储地址H(k)=k，请画出存储结构图。

数组下标和值对应。

这样以来如果要查找key=9，则访问H(9)=9号地址，若内容为9则成功；若查不到，则返回一个特殊值，如空指针或空记录。

__优点：__查找效率高。

__缺点：__空间效率低。

优点很完美，但是缺点就是空间效率低。

那接下来我们就要解决使用散列表并且提高此空间效率。

散列存储：

​ 选取某个函数，依该函数按关键字计算元素的存储位置。

​ Loc(i)=H(keyi)。

4.2、散列表相关术语

散列方法：

​ 选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成功。

__散列函数：__散列方法中使用的转换函数。

__散列表：__按照散列法构造的表就是散列表。如下

__冲突：__不同的关键码映射到同一个散列地址。key1 != key2，但是H(key1)=H(key2)。

比如：上图中的数组下标为9对应多个值，9—>9，9—>19，9—>29，

在散列查找方法中，冲突是不可能避免的，只能尽可能减少。

__同义词：__具有相同函数值的多个关键字。

4.3、散列函数的构造问题解决

通过以上引入和发现问题。

要想构造好的散列函数，我们现在要解决两个问题：

• 所选函数尽可能简单，以便提高转换速度，并且所选函数对关键码计算出的地址，应在散列地址集中均匀分布，以减少空间浪费。
• 查找时，解决冲突规则，有规律的查询其它相关单元。

构造散列函数考虑的因素：

• 执行速度（即计算散列函数所需时间）。
• 关键字的长度。
• 散列表的大小。
• 关键字的分布情况。
• 查找频率。

根据元素集合的特性构造：

• 要求一：n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但任希望散列的__地址空间尽量小__。
• 要求二：无论用什么方法存储，目的都是尽量均匀的存放元素，以避免冲突。

散列函数的构造由多种，如下：

• 直接定址法

• 除留余数法

• 数组分析法

• 平方取中法

• 折叠法

• 随机数法

其中主要学习：重点学习除留余数法，和直接定址法。

4.3.1、直接定址法

__核心方法：__以关键码key的某个线性函数值为散列地址，不会产生冲突。

如下线性函数：

Hash(key) = a*key + b（a、b为常数）

或者

Hash(key) = key/100

例：{100，300，500，700，800，900}

散列函数Hash(key) = key/100，那100对应1，300对应3，500对应5，700对应7…

4.3.2、除留余数法

__核心思想：__将key除以一个树，我们相除所得到的余数存储下来。余数和key就是对应关系。

Hash(key) = key mod p（p是一个整数）

这种方法的关键在于：如何选取合适的p？

技巧：设表长为m，取p<=m且p为质数。

例：{15，23，27，38，53，61，70}

散列函数Hash(key) = key mod 7。

那可以得出散列表：

4.4、解决冲突问题

解决冲突也有多种方法：

• 开放定址法（开地址法）。
• 链地址法（拉链法）。
• 再散列法（双散列函数法）。
• 建立一个公共溢出区。

4.4.1、开放地址法

__基本思想：__有冲突就去寻找下一个空的散列地址，只要散列表足够大，空的散列表地址总能找到，并将数据元素导入。

例如：使用除留余数法确定的散列函数：Hi=(Hash(key)+di) mod n。 di为增量。

为什么是Hash(key)+di，而不是key+di呢？

因为冲突发生的现象是，一个Hash(key)对应对各值，所以我们需要更换Hash(key)的值。

其中取di增量的方法也有三种：

下面对以上三种方法进行说明。

4.4.1.1、线性探测法

Hi= (Hash(key)+di) mod m（1<=i<m）

其中：m为散列列表长度。di为增量1，2，3，…，m-1，且di=i。

示例：

关键码集为{47，7，29，11，16，92，22，8，3}。散列表长度为11；

散列函数为Hash(key)=key mod 11；拟采用线性探测来解决冲突。建散列表如下：

解释：

• 47、7均是由散列函数得到的没有冲突的散列地址。Hash(key)=key mod 11=47 % 11 =3，

  Hash(key)=key mod 11=47 % 11 =7。

• Hash(29)=7，散列地址有冲突了，需要寻找下一个空的散列地址：由H1=(Hash(29)+1) mod 11 = 8，散列地址8为空，因此将29存入。

• 11、16、92均是由散列函数得到的没有冲突的散列地址。

• 另外，22、8、3同样再散列地址上有冲突，也是有Hi找到空的散列地址。

  • H1(22)=(Hash(22)+1) mod 11 = 1。

  • H1(16)=(Hash(16)+1) mod 11 = 5。

  • 这里key=3需要找3回地址，第一回：H1(3)=(Hash(3)+1) mod 11 = 4。发现4已经被占用了，然后再寻地址，第二回：H2(3)=(Hash(3)+2) mod 11 = 5。发现5依然被占用，再寻地址，第三回：H3(3)=(Hash(3)+3) mod 11 = 6。发现6是空的，所以将key=3放在下标为6处。

    我们可以发现，key=3再寻地址过程中，如果不成，di变量是递增的。di=1/2/3。

4.4.1.2、二次探测法

关键码集为{47、7、29、11、16、92、22、8、3}。

设：

​ 散列函数为：Hash(key) = key mod 11

​ Hi=(Hash(key)+di) mod m

其中：m为是散列表长度，m要求是某个4k+3的质数；di为增量序列：{1^2，-12，2^2，-22，…，q^2，-q2}

求得散列表：

解释：

• 11、47、92、16、7均是由散列函数得到的没有冲突的散列地址。根据这个方法即可Hash(key) = key mod 11。

• 22、29、8，散列地址有冲突了，需要寻找下一个空的散列地址，但只需要一次寻址即可。根据这个方法即可H1=(Hash(22)+1) mod 11 = 1

• 3，散列地址有冲突了，需要寻找下一个空的散列地址，并且需要两次寻址，第一回寻址：H1=(Hash(3)+1^2) mod 11 = 4，发现任有冲突，第二回寻址：H2=(Hash(3)-1^2) mod 11 =2，下表为2的位置空着，所以找到空的散列地址，存入。

  可以发现，再3的寻址过程中，di变量为：{1^2，-12，2^2，-22…}

4.4.1.3、伪随机探测法

根据上面两个方法的学习，我们也能感知到伪随机探测法的__di变量__是伪随机数。

Hi=(Hash(key)+di) mod m

其中：m为是散列表长度，di为伪随机数。

4.4.2、链地址法（拉链法）

__基本思想：__相同散列地址的记录链成一单链表，__m个散列地址就设m个单链表，__然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。

例如：一组关键字为{19，14，23，1，68，20，84，27，55，11，10，79}

散列函数为：Hash(key)=key mod 13

因为：

• 14、1、27、79对13取余值都为1，所以可以将它们链接在一起。
• 68，55对13取余值都为3，所以可以将它们链接在一起。
• 19、84对13取余值都为6，所以可以将它们链接在一起。
• 20对13取余值都为7，所以可以将它们链接在一起。
• 23、10对13取余值都为10，所以可以将它们链接在一起。
• 11对13取余值都为11，所以可以将它们链接在一起。

所以得到如下表格：

对链地址法有了大概的认知后，我们来看看链地址法的步骤。

核心步骤

• Step1：取数据元素的关键字key，计算其散列函数值（地址）。若该地址对应的链表为空（链表为空代表直接寻址成功了），则将该元素插入此链表；否则执行Step2进行解决。
• Step2：根据选择的冲突处理方法，计算关键字key的下一个存储地址。若该地址对应的链表不为空，则利用链表的头插法或尾插法将该元素插入此链表。

链地址法的优点：

• 非同义词不会冲突，无“聚集”现象。（而开放地址法中的三种解决冲突的方法，会产生冲突，是只不过在检测到地址冲突后，可以再次寻址，直到没有冲突。）
• 链表上结点空间动态申请，更适合于表长不确定的情况。

4.5、散列表的查找

上面学习了散列表的构造，以及解决冲突和空间效率问题。

下面我们来学习散列表的查找。

如果给定值查找值k，查找过程：

例题：

已知一组关键字{19，14，23，1，68，20，84，27，55，11，10，79}

散列函数为：H(key)=key mod 13 ，散列表长为m=16，设每个记录的查找概率相等

__解法一：用线性探测法处理冲突，即__Hi=(H(key)+di) mod m

解释：

• H(19)=6，没被占用，直接存储。
• H(14)=1，没被占用，直接存储。
• H(23)=10，没被占用，直接存储。
• H(1)=1，冲突，再次寻址：
  • H(1)=(1+1) mod 13 = 2，没被占用，直接存储。
• H(68)=3，没被占用，直接存储。
• H(20)=7，没被占用，直接存储。
• H(84)=6，冲突，再次寻址：
  • H(84)=(6+1) mod 13 = 7，冲突，再次寻址
  • H(84)=(6+2) mod 13 = 8，没被占用，直接存储。
• H(27)=1，冲突，再次寻址：
  • H(27)=(1+1) mod 13 = 2，冲突，再次寻址
  • H(84)=(1+2) mod 13 = 3，冲突，再次寻址
  • H(84)=(1+3) mod 13 = 4，没被占用，直接存储。

…（后面寻址的次数很多这里不在列出）。

现在散列表已经构造好了，现在怎么查找呢？

既然散列函数，H(key)=key mod 13

那我们就将要找的key mod 13的余数，这个余数对应数组的下标，如果匹配，说明查找成功，如果不匹配再根据线性探测法的di变量取一次+1去查找。

例子：

• 查找的值为19，19 mod 13 = 6，说明下标为6存储key19的数据。
• 查找的值为14，14 mod 13 = 1，说明下标为1存储key19的数据。

但是也有一次查找不成功的，如下：

• 查找的值为84，84 mod 13 = 6，但是下标为6的位置存储的不是key=84，这个时候怎么办呢？注意这个时候需要用题目中给解决冲突问题的规则取处理，题目中说了用线性探测法处理冲突这个方法的di变量集合是{1,2,3,4,…,}

  所以此时下标为6找不到，将6+1=7，查找下标为7的位置，发现还查找不到。那就6+2=8，发现这次查找了。可以发现每次需要加di变量的值。因为根据解决冲突方法的不同，那di变量也不一样，那查找的方式也就不一样。

这里查找只列举几个例子，下面红色数字标记每个key需要查找的次数：

那此散列表的ASL=(1*6+2+3*3+4+9)/12=2.5。

__解法二：__用链地址法处理冲突

关键字{19,14,23,1,68,20,84,27,55,11,10,79}

散列函数：H(key)=key mod 13

可以得到如下散列表：

那查找每个key的次数是多少呢？

所以次ASL=(1*6+2*4+3+4)/12=1.75

4.6、散列表查找效率分析

使用平均查找长度ASL来衡量查找算法，ASL取决于三个因素：

• 散列函数

• 处理冲突的方法

• 散列表的装填因子α

  • 装填因子：

    

比如上面例题中的解法一，数组长度为16，但元素个数为12，那α=12/16=0.75。

可以发现：α越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。

ASL与装填因子α有关，既不是严格的O(1)，也不是O(n)。

那下面有个大约平均查找长度ASL的公式：

关于散列表的几点结论：

• 散列表技术具有很好的平均性能，优于一些传统的技术。
• 链地址法优于开地址法。
• 除留余数法散列函数由于其它类型函数。