了解什么是哈希表

---

前言

本次将从概念上理解什么是哈希表，理论知识较多，满满干货

1、什么是哈希表

1.1 哈希表的整体概念

在我们之前学过的数据结构中，例如线性表(顺序表、链表等)和树结构(AVL树、红黑树)，在这些结构中存储的记录(数据)的相对位置是随机的，和记录的关键字key没有任何关联。在这些结构中进行查找，因为不知道key(关键字)和记录在结构中存储位置的关系，所以只能让key和结构中的记录进行一一比较，但是不一定是每个记录都要与key进行比较。在顺序查找时，比较的结果有"=“和"≠"两种可能。在二分查找或者平衡搜索树查找，比较的结果有”>“,”<“和”="三种可能。所以对于这种比较型查找，效率和比较的次数强关联，比较次数少，效率就高，比较次数多，效率就低。
对于上诉所说的情况，有没有一种可能，我们不需要通过任何比较就能找到我们想要查询的记录，当然是有可能的。只需要在记录的存储位置和它的key建立一个确定的对应关系f(也可以称之为映射关系)，使key与结构中唯一一个存储位置相对应。
说到这里，初学者可能看得不是很明白，那就举个栗子：
例如我在给别人自我介绍的时候，我说我来自重庆，此时在其他人脑海里就会联想到重庆火锅，小面等许多美食或者洪崖洞等地标性建筑。这就是一种映射关系，通过重庆这个关键字就能得到所对应的信息。
因此在查找时，只需要通过这个对应关系，就能找到key所对应的值。如果结构中存在key和我们所想要查找的K相等的记录，则必定在f(K)的存储位置上，所以我们并不需要任何比较就能找到所查记录。对于这种映射关系，我们将其称之为哈希函数，按照这个思想建立的表，我们称之为哈希表或者散列表。

1.2 举例说明

1.2.1 例子1

通过上面的概念和"判定字符是否唯一"这个题，我们就能从大体方向了解哈希表究竟是一个什么样的数据结构。至少我认为这道题直接明了的运用到了哈希思想。有兴趣的伙伴也可以尝试一下。

对于初学者(没学过哈希)来说，做这个题基本都是用暴力解法：定义52个变量，初始值为0，用于分别代表字母a~ z 和A ~ Z ，然后对字符串s进行52次遍历，统计字母出现的次数，再计算这些变量值是否相同。虽然这样做没什么问题，但是效率太低。假设字符串长度为n，那么就会对字符串进行n次遍历，时间复杂度为O(N²)。
此时就需要用到哈希思想，建立映射关系了。那如何建立映射关系呢？
每个字符(字母)是有ASCII码的，ASCLL码也是一个整数。哈希思想就是在记录的存储位置和它的key建立一个确定的对应关系，使key与结构中唯一一个存储位置相对应，通过这个特征，我们可以用数组，因为数组有下标，下标是一个整数，而且通过下标我们就可以直接确定数组中的位置，从而取得该位置中的数据。

通过这种映射，时间复杂度为O(N)，因为我们只需要遍历字符串一次就能得到所有字符出现的次数，它们分别放在了数组中对应下标的位置中。

1.2.2 例子2

假设我们建立一张全国34个地区的各名族人口统计表，每个地区为一个记录，记录的各数据项为：

显然，可以用一个一维数组C(1…30)来存放这张表，其中C[i]是编号为i的地区的人口情况。编号i便为记录的关键字，由它唯一确定记录的存储位置C[i]。例如：假设北京市的编号为1，若要查看北京市的各名族人口，只需要取出C[1]的记录即可。假如把这个数组看成是哈希表，则哈希函数f(key) = key。然而，很多情况下的哈希函数并不是如此简单
。为了查看方便，应以地区作为关键字。假设地区名以汉语拼音的字符表示，则不能简单的取哈希函数f(key) = key，而是要将这些字符转换为数字，再进行其他相关处理。例如我们可以有这样的哈希函数：

1. 取关键字中的第一个字母在字母表中的序号作为哈希函数。例如：BEIJING的哈希函数值为字母’B’在字母表中的序号等于02。
2. 先求关键字的第一个和最后一个字母在表中的序号之和，然后判别这个值，若比30(表长)大，则减去30。例如：TIANJING的首尾字母’T’和’N’之和为34，故取04为它的哈希函数值。

