字典dict与集合set简介

字典是一系列由键（key）和值（value）配对组成的元素的集合，在Python3.7+，字典被确定为有序（注意：在3.6中，字典有序是一个implementation detail，在3.7才正式成为语言特性，因此3.6中无法100%确保其有序性），而3.6之前是无序的，其长度大小可变，元素可以任意地删减和改变。

相比于列表和元组，字典的性能更优，特别是对于查找、添加和删除操作，字典都能在常数时间复杂度内完成。

而集合和字典基本相同，唯一的区别，就是集合没有键和值的配对，是一系列无序的、唯一的元素组合。

内部数据结构与工作原理

字典和集合的内部结构都是一张哈希表。

• 对于字典而言，这张表存储了哈希值（hash）、键和值这3个元素。

• 而对集合来说，区别就是哈希表内没有键和值的配对，只有单一的元素。

插入操作

每次向字典或集合插入一个元素时，Python会首先计算键的哈希值（hash(key)），再和 mask = PyDicMinSize - 1做与操作，计算这个元素应该插入哈希表的位置index = hash(key) & mask。如果哈希表中此位置是空的，那么这个元素就会被插入其中。

而如果此位置已被占用，Python便会比较两个元素的哈希值和键是否相等。

• 若两者都相等，则表明这个元素已经存在，如果值不同，则更新值。

• 若两者中有一个不相等，这种情况我们通常称为哈希冲突（hash collision），意思是两个元素的键不相等，但是哈希值相等。这种情况下，Python便会继续寻找表中空余的位置，直到找到位置为止。

值得一提的是，通常来说，遇到这种情况，最简单的方式是线性寻找，即从这个位置开始，挨个往后寻找空位。当然，Python内部对此进行了优化（这一点不再赘述），让这个步骤更加高效。

查找操作

和前面的插入操作类似，Python会根据哈希值，找到其应该处于的位置；然后，比较哈希表这个位置中元素的哈希值和键，与需要查找的元素是否相等。如果相等，则直接返回；如果不等，则继续查找，直到找到空位或者抛出异常为止。

删除操作

对于删除操作，Python会暂时对这个位置的元素，赋于一个特殊的值，等到重新调整哈希表的大小时，再将其删除。

不难理解，哈希冲突的发生，往往会降低字典和集合操作的速度。因此，为了保证其高效性，字典和集合内的哈希表，通常会保证其至少留有1/3的剩余空间。随着元素的不停插入，当剩余空间小于1/3时，Python会重新获取更大的内存空间，扩充哈希表。不过，这种情况下，表内所有的元素位置都会被重新排放。

虽然哈希冲突和哈希表大小的调整，都会导致速度减缓，但是这种情况发生的次数极少。所以，平均情况下，这仍能保证插入、查找和删除的时间复杂度为O(1)。