一文搞懂Hash算法以及应用场景

一、什么是哈希算法

哈希和散列都来源于单词hash，前者是音译，后者是意译。是一种可以将任意长度的二进制值映射为固定长度二进制值的算法，映射后固定长度的二进制值被称为哈希值。一个优秀的哈希算法需要满足以下几点要求：

不能从哈希值反向推导出原始数据；

对输入数据非常敏感，一个bit不同就会导致哈希值非常不一样；

散列冲突的概率要很小；

哈希算法的计算过程要足够简单高效，即使原始数据很长，也能很快得到哈希值；

二、哈希算法的使用场景

2.1 安全加密

比较常见的哈希加密算法有MD5(MD5 Message-Digest Algorithm, MD5消息摘要算法)和SHA(Secure Hash Algorithm, 安全散列算法)。

不能从哈希值密文反推出明文密码，且散列冲突概率比较小，这两点确保了哈希算法作为安全加密手段的可靠性。

为什么哈希算法不能完全避免散列冲突，只能尽量减少？

鸽巢原理告诉我们，11个鸽子飞进10个鸽子笼，那么必定有一个鸽子笼里面有2只及以上的鸽子。那么散列值是固定长度的，也就决定了散列值可以被穷举，但是理论上原始数据是无穷无尽的，因此必定有可能会导致散列冲突。

这种应用场景用到了哈希算法的特点1和3，其中3保证了密码被正向破解的难度很大（以MD5为例，散列值长度为128位，有2^128个不同的哈希值，很难被破解）。

安全领域没有绝对的安全，虽然MD5很难被破解，但是还是有办法被破解的，比如使用彩虹表匹配可以很轻松地破解常见密码。

所以一般我们会使用加盐的哈希算法来进行安全加密，加盐的方法需要严格保密，如此让破解的难度和成本都大大增加。

2.2 唯一标志

我们在校验两个文件是否一样的时候，是不能简单地通过文件名来进行判断的。因为同名文件的存在太常见了。

我们可以从大文件中按照特定的规则取一些二进制数据，利用哈希算法得出哈希值作为该文件的唯一标志。如此相同的文件必定具有相同的哈希值，也就是相同的唯一标志；不同的文件在很大概率上是具有不同的哈希值唯一标志的；

即使真的遇到了散列冲突，我们可以再详细比对两个文件的全部二进制数据，进一步判断它们是否是同一个文件，这个事件发生的概率太小了。但是这种方案既保证了高效，又保证了可靠。

这种应用场景用到了哈希算法的特点2和3。

2.3 数据校验

在P2P下载协议中，我们会从不同的机器上下载同一部电影的不同部分，然后在自己的机器上将电影组装起来。如果这其中某个部分的电影下载过程中出了错误或者内容被篡改了，就可能导致下载出错或者中病毒。

因此，我们先对所有部分进行hash计算，并保存在种子文件中。等到所有部分下载完成，我们对所有部分进行哈希计算得到哈希值，再和种子文件中的进行比较，以此来校验文件是否完整。

这种应用场景用到了哈希算法的特点2和4。

2.4 散列函数

这种场景在前面讲过散列表的时候就已经介绍了。这种场景下，对特点1要求不是很高，特点2的要求是散列值要尽量均匀分布，特点3也在一定程度上可以接受冲突，使用开放寻址法和拉链法就可以解决，就是特点4要求高一点，需要追求性能。

2.5 负载均衡

负载均衡的算法有很多，比如轮询、随机、加权轮询等，但是目标是要实现一个会话粘滞的负载均衡算法，即同一个客户端在一个会话期间所有的请求都是路由到同一台服务器的。

我们可以将客户端的IP或者会话ID进行哈希计算，得到的哈希值与服务器个数进行取模运算，最终得到的值就是需要路由的服务器，这样就能实现会话粘滞的目的。

2.6 数据分片

当我们需要处理海量数据的时候，单台服务器无法加载和计算如此海量的数据，那么我们就需要将海量数据均匀地分给N台服务器进行并行计算，如何将数据均匀地分给N台服务器呢？

我们对数据进行哈希计算，用得到的哈希值对服务器个数N取模，相同结果的数据会被分到相同的服务器上，交给这台服务器处理。N台服务器并行处理海量数据，最终再将结果合并起来即可。

2.7 分布式存储

将海量数据存储到分布式缓存或者分布式数据库中，借用的思想和上面的数据分片是类似的。只不过，当原先设定好的服务器数量不够的时候该如何处理呢？

并不是简单地加几台机器就能解决的，这会破坏哈希值的取模运算，导致缓存穿透，引起雪崩效应。同理，当某个机器故障被移除时也会导致相同的问题。这个时候需要借助一致性哈希算法来解决这个问题。

一致性哈希算法简单地说就是构造一个hash环，环上有2^32个节点，将服务器IP和文件都hash计算映射到对应的节点上。所有文件顺时针遇到的第一个服务器就作为自己存放的服务器。如此，当增加或者删除某个服务器的时候，影响的文件个数就可控，不会造成全局雪崩。

hash环

但是，在一定概率上，服务器IP在映射到hash环上时，会出现hash环偏斜的问题，此时会导致服务器上文件分布极其不均匀，退化为一开始在增删服务器时容易造成雪崩效应的场景。

hash环的偏斜

我们可以人为地为这些服务器增加若干虚拟节点，使得所有服务器节点在hash环上分布均匀。

带虚拟节点的hash环

三、总结

Hash算法的使用场景远远不止上述这些，还有比如CRC校验。