哈希算法详解

Love The Way You Lie 2023-10-03 07:34 29阅读 0赞

### 前言 ###

哈希(Hash)或者说散列表，它是一种基础数据结构。Hash 表是一种特殊的数据结构，它同数组、链表以及二叉排序树等相比较有很明显的区别，但它又是是数组和链表的基础上演化而来，既具有数组的有点，又具有链表的有点。能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。应用了函数映射的思想将记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。

### Hash设计思想 ###

试想如果我们对一个数组进行查询，这个数组里，每一个元素都是一个字符串。我们知道数组最快的检索办法是通过数组的下标进行检索，但是对于这种场景，我们无能为力，只能从头查到尾，从而查询出目标元素。  
![在这里插入图片描述][20210711204111207.PNG_pic_center]

如果我们要根据名字找到其中的任何一个元素，就需要遍历整个数组。最坏情况下时间复杂度是O(n) ,但是借助 Hash 可以将时间复杂度降为O(1)。

Hash表采用一个映射函数 f :key —> address 将关键字映射到该记录在表中的存储位置，从而在想要查找该记录时，可以直接根据关键字和映射关系计算出该记录在表中的存储位置，通常情况下，这种映射关系称作为Hash函数，而通过Hash函数和关键字计算出来的存储位置（注意这里的存储位置只是表中的存储位置，并不是实际的物理地址）称作为Hash地址。比如上述例子中，假如联系人信息采用Hash表存储，则当想要找到 “lisi” 的信息时，直接根据 “lisi” 和 Hash 函数计算出 Hash 地址即可。

所谓的 hash 算法就是将字符串转换为数字的算法。为了更好说明这种设计思想，笔者先设计出一种最笨的 Hash 函数，将所有字符串中的字符转化为数字后相加。  
![在这里插入图片描述][20210711204136816.PNG_pic_center]  
上表中数组的下标就是字符串对应的数字值。根据对应的数字值，我们就能轻易找到任何想要的对象，时间复杂度为O(1)。

### Hash函数设计 ###

所谓的 hash 算法就是将字符串转换为数字的算法。通常有以下几种构造 Hash 函数的方法：

##### 2.1 直接定址法 #####

取关键字或者关键字的某个线性函数为 Hash 地址，即address(key) = a \* key + b; 如知道学生的学号从2000开始，最大为4000，则可以将address(key)=key-2000(其中a = 1)作为Hash地址。

##### 2.2 平方取中法 #####

对关键字进行平方计算，取结果的中间几位作为 Hash 地址。如有以下关键字序列 \{421，423，436\} ，平方之后的结果为 \{177241，178929，190096\} ，那么可以取中间的两位数 \{72，89，00\} 作为 Hash 地址。

##### 2.3 折叠法 #####

将关键字拆分成几部分，然后将这几部分组合在一起，以特定的方式进行转化形成Hash地址。如图书的 ISBN 号为 8903-241-23，可以将 address(key)=89+03+24+12+3 作为 Hash 地址。

##### 2.4 除留取余法 #####

如果知道 Hash 表的最大长度为 m，可以取不大于m的最大质数 p，然后对关键字进行取余运算，address(key)=key % p。这里 p 的选取非常关键，p 选择的好的话，能够最大程度地减少冲突，p 一般取不大于m的最大质数。

### Hash表大小的确定 ###

Hash 表的空间如果远远大于实际存储的记录数据的个数，则造成空间浪费；如果过小，则容易造成冲突。Hash 表大小确定通常有这两种思路：

如果最初知道存储的数据量，则需要根据存储个数 和 关键字的分布特点来确定 Hash 表的大小。

事先不知道最终需要存储的记录个数，需要动态维护Hash表的容量，此时可能需要重新计算 Hash 地址。

### Hash 冲突及解决方案 ###

##### 4.1 Hash冲突产生 #####

有这样一个问题：因为我们是用数组大小对哈希值进行取模，有可能不同键值所得到的索引值相同，这里就是冲突。如在最初的实例中，如果多出了sizhang这样一个元素，那么就存在两个 756。  
![在这里插入图片描述][20210711204442300.PNG_pic_center]  
显然出现的这种情况是不合理的，解决该冲突的方法就是改变数据结构。我们将数组内的元素改变为一个链表，这样就能容下足够多的元素了，冲突问题也能得到解决。具体如何解决请看下面的链地址法。

