【哈希表：哈希函数构造方法、哈希冲突的处理】

预测未来的最好方法就是创造它💦

目录

一、什么是Hash表

二、Hash冲突

三、Hash函数的构造方法

  1. 直接定址法
  2. 除余法
  3. 基数转换法
  4. 平方取中法
  5. 折叠法
  6. 移位法
  7. 随机数法

四、处理冲突方法

  1. 开放地址法
   • 线性探测法
   • 双散列函数法
  2. 拉链法

---

一、什么是Hash表

  哈希表（Hash Table），也叫散列表，是一种根据关键字直接访问内存存储位置的数据结构。它通过把关键字映射到哈希表中一个位置来访问记录，以加快查找的速度。

  哈希表是由哈希函数和数组组成的，通过哈希函数将关键字转换成数组的下标，然后把该关键字存储在这个下标所对应的数组元素中，从而实现快速的查找、插入和删除操作。

二、Hash冲突

  当不同的关键字被映射到同一个数组下标时，就发生了哈希冲突（Collision）。哈希表解决冲突的方式有多种，常见的方式是使用链式法（Chaining）和开放地址法（Open Addressing）。

三、Hash函数的构造方法

  对于Hash函数的构造，没有特定的要求，所以方法很多，只是我们需要了解，什么样的哈希函数，才叫好的Hash函数，这样就便于我们根据实际情况来构造合理的Hash函数。
  衡量一个哈希函数是否合理，是否是一个好的哈希函数，就看哈希函数对一组关键字所产生的冲突的频率有多高，如果一个哈希函数能够尽量的避免掉这些冲突，那么这个哈希函数就是一个好的哈希函数。

1. 直接定址法

  取关键字或关键字的某个线性函数值为哈希地址。即：
    H(key) = key 或 H(key) = a*key +b

2. 除余法

  以关键码除以表元素总数后得到的余数为存储地址

例:

对21，30，11三个数，利用k MOD 3的方式，求他们的哈希地址有:
21 MOD 3=0
30 MOD 3=0
11 MOD 3= 2

3. 基数转换法

  将关键码看作是某个基数制上的整数，然后将其转换为另一基数制上的数，转换后得到的数据就是存储地址

例：
对21、30、11进行基数转换法求哈希地址。

假设这三个数看成是八进制数(不一定是八进制数，只是假设)，转成十进制有:17、24、9

4. 平方取中法

  先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。

例：
对:21、30、11进行平方取中法求哈希地址(取中间的一位)。

21x21 = 441   4
30x30 = 900   0
11x11 = 121   2

5. 折叠法

  折叠法是一种常见的哈希函数构造方法，其基本思想是将关键字分组后，每组相加、相乘或进行异或运算，然后得到一个总和值。最后，按照需求截取其中一段作为哈希值。

折叠法的具体实现方式如下：

1. 将关键字分成若干段，每段固定长度（通常为哈希表大小），不足时可以补0或者随机数。

2. 对每段进行相加、相乘或进行异或运算，得到一个中间值。

3. 所有中间值相加或相乘得到一个总和值。

4. 按照需求截取其中一段作为哈希值。

---

  假设我们要将数字 12345678 转换成哈希值。为了方便起见，我们将其分成两段，每段四个数字。由于 1234 和 5678 长度相同，可以直接采用加法或者乘法的方式计算中间值。

以下是一种可能的折叠法实现方法：

1. 将数字 12345678 分成两段：1234 和 5678。

2. 将每段数字逆序排列得到 4321 和 8765。

3. 将每段数字相加或相乘得到中间值。

 例如，我们选择将每段数字相加：

• 中间值 1：4+8=12；

• 中间值 2：3+7=10；

• 中间值 3：2+6=8；

• 中间值 4：1+5=6；

4. 将所有中间值相加得到总和值：12+10+8+6=36。

5. 按照需求截取其中一段作为哈希值。假设哈希表大小为 10，因此选择取总和值的最后一位 6 作为哈希值。

因此，使用折叠法将数字 12345678 转换成哈希值为 6。

6. 移位法

  将关键码分为多段，左边的段右移，右边的段左移，然后将它们叠加。和折叠法相似。

7. 随机数法

  随机数法是一种基于随机数的哈希函数构造方法，它主要通过将关键字和一个在某个范围内随机生成的常数进行运算，从而得到一个哈希值。这种方法的优势在于对大部分数据集都能够提供比较均匀的哈希分布。

  假设我们有一个数字 666，现在我们想要将它映射为某个哈希表中的桶号，我们可以按照以下步骤进行：

1. 选取一个随机数，假设为 x；

2. 对于 666这个数字，将它与 x 相乘得到一个新的数字；

3. 将这个新的数字除以桶的数量，然后将余数作为桶号返回即可。

例如，我们选取 x = 9876，并且哈希表中总共有 100 个桶。那么，使用随机数法将 666映射到相应的桶号的过程如下：

1. x = 9876

2. new_key = 666* 9876 = 6577416

