用循环输出以下数列:斐波那契数列(要输出20个数字)_Python学习之“为女朋友解释hash是个什么东西”

hash,一般翻译做散列、杂凑&＃xff0c;或音译为哈希&＃xff0c;是把任意长度的输入&＃xff08;又叫做预映射pre-image&＃xff09;通过散列算法变换成固定长度的输出&＃xff0c;该输出就是散列值。这种转换是一种压缩映射&＃xff0c;也就是&＃xff0c;散列值的空间通常远小于输入的空间。

它其实就是一个算法&＃xff0c;最简单的算法就是加减乘除&＃xff0c;比方&＃xff0c;我设计个数字算法&＃xff0c;输入&＃43;7&＃61;输出&＃xff0c;比如我输入1&＃xff0c;输出为8&＃xff1b;输入2&＃xff0c;输出为9。

哈希算法不过是一个更为复杂的运算&＃xff0c;它的输入可以是字符串&＃xff0c;可以是数据&＃xff0c;可以是任何文件&＃xff0c;经过哈希运算后&＃xff0c;变成一个固定长度的输出&＃xff0c;该输出就是哈希值。但是哈希算法有一个很大的特点&＃xff0c;就是你不能从结果推算出输入,所以又称为不可逆的算法

1. >>> hash(&＃39;我爱你&＃39;)
2. 3471388576844338423
3. >>> hash(&＃39;小猿圈&＃39;)
4. 5000768010434506639

如上所示&＃xff0c;输入“我爱你”三个字&＃xff0c;经过哈希运算后&＃xff0c;会得到一个随机数列&＃xff0c;而且不管你的输入文件多大&＃xff0c;最后得到的结果都是这么一个固定长度的数列&＃xff0c;即使你输入的是一部电影&＃xff0c;输出也是这么大。而且通过数列不能推导出输入。

哈希特性

不可逆&＃xff1a;在具备编码功能的同时&＃xff0c;哈希算法也作为一种加密算法存在。即&＃xff0c;你无法通过分析哈希值计算出源文件的样子&＃xff0c;换句话说&＃xff1a;你不可能通过观察香肠的纹理推测出猪原来的样子。

计算极快&＃xff1a;20G高清电影和一个5K文本文件复杂度相同&＃xff0c;计算量都极小&＃xff0c;可以在0.1秒内得出结果。也就是说&＃xff0c;不管猪有多肥&＃xff0c;骨头多硬&＃xff0c;做成香肠都只要眨眨眼的时间&＃xff0c;

哈希的用途

哈希算法的不可逆特性使其在以下领域使用广泛

1. 密码&＃xff0c;我们日常使用的各种电子密码本质上都是基于hash的&＃xff0c;你不用担心支付宝的工作人员会把你的密码泄漏给第三方&＃xff0c;因为你的登录密码是先经过 hash&＃43;各种复杂算法得出密文后 再存进支付宝的数据库里的
2. 文件完整性校验&＃xff0c;通过对文件进行hash&＃xff0c;得出一段hash值 &＃xff0c;这样文件内容以后被修改了&＃xff0c;hash值就会变。 MD5 Hash算法的”数字指纹”特性&＃xff0c;使它成为应用最广泛的一种文件完整性校验和(Checksum)算法&＃xff0c;不少Unix系统有提供计算md5 checksum的命令。
3. 数字签名&＃xff0c;数字签名技术是将摘要信息用发送者的私钥加密&＃xff0c;与原文一起传送给接收者。接收者只有用发送者的公钥才能解密被加密的摘要信息&＃xff0c;然后用HASH函数对收到的原文产生一个摘要信息&＃xff0c;与解密的摘要信息对比。如果相同&＃xff0c;则说明收到的信息是完整的&＃xff0c;在传输过程中没有被修改&＃xff0c;否则说明信息被修改过&＃xff0c;因此数字签名能够验证信息的完整性。

此外&＃xff0c;hash算法在区块链领域也使用广泛。

基于hash的数据类型有哪些&＃xff1f;

Python 中基于hash的2个数据类型是dict and set , 之前说dict查询速度快&＃xff0c;为何快&＃xff1f; 说set天生去重&＃xff0c;怎么做到的&＃xff1f;其实都是利用了hash的特性&＃xff0c;我们下面来剖析

dict 为何查询速度超快&＃xff0c;且不受dict大小影响 &＃xff1f;

解析&＃xff1a;假设我要存14亿人的基本信息

1. data &＃61; {
2. "张三":[23742364782642342323234,28,"山东济南"],
3. "李四":[12124234232311214458271,25,"北京昌平"],
4. "王五":[23030293483727384383929,33,"山东济南"],
5. "赵六":[42302033030302482634674,28,"河北保定"],
6. # "alex":["xxxx"],
7. # "黑姑娘":["xxxx"]
8. # ...
9. }

dict 的每个key 都要先经过hash生成一段固定长度的hash值&＃xff0c;假设生成的hash值如下

dict会把这些数字按大小排序好放在一个列表里kd &＃61; [-10, 53, 67, 81, 99, 123]

当我们想查找”赵六”的信息时&＃xff0c; 会把“赵六”先hash, 得到99这个值&＃xff0c;然后拿这个值去到kd列表里找&＃xff0c;想象这个列表有14亿个值 &＃xff0c;如何快速找到99&＃xff1f; 二分法就行&＃xff0c;具体看剖析视频。

只要找到了99的位置&＃xff0c;就可以定位到赵六对应的value的值了。 通过2分法查找&＃xff0c;每次数据量都会少一半&＃xff0c;这样查找最多31次(2**31&＃61;2147483648)就能从20亿信息里找到这个人的信息。

当然 dict 真实的查找算法比这个还要复杂些&＃xff0c; 我只是通过这个例子让大家理解下为何基于hash的数据类型查找速度会快很多。

set为何是天生去重的&＃xff1f;

因为每存一个值到set里时&＃xff0c; 都要先经过hash&＃xff0c;然后通过得出的这个hash值算出应该存在set里的哪个位置&＃xff0c;存的时候会先检查那个位置上有没有值 &＃xff0c;有的话就对比是否相等&＃xff0c;如果相等&＃xff0c;则不再存储此值。 如果不相等(即为空)&＃xff0c;则把新值 存在这。