哈希算法（上）：在实际的开发中，我们该如何用哈希算法解决问题
哈希算法（上）：在实际的开发中，我们该如何用哈希算法解决问题
一、什么是哈希算法
前面学习到的 散列表 散列函数，这里又讲到 哈希算法，实际上，不管是 散列 还是 哈希，都是中文翻译的差别，英文其实就是 Hash。所以，也可以将 散列表 叫做 哈希表 Hash 表，把 哈希算法 叫做 Hash算法 或者 散列算法。
那到底什么是哈希算法呢？
将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是 哈希算法。
通过原始数据映射之后得到的二进制值串就是 哈希值。
要设计一个优秀的哈希算法需要满足的几点要求：
- 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）
- 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同
- 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小
- 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值
以 MD5 这种哈希算法来具体说明一下
MD5 的哈希值是 128 位的 Bit 长度，为了方便表示，这里把它们转成了 16 进制编码。
MD5(" 今天我来讲哈希算法 ") = bb4767201ad42c74e650c1b6c03d78fa
MD5("jiajia") = cd611a31ea969b908932d44d126d195b
可以看到，无论目标数据（我们要哈希的文本）有多长、多短，通过 MD5 哈希之后，得到的哈希值的长度都是相同的，而且得到的哈希值看起来像一堆随机数，完全没有规律。
再来看两个非常相似的文本，尽管只有一字之差，最后得到的哈希值也是完全不同的。
MD5(" 我今天讲哈希算法！") = 425f0d5a917188d2c3c3dc85b5e4f2cb
MD5(" 我今天讲哈希算法 ") = a1fb91ac128e6aa37fe42c663971ac3d
我们很难通过哈希值 a1fb91ac128e6aa37fe42c663971ac3d 反推出对应的文本 我今天讲哈希算法。
哈希算法的应用非常多，作者 @王争 选了最常见的七个，分别是 安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。
应用一：安全加密
提到哈希算法的应用，最先想到的应该就是安全加密。最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5消息摘要算法） 和 SHA（Secure Hash Algorithm，安全散列算法）。
除了上述两个，还有很多其他的加密算法，比如 DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）
上面提到的对哈希算法的四点要求，有两点格外重要：
- 很难根据哈希值反向推导出原始数据
- 散列冲突的概率要很小
实际上，不管是什么哈希算法，我们只能尽量减少碰撞冲突的概率，理论上是没办法做到完全不冲突的。为什么这么说呢？
这里就基于组合数学中一个非常基础的理论，鸽巢原理（也叫抽屉原理）。它是说，如果有 10 个鸽巢，有 11 只🕊，那肯定有 1 个鸽巢中🕊的数量多于 1 个，换句话说，肯定会存在，2 只🕊共处 1 个鸽巢内。
鸽巢原理其实就解释了 为什么哈希算法无法做到零冲突？
因为哈希算法产生的哈希值的长度是固定且有限的。哈希值是固定的 128 位二进制串，能表示的数据是有限的，最多能表示 2^128 个数据，而我们要哈希的数据是无穷的。基于鸽巢原理，如果我们队 2^128+1 个数据求哈希值，就必然会存在哈希值相同的情况。一般情况下，哈希值越长的哈希算法，散列冲突的概率越低。
即便哈希算法存在散列冲突的情况，但是因为哈希值的范围很大，冲突的概率极低，所以相对来说是很难破解的。像 MD5 ，有 2^128 个不同的哈希值，这个数据已经是一个天文数字了，所以散列冲突的概率要小于 1/2^128。
没有绝对安全的加密，越复杂、越难破解的加密算法，需要的计算时间也越长。在实际的开发过程中，也需要权衡破解难度和计算时间，来决定究竟使用哪种加密算法。
应用二：唯一标示
如果要在海量的图库中，搜索一张图是否存在，我们不能单纯地用图片的原信息（比如图片名称）来比对，因为有可能存在名称相同但图片内存不同，或者名称不同图片内容相同的情况。那我们该如何搜索呢？
可以给每个图片取一个唯一标识。比如，我们可以从图片的二进制码串开头取一百个字节，从中间取一百个字节，从最后取一百个字节，然后将这三百个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识，通过这个唯一标识判断图片是否在图库中。
如果还想继续提高效率，可以把每个图片的唯一标识，和相应的图片文件在图库中的路径信息，都存储在散列表中。当要查看某个图片是不是在图库中的时候，先通过哈希算法对这个图片取唯一标识，然后在散列表中查找是否存在这个唯一标识。（这个唯一标识就是散列表中数组的下标）
如果不存在，那就说明这个图片不在图库中；如果存在，再通过散列表中存储的文件路径，获取到这个已经存在的图片，跟现在要插入的图片做全量的比对，看是否完全一样。如果一样，就说明已经存在；如果不一样，说明两张图片尽管唯一标识相同，但是并不是相同的图片。（就是冲突了）
应用三：数据校验
BT 下载的原理是基于 P2P 协议（百度了一下这个协议，看的似懂非懂）的。从多个机器上并行下载一个 2GB 的电影，这个电影文件可能会被分隔成很多文件块（比如分成 100 块，每块大约 20MB）。等所有的文件块都下载完成之后，再组装成一个完整的电影文件就行了。
我们知道，网络传输是不安全的，下载的文件块有可能是被宿主机器恶意修改过的，又或者下载过程中出现了错误，所以下载的文件块可能不是完整的。如果我们没有能力检测这种恶意修改或者文件下载出错，就会导致最终合并后的电影无法观看，甚至导致电脑中毒。现在的问题是，如何来校验文件块的安全、正确、完整呢？
具体的 BT 协议很复杂，这里作者只说了一种思路：
通过哈希算法，对 100 个文件块分别取哈希值，并且保存在种子文件中。当文件块下载完成之后，可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。
应用四：散列函数
散列函数也是哈希算法的一种应用。
散列函数是设计一个散列表的关键。它直接决定了散列冲突的概率和散列表的性能。不过，相对哈希算法的其它应用，散列函数对应散列算法冲突的要求要低很多。即便出现个别散列冲突，只要不是过于严重，我们都可以通过开放寻址法或者链表法解决。
不仅如此，散列函数对于散列算法计算得到的值，是否能反向解密也不关心。散列函数中用到的散列算法，更加关注散列后的值是否能平均分布，也就是一组数据是否鞥呢均匀地散列在各个槽中。除此之外散列函数执行的快慢，也会影响散列表的性能，所以，散列函数用的散列算法一般都比较简单，比较追求效率。
