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

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

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

Hash算法的特点

一个优秀的hash算法基本满足以下几点:

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

Hash算法的应用

1.安全加密

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

2.唯一标识

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

3.数据校验

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

4.散列函数

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

5.负载均衡

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

6.数据分片

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

7.分布式存储

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