本文预计阅读需 3min
你好，我是你老朋友 Payne，大家都或许过我之前写的水文 - JS 解密入门，没看过的童鞋开源回头看看啊。里面主要讲述了 Hash MD5 的例子，以及加密与解密，相关的。那么今天我们去搞一下 MD5 的 “父亲”， Hash。主要阐述了什么是哈希，哈希运用方向以及 hash 碰撞及解决方向，请查阅
Hash 算法
哈希
（hash）也叫散列。Hash 算法，是将一个不定长的输入，通过散列函数变换成一个定长的输出，即散列值。
应用
Hash 主要应用在数据结构以及密码学领域。
数据结构：
使用 Hash 算法的数据结构叫做哈希表，也叫散列表，主要是为了提高查询的效率。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数就是 hash function，存放记录的数组叫做哈希表。 在数据结构中应用时，有时需要较高的运算速度而弱化考虑抗碰撞性，可以使用自己构建的哈希函数。
密码学：
这种 hash 散列变换是一种单向运算，具有不可逆性即不能根据散列值还原出输入信息，因此严格意义上讲 Hash 算法是一种消息摘要算法，不是一种加密算法。常见的 hash 算法有：SM3、MD5、SHA-1 等 。 在不同的应用场景下，hash 函数的选择也会有所侧重。比如在管理数据结构时，主要要考虑运算的快速性，并且要保证 hash 均匀分布；而应用在密码学中就要优先考虑 抗碰撞性 ，避免出现两段不同明文 hash 值相同的情况发生。
哈希碰撞:
不同的值经过 Hash function 得到同一值则产生哈希碰撞， 防止哈希碰撞的最有效方法，就是扩大哈希值的取值空间
1 |
16个二进制位的哈希值，产生碰撞的可能性是 65536 分之一。如果有65537个用户，就一定会产生碰撞。哈希值的长度扩大到32个二进制位，碰撞的可能性就会下降到 4,294,967,296 分之一。 |
hash 碰撞解决办法：
1. 开放地址法
- 线性探测再散列
- 二次探测再散列
-
伪随机探测再散列
1
2
3
4
5
6
7
8
9
10
11
12
13所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入 。
开放寻址法：Hi=(H(key) + di) MOD m,i=1,2,…，k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：
1)． di=1,2,3,…，m-1，称线性探测再散列；
2)． di=1^2,(-1)^2,2^2,(-2)^2,(3)^2,…，±(k)^2,(k<=m/2)称二次探测再散列；
3)． di=伪随机数序列，称伪随机探测再散列。
用开放定址法解决冲突的做法是：当冲突发生时，使用某种探测技术（线性探测法、二次探测法（解决线性探测的堆积问题）、随机探测法（和二次探测原理一致，不一样的是：二次探测以定值跳跃，而随机探测的散列地址跳跃长度是不定值））在散列表中形成一个探测序列。
沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止插入即可。 -
再哈希法
再哈希法又叫双哈希法，有多个不同的 Hash 函数，当发生冲突时，使用第二个，第三个，….，等哈希函数去计算地址，直到无冲突。 虽然不易发生聚集，但是增加了计算时间。
- 链地址法 (Java hashmap)
链地址法的基本思想是：每个哈希表节点都有一个 next 指针，多个哈希表节点可以用 next 指针构成一个单向链表，将所有关键字为同义词的结点链接在同一个单链表中，
- 建立公共溢出区
建立公共溢出区的基本思想是：假设哈希函数的值域是 [1,m-1]，则设向量 HashTable [0…m-1] 为基本表， 每个分量存放一个记录，另外设向量 OverTable [0…v] 为溢出表，所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。
文章来源: cuiqingcai.com，作者：Payne，版权归原作者所有，如需转载，请联系作者。
原文链接：cuiqingcai.com/9544.html