除了这两种哈希函数之外，还有其他很多的哈希函数，这得看自己怎么实现。
从这个例子来看：

• 哈希函数是一个映射，怎么映射，如何建立映射关系，100个人有100种想法，但是建立出来的映射关系也有好也有坏，说明哈希函数的建立是很灵活的，只要关键字通过哈希函数所得的位置在哈希表内即可。
• 对于不同的关键字通过哈希函数可能得到同一个地址，即key1 ≠ key2，而f(key1) = f(key2)，这种现象称为哈希冲突或者哈希碰撞。例如在第一种哈希函数情况下，山西、上海、山东和四川的首字母都是’H’，哈希地址均为19，但C[19]只能存放一个记录，如果存放了山西，那么其他三个记录放在何处呢？对于这种情况，需要仔细分析关键字的特性，构造出合适的哈希函数，从而避免哈希冲突的发生。

该例子来源于严尉敏老师的《数据结构与算法》一书。

1.3 小总结

一般情况下，哈希冲突只能可能的减少，无法达到完全避免的效果。因为，哈希函数是从关键字集合到地址集合的映像。表越长，数据量越少，冲突的概率就越低，表越短，数据量越大，冲突的概率就越高。在建立哈希表时不仅要设定一个好的哈希函数，也要设定一种好的处理冲突的方法。
综上所述，可如下描述哈希表：根据哈希函数和处理哈希冲突的方法，将一组记录的关键字映射到一个有限且连续的一段区间内，并以关键字处理得到地址作为记录在表中的存储位置，这种表就成为哈希表，这个过程称为哈希造表或散列，所得的存储位置称为哈希地址或者散列地址。

2、哈希函数的构造方法

构造哈希函数的方法有很多，但能尽可能的避免哈希冲突才能称得上好的哈希函数。换言之，就是关键字通过哈希函数的处理得到一个随机的地址，以便使一组关键字的哈希地址均匀的分布在整个地址区间，从而减少哈希冲突。常见的哈希函数的构造方法有以下几种：

2.1 直接定址法

取关键字或关键字的某个线性函数值为哈希地址，即：H(key) = key或者H(key) = a·key+b
其中a和b是常数(这种哈希函数叫做自身函数)。
对于上述例子1中提到的过的"判定字符是否唯一"这道题，就是采用的直接定址法。
又例如：有一个从0到100分的期末成绩数字统计表，其中，分数作为关键字，哈希函数取关键字自身

这样的话，如果要询问分数为88的有几人，则只需要查表的第88项即可。由于直接定址法所得的地址集合和关键字集合的大小相同。因此，对于不同的关键字不会发生冲突。但实际上用这种哈希函数的情况比较少。

2.2 数字分析法

假设 关键字是一个N进制数，并且哈希表中的可能出现的关键字都是事先知道的，则可以去关键字的若干数位组合成哈希地址。
例如有9个记录，其关键字为8位十进制数。

对于关键字全体的分析中，发现第①位和第②位都是‘1’和‘2’。第②位只能取‘’、‘6’和‘7’。第③位只能取‘6’和‘9’。第⑧位只能取‘2’、‘4’和‘6’。第⑨位只能取‘2’、‘3’和6。因此这些位不能取。但是对于⑤⑥⑦三位出现的数都是随机的，所以我们可以任取两位组合成为一个哈希地址。

2.3 除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得的余数为哈希地址。即：H(key) = key % p，p ≤ m
这是一种简单，也是最常用的构造哈希函数的方法。它不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。

2.4 随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即：H(key) = random(key)，其中random为随机函数。通常，当关键字长度不等时采用此方法构造哈希函数比较恰当。

2.5 小总结

除了上述所提到的方法之外，还有其他的一些哈希函数构造方法，例如平方取中法和折叠法等。
在构造哈希函数时，需要根据实际情况来考虑采用不同的哈希函数。通常需要考虑一下因素：

1. 计算哈希函数所需要的时间(包括硬件指令的因素)
2. 关键字的长度
3. 哈希表的大小
4. 关键字的分布情况
5. 记录的查找频率

3、处理哈希冲突的方法

在前面哈希表的概念中提及到好的哈希函数能够减少哈希冲突。那究竟什么是哈希冲突呢？例如下图：

