【数据结构】七、查找：3.散列查找（哈希表）

四、散列查找（哈希表）

1.散列表查找的基本概念

散列表是根据关键字而直接进行访问的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。我们只需要通过某个函数f，使得：

存储位置 = f(关键字)

那样我们可以通过查找关键字不需要比较就可获得需要的记录的存储位置。

---

散列技术既是一种存储方法， 也是一种查找方法，散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置 f(key)。查找时，根据这个确定的对应关系找到置上。

这里我们把这种对应关系 f 称为散列函数，又称为哈希(Hash)函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表(Hash table)。那么关键字对应的记录存储位置我们称为散列地址。

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词。一方面，设计得好的散列函数应尽量减少这样的冲突；另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。

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

这里使用拉链法：

2.散列函数的构造方法

2.1直接定址法

适合关键字的分布基本线性连续的情况。

直接取关键字的某个线性函数值为散列地址，散列函数为：
$$H(key)=key或H(key)=a\ast key＋b$$
式中，a和b是常数。

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

例如：0~100岁的人口数字统计表，可以吧年龄数值直接当做散列地址。

2.2数字分析法

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。

设关键字是r进制数（如十进制数)，而 r 个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。

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

例如，当手机号码为关键字时，其11位数字是有规则的，此时是无需把11位数值全部当做散列地址，这时我们给关键词抽取， 抽取方法是使用关键字的一部分来计算散列存储位置的方法，这在散列函数中是常常用到的手段。

2.3平方取中法

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

具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，

平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。

【另一种说法】适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数

这个方法计算很简单，假设关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227，用做散列地址。

再比如关键字是4321，那么它的平方就是18671041，抽取中间的3位就可以是671，也可以是710，用做散列地址。

❗2.4除留余数法

这是一种最简单、最常用的方法，假定散列表表长为 m，取一个不大于 m 但最接近或等于 m 的质数 p，利用以下公式把关键字转换成散列地址。散列函数为：
$$H(key)=key\%p(p<=m)$$
事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。

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

【原因】因为质数对其他的数没有公因子。

2.5随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址。也就是

H(key) =random(key)

这里random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

3.处理散列冲突

7.5_2_散列查找(下)_哔哩哔哩_bilibili

3.1开放定址法

所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

它的公式是：
$$H_i(key)=(f(key)+d_i)\%m(d;=1,2,3,...,m-1)$$
式中：

• Hi(key)为散列函数，i=0,1,2,…, k (k <=m - 1)。
• m表示散列列表表长。
• di为增量序列。

1. 线性探测法

+1

3.2链地址法（拉链法）

不换地方。

转换一下思路，为什么非得有冲突就要换地方呢，如果不换地方该怎么处理？于是我们就有了链地址法。

将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。

3.3再散列法

再散列法（再哈希法)︰除了原始的散列函数H(key)之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止：
$$H_i=R{H}_i(Key)i=1,2,\mathrm{3...},k$$

3.4公共溢出区法

这个方法其实就更加好理解，就是把凡是冲突的家伙额外找个公共场所待着。我们为所有冲突的关键字建立了一个公共的溢出区来存放。

就前面的例子而言，我们共有三个关键字{37,48,34}与之前的关键字位置有冲突，那么就将它们存储到溢出表中，如下图所示：

如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

4.散列表查找

查找效率取决于散列函数的填装因子α。

成正比。

• 查找成功

例如存了12个元素，那么每一个被查询的概率是 1/12。

这里第一层有6个，所以是1*6，

第二层有4个，所以是2*4，

第三层第四层分别有1个，所以是3+4。

• 查找失败

这个分子的数，就是链表的长度。