哈希

1.什么是哈希？

散列算法（Hash Algorithm），又称哈希算法，杂凑算法，是一种从任意文件中创造小的数字「指纹」的方法。生成的值成为哈希值。与指纹一样，散列算法就是一种以较短的信息来保证文件唯一性的标志，这种标志与文件的每一个字节都相关，而且难以找到逆向规律。因此，当原有文件发生改变时，其标志值也会发生改变，从而告诉文件使用者当前的文件已经不是你所需求的文件。

Hash 算法能将将任意长度的二进制明文映射为较短的二进制串的算法，并且不同的明文很难映射为相同的 Hash 值。

也可以理解为空间映射函数，是从一个非常大的取值空间映射到一个非常小的取值空间，由于不是一对一的映射，Hash 函数转换后不可逆，意思是不可能通过逆操作和 Hash 值还原出原始的值。

散列方法的主要思想是根据结点的关键码值来确定其存储地址：以关键码值K为自变量，通过一定的函数关系h(K)(称为散列函数)，计算出对应的函数值来，把这个值解释为结点的存储地址，将结点存入到此存储单元中。检索时，用同样的方法计算地址，然后到相应的单元里去取要找的结点。通过散列方法可以对结点进行快速检索。散列（hash，也称“哈希”）是一种重要的存储方式，也是一种常见的检索方法。

这里有几点：a.将不定长度转换为固定长度（长度一般128）。b.不可逆的

2.特点是什么？

Hash 值又称为指纹或者摘要，具有以下特点：

正向快速：给定明文和 Hash 算法，在有限时间和有限资源内能计算得到 Hash 值。

逆向困难：给定 Hash 值，在有限时间内很难逆推出明文。

输入敏感：原始输入信息发生任何变化，新的 Hash 值都应该出现很大变化。

冲突避免：很难找到两段内容不同的明文，使得它们的 Hash 值一致。

3.Hash 算法有哪些？

常见 Hash 算法有 MD5 和 SHA 系列，目前 MD5 和 SHA1 已经被破解，一般推荐至少使用 SHA2-256 算法。

4.Hash 算法碰撞

稍微想一下就可以发现，既然输入数据长度不固定，而输出的哈希值却是固定长度的，这意味着哈希值是一个有限集合，而输入数据则可以是无穷多个，那么建立一对一关系明显是不现实的。所以“碰撞”是必然会发生的，所以一个成熟的哈希算法会有较好的抗冲突性，同时在实现哈希表的结构时也要考虑到哈希冲突的问题。

比如“666”经过 Hash 后是“fae0b27c451c728867a567e8c1bb4e53”，相同 Hash 算法得到的值是一样的。比如 WiFi 密码如果是 8 位纯数字的话，顶多就是 99999999 种可能性，破解这个密码需要做的就是提前生成好 0 到 1 亿数字的 Hash 值，然后做 1 亿次布尔运算（就是 Bool 值判断，0 或者 1），而现在普通 I5 四核 CPU 每秒能到达 200 亿次浮点数计算，做 1 亿次布尔运算也就是秒级别的时间就破解了。

所以密码尽量不要用纯数字，因为根本没有任何安全性。

5.加盐防碰撞

对数字内容进行 Hash 运算，获取唯一的摘要值来指代原始完整的数字内容，利用 Hash 函数的抗碰撞性来确保内容未被篡改。

常用于用户名和密码来确保用户信息安全，为了防止攻击会采用加盐的方法，就是原来的明文加上一个随机数之后的 Hash 值，Hash 值和盐会保存在两个地方，只要不是同时泄漏就很难被破解。

6.哈希冲突解决策略：

1）开放寻址法（Open Addressing），将所有的元素都存放在哈希表内的数组中，不使用额外的数据结构。开放寻址法的最简单的一种实现就是线性探查（Linear Probing）。

2）链接技术（chaining），在链接法中，把哈希到同一个槽中的所有元素都放到一个链表中。

部分引用：

https://blog.csdn.net/guidao13/article/details/84104526

https://www.cnblogs.com/gaochundong/p/hashtable_and_perfect_hashing.html