了解什么是哈希表

前言

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

1、什么是哈希表

1.1 哈希表的整体概念

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

1.2 举例说明

1.2.1 例子1

1.2.2 例子2

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 数字分析法

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 = 伪随机数序列，称为随机探测再散列

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之间，当α大于这个区间，就应该对哈希表进行扩容。