1、什么是 Hash

Hash 又称散列，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。

压缩映射

举例：
MD5 和 SHA 都是历史悠久的 Hash 算法。

2、Hash 算法的用途

1）安全加密
2）唯一标识
3）数据校验
4）散列函数
5）负载均衡
6）数据分片
7）分布式存储

3、Hash 的特点

1）从 Hash 值不可以反向推导出原始值；
2）输入数据的微小变化，会得到完全不同的 Hash 值；
3）Hash 算法的执行效率要高效，对长文本也能快速计算出 Hash 值；
4） Hash 算法的冲突概率要小 。

以上 4 个特点，也是衡量一个 Hash 算法好坏的标准，需要根据应用场景进行取舍，选择合适 Hash 算法。

4、Hash 碰撞

因为 Hash 算法是压缩映射，即输入值空间远大于 Hash 值空间，根据数学抽屉原理，一定存在两个不同的输入，经过 Hash 等到相同的 Hash 值，这时就是发生了 Hash 碰撞。

5、如何防止 Hash 碰撞

最有效的方法就是扩大 Hash 值空间。

16 个二进制位 Hash 值，产生 Hash 碰撞的可能性是 65536 分之一。

32 个二进制位 Hash 值，产生 Hash 碰撞的机会是 4294967296 分之一。

我们熟悉的 MD5 生成的是 128 个二进制位的 Hash 值，其发生 Hash 碰撞的可能性就更低了。

更长的 Hash 值，意味着需要更大的存储空间，更高的运算成本，应根据实际使用场景进行取舍。

6、Hash 碰撞的解决方案

什么时候需要解决 Hash 碰撞呢？Java 中的 HashMap 数据结构，作为一个容器类，目的是存储数据，发生碰撞时，是需要解决的。

比较常用的算法有 链表法 和 开放寻址法 。

7、一致性 Hash 算法

在分布式存储应用中，会根据数据进行计算 Hash 值，然后和机器总数取余数，确定要存储的机器，如果刚开始是 3 台机器，当机器增加到 4 台时，这时就需要对所有数据进行重新 Hash，来确定新的存储位置，成本很高。

一致性 Hash 算法，将 Hash 值的范围划分为几个区，每台机器负责几个区，这样在新增机器时，仅需要对几个区进行重新计算 Hash 和数据搬移了。

8、参考文档

1、《网易云课堂》
2、《极客时间-数据结构与算法》