哈希算法-上
本文为数据结构与算法之美-王争的学习笔记，如需查看完整内容，请参考链接。
哈希算法的定义
将任意长度的二进制值串映射为固定长度的二进制值串，所用的映射规则就是哈希算法，通过原始数据映射之后得到的二进制值串就是哈希值。
一个优秀的哈希算法需要满足以下几点要求：
- 从哈希值不能反向推导出原始数据（哈希算法也叫做单向哈希算法）；
- 对输入数据非常敏感，原始数据较小的修改也会导致哈希值的大不相同；
- 散列冲突的概率小，不同的原始数据，哈希值相同的概率非常小；
- 哈希算法的执行效率要高，针对较长的文本也需要能快速地计算出哈希值。
以MD5哈希算法为例。对“今天我来讲哈希算法”和“jiajia”两个文本计算MD5哈希值，将得到的字符串转换为16进制编码。可以看出，两者的哈希值的长度相同。
1 | MD5("今天我来讲哈希算法") = bb4767201ad42c74e650c1b6c03d78fa |
而对于两个非常相似的文本，如“我今天讲哈希算法！”和“我今天讲哈希算法”。两者虽然只有一个叹号的差别，但得到的哈希值完全不同。
1 | MD5("我今天讲哈希算法！") = 425f0d5a917188d2c3c3dc85b5e4f2cb |
同时，MD5算法的计算速度也非常快。
哈希算法的应用
安全加密
常用于加密的哈希算法有MD5（MD5 Message-Digest Algorithm，MD5消息摘要算法）和SHA（Secure Hash Algorithm，安全散列算法）。
在对哈希算法的四点要求中，对用于加密的哈希算法，有两点格外重要。第一点：很难根据哈希值反向推导出原始数据；第二点：散列冲突的概率很小。
对于加密来说，第一点很好理解。第二点需要进一步的解释。
实际上，哈希算法无法做到零冲突。因为，哈希算法产生的哈希值的长度是固定且有限的。哈希值的长度固定时，能表示的数据就是有限的，但是要进行哈希的数据的个数是无限的。因而，必然存在哈希值相同的情况。
但是，尽管哈希算法存在散列冲突的情况，但是因为哈希值的范围很大，因而冲突的概率很低。因而，当我们得到一个哈希值，希望通过穷举的方式找到与该哈希值相同的另一个数据时，也需要耗费极大的难以承担的时间。
实际上，无法找到一种绝对安全的加密算法。越复杂、越难破解的加密算法，需要的计算时间就越长。在实际工程中，需要对加密算法的时间和安全性进行权衡。
唯一标识
例：当我们要在大量的数据集中查找某一张图片时，就不能单纯地使用图片的元信息（例如名字）进行对比，因为可能存在名字不同但内容相同、名字相同但内容不同的图片。
一种比较笨的方法是使用图片的原始二进制值进行一一比对，但是效率很低。此时，就可以给每一张图片赋予一个唯一的标识。例如，可以从图片的二进制码的开头取100个字节，中间取100个字节，末尾取100个字节，然后将这300个字节拼接在一起，通过哈希算法计算得到一个哈希字符串，将该字符串作为图片的唯一标识。
为了进一步提高效率，可以提前计算图库中的所有图片的哈希值，将哈希值和图片文件的路径信息存放为散列表。当要查看某个图片是否存在时，先使用哈希算法计算该图片的哈希值，再从散列表中查找是否存在该唯一标识。
如果散列表中不存在则说明不存在，如果存在则通过路径信息找到对应的图片，并进行完全比对，一样则说明存在，否则不存在。
数据校验
我们经常使用的BT下载软件是基于P2P协议的。BT下载软件从多个机器上并行地下载一部电影，该电影文件可能会被分割成多个文件块，等所有的文件下载完成后，再组装成一个完整的电影文件。
但是，所下载的文件块可能存在损坏的情况。因而，需要对各个文件块的完整性等进行检查。
有一种BT校验思路便是利用哈希算法。使用哈希算法对各个文件分别取哈希值并且保存在种子文件中。当文件下载完成后，通过相同的哈希算法对下载好的文件计算哈希值，与种子文件中的哈希值进行逐一比对。如果不同则说明文件有问题，否则说明文件完好。