[Python学习日记-25] 哈希（HASH）是个什么东西？

简介

哈希的特性

哈希的用途

基于 HASH 的数据类型

简介

        哈希（Hash），也称为散列，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是哈希值（散列值）。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间。其实这种转换就是一个算法，世界上最简单的算法就是加减乘除，打个比方

算法本体为：

输入 + 7 = 输出

输入	算法转换	输出
1	1 + 7 =	8
2	2 + 7 =	9

        哈希算法不过是一个更为复杂的运算，它的输入可以是字符串，可以是数据，可以是任何文件，而经过哈希运算后，这些东西都会变成一个固定长度的输出，该输出就是哈希值。

        值得注意的是哈希算法有一个很大的特点，就是你不能从结果推算出输入，所以又称为不可逆的算法，这也是为什么哈希可以用于加密密码的原因。

        在 Python 中要把输入转换为哈希值可以使用 hash() 方法，如下代码所示

print(hash("Jove"))
print(hash("Python No.1!"))
print(hash("Python No.1!"))    # 在同一个命令行中同一个字符串进行 hash 结果会一模一样

 代码输出如下：

 

        如上所示，输入“Jove”四个英文字母后，经过哈希运算，会得到一个随机数列，而且不管你的输入文件多大，最后得到的结果都是一个固定长度的数列，即使你输入的是一部电影那么大的文件，输出也是这么大。而且通过数列不能推导出输入。 在我们下载 Python 时在 Python 的官网也能看到哈希值，如下图所示

 

哈希的特性

不可逆：在具备编码功能的同时，哈希算法也作为一种加密算法的存在。即无法通过分析哈希值计算出源文件的样子，举个生活当中的例子，你不可能通过观察看肠的纹理推测出猪原来的样子。

计算极快：20G 高清电影和一个 5K 文本文件对于哈希算法来说复杂度相同，并且计算量都极小，可以在0.1秒内得出结果。也就是说，不管猪有多，骨头多硬，做成香肠都只要眨眼的时间。

 

哈希的用途

        哈希算法的不可逆特性使其在密码、文件完整性校验、数字签名领域广泛使用

一、密码

         我们日常使用的各种电子密码，本质上都是基于哈希的，以支付宝为例，当你付款时无需担心支付宝的数据库管理人员（DBA）会把你的密码泄漏给第三方，因为你的登录密码是先经过哈希和其他各种复杂算法得出密文后，再存进支付宝的数据库里的，所以当你的手机像数据库确认密码是否正确时只是对比哈希值而已，当然真是的过程当然比现在说的复杂得多。

二、文件完整性校验

         通过对文件进行哈希，得出一段哈希值，若文件内容中间被拦截并修改了，哈希值就会发生变化。其中最出名还要数 MD5 Hash 算法，其具有“数字指纹”的特性，这使它成为应用最广泛使用的一种文件完整性校验和（Chacksum）算法，还有不少 Unix 系统有提供计算 MD5 Checksum 的命令。但 MD5 在2004年被王小云教授破解，在此之前 MD5 号称100万年才能破译的MD5密码系统，随后顶尖加密算法 SHA-1，同样也被王小云教授在半年后破解，王小云教授还为中国设计了自己的哈希函数算法——SM3。

三、数字签名领域

         数字签名技术是将摘要信息用发送者的私钥加密，与原文一起传送给接收者，接收者只有用发送者的公钥才能解密被加密的摘要信息，然后用哈希函数对收到的原文生成一个摘要信息，与解密的摘要信息对比。如果相同，则说明收到的信息是完整的，在传输过程中没有被修改，否则说明信息被修改过，因此数字签名还能够验证信息的完整性。

 

         此外，哈希算法在区块链领域也有广泛应用，人们常说的挖矿就是使用巨量的资源遍历运算出哈希值对应的数据。

 

基于 HASH 的数据类型

        Python 中基于哈希的数据类型有两个分别是字典（dict）和集合（set），在前面介绍字典是说字典的查询速度快，这是为何呢？而当时也说了集合天生去重，怎么做到的呢？其实都是利用了哈希的特性，下面来一一介绍

一、字典（dict）

        字典的查询速度非常快，并且不受字典大小的影响，下面我们假设有14亿人的身份信息存在字典里，而我们需要进行查询

data = {

        "张三":[23742364782642342323234,28,"山东济南"],

        "李四":[12124234232311214458271,25,"北京昌平"],

        "王五":[23030293483727384383929,32,"山东济南"],

        "赵六":[42302033030302482634674,28,"河北保定"],

        # "Jove":[xxxx],

        # "Kerry":[xxxx],

        # ...

}

        字典在创建时会为每一个 key 使用哈希算法生成一段固定长度的哈希值，假设生成的哈希值如下

张三	53
李四	67
王五	81
赵六	99
Jove	-10
Kerry	123

        在为每一个 key 生成完哈希值后，字典会把这些哈希值按照大小顺序排序好，并放在一个列表里，假设为 kd = [-10,53,67,81,99,123]；当我们想查找“赵六”的信息时，会把“赵六”先进行哈希得到其哈希值99 ，然后拿这个值去到 kd 列表里找，到这里就会有个疑问了，即使是生成了哈希值也会有14亿个数据在列表当中，像之前那样使用 for 循环进行遍历肯定也会非常漫长，那字典是如何做到快速找到99的呢？其实它用到了数据结构当中的二分法。

二分法：也称为折半查找法，是一种用于在有序数组中查找特定元素的高效算法。

基本原理：

1、首先，确定一个有序数组以及要查找的目标元素。

2、取数组的中间元素，将其与目标元素进行比较。

• 如果中间元素等于目标元素，则查找成功，返回中间元素的索引。
• 如果中间元素大于目标元素，则在数组的前半部分继续查找。
• 如果中间元素小于目标元素，则在数组的后半部分继续查找。

3、重复上述步骤，直到找到目标元素或者确定目标元素不在数组中。

举例：

 在 kd = [-10,53,67,81,99,123] 中查找99

第1步：首先，确定数组的范围是从索引 0 到索引 5

第2步：计算中间索引为 (0 + 5) // 2 = 2，中间元素是 kd[2] = 67

第3步：由于67小于99，所以在数组的后半部分继续查找，范围变为索引3到索引5

第4步：再次计算中间索引为 (3 + 5) // 2 = 4，中间元素是99，查找成功，返回索引4

        在例子里面可以看出在元素数量为6的列表中查找一个数只需要2此查询，和 for 循环遍历需要查询5次才能找到99，并且列表越大，效率提升越明显。在字典中只要到了99的位置，就可以定位到赵六对应的 value 值了。通过二分法查找，每次数据量都会少一半，这样查找最多31次(2^31=2147483648)就能从14亿信息里找到这个人的信息。当然字典真实的查找算法比这个还要复杂， 本篇是通过这个例子让大家理解下为何基于哈希的数据类型查找速度会快很多。但也有缺点，那就是增加数据时会非常慢，这次因为插入一个新的数据之后字典生成的哈希值需要重新排序。

二、集合（set）

         每存一个值到集合里时， 都要先经过哈希，然后通过得出的这个哈希值算出应该存在集合里的哪个位置，存的时候会先检查那个位置上有没有值，有的话就对比是否相等，如果相等，则不再存储此值。如果不相等（即为空——None），则把新值存在为空的位置。