什么是哈希（哈希算法）

哈希算法是将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。

哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。一般用于快速查找和加密算法。

什么是哈希碰撞

Hash算法并不完美，有可能两个不同的原始值在经过哈希运算后得到同样的结果， 这样就是哈希碰撞。

哈希碰撞解决办法

• 开放定址法
• 链地址

链地址法

链地址法其实就是HashMap中用的策略。原理是在HashMap中同样哈希值的位置以一串链表存储起来数据，把多个原始值不同而哈希结果相同的数据以链表存储起来。hashmap既是该种处理办法。

开放定址法

当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。 用方程来表达的话是这样子，

H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… ， k ( k ≤ m – 1))

m 是哈希表的长度。 举一个实际的例子， 一个哈希函数是 H ( key ) = key mod 7 ， 哈希表长度为 7， 关键字序列（ 32 ， 13 ， 49 ， 55 ， 22 ， 38 ， 21 ） 如果以线性探测再散列来生成哈希表的话， 过程是这样的

m 是哈希表的长度。 举一个实际的例子， 一个哈希函数是 H ( key ) = key mod 7 ， 哈希表长度为 7， 关键字序列（ 32 ， 13 ， 49 ， 55 ， 22 ， 38 ， 21 ） 如果以线性探测再散列来生成哈希表的话， 过程是这样的

32 ％ 7 = 4 ； 13 ％ 7 = 6 ； 49 ％ 7 = 0 ； 55 ％ 7 = 6 发生冲突，下一个存储地址（ 6 ＋ 1 ）％ 7 ＝ 0 ，仍然发生冲突，再下一个存储地址：（ 6 ＋ 2 ）％ 7 ＝ 1 未发生冲突，可以存入。 22 ％ 7 ＝ 1 发生冲突，下一个存储地址是：（ 1 ＋ 1 ）％ 7 ＝ 2 未发生冲突； 38 ％ 7 ＝ 3 ； 21 ％ 7 ＝ 0 发生冲突，按照上面方法继续探测直至空间 5 ，不发生冲突

所得到的哈希表对应存储位置：

下标： 0 1 2 3 4 5 6 49 55 22 38 32 21 13

关于哈希输入链接说明