哈希查找算法的构造和冲突解决方法

谢宇翔

摘要：本文对经典算法中的哈希算法（又称散列），介绍了其常用的七种构造方法和四种冲突解决方法及其原理，并通过举例，详细说明了各种方法的具体实现和适用场景。

关键词：哈希，关键字，冲突，时间复杂度，空间复杂度，大数据

正文：

在如今的大数据时代，需要各种高效，海量的数据处理技术，哈希（HASH）算法以自身的优点，被广泛应用在查找，存储，加密，校验，区块链等众多场景，大大提升了数据存储分析的效率，是不可或缺的数据处理技术。

以下就对哈希的构造和冲突解决原理进行详细的理论和举例说明。

一、哈希的构造方法[1][2]

1.直接定址法：

哈希地址：f（key）=a*key+b （a，b为常数）

简单均匀，不产生冲突，需事先知道key的分布情况，适合查找表较小且连续的情况。

举例：比方说某校从1905年起招生，则统计每届招生人数时，可以用年份-1905作为地址：

此时 f（key）=key-1905

2.数字分析法

假设关键字以固定位组成，且可能出现的关键字是事先知道的，则可取关键字的若干数位组成哈希地址。

3.平方取中法

一个数平方的中间几位与这个数的每一位都有关，因而平方取中法产生冲突的机会相对较小。所取的位数由表长决定。适合于不知道关键字分布，而位数又不是很大的情况。

4.折叠法

把一个关键字分成位数相同的几段（最后一段位数可以不同），然后将各段的叠加和（舍去进位）作为哈希地址。

事先不需要知道关键字的分布，而且关键字中每一位上数字分布大致均匀，适合关键字位数较多的情况。

5.除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得的余数为哈希地址。即 f（key） = key mod p，p<=m。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取质数或m。这是比较重要和常用的方法，被广泛使用。

6.伪随机数法

f（key） = random（key）

這里 random 是随机函数，当 key 的长度不等时，采用这种方法比较合适。

7.基数转换法

将一个数看作其它进制，然后按照新进制取其中若干位作为哈希值。一般取大于原基数的数作为转换的基数，并且两个基数是互质的。

比方说key是十进制的，那可以新的进制为十三进制，取其第3，6，9位，即f（key）=key13的第3，6，9位。

二、哈希的冲突解决

下面以创建哈希表为例，说明解决冲突的方法。

常用的解决冲突方法有以下四种：开放寻址法、再哈希法、链地址法（拉链法）和建立一个公共溢出区。[1][2]

1.开放寻址法：当关键字key的哈希地址q=f（key）发生冲突，以q为基数再生成一个哈希地址q1，若q1仍然冲突，再以q为基数生成另一个哈希地址q2，…，直到找到不冲突的哈希地址。这种方法有一个通用的再散列函数形式：

fi=（f（key）+di）%m i=1，2，…，n

其中f（key）为哈希函数，m 为表长，di称为增量序列。di的取值方式，主要有以下三种：

a） 线性探测再散列 di=1，2，3，…，m-1

b） 二次探测再散列 di=k，-k，k-1，-（k-1），…，1，-1    （ k<=m/2）

c） 伪随机探测再散列 di=伪随机数序列。

2.再哈希法：

这种方法是同时构造多个不同的哈希函数：

fi（key） i=1，2，…，k

当哈希地址f1（key）发生冲突时，再计算f2（key）……，直到冲突不再产生。

比方说fi（key） 定义为对key取5+6i的模，也就是11，17，23，29….

3.链地址法（拉链法）

这种方法的基本思想是将所有哈希地址为f（key）=i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

举例，用以上f（key）=key%13为例，首先建立一个拥有索引为13的数组，数组中每个元素为一个链表的头指针，然后在需要存放数据的时候，根据f（key）找到数组中对应元素对应的链表（头指针），然后在此链表最后插入数据。

4.建立公共溢出区：

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

三、综合实例：

问题描述[3]

A和 B各有排列好的n块积木，每块积木上写有一个小写英文字母。

允许A从自己的积木串s中丢掉任意块（也允许不丢）;允许B从自己的积木串t中丢掉左边连续的一段积木和右边连续的一段积木（也允许只丢一边或两边都不丢）。不允许丢弃自己所有积木。然后A和B分别将自己剩下的积木按原来的顺序重新排成一排。

计算一下，有多少种不同的情况下他们最后剩下的两排积木是相同的（剩下的这两排积木块数相同且每一个位置上的字母都对应相同）？

解答：因为对s的要求比较宽松，所以首先枚举t的子串，通过逐一匹配s的位，以此来获取t中可能匹配的所有子串，时间复杂度为O（n^2）。然后在累计答案处进行字符串的相等判断和去除重复，这里的比较用哈希表来大大提高效率：首先计算t每个可能字串的哈希值，把每个字符转换成ascii与‘a’的差值，即a=1，b=2，…，并把每个位以base（很大的质数）作为进制获得表示t从i到j的哈希key数组HashKey[i][j]，然后比方说采用除留余数法，以另一个大质数作为模数获得哈希地址来进行比较。若是简单的进行枚举比较，那时间复杂度将大幅度增加;和其它方法相比较，使用hash应该是时间复杂度最优的方法。

参考文献：

[1]哈希算法原理详解 https：//www.jianshu.com/p/f9239c9377c5

[2]哈希算法以及冲突解决 https：//www.itdaan.com/blog/2016/12/06/c885400f4092.html

[3]洛谷 https：//www.luogu.com.cn/problem/P7469