因此，如何处理哈希冲突也是哈希表不可缺少的一部分。

3.1 开放定址法

H_i = H(key)+d_i)%m i = 1, 2, 3…,k(k ≤ m-1)
其中：H(key)为哈希函数，m为哈希表表长，d为增量序列，可以有下列3种取法：

1. d_i = 1, 2, 3, …, m - 1，称为线性探测再散列
2. d_i = 1², 2², 3², …, k² (k ≤ m/2)，称为二次线性探测再散列
3. d_i = 伪随机数序列，称为随机探测再散列

例如，在长度为10的哈希表中已经填入有关键字分别为35、56和97的记录(哈希函数H(key) = key % 10)，现在有第四个记录，其关键字为65，有哈希函数得到哈希地址为5，产生冲突。若采取线性探测再散列，得到下一个地址6，让然冲突，再求下一个地址，还是冲突的，知道哈希地址为8，不冲突后将该记录放入，处理哈希冲突的过程也就结束。

若采用二次线性探测再散列也类似

从上述线性探测再散列的过程中我们可以发现一个现象：当表中i，i+1，i+2位置已经被填上的时候，当下次插入数据的哈希地址为i，i+1，i+2和i+3时都会填入到i+3的位置，·这种在处理冲突过程中发生的两个第一个哈希地址不同的记录去争夺同一个后继哈希地址的现象称为“二次聚集”即在处理同义词(哈希地址相同的记录)的冲突中有添加了非同义词的冲突，显然这种对查找不利。
举个栗子：比如在一张表中，表的大小为150，如果前面100个地址所对应的空间都填入了记录，现在需要插入一个哈希地址为1的记录，经过线性探测再散列的方式，最终会将这个记录填入到哈希地址为101的空间。如果在查找这个记录时，就需要从表的起始位置开始查找，直到哈希地址为101为止。本来我们是想通过哈希表进行1次查找就能找到记录，但实际上却查找了101次，效率大大得降低了。
相对于线性探测再散列的方式，二次线性探测再散列能降低二次聚集，大家可以思考一下为什么。
但在另一方面，用线性探测再散列处理冲突可以保证做到：只要哈希表未被填满，总能找到一个不发生哈希冲突的地址。而二次探测再散列只有早哈希表长为m形如4j+3(j为整数)的素数是才有可能，随机探测再散列，取决于伪随机数列。

3.2 再哈希法

H_i = RH_i(key) i = 1，2，…，k
RH_i为不同的哈希函数。当发生哈希冲突时，需要使用其他哈希函数计算哈希地址，如果再冲突，再重复上述操作，直到不在发生哈希冲突位置。这种做法降低了"二次聚集"，但增加了计算哈希地址的时间。

3.3 链地址法

链地址法又被称为拉链法。它将所有关键字为同义词的记录存储在一张线性表中，这个线性表一般为链表。同时还需要一张表(暂时称之为A表)来存放这些线性表的指针。初始状态时，A表存放的都是空指针。凡是哈希地址为i的记录都插入到头指针为A[i]的链表中，插入的方式也是根据实际情况定，例如头插、尾插，也可在中间插入，从而保证链表中的记录有序。
例如：已知一组关键字为{99，77，57，37，21，11，3}。按照哈希函数H(key) = key%10和链地址法处理哈希冲突：

3.4 建立公共溢出区

我们不仅要构造基本表，还有构造溢出表。基本表每个空间都存放一个有效记录。溢出表存放与基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生哈希冲突，都将其填入溢出表。

4、哈希表的装填因子

虽然哈希表在关键字和记录的存储位置建立的映射关系，但是由于哈希冲突，使哈希表的查找任然需要给定值和关键字的比较。而比较次数取决于三个因素：哈希函数、处理哈希冲突的方法和哈希表的装填因子
哈希表的装填因子定义：α = 表中填入的记录数/哈希的长度，α标志哈希表的装填程度。
直直观的看α越大，表明填入的记录越多，再次插入记录时，发生哈希冲突的概率越大。α越小，表明填入的记录就越少，再次插入记录时，发生哈希冲突的概率越小。所以我们应该使α保持在某个特定的值附近，即不浪费太多的空间，也降低了哈希冲突的概率。一般而言，α最好在0.7~0.8之间，当α大于这个区间，就应该对哈希表进行扩容。