哈希算法历史悠久，业界著名的哈希算法也有很多，比如MD5、SHA等。在我们实际开发中，基本上都是拿现成的直接用。所以，接下来将会从实战的角度来看看，在实际开发中，我们该如何用哈希算法解决问题。
什么是哈希算法？
在开始之前，我们得先来了解了解，什么是哈希算法。前面这篇文章：18-散列表 中有讲到“散列表”、“散列函数”，这里又讲到了“哈希算法”。其实这只是英文翻译的问题，不管是“散列”还是“哈希”，它的英文都是“Hash”。所以，“哈希算法”也可以叫做“散列算法”(注意和散列函数的区别，马上也会讲到)。
哈希算法的定义是这样的：将任意长度的二进制串映射为固定长度的二进制串，这个规则就是哈希算法。而通过原始数据映射之后得到的二进制值串就是哈希值。
但是想要设计一个优秀的哈希算法并不容易，下面是设计时需要满足的要求：
- 从哈希值不能反向推导出原始数据。
- 对输入数据非常敏感，哪怕原始数据只修改了一个Bit，最后得到的哈希值也大不相同。
- 散列冲突的概率要小，对不同的原始数据，哈希值相同的概率非常小。
- 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速的计算出哈希值。
下面就是MD5这种哈希算法得出的结果：
1 | MD5(" 我今天讲哈希算法！") = 425f0d5a917188d2c3c3dc85b5e4f2cb |
哈希算法的应用非常非常多，接下来我们就讲讲常见的七个，分别是安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。
1. 安全加密
我们比较熟知、最常用的加密哈希算法是MD5(MD5 Message-Digest Algorithm, MD5消息摘要算法)和SHA(Secure Hash Algorithm，安全散列算法)。
上面讲到的哈希算法四点要求中，有两点对于加密哈希算法来说特别重要。第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要很小。
第一点很好理解，加密的目的就是防止原始数据泄露，所以很难通过哈希值反向推到原始数据是最基本的要求。现在我们来着重讲一下第二点。实际上，不管是什么哈希算法，我们只能尽量降低冲突发生的概率，理论上是没有办法做到完全不发生冲突的。
根据 鸽巢原理，如果有10个鸽子窝，现在有11只鸽子，那肯定有一个鸽子窝里面鸽子数量大于1。我们知道，哈希算法产生的哈希值的长度是固定且有限的，比如MD5是128位二进制串。所以，当我们的数据超过某一个阈值时，就必然存在哈希值相同的情况。
除此之外，没有绝对安全的加密(算法)。越复杂、越难破解的加密算法，需要的计算时间也越长。我们在实际的开发过程中，也需要权衡破解难度和计算时间，来决定究竟使用哪种加密算法。
2. 唯一标识
现在我们有一个需求，要求在海量的图库中，搜索一张图片是否存在，那我们应该怎么做呢？
我们知道，任何文件在计算机中都可以用二进制码串表示。比较直(笨)的方式就是一个一个去比对了。但是，现在的图片怎么的都有几兆甚至十几兆，转化成的二进制串很长，这还要去比对的话，在这里肯定行不通。那有没有什么更快的方法呢？
这会，我们就可以给每一张图片取一个唯一标识了。比如，我们可以从图片的二进制码串中取出一部分来，通过哈希算法得到一个哈希字符串，用它作为图片的唯一标识。通过这个标识来判定图是否在图库中。这样就可以减少很多工作量了。
3. 数据校验
电驴这样的BT下载软件你肯定用过吧？BT下载的原理是基于P2P协议的。我们从多个机器上并行下载一部电影，然后电影会被分割成很多块，等所有的文件块都下载完了，再组装成一部完整的电影文件。
但是，我们都知道，网络传输是不安全的，下载的文件块有可能是被宿主机器恶意修改过的，又或者下载过程中出现了错误。这就会导致最后合并后的电影无法观看，甚至导致电脑中毒。
具体的BT协议很复杂，校验方法也有很多，我们来说其中的一种思路。
我们通过哈希算法，对100个文件块分别取哈希值，并且保存在种子文件中。我们前面也有讲过哈希算法的一个特点，对数据很敏感。所以，当文件下载完成之后，我们可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后和种子文件中保存的哈希值对比。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其它的宿主机器上下载这个文件块。
4. 散列函数
前面讲了很多哈希算法的应用，实际上，散列函数也是哈希算法的一种应用。
前一节讲到了，散列函数是设计一个散列表的关键。它直接决定了散列冲突的概率和散列表的性能。不过相对哈希算法的其他应用，散列函数对于散列算法冲突的要求要低很多。即便出现个别散列冲突，只要不是过于严重，我们都可以通过开放寻址法或者链表法解决。
不仅如此，散列函数对于散列算法计算得到的值，是否能反向解密也并不关心。散列函数中用到的散列算法，更加关注散列后的值是否平均分布，也就是，一组数据能否被平均的分到各个槽中。除此之外，散列函数的执行快慢也会影响散列表的性能。所以，散列函数用的散列算法一般都比较简单，比较追求效率。
5. 负载均衡
负载均衡算法有很多，比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞的负载均衡呢？也就是说，我们需要在同一个客户端，将一次会话中的所有请求都路由到同一个服务器上。
最直接的方法就是，维护一张映射关系表，客户端IP或者会话ID与服务器编号的映射关系。客户端每次发出的请求，都要先在映射表中查找应该路由的服务器编号，然后再请求编号对应的服务器。
这种方法简单直观，但也有几个弊端：
- 如果客户端很多，映射表可能会很大，比较浪费内存空间
- 客户端下线、上线，服务器扩容、缩容都会导致映射失效，这样维护映射表的成本就会很大。
如果借助哈希算法，这些问题可以非常完美的解决。我们可以通过哈希算法，对客户端IP地址或者会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。
6. 数据分片
哈希算法还可以用于数据的分片。下面有两个例子：
- 如何统计“搜索关键词”出现的次数
假如我们有1T的日志文件，这里面记录了用户搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？
我们来分析一下。这个问题有两个难点，第一个搜索日志很大，没办法放到一台机器的内存。第二个难点，如果只用一台机器来处理这么巨大的数据，处理的时间会很长。
针对这两个难点，我们可以先对数据进行分片，然后采用多台机器分片，以此来提高速度。
具体思路是这样的：为了提高处理的速度，我们用n台机器并行处理。从搜索记录的日志文件中，依次读出每个搜索关键字，并且通过哈希函数计算哈希值，然后再跟n取模，最终得到的值，就是应该被分配的机器编号。
这样，哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分布计算关键词出现的次数，最后合并起来就是最终的结果。
- 如何快速判断图片是否在图库中？
还是刚刚判断图片是否存在于图库中得例子。假设，现在我们得图库中有1亿张图片，很显然，在单台机器上构建散列表是行不通的。
我们同样可以对数据进行分片，采用多机处理。
实际上，针对这种海量数据得处理问题，我们都可以采用多机分布式处理。借助这种分片的思路，可以突破单机内存、CPU等资源的限制。
7. 分布式存储
现在互联网面对的都是海量的数据、海量的用户。我们为了提高数据的读写能力，一般都采用分布式的方式来存储数据，比如分布式缓存。
那么，我们该如何决定将哪个数据放到哪台机器上呢？这里我们可以借助数据分片的思想，通过哈希算法对数据取哈希值，然后将值和机器个数取模，这个最终值就是应该存储的缓存机器编号。这样：
但是，仔细想想，这样做的局限性很大。如果数据量一多，原来的机器装不下了，那我们肯定得扩容。比如从原来的10变成13。那我们就需要对所有的数据重新计算哈希值，放入到对应机器中了。这样就相当于，缓存中的数据一下子就失效了。所有的数据请求都会穿透缓存，直接去请求数据库。这样就可能发生雪崩效应，压垮数据库。
所以，我们需要一种方法，使得在新加入一台机器后，并不需要做大量的数据搬移。这时候，一致性哈希算法就登场了。
假设，我们有k台机器，数据的哈希值范围是[0, MAX]。我们将整个范围划分成m个小区间(m远大于k)，每个机器负责m/k个小区间。当有新机器加入时，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样就不会全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。
除了上面讲到的分布式缓存，实际上，一致性哈希算法的应用非常广泛，在很多分布式存储系统中，都可以看到它的影子。
内容小结
这一节的内容主要篇实战，贴近具体开发。
唯一标识，哈希算法可以对大数据做信息摘要，通过一个较短的二进制编码来表示很大的数据。哈希算法还可以应用于校验数据的完整性和正确性。
第三个应用是安全加密，我们讲到，任何哈希算法都会出现散列冲突，但是这个冲突的概率非常小。越是复杂的哈希算法越难破解，但同样计算时间也将会变长。所以，选择哈希算法的时候，要权衡安全性和计算时间来决定用哪种哈希算法。第四个是散列函数，这个我们前面讲散列表的时候已经详细讲过，它对哈希算法的要求非常特别，更加看重的散列的平均性和哈希算法的执行效率。
在负载均衡应用中，利用哈希算法替代映射表，可以实现一个会话粘滞的负载均衡策略。在数据分片应用中，通过哈希算法对处理的海量数据进行分片，多机分布式处理，可以突破单机资源的限制。在分布式存储应用中，利用一致性哈希算法，可以解决缓存等分布式系统的扩容、缩容导致数据量大量搬移的难题。
讲真，对于我这个小白来讲，这一节真的只是用来扩展知识面啦。能理解多少是多少，慢慢来叭~
有问题？发送 issues 给我~