哈希算法将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，通过原始数据映射之后得到的二进制值串就是哈希值。
哈希算法
要求
- 不可逆，从哈希值不能反向推导出原始数据
- 雪崩效应，对输入的原始数据非常敏感，只修改1bit得到的哈希值也大不同
- 避免碰撞，散列冲突的概率要尽量小
- 执行效率高，对于较长的文本也能很快地算出哈希值
应用
1. 安全加密
常用于加密的哈希算法是MD5和SHA。哈希值越长的哈希算法，散列冲突的概率就越低。
2. 唯一标识
在海量的图库中搜索一张图是否存在，若单纯地用图片的元信息来比对效率十分低下而且可能会有错误产生。这时可以给每一个图片取一个信息摘要，比如从图片的二进制码串开头、中间和尾部分别取100字节，再组合这300字节并通过哈希算法得到哈希值，用它作为图片的唯一标识，这样的搜索效率就很高。
3. 数据校验
主要应用于分块下载的大文件，用哈希算法对每块取哈希值可以验证文件块的完整性。
4. 散列函数
应用于散列表的散列函数设计。散列表用的散列算法一般都比较简单。
5. 负载均衡
通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。
6. 数据分片
假如有比较大的日志文件，记录了用户的搜索关键词，要想快速统计出每个关键词被搜索的次数，可以对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。用 n 台机器并行处理。我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟 n 取模，最终得到的值，就是应该被分配到的机器编号。这样，哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。
分布式存储
原理同5和6，但当机器要扩容或锁容时需要重新计算哈希值，所有数据都需要搬移，缓存全部失效，很容易产生雪崩效应，压垮数据库。因此需要一致性哈希算法来解决。
一致性哈希算法
一致性哈希同样是采用取模的方法，它对$2^{32}$取模。将$2^{32}$想象成一个圆，就像钟表一样，圆上的每一个点代表一个数字，从0，1，2一直到$2^{32}-1$，这个圆环称为hash环。
用服务器的IP地址进行哈希计算，使用哈希后的结果对$2^{32}$取模：
$$
hash(IP) \quad % \quad 2^{32}
$$
这个公式得到一个整数，用这个整数代表服务器A，并映射到哈希环上，同理，其他服务器也可以用同样的方法映射到哈希环上。
此时，将缓存对象同样映射到hash环上，比如对于图片对象，计算图片摘要信息的hash值后，对$2^{32}$取模即可。映射完毕之后，缓存对象沿顺时针方向遇到的第一个服务器就是它应该存放的缓存服务器。图例如下所示，图中的1-4代表待缓存对象，ABC表示缓存服务器，按照算法，1、2号对象会被缓存到服务器A上，3号对象会被缓存到B上，4会到C上。
一致性哈希的优点
服务器数量的扩容和缩容所需要进行的数据搬移量比较小。比如上图中的B出现了故障，只有对象3受到了影响，需要改变缓存服务器，而对象1、2、4都不需要作任何变动。
哈希环的偏斜
在实际映射过程中，可能会出现如下情况。
这时候缓存的对象很可能大部分都集中缓存在某一台服务器上。此时缓存的分布极度不均匀，在极端情况下，A崩溃也会导致雪崩效应，这种情况称为hash环的偏斜。
虚拟节点
哈希环偏斜的情况可以引入虚拟节点来解决。将实际的服务器节点在hash环上生出复制的虚拟节点，这样可以减小偏斜带来的影响。虚拟节点越多，hash环上的节点就越多，缓存被均匀分布的概率就越大。
参考文章