##### 4.2 Hash 冲突解决 #####

**4.2.1 开放定址法**

发生冲突时，使用某种探测技术在 Hash 表中形成一个探测序列，然后沿着这个探测序列依次查找下去，当碰到一个空的单元时，则插入其中。比较常用的探测方法有线性探测法，如有一组关键字\{12，13，25，23，38，34，6，84，91\}，Hash 表长为14，Hash 函数为 address(key) = key % 11，当插入12，13，25时可以直接插入，而当插入 23 时，地址 1 被占用了（因为 12%11 和 23%11 的结果相同）。

此时沿着地址 1 依次往下探测(探测步长可以根据情况而定)，直到探测到地址4，发现为空，则将 23 插入其中。

**4.2.2 链地址法**

采用数组和链表相结合的数据结构，将 Hash 地址相同的记录存储在一张线性表中，而每张表的表头的序号即为计算得到的Hash地址。如下图最左边是数组结构，数组内的元素为链表结构。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3_size_16_color_FFFFFF_t_70_pic_center]  
采用链地址法形成的 Hash 表存储形式

所以针对之前案列冲突的解决方案如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3_size_16_color_FFFFFF_t_70_pic_center 1]  
检索的时候可以这样检索，首先找到gaofei后，之后再遍历链表，找到feigao了。同理对于 sizhang 的冲突也是如此解决。

### Hash 表的用处以及优劣 ###

##### 5.1 Hash 表的实际应用 #####

上述说了这么多关于 Hash 表的知识点，但是 Hash 表在代码的世界中，实际上又有什么应用场景，可能有些读者会一头雾水，这里笔者就以简单的三个例子来说明 Hash 表的实际应用场景。

**1 、找出两文件找出重复的元素**

假设有两个文件，文件中均包含一些短字符串，字符串个数分别为n。它们是有重复的字符串，现在需要找出所有重复的字符串。

最笨的解决办法可能是：遍历文件 1 中的每个元素，取出每一个元素分别去文件 2 中进行查找，这样的时间复杂度为O（n^2）。

但是借助 Hash 表可以有一种相对巧妙的方法，分别遍历文件 1 中的元素和文件 2 中的元素，然后放入 Hash Table 中，对于遍历的每一个元素我们只要简单的做一下计数处理即可。最后遍历整个 Hash 列表，找出所有个数大于 1 的元素即为重复的元素。

**2、找出两文件找出出现次数最多的元素**

同找出两文件找出重复的元素这样的问题解决方案类似，只是在最后遍历的时找计数最大的元素，即为出现次数最多的元素。

**3、路由算法**

多线程处理数据的场景下，通常需要将一个数据集分给不同的线程进行处理，同时要保证，相同的元素需要分到相同的处理线程上。这  
其实这个就是一个很典型的 Hash 值应用场景，对于很多的计算引擎默认都是用 Hash 算法去解决这个问题。因为相同元素的 Hash 值相同，那么我们可以取 Hash 之后进行模运算，运算结果分配到不同的线程。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3_size_16_color_FFFFFF_t_70_pic_center 2]

##### 5.2 Hash 表的优缺点及注意点 #####

**优点**

哈希表的效率非常高，查找、插入、删除操作只需要接近常量的时间即0(1）的时间级。如果需要在一秒种内查找上千条记录通常使用哈希表，哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。如果不需要遍历数据，不二的选择。

**缺点**

它是基于数组的，数组创建后难于扩展。有些情况下，哈希表被基本填满时，性能下降得非常严重，所以开发者必须要清楚表中将要存储的数据量。或者也可以定期地把数据转移到更大的哈希表中，不过这个过程耗时相对比较大。

**注意点**

在设计Hash算法的时候。一定要保证相同字符串产生的 Hash 值相同，同时要尽量的减小Hash冲突的发生，这样才算是好的 hash 算法。

[20210711204111207.PNG_pic_center]: https://img-blog.csdnimg.cn/20210711204111207.PNG#pic_center
[20210711204136816.PNG_pic_center]: https://img-blog.csdnimg.cn/20210711204136816.PNG#pic_center
[20210711204442300.PNG_pic_center]: https://img-blog.csdnimg.cn/20210711204442300.PNG#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210711204623950.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210711204652113.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20210711204907382.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NTcwNjA3,size_16,color_FFFFFF,t_70#pic_center