首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
所谓脱库指网站遭到入侵后，黑客盗取其数据库。知道有脱库这种行为后，你会如何存储用户密码这么重要的数据呢？仅仅MD5加密一下存储就行了么？解答这个问题要先弄懂哈希算法。
哈希算法包含MD5、SHA等著名算法。我们平时也是直接拿现成的用。本节课不会重点剖析哈希算法的原理，也不会教你如何设计一个哈希算法，而是从实战的角度告诉你，在实际的开发中，我们该如何用哈希算法解决问题。
什么是哈希算法？
前几节我们提到过“散列表”、“散列函数”，这里又提到“哈希算法”。实际上，不管是”哈希”还是“散列”，都是中文翻译的区别，英文其实都是“Hash”。所以，我们常听到有人把“散列表”叫作“哈希表”“Hash 表”，把“哈希算法”叫作“Hash 算法”或者“散列算法”。那到底什么是哈希算法呢？
将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。优秀的哈希算法需要满足如下几个特性：
- 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；
- 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；
- 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
- 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。
以MD5算法为例，说明下这几个特性。
对“今天我来讲哈希算法”和“jiajia”这两个文本，计算MD5值，得到两串毫无规律的字符串。如下所示，MD5的哈希值是128位的Bit长度，为了表示方便，将它们均转换为了16进制编码。可以看出来，无论文本多长、多短，通过MD5哈希之后，得到的哈希值的长度都是相同的，而且得到的哈希值看起来像一堆随机数，完全没有规律。
1 | MD5("今天我来讲哈希算法") = bb4767201ad42c74e650c1b6c03d78fa |
我们再来看两个非常相似的文本，“我今天讲哈希算法！”和“我今天讲哈希算法”。这两个文本只有一个感叹号的区别。如果用 MD5 哈希算法分别计算它们的哈希值，你会发现，尽管只有一字之差，得到的哈希值也是完全不同的。
1 | MD5("我今天讲哈希算法！") = 425f0d5a917188d2c3c3dc85b5e4f2cb |
而且通过哈希算法得到的哈希值，很难反向推导出原始数据。比如上面的例子中，我们就很难通过哈希值“a1fb91ac128e6aa37fe42c663971ac3d”反推出对应的文本“我今天讲哈希算法”。
哈希算法的应用特别多。常见的有七个：分别是安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。这节我们先来看前四个应用。
应用一：安全加密
哈希算法应用最先想到的是安全加密。最常用于加密的哈希算法是MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和 SHA（Secure Hash Algorithm，安全散列算法）。
对于前面讲到的哈希算法四点要求，有两点特别重要。
- 很难根据哈希值反向推导出原始数据；
- 散列冲突的概率要很小。
第一点很好理解，加密的目的就是防止原始数据泄露，所以很难通过哈希值反向推导原始数据，这是一个最基本的要求。对于第二点，其实不管是什么哈希算法，我们只能尽可能减少碰撞冲突的概率，理论上是没办法做到完全不冲突的。
组合数学中有一个非常基础的理论，鸽巢原理（也叫抽屉原理）。这个原理本身很简单：如果有 10 个鸽巢，有 11 只鸽子，那肯定有 1 个鸽巢中的鸽子数量多于 1 个，换句话说就是，肯定有 2 只鸽子在 1 个鸽巢内。
有了鸽巢原理的铺垫之后，我们再来看，为什么哈希算法无法做到零冲突？哈希算法产生的哈希值的长度是固定且有限的。比如前面举的 MD5 的例子，哈希值是固定的 128 位二进制串，能表示的数据是有限的，最多能表示 2^128 个数据，而我们要哈希的数据是无穷的。基于鸽巢原理，如果我们对 2^128+1 个数据求哈希值，就必然会存在哈希值相同的情况。这里你应该能想到，一般情况下，哈希值越长的哈希算法，散列冲突的概率越低。
例如下面两段字符串经过MD5哈希算法加密之后，产生的哈希值是相同的。
不过，即便哈希算法存在散列冲突的情况，但是因为哈希值的范围很大，冲突的概率极低，所以相对来说还是很难破解的。像 MD5，有 2^128 个不同的哈希值，这个数据已经是一个天文数字了，所以散列冲突的概率要小于 1/2^128。如果我们拿到一个MD5值，采用毫无规律的穷举方法，找到跟这个MD5值相同的另外一个数据，那消耗的时间将是天文数字。所以即便哈希算法存在冲突，但是在有限的时间和资源下，哈希算法还是很难破解的。
没有绝对安全的加密。越复杂、越难破解的加密算法，需要的计算时间也越长。比如 SHA-256 比 SHA-1 要更复杂、更安全，相应的计算时间就会比较长。密码学界也一直致力于找到一种快速并且很难被破解的哈希算法。我们在实际的开发过程中，也需要权衡破解难度和计算时间，来决定究竟使用哪种加密算法。
应用二：唯一标识
首先举一个例子：如果要在海量的图库中，搜索一张图是否存在，我们不能单纯地用图片的元信息（比如图片名称）来比对，因为有可能存在名称相同但图片内容不同，或者名称不同图片内容相同的情况。那我们该如何搜索呢？
我们知道，任何文件在计算中都可以表示成二进制码串，所以可以拿要查找的图片的二进制码串与图库中所有图片的二进制码串一一比对。如果相同，则说明图片在图库中存在。但是每个图片小则几十 KB、大则几 MB，转化成二进制是一个非常长的串，比对起来非常耗时。
为了加快比对速度，我们可以给每一个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。
如果还想继续提高效率，我们可以把每个图片的唯一标识，和相应的图片文件在图库中的路径信息，都存储在散列表中。当要查看某个图片是不是在图库中的时候，我们先通过哈希算法对这个图片取唯一标识，然后在散列表中查找是否存在这个唯一标识。如果不存在，那就说明这个图片不在图库中；如果存在，我们再通过散列表中存储的文件路径，获取到这个已经存在的图片，跟现在要插入的图片做全量的比对，看是否完全一样。如果一样，就说明已经存在；如果不一样，说明两张图片尽管唯一标识相同，但是并不是相同的图片。
应用三：数据校验
我们使用下载软件下载文件时，这些文件可能会被分割成很多文件块。等所有的文件块都下载完之后，再组装成一个完整的文件。那怎么校验文件块的安全、正确、完整呢？校验方法也有很多，其中有一种思路是借助哈希算法实现的。
我们通过哈希算法，对 100 个文件块分别取哈希值，并且保存在种子文件中。我们在前面讲过，哈希算法有一个特点，对数据很敏感。只要文件块的内容有一丁点儿的改变，最后计算出的哈希值就会完全不同。所以，当文件块下载完成之后，我们可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。
应用四：散列函数
散列函数也是哈希算法的一种应用。前面提到过，散列函数是设计一个散列表的关键。它直接决定了散列冲突的概率和散列表的性能。不过，相对哈希算法的其他应用，散列函数对于散列算法冲突的要求要低很多。即便出现个别散列冲突，只要不是过于严重，我们都可以通过开放寻址法或者链表法解决。
不仅如此，散列函数对于散列算法计算得到的值，是否能反向解密也并不关心。散列函数中用到的散列算法，更加关注散列后的值是否能平均分布，也就是，一组数据是否能均匀地散列在各个槽中。
除此之外，散列函数执行的快慢，也会影响散列表的性能，所以，散列函数用的散列算法一般都比较简单，比较追求效率。
解答开篇
对于开篇的问题，我们可以通过哈希算法，对用户密码进行加密之后再存储，不过最好选择相对安全的加密算法，比如 SHA 等（因为 MD5 已经号称被破解了）。
但是这样加密之后存储还是不行，因为很多人习惯使用00000、123456这样简单的密码。如果用户信息被脱库，黑客虽然拿到的是加密之后的密文，但可以通过猜的方式来破解密码。这也就是常说的字典攻击。
这时，我们要维护一个常用密码的字典表，那字典中的每个密码用哈希算法计算哈希值，然后拿哈希值跟脱库后的密文比对。如果相同，基本上就可以认为，这个加密之后的密码对应的明文就是字典中的这个密码。注意，这里说是的是“基本上可以认为”，因为根据我们前面的学习，哈希算法存在散列冲突，也有可能出现，尽管密文一样，但是明文并不一样的情况。
针对字典攻击，我们可以引入一个盐（salt），跟用户的密码组合在一起，增加密码的复杂度。我们拿组合之后的字符串来做哈希算法加密，将它存储到数据库中，进一步增加破解的难度。
内容小结
本节主要讲了哈希算法的四个应用场景。
- 唯一标识。哈希算法可以对大数据做信息摘要，通过一个较短的二进制编码来表示很大的数据。
- 校验数据的完整性和正确性。
- 安全加密。任何哈希算法都会出现散列冲突，但是这个冲突概率非常小。越是复杂哈希算法越难破解，但同样计算时间也就越长。所以，选择哈希算法的时候，要权衡安全性和计算时间来决定用哪种哈希算法。
- 散列函数。它对哈希算法的要求非常特别，更加看重的是散列的平均性和哈希算法的执行效率。
课后思考
区块链的底层实现原理并不复杂。其中哈希算法就是它的一个非常重要的理论基础。那么区块链使用的是哪种哈希算法？是为了解决什么问题而使用的呢？
答：区块链是一块块区块组成的，每个区块分为两部分：区块头和区块体。区块头保存着 自己区块体 的哈希值和 上一个区块头 的哈希值。因为这种链式关系和哈希值的唯一性，只要区块链上任意一个区块被修改过，后面所有区块保存的哈希值就不对了。区块链使用的是 SHA256 哈希算法，计算哈希值非常耗时，如果要篡改一个区块，就必须重新计算该区块后面所有的区块的哈希值，短时间内几乎不可能做到。
