为什么字典和集合，要比列表更高效
为什么字典和集合，要比列表更高效
字典和集合高效背后的玄机
缘起
前段时间，小甲鱼在【奇技淫巧】版块中分享了一个小技巧 —— 仅需要简单地添加一行代码，即可将代码的执行效率提高 10000 倍以上（传送门）
很多鱼油看了答案之后啧啧称奇，因为只是简单地将列表对象转换成集合对象，执行效率立马是天上和地下之别。
为什么列表变成集合之后，效率竟然提高了这么多呢？
其真相是由于集合的背后是有散列表的支持，而列表却没有！
所以，列表每次的查找运算都是需要从头到尾进行扫描，而集合则只需要简单地进行查表即可。
打个比方，同样是在新华字典中查找 “龟” 字，列表是从头到尾一页一页地翻，而集合则是先通过偏旁部首索引表，找到 “龟” 所在的页码，然后直接一步到位。
好，那么这一篇文章，小甲鱼就尝试探讨一下 Python 字典和集合背后的玄机 —— 散列表。
散列表（Hash table）
散列表（Hash table）也称为哈希表，其实就是一个稀疏数组（总是有空白元素的数组称为稀疏数组）。
将要存储的数据是先通过哈希函数（在 Python 中，这个函数是 hash()）进行计算，获得一个哈希值，这个值决定了数据将存放在什么位置：
右边这个表格我们就叫做散列表，其中的每一行我们称之为一个 bucket，每个 bucket 中存放一个字典的键值对
（其实分别是键和值的引用，因为只有存放引用地址，才能确保每个 bucket 大小一致，进而才能通过偏移进行索引）
写入
如果希望将 "FishC":1314 这个键值对写入散列表
那么第一步 Python 会调用 hash() 函数
将字典的 “键” 进行计算，从而得到一个哈希值
接着将哈希值的最低几位数字加工后作为偏移量，在散列表中进行索引
若找到的 bucket 为空，将键值对 "FishC":1314 写入
若找到的 bucket 已经被存放了数据，那么将产生散列冲突（几乎任何散列算法都无法避免散列冲突）
-- 为了解决冲突，Python 会在哈希值中另外取几位数字进行加工，重新得到一个新的 bucket 索引值
-- -- 若新的 bucket 为空，则将键值对写入
-- -- 若新的 bucket 仍然已有数据，则重复以上的步骤
查找
如果希望在散列表中查找 "FishC" 这个键对应的值
那么第一步 Python 同样会调用 hash() 函数
将字典的 “键” 进行计算，从而得到一个哈希值
接着将哈希值的最低几位数字加工后作为偏移量，在散列表中进行索引
若找到的 bucket 为空，将抛出 KeyError 异常
若找到的 bucket 已经被存放了数据，那么对比两者的键是否相等
-- 如果相等，返回 bucket 里的值
-- 如果不相等，说明在写入时发生了散列冲突
-- -- 为了解决冲突，Python 会在哈希值中另外取几位数字进行加工，重新得到一个新的 bucket 索引值
-- -- -- 若新的 bucket 为空，将抛出 KeyError 异常
-- -- -- 若新的 bucket 仍然已有数据，则继续重复以上的步骤
那么在查找操作上，散列表（字典和集合）的速度可以说是降维碾压序列的
这是因为散列表只需进行查表操作，而序列则需要挨个去比对
因此，两者速度随数据规模变化的曲线如下：
可见，散列表是常量时间，其查找速度并不会受数据规模的影响
而序列则是线性时间，其查找速度随数据规模线性增长
弱点
在查找速度上，散列表的优势可谓相当明显
但是，它的这个效率是 “拿空间来换时间” 的结果
为什么这么说呢？
因为均匀分布所有随机的键是每一个散列函数终身追求的终极目标
但这就犹如嫦娥之于八戒一样可望而不可即
想想就好了
散列函数是根据键进行一系列计算才得到的哈希值
由于传入的键是随机的，那么这个哈希值往往也会是飘忽不定的
小甲鱼打个不是那么恰当的比方
比如你从 12 楼往下扔 12 个 “女朋友”
那么她们落地后整齐排列的几率有多大？
几乎不可能的嘛
这就意味着散列表的尺寸会非常大
因此，散列表又叫做稀疏数组
稀疏数组，言下之意就是一个占据 100 个空位的洗漱数组，里面存放数据的，可能也就 3 个……
所以浪费大量的空间，就是散列表最大的毛病
FAQ
集合跟字典有什么关系？
集合可以看作是 “只有键没有值” 的字典，其实当初 Python 没有将集合设置为内置类型的时候，大家也是这么干的。
为什么字典的键和集合的元素必须是可哈希的？
可哈希，即能够通过调用 hash() 函数获得对应的哈希值
根据上面的写入和查找原理，如果一个对象未能通过计算得到一个固定的哈希值
那么，相当于没办法在散列表中确定它的位置。
为什么键的值如果相等，哈希值就必须一致呢？
因为 hash() 函数的作用是将参数进行一系列运算后，才变成最终的哈希值
那么这一系列运算不外乎就是加、减、乘、除、求余之类的搞来搞去……
那我问你，1 + 2 和 1.0 + 2，最终的值是一样的吗？
那不就得了~
尽管 1 和 1.0 这两个数字的内部存储结构完全不同，但将它们参与运算后得到的结果却往往是相同的！
所以，才有了 “值相等，那么哈希值必须相等” 这么一个原则。
网盘 “秒传” 的背后的真相
由于网盘上存储了大量相同的文件
那么既然是同一个文件
网盘就可以在后台只存一份，然后在用户的前端显示每个人都有一份
当某些用户要删除这个文件的时候，我并不真的删除，只需要在前端显示已经删除了
但后端其实还是一直保留着……
直到所有使用此文件的用户都删除了这个文件（是不是很像 Python 的变量）
实现就是在用户上传文件时，首先计算上传文件的哈希值
一旦计算出用户要上传的数据和服务器上已经存储的某个数据是一样的
那么就直接不用上传了
直接在用户那里标记上这个文件已经上传成功即可
这个过程几乎是瞬间搞定的，也就是所谓的 “秒传”！