1 什么是哈希算法？

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

2 哈希算法的绩效

• 从哈希值不能反推出原数据
  所以哈希算法也称单向哈希算法
• 对输入数据敏感
  即使原数据只修改一bit，最后的哈希值也大不相同
• 散列冲突的概率要很小
  即对不同原数据，哈希值相同的概率要非常小
• 执行效率要尽量高效
  针对较长的文本，也要能快速算得哈希值

这些定义和要求都比较理论，可能还是不好理解，我拿MD5这种哈希算法来具体说明一下。

比如：

• 公众号
• JavaEdge

这两个字符串，计算MD5哈希值，得到两串看起来毫无规律的字符串（MD5的哈希值是128位的Bit长度，为了方便表示，我把它们转化成了16进制编码）。
无论要哈希的文本有多长、多短，通过MD5哈希之后，得到的哈希值的长度都是相同的，而且得到的哈希值看起来像一堆随机数，完全没有规律。

MD5(“公众号”) = 215feec56c2ae2ebc5c15e0bf7baf63b
MD5(“JavaEdge”) = a2a78ee5e4c9c0547a6e9acca6b54393

“公众号！”和“公众号”。这两个字符串仅一叹之差。但MD5后 hash 值大不相同：
MD5(“公众号！”) = c9a7de168253f3d653b6db1b35bab5a8
MD5(“公众号”) = 215feec56c2ae2ebc5c15e0bf7baf63b

你看看，通过算后的hash值，你狠难反推原数据吧？

3 适用场景

3.1 安全加密

常用加密的哈希算法：

• MD5（MD5 Message-Digest Algorithm，MD5消息摘要算法）
• SHA（Secure Hash Algorithm，安全散列算法）
• DES（Data Encryption Standard，数据加密标准）
• AES（Advanced Encryption Standard，高级加密标准）

散列冲突的概率要很小。
不管是什么哈希算法，只能尽量减少碰撞冲突的概率，理论上是没办法做到完全不冲突的。为什么这么说呢？
如果有10个鸽巢，有11只鸽子，那肯定有1个鸽巢中的鸽子数量多于1个，换句话说就是，肯定有2只鸽子在1个鸽巢内。

哈希算法产生的哈希值的长度是固定且有限的。比如前面举的MD5的例子，哈希值是固定的128位二进制串，能表示的数据是有限的，最多能表示2^128 个数据，而我们要哈希的数据是无穷的。基于鸽巢原理，如果我们对2^128+1个数据求哈希值，就必然会存在哈希值相同的情况。
哈希值越长的哈希算法，散列冲突的概率越低。

即便哈希算法存在散列冲突的情况，但是因为哈希值的范围很大，冲突的概率极低，所以相对来说还是很难破解的。像MD5，有2^128个不同的哈希值，这个数据已经是一个天文数字了，所以散列冲突的概率要小于1/ 2^128。

如果我们拿到一个MD5哈希值，希望通过毫无规律的穷举的方法，找到跟这个MD5值相同的另一个数据，那耗费的时间应该是个天文数字。所以，即便哈希算法存在冲突，但是在有限的时间和资源下，哈希算法还是被很难破解的。

没有绝对安全的加密。越复杂、越难破解的加密算法，需要的计算时间也越长。比如SHA-256比SHA-1要更复杂、更安全，相应的计算时间就会比较长。密码学界也一直致力于找到一种快速并且很难被破解的哈希算法。
需要权衡破解难度和计算时间，来决定究竟使用哪种加密算法。

可通过哈希算法，对用户密码进行加密之后再存储，不过最好选择相对安全的加密算法，比如SHA等（因MD5已号称被破解）。不过仅仅这样加密之后存储就万事大吉了吗？

字典攻击

如果用户信息被“脱库”，黑客虽然拿到是加密之后的密文，但可通过“猜”破解密码，因为有些用户密码太简单。比如00000、123456这样的简单数字组合，所以现在也都要求你大小写字母数字都有。

就需维护一个常用密码的字典表，把字典中的每个密码用哈希算法计算哈希值，然后拿哈希值跟脱库后的密文比对。如果相同，基本上就可以认为，这个加密之后的密码对应的明文就是字典中的这个密码。（哈希算法存在散列冲突，也可能密文一样，但明文不一样）

