数据结构与算法之美-Hash算法

将任意长度的二进制值串映射成固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。

## Hash算法的特点 一个优秀的hash算法基本满足以下几点：

• 从哈希值不能反向推导出原始数据，所以哈希算法是单向不可逆算法。
• 对输入数据非常敏感，哪怕原始数据只修改了一个Bit，最后得到的哈希值也大不相同。
• 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。
• 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

## Hash算法的应用 ### 1.安全加密 多用于用户密码的加密存储，防止用户数据被脱库后明文密码泄露。对用于安全加密的哈希算法，有两点格外重要，第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要小。常用的有MD5、SHA、AES、DES，在实际开发中要权衡破解难度和计算时间来选择合适的Hash算法。

### 2.唯一标识 通过哈希算法计算出数据的唯一标识，从而用于高效检索数据。

### 3.数据校验 利用哈希算法对输入数据敏感的特点，可以对数据取哈希值，从而高效校验数据是否被篡改过。

### 4.散列函数 散列函数中用到的哈希算法更加关注散列后的值能不能平均分布，以及散列函数的执行快慢。

### 5.负载均衡 可以通过哈希算法对客户端ip或者会话id计算hash值，将取得的hash值与服务器列表大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。这样，我们就可以实现一个会话粘滞的负载均衡算法。

### 6.数据分片 当要处理数据量非常大，而机器内存有限的情况下，可通过将数据先进行hash，然后模分片数量取余的方式进行分片处理。

### 7.分布式存储 利用一致性哈希算法，可以解决缓存等分布式系统的扩容、缩容导致数据大量搬移的难题。