数据结构基础详解:哈希表【理论计算篇】开放地址法_线性探测法_拉链法详解

哈希表（散列表）

1. 哈希表(散列表)的基本概念

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

解释说明 已知关键字，能计算出来它的存储地址

若不同的关键字通过散列函数映射到同一个值，则称他们为“同义词”。

通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”

给出一个具体实例：

注意在本题中，采用处理冲突的方法是拉链法，即两个关键字，映射到相同的地址，就让他们之间顺序的指向

1.查找27的过程：

27%13=1 顺序查找地址1，查到第三个成功查到了27。

2.查找21的过程：

21%13=8，为空。

查找长度为0

查找长度-- 在查找运算中，需要对比关键字的次数称为查找长度

:three: ASL~成功~

（1*6+2*4+3*1+4*1）/12=1.75

平均成功查找长度=查找成功各情况比较的总次数/查找成功的情况总数

最理想的情况

:four: 平均失败查找长度

（0+4+0+2+0+0+2+1+0+0+2+1+0）/13=0.92

平均失败查找长度：从头带尾都查找失败的总次数/散列表长度 其实就是：表中记录数/散列表长度 平均失败查找长度又叫装填因子a ，，，，，，，，，，，，

引出下文：

不难发现，哈希表最重要的两部分是

如何让关键值分布的均匀------散列函数解决

如果冲突了怎么处理 ----------处理冲突的方法

2. 常见的散列函数

2.1 除留余数法

H(key)=key%p

散列表表长为m，取一个不大于m但最接近或等于m单的质数p,这个p作为散列表新的表长

为什么取最大质数？

让不同关键字的冲突尽可能少。所以即使散列表本身是15，为了减少冲突，还是得取13

2.2 直接定址法

直接定址法

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

适合分布基本连续的情况，如存储同一个班级的学生信息，班内学生学号为(1120112176~1120112205),设计哈希函数为H(key)=key-1120112176

若分布不连续，空位就会比较多，会造成存储空间的浪费。

2.3 数字分析法

选取数码分布较为均匀的若干位作为散列地址

数码在各位上出现的频率不一定相同，可能在某些位上分布的均匀，某些位不均匀

2.4 平方取中法

取关键字的平方值的中间几位作为散列地址

具体取多少位要视实际情况而定。这种方法得到的散列地址与关键的每位都有关系

总结：散列查找是典型的用空间换时间的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低。

3. 处理冲突的方法

3.1 拉链法

前面提到的拉链法就是处理冲突的一种方法

3.2 开放定址法

• 线性探测法
• 平方探测法
• 伪随机序列法3.2.1开放地址法的定义开放地址法的核心就是说把其他地址开放，发生冲突时，可以把关键字放入其他的地址 数学公式 H~i~=(H(key)+d~i~)%m，其中m是<font color="red">表长!!!</font> d~i~是增量序列，根据d~i~的不同，可以分为三种方法。
• :star:线性探测法
• 平方探测法
• 伪随机序列法 ==注意==：H(key)是哈希函数，哈希函数的计算是哈希函数，开放地址的计算是另一个东西，切不可混淆。尤其是哈希函数➗的是我们人为设置的，而开放地址法➗的是表长。

使用开放地址法计算ASL的时候，要注意空位置的判断也要算作一次比较，和上面的拉链法不同，可以理解为拉链法比较的是空指针，开放地址法是空的元素，所以算作一次

采用开放定址法时，删除结点不能简单地将被删结点的空间置为空，要做一个删除标记，进行逻辑删除(只能逻辑删除)，如果不这么做，后面再查找时，可能会出现中间出现截断就不查找了，直接算查找失败了.

3.2.2 开放地址法的三种方法

1.线性探测法：

d~i~=0，1，2，3，4....m-1，即发生冲突时，每次往后探测相邻的下一个单元是否为空。

d~i~，意味着发生第0次冲突，d~i~取0，+d~i~就是+0，意味着发生第1次冲突，d~i~取1，+d~i~就是+1

举一个计算ASL成功的例子

举出一个查找失败的例子:

2.平方探测法：

d~I~=0^2^,1^2^,-1^2^,2^2^,-2^2^,...,k^2^,-k^2^

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

注意一点,一个坑：平方探测法散列表长度m必须是一个可以表示4j+3的素数，才能探测到所有位置。

3.伪随机序列法：d~i~=某个伪随机序列，如d~i~=0,5,24,11,....

3.3 再散列法(再哈希法)

准备多个散列函数，一个发生冲突就用下一个。

4. 重难点题型总结

4.1 拉链法求平均成功查找长度与查找失败长度

ASL~成功~要横着看，（一次查找到的结点数+2*两次的查到的结点数+...n*n次查到的结点数）/表中所有的结点数

ASL~失败~=表中所有的结点数/mod的数

解释说明，上面给出的ASL~失败~只是一种数值相等的公式，并不是理解。

拉链法中空指针算0次比较，所以拉链法在每一种查找失败的情况，就是该条链下结点的个数，mod的数，就是情况数，比如mod7，会得到0-6，7种情况。

例题如下:

【1999年 9分】

4.2 开发地址法之线性探测法求平均成功查找长度与查找失败长度

重点讲解：

1.当用哈希函数算完之后，使用线性探测的时候，要注意，分母变成了表长，不是哈希函数中的modx中的x，并且使用结果是上一步中哈希函数的结果，比如算完46%11=2，假设表长为13，线性探测就是（2+1）%13，而不是（46+1）%13，也不是（2+1）%11，这都是值得注意的。

2.在计算平均查找失败长度的过程中，每一次的情况是遇到空的时候就停止。

分母是映射空间，哈希函数是mod7，地址空间就是0-6，7种情况，从为0的情况出发一直加到6的情况

3.查找成功就是比较次数，这里不多说了

例题1:

例题2:

4.3 开发地址法之平方探测法求平均成功查找长度

根据题目给出的H~i~函数，来具体进行平方探测法的计算，本质和线性探测是一回事

例题1: