点击上方“蓝字”关注我们
散列（Hash）
对于一组数据项，顺序查找的时间复杂度是O(n)，二分查找是O(logn)，而对于散列的数据结构，查找算法的时间复杂度降到了O(1)
散列表（hash table）
散列表又叫“哈希表”，是一种数据集，其中数据项的存储方式有利于快速的进行查找操作
散列表中每一个用于存储数据项的存储位置加作“槽（slot）”，每一个槽都对应着一个唯一的名字
在python中与之对应的数据结构就是字典
{'a': 1, 'b': 2, 'c': 3}
散列函数（hash function）
散列函数：实现从数据项到存储槽名称的转换
有一种常用的散列函数就是“求余数”：将数据项除以散列表的大小，得到的余数作为槽名
为什么求余数比较常见呢？因为散列函数返回的槽号必须在散列表的范围内，所以一般会对散列表大小求余
当数据项都保存到散列表后，查找就可以直接通过槽号直接查询了，算法时间复杂度O(1)
冲突（collision）
散列函数在计算槽位的时候，不同数据项理应计算出不同的槽位，但是有时候会出现不同数据项计算出相同槽位（即冲突）
例如：大小11的散列表，散列函数“求余数”，77和44计算出的槽位都是0号！出现了冲突
对于散列表而言，最主要的讨论话题就是解决冲突
完美散列函数
完美散列函数：若给定一组数据项，完美散列函数可以把每一个数据项映射到不同的槽中
对于固定的一组数据，总是能想办法设计出近似完美的散列函数
好的散列函数具备的特征：
冲突少（每个数据项的槽位都不同）
计算难度较低（计算槽位的过程较容易）
充分分散数据项（节约空间）
散列技术的应用
散列技术除了在散列表中安排数据项的存储位置，还在许多信息处理领域有较多的应用
由于散列函数能够对任何不同的数据生成不同的散列值，若将散列值作为数据的“标志”，这一特性就可以广泛应用于数据一致性校验
因为散列值往往是一对一的，具有唯一性，所以可以作为某一个数据项的标志
作为一致性校验额数据“标志”，散列函数需要具备以下特征：
压缩性 ：任意长度的数据，通过散列函数计算出的散列值是 固定长度 的
容易计算 ：很容易从原数据计算出散列值（“标志”）， 注意不能从“标志”反向推出原数据
抗修改性：对原数据的微小变动，都会引起“标志”（散列值）巨大改变
抗冲突性：已知原数据和对应的散列值（“标志”），要再找到相同的散列值很难（即唯一性！）
近似完美函数：MD5/SHA
MD5（Message Digset）：将任何长度的数据变换成固定长度为128位（16字节）的“标志”
128位已经是非常巨大的数字空间了，据说地球的沙子的数量就是这么多
SHA（Secure Hash Algorithm）
SHA-0/SHA-1：输出散列值160位（20字节）
SHA-256/SHA-224：分别输出256位和224位
SHA-512/SHA-384：分别输出512位和384位
Python的散列函数库：hashlib
Python自带了MD5和SHA系列的散列函数：hashlib
包含了：md5、sha1、sha224、sha256、sha384、sha512
计算结果：
d26a53750bc40b38b65a520292f69306
数据一致性检验中的应用
1. 数据文件是否是一致的
为每个文件计算其散列值，通过比对散列值即可得知是否文件内容相同
2. 用于网络文件下载完整性校验
下载时会提供文件的散列值，下载过程中不断比对散列值，看是否下载出错
3. 用于文件分享系统（例如：百度网盘）
服务器中都存储了文件的散列值，相同文件无需存储多次
4. 加密形式保存密码（常用
）
在注册账户密码时，服务器往往存储的是密码对应的散列值，用户登录输入密码时，通过散列值比对验证
本文分享自微信公众号 - 小杨的python之路（gh_6ba152d49331）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
