HASH 碰撞问题一直没真正搞懂？这下不用慌了
HASH 算法介绍
散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或 hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。
哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即 key，即可查找到其对应的值。
哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
Hash 算法可以将一个数据转换为一个标志，这个标志和源数据的每一个字节都有十分紧密的关系。Hash 算法还具有一个特点，就是很难找到逆向规律。
Hash 算法也被称为散列算法，Hash 算法虽然被称为算法，但实际上它更像是一种思想。Hash 算法没有一个固定的公式，只要符合散列思想的算法都可以被称为是 Hash 算法。
常用 HASH 算法
常见 Hash 算法介绍：
1）MD4
MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest（消息摘要） 的缩写。它适用在 32 位字长的处理器上用高速软件实现——它是基于 32 位操作数地位操作来实现的。
2）MD5
MD5（RFC 1321）是 Rivest 于 1991 年对 MD4 的改进版本。它对输入仍以 512 位分组，其输出是 4 个 32 位字的级联，与 MD4 相同。MD5 比 MD4 来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。
3）SHA-1 及其他
SHA1 是由 NIST NSA 设计为同 DSA 一起使用的，它对长度小于 264 的输入，产生长度为 160bit 的散列值，因此抗穷举（brute-force）性更好。SHA-1 设计师基于和 MD4 相同原理，并且模仿了该算法。
HASH 算法的性质
所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。
散列表，它是基于快速存取的角度设计的，也是一种典型的“空间换时间”的做法。顾名思义，该数据结构可以理解为一个线性表，但是其中的元素不是紧密排列的，而是可能存在空隙。
比如我们存储 70 个元素，但我们可能为这 70 个元素申请了 100 个元素的空间。70/100=0.7，这个数字称为负载因子。
我们之所以这样做，也是为了“快速存取”的目的。
我们基于一种结果尽可能随机平均分布的固定函数 H 为每个元素安排存储位置，这样就可以避免遍历性质的线性搜索，以达到快速存取。
这类似于 70 个人去一个有 100 个椅子的饭店吃饭。散列函数的计算结果是一个存储单位地址，每个存储单位称为“桶”。设一个散列表有 m 个桶，则散列函数的值域应为［0，m-1］。
哈希碰撞是什么？
如果不同的输入经哈希映射得到了同一个哈希值，就发生了"哈希碰撞"（collision）。
假设 hash 表的大小为 11（即有 11 个槽），现在要把一串数据存到表里：1，2，3，4，5，6...
简单计算一下：hash(1) = 5, 即数据 1 应该放在 hash 表的第 5 个槽里；hash(2)=1，所以数据 2 应该放在 hash 表的第 1 个槽里；hash(3)=1，也就是说，数据 3 也应该放在 hash 表的第 1 个槽里——于是就造成了碰撞（也称为冲突）。
Hash 冲突常用解决方案
常用的 Hash 冲突解决方法有以下几种：
1. 开放寻址法
这种方法也称再散列法，其基本思想是：当关键字 key 的哈希地址 p=H（key）出现冲突时，以 p 为基础，产生另一个哈希地址 p1，如果 p1 仍然冲突，再以 p 为基础，产生另一个哈希地址 p2，…，直到找出一个不冲突的哈希地址 pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：
线性探测再散列
二次探测再散列
伪随机探测再散列
di=伪随机数序列。
具体实现时，应建立一个伪随机数发生器，（如 i=(i+p) % m），并给定一个随机数做起点。
例如，已知哈希表长度 m=11，哈希函数为：
则 H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为 69，则 H（69）=3，与 47 冲突。
case1：如果用线性探测再散列处理冲突
下一个哈希地址为
仍然冲突，再找下一个哈希地址为
还是冲突，继续找下一个哈希地址为
此时不再冲突，将 69 填入 5 号单元。
case2：二次探测再散列处理冲突
下一个哈希地址为：
仍然冲突，再找下一个哈希地址为
此时不再冲突，将 69 填入 2 号单元。
case3：用伪随机探测再散列处理冲突
且伪随机数序列为：2，5，9，……..，则下一个哈希地址为
仍然冲突，再找下一个哈希地址为
此时不再冲突，将 69 填入 8 号单元。
2.再哈希法（Rehash）
这种方法是同时构造多个不同的哈希函数：
Hi=RH1（key） i=1，2，…，k
当哈希地址 Hi=RH1（key）发生冲突时，再计算 Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
3.链地址法（拉链法）
这种方法的基本思想是将所有哈希地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
链地址法优缺点分析：
优点
1）拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
2）由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
3）开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
4）在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
而对开放地址法构造的散列表，空地址单元(即开放地址)都是查找失败的条件，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径。只能在被删结点上做删除标记，而不能真正删除结点。
缺点
拉链法的缺点是：
指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
Hash 算法用途
1.数据校验
上面说到的 md5 就是其中的一个, 好像还有一个什么 SHA, 不过我不知道, 也就不展开探讨了.
md5 可以将一个文件经过计算转换成一个指定长度的字符串, 可以防止文件被篡改, 但是通过加密后的字符串很难逆向推出原文.
前面那个例子可以看到, 即使文件被修改了一点点, 也会导致计算后的值发生很大变化.
2.唯一标识
比如说, 现在有十万个文件, 给你一个文件, 要你在这十万个文件中查找是否存在. 一个很笨的办法就是把每一文件都拿出来, 然后按照二进制串一一进行对比. 但是这个操作注定是比较费时的.
可以用哈希算法对文件进行计算, 然后比较哈希值是否相同. 因为存在哈希冲突的情况, 你可以在相同哈希值的文件再进行二进制串比较.
3.哈希表
在哈希表中使用哈希函数已经并不陌生了, 在此不再赘述。
4.负载均衡
比如说, 现在又多台服务器, 来了一个请求, 如何确定这个请求应该路由到哪个路由器呢?当然, 必须确保相同的请求经过路由到达同一个服务器. 一种办法就是保存一张路由关系的表, 比如客户端 IP 和服务器编号的映射, 但是如果客户端很多, 势必查找的时间会很长. 这时, 可以将客户端的唯一标识信息(如:IP、username 等)进行哈希计算, 然后与服务器个数取模, 得到的就是服务器的编号.
5.分布式存储
当我们有大量数据时, 一般会选择将数据存储到多个服务器, 为了提高读取与写入的速度嘛. 决定将文件存储到哪台服务器, 就可以通过哈希算法取模的操作来得到。
总结
HASH 算法作为编程应用的基础知识点，本文主要介绍了 HASH 算法碰撞，以及常用的碰撞解决方案如下：
开放寻址法
再哈希法
链地址法
HASH 算法常用于：
数据校验
唯一标识
哈希表
负载均衡
- END -
作者：架构精进之路，专注软件架构研究，技术学习与个人成长，关注并私信我回复“01”，送你一份程序员成长进阶大礼包。
文章首发于同名公众号《架构精进之路》，原文链接：HASH碰撞问题一直没真正搞懂？这下不用慌了
Thanks for reading!
版权声明: 本文为 InfoQ 作者【架构精进之路】的原创文章。
原文链接:【http://xie.infoq.cn/article/9f4997cd5cfa83d5c2f42fd6d】。文章转载请联系作者。
坚持分享接地气儿的架构技术文章！ 2018.02.26 加入
同名微信公众号「架构精进之路」，专注软件架构研究，技术学习与职业成长！坚持原创总结、沉淀和分享，希望能带给大家一些引导和启发，感谢各位的支持(关注、点赞、分享)！
评论