可引入一个盐（salt），跟用户的密码组合在一起，增加密码的复杂度。拿组合后的字符串做哈希算法加密，存储到数据库，进一步增加破解的难度。

3.2 唯一标识

对大数据做信息摘要，通过一个较短二进制编码以表示很大的数据。

在海量图库搜索一张图，不能简单用图片元信息（比如图片名）做比对，有可能：

• 名称相同，但内容不同
• 名称不同，内容相同

那到底该如何搜索？

任何文件在计算中都是二进制码序列，所以，比较粗暴的就是将待搜索图片的二进制码序列与图库中所有图片二进制码序列一一比对。

但问题是，图片大小从几K~几M，转化成二进制就是一个超长的序列，比对极为耗时！怎么能更快？

可以给每个图片取个唯一标识或信息摘要。

比如，可以从图片的二进制码序列：

• 开头取100个字节
• 中间取100个字节
• 最后再取100个字节

将这300个字节放到一块，通过哈希算法（如MD5），得到一个哈希字符串，将其作为图片唯一标识。

还能更快吗？

把每个图片的唯一标识和相应图片文件在图库中的路径信息，都存储在hash表。

搜索某图片时：

• 通过哈希算法对该图片取唯一标识
• 在hash表查找是否存在该标识：
  • 不存在
    该图片不在图库
  • 存在
    再通过hash表中存储的文件路径，获取该已存在图片，跟现在要插入的图片做全量比对，看是否完全一样：
    • 一样
      说明已经存在
    • 不一样
      说明两张图片尽管唯一标识相同，但并非相同图片

3.3 数据校验

P2P下载，从多个机器并行下载一个2G电影，该电影文件可能被分割成很多文件块。等所有的文件块都下载完成之后，再组装成一个完整的电影文件就行了。

网络传输是不安全的，下载的文件块有可能是被宿主机器恶意修改过的，又或者下载过程中出现了错误，所以下载的文件块可能不是完整的。如果没有能力检测这种恶意修改或者文件下载出错，就会导致最终合并后的电影无法观看，甚至导致电脑中毒。

如何校验文件块的安全、正确、完整？

使用哈希算法对100个文件块分别取哈希值，并保存在种子文件。

只要文件块内容有丁点改变，最后哈希值就完全不同。

所以，当文件块下载完成后：

• 使用相同哈希算法对下载好的文件块逐一求哈希
• 对比种子文件中的哈希值：
  • 若不同
    说明该文件块不完整或被篡改，重新从其它宿主机器下载该文件块

3.4 Hash函数

该场景：

• 对hash算法冲突的要求较低，偶尔hash冲突问题不大
• 也不关心hash函数对于hash算法计算得到的值，是否能反向解密

hash函数中用到的hash算法，更加关注hash后的值是否能均匀分布。
hash函数执行的快慢，也影响hash表的性能，所以，hash函数用的hash算法一般较简单，追求效率。

哈希算法还能解决很多分布式问题。

3.5 负载均衡

实现一个会话粘滞（session sticky）负载均衡算法，需在同一客户端上，在一次会话中的所有请求都路由同一服务器。

最直接的维护一张映射关系表：
客户端IP地址或会话ID =》服务器编号的映射关系

客户端发出的每次请求，先映射表查找路由的服务器编号，再请求对应服务器。
简单直观，但：

• 客户端很多
  映射表可能会很大，比较浪费内存空间
• 客户端下线、上线，服务器扩容、缩容都会导致映射失效
  维护映射表的成本很大

借助哈希算法即可解决：对客户端IP地址或会话ID计算哈希值，与服务器列表的大小取模，最终得到的值即被路由到的服务器编号。
这就可以把同一IP过来的所有请求，都路由到同一后端服务器。

3.6 数据分片

统计关键词

假如1T日志文件，这里面记录了用户的搜索关键词，快速统计出每个关键词被搜索的次数。
这个问题有两个难点：

• 搜索日志很大，没法放到一台机器的内存
• 如果只用一台机器来处理这么巨大的数据，处理时间会很长。

可以先对数据进行分片，然后采用多台机器处理提高处理速度：
用n台机器并行处理：

• 从搜索记录的日志文件依次读出每个搜索关键词
• 通过哈希函数计算哈希值
• 再跟n取模
• 得到应该被分配到的机器编号

哈希值相同的搜索关键词就被分配到了同一个机器上。即同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。

