Hash算法及常见碰撞解决方法

秒速五厘米 2021-11-08 16:44 486阅读 0赞

> 转载请标明出处^\_^  
> 原文首发于： [https://www.zhangruibin.com][https_www.zhangruibin.com]  
> 本文出自于： [RebornChang的博客][https_www.zhangruibin.com]

# Hash算法及常见碰撞解决方法 #

# Hash算法及由来 #

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

哈希表是根据设定的哈希函数H（key）和处理冲突方法将一组关键字映射到一个有限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储位置，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。

通过将单向数学函数（有时称为“哈希算法”）应用到任意数量的数据所得到的固定大小的结果。如果输入数据中有变化，则哈希也会发生变化。哈希可用于许多操作，包括身份验证和数字签名。也称为“消息摘要”。

简单解释：哈希（Hash）算法，即散列函数。它是一种单向密码体制，即它是一个从明文到密文的不可逆的映射，只有加密过程，没有解密过程。同时，哈希函数可以将任意长度的输入经过变化以后得到固定长度的输出。哈希函数的这种单向特征和输出数据长度固定的特征使得它可以生成消息或者数据。  
—以上摘自网络

# Hash算法用途 #

## 1.数据校验 ##

上面说到的md5就是其中的一个, 好像还有一个什么SHA, 不过我不知道, 也就不展开探讨了.

md5可以将一个文件经过计算转换成一个指定长度的字符串, 可以防止文件被篡改, 但是通过加密后的字符串很难逆向推出原文.

前面那个例子可以看到, 即使文件被修改了一点点, 也会导致计算后的值发生很大变换.

## 2.唯一标识 ##

比如说, 现在有十万个文件, 给你一个文件, 要你在这十万个文件中查找是否存在. 一个很笨的办法就是把每一文件都拿出来, 然后按照二进制串一一进行对比. 但是这个操作注定是比较费时的.

可以用哈希算法对文件进行计算, 然后比较哈希值是否相同. 因为存在哈希冲突的情况, 你可以在相同哈希值的文件再进行二进制串比较.

## 3.哈希表 ##

在哈希表中使用哈希函数已经并不陌生了, 不再赘述.

## 4.负载均衡 ##

比如说, 现在又多台服务器, 来了一个请求, 如何确定这个请求应该路由到哪个路由器呢?当然, 必须确保相同的请求经过路由到达同一个服务器. 一种办法就是保存一张路由关系的表, 比如客户端IP和服务器编号的映射, 但是如果客户端很多, 势必查找的时间会很长. 这时, 可以将客户端的唯一标识信息(如:IP、username等)进行哈希计算, 然后与服务器个数取模, 得到的就是服务器的编号.

## 5.分布式存储 ##

## 当我们有大量数据时, 一般会选择将数据存储到多个服务器, 为了提高读取与写入的速度嘛. 决定将文件存储到哪台服务器, 就可以通过哈希算法取模的操作来得到. ##

[原文链接][Link 1]

# 一致性Hash算法 #

## 什么是一致性hash算法 ##

简单的说：为了减少碰撞，按照一定的物理规律模拟出来一个环，将自己的有限资源分布在环上，然后每当一个请求寻址过来时，按照计算给予分配环上的资源。  
以上这句话是本人自己总结的，里面有几个问题：  
1.环的构造方式是什么？  
2.怎样将有限的资源在环上分配？  
3.怎样合理有效的分配资源？  
4.怎样判断构造的环的优缺？  
…  
可以参考[本连接][Link 2]。

# Hash碰撞及避免碰撞策略 #

## Hash碰撞 ##

对象Hash的前提是实现equals()和hashCode()两个方法，那么HashCode()的作用就是保证对象返回唯一hash值，但当两个对象计算值一样时，这就发生了碰撞冲突。如下将介绍如何处理冲突，当然其前提是一致性hash。

## 避免Hash碰撞策略 ##

### 1.开放地址法(再散列法) ###

开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)  
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。  
如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k<=m/2)，称二次探测再散列。  
如果di取值可能为伪随机数列。称伪随机探测再散列。

### 2.再哈希法Rehash ###

当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。  
缺点：计算时间增加。  
比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止.这种方法不易产生聚集，但增加了计算时间。

### 3.链地址法（拉链法） ###

将所有关键字为同义词的记录存储在同一线性链表中.基本思想:将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。  
对比JDK 1.7 hashMap的存储结构是不是很好理解。至于1.8之后链表长度大于6rehash 为树形结构不在此处讨论。

#### 拉链法的优缺点 ####

##### 优点： #####

①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；  
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；  
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；  
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

##### 缺点： #####

指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

### 4.建立一个公共溢出区 ###

假设哈希函数的值域为\[0,m-1\],则设向量HashTable\[0…m-1\]为基本表，另外设立存储空间向量OverTable\[0…v\]用以存储发生冲突的记录。  
[以上部分参考自][Link 3]

注：本文为整理学习记录所用，博主不产生这种知识，只是知识的搬运工。如有侵权请告知，秒删！

[https_www.zhangruibin.com]: https://www.zhangruibin.com
[Link 1]: https://blog.csdn.net/qq_31725391/article/details/90551838
[Link 2]: https://blog.csdn.net/cb_lcl/article/details/81448570
[Link 3]: https://blog.csdn.net/zeb_perfect/article/details/52574915