3. bucket_id = new_key % 100 = 16

因此，在桶数量为 100 ，随机数为 9876 的情况下，数字 666的哈希值为 16。

需要注意的是，如果随机数选择不当，也有可能会导致哈希冲突，因此在实际应用中需要根据具体情况选择合适的随机数，并且根据哈希键值的特征做出相应的调整。

四、处理冲突方法

  哈希函数在将关键字映射到桶中时，由于桶数量的限制和哈希函数本身的不可避免性质，可能会出现多个关键字映射到同一个桶中的情况，即产生了哈希冲突。为了解决这种问题，常用的处理方法有以下几种：

1. 开放地址法

  开放地址法是一种简单有效的哈希冲突处理方法。当发生哈希冲突时，就尝试在哈希表中另外寻找空桶来存储该关键字，通常包括线性探测法、双散列函数法等方式，直到遇到空桶或达到最大探测次数为止。这种方法具有简单、高效的特点，但是会导致集群化、二次聚集等问题。

1. 线性探测法
     线性探测法是一种应用较为广泛的哈希冲突解决方法。当出现哈希冲突时，线性探测法会从当前索引值往后顺序查找下一个可以使用的空桶，并将新元素插入该空桶中。
     具体而言，当哈希函数计算得到的桶已经被占用（即存在冲突）时，线性探测法通过沿着连续下一位置的方式来寻找空闲的桶。假设当前我们要插入的元素的哈希值为 h，则线性探测法的插入流程大致如下：

   1. 如果桶 h 为空，则将元素直接存储到桶 h 中；

   2. 如果桶 h 不为空，则从桶 h 的下一项开始，依次检查其后面所有的相邻桶，直到找到一个空桶 k，然后将元素存储在空桶 k 中；

   3. 如果从桶 h 开始，依次检查完了哈希表中所有的桶，但是没有找到空桶，则认为哈希表已满，此时需要进行哈希表扩容等操作才能继续向其中添加元素。
      
      同时，在哈希表中查询某个元素时，也需要采用类似的方式来进行查找。具体而言，查询时从哈希函数计算得到的初始桶 h 开始，逐个检查当前桶、其下一项、再下去的下一项等等直到查询到的元素或者一个空桶为止。
      

需要注意，线性探测法虽然简单，但是容易出现堆积和聚集的问题，导致哈希表的效率急剧降低。因此，在实际应用中，如果采用了线性探测法作为哈希表存储冲突处理的方法，就需要根据具体情况进行调整，以避免这种问题的发生。

2. 双散列函数法
     双散列函数法也是一种常见的开放地址哈希表冲突解决方法，它通过构造两个不同的哈希函数，分别计算出可能的插入位置，以此来避免冲突，并且添加新元素时按照一个固定的步长，在空桶之间线性查找下一个可以使用的位置。
     具体来说，对于双散列函数法，假设我们有两个哈希函数 h1、h2，在哈希表中查找第 i 个关键字时，计算其哈希值有两种方式：

   1. 计算第一层哈希：h1(key)=ih1​(key)=i
      如果第 h1(i) 个桶为空，则将关键字存储在该桶中。否则执行第二步；

   2. 计算第二层哈希：h2(key)=1+(imod  m−1)h2​(key)=1+(imodm−1)
      从第 h2(i) 个桶开始向后顺序查找空桶，直到找到空桶并将新元素存储在该处。

其中，步骤 2 中的 「1」可理解为步长，这里常常选择m - 1作为其值，m 表示哈希表的桶数。这样计算出的 h2(i) 内部等于 i+1i+1 在模mm下的余数，使得整个哈希表能够被覆盖到，不会出现漏掉某些桶的情况。

2. 拉链法

  拉链法使用了链表数据结构来解决哈希冲突。具体而言，对于哈希表中的每个桶，我们不再将其存储单个元素，而是维护一个指向链表头部的指针，这个链表包含了所有映射到该桶上的关键字。

例如：

对于关键字集合{4, 11, 16, 54}和桶数 m=5，我们需要确定每一个关键字在哈希表中的存储位置。

首先可以使用某个常见的哈希函数如：h(key)=key mod p，其中 p 是一个比 m 小的素数，在这里 p=5。根据该哈希函数，我们可以求得各个关键字的哈希值：

h(4)=4 mod 5 = 4

h(11)=11  mod  5 = 1

h(16)=16  mod  5 = 1

h(54)=54  mod  5 = 4

因为 11 和 16 的哈希值相同，它们属于同一个桶，因此需要将它们分别插入到同一个链表中。最终，我们可以得到下面这张包含所有关键字的哈希表表示：

0	1	2	3	4
	11 -> 16			4 -> 54

其中，表格的每一列表示一个桶，在第 i 列中的元素都是哈希值为 i 的关键字列表。

在实际情况中哈希函数和桶数的选择都需要经过合理设计和评估，我们通常需要考虑许多因素如质数选取、哈希函数效率、动态扩容、负载因子等等以保证哈希表的正常运行。