MapReduce的基本思想。

快速判断图片是否在图库

前面提到可以给每个图片取唯一标识（或者信息摘要），然后构建hash表。

现在图库现有1亿张图片，单机构建hash表就做不到了。因为单台机器的内存有限，而1亿张图片构建散列表显然远远超过了单台机器的内存上限。

我们同样可以对数据进行分片，然后采用多机处理。我们准备n台机器，让每台机器只维护某一部分图片对应的散列表。我们每次从图库中读取一个图片，计算唯一标识，然后与机器个数n求余取模，得到的值就对应要分配的机器编号，然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。

当我们要判断一个图片是否在图库中的时候，我们通过同样的哈希算法，计算这个图片的唯一标识，然后与机器个数n求余取模。假设得到的值是k，那就去编号k的机器构建的散列表中查找。

现在，我们来估算一下，给这1亿张图片构建散列表大约需要多少台机器。

散列表中每个数据单元包含两个信息，哈希值和图片文件的路径。假设我们通过MD5来计算哈希值，那长度就是128比特，也就是16字节。文件路径长度的上限是256字节，我们可以假设平均长度是128字节。如果我们用链表法来解决冲突，那还需要存储指针，指针只占用8字节。所以，散列表中每个数据单元就占用152字节（这里只是估算，并不准确）。

假设一台机器的内存大小为2GB，散列表的装载因子为0.75，那一台机器可以给大约1000万（2GB*0.75/152）张图片构建散列表。所以，如果要对1亿张图片构建索引，需要大约十几台机器。在工程中，这种估算还是很重要的，能让我们事先对需要投入的资源、资金有个大概的了解，能更好地评估解决方案的可行性。

海量数据处理都可采用多机分布式处理方案。分片设计以突破单机内存、CPU等资源的限制。

3.7 分布式存储

为提高数据读、写能力，一般采用分布式存储，比如分布式缓存。因为大量数据要缓存，所以单机缓存肯定不够，就需要将数据分布在多机。

哪个数据又该存在哪个机器呢？

参考数据分片设计，通过哈希算法处理数据，然后对机器个数取模，就得到该缓存数据应存储的机器编号。

但若数据增多，原先10个机器已无法支撑，就得扩容，比如扩到11个节点。
但问题也来了，原先数据通过与10取模，现在节点多了一个，所有数据需重新计算哈希值，然后迁移到现在的对应节点。
这时，原缓存中的数据突然大量失效，这些缓存数据的请求就会穿透缓存，直接请求DB。

所以，此时我们就需要一个方案，能在加新节点后，无需做大量数据迁移。
救星就是一致性 hash 算法！

先假设：

• 有k个节点
• 数据哈希值范围[0, MAX]
• 将整个范围划分成m个小区间（m>>k）
• 每个节点负责m/k个小区间

加入新节点时，就将某几个小区间的数据，从原节点迁移至新节点。
这就避免了全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。

这就是一致性哈希算法的基本思想。

案例

钟表有 60 分钟，从 0 开始到 59，共 60 个点。
现在将机器往这 60 个点分配，规则如下：

hash(ip) % 60

  

 

  
1
 

假设 3 台机器 A，B 和 C，分别被分配到了 14，37 和 46 三个点。

图片的分配规则类似：

hash(image_id) % 60

  

 

  
1
 

现有 3 张图片 x， y， z，分别被分配到 5，30，50 这三个点。

图片都没被分配到机器的节点，这咋办？
在钟表上顺时钟往前寻找，第一台遇到的机器，就是它的归属。

不凑巧，A B C 三台机器分别分配到 5，10，15 这三个点。这样对 A 很不公平啊！要负责存储绝大多数的图片，那这怎么办呢?

为避免不必要争端，于是引入“虚拟节点”，每台机器都可拔一根汗毛，变成若干台，把虚拟节点分散到 60 个点，归属“虚拟节点”的图片，均保存到它的真身。这就能解决分配不均匀问题。

应用时，将 60 替换下即可，如替换为 2^32。

参考

• https://en.wikipedia.org/wiki/Consistent_hashing
• https://www.zsythink.net/archives/1182

文章来源: javaedge.blog.csdn.net，作者：JavaEdge.，版权归原作者所有，如需转载，请联系作者。

原文链接：javaedge.blog.csdn.net/article/details/120070265