set()是如何实现的？
我看到有人说，Python中的set对象在检查某个元素是否存在时是O(1)的。这是怎么实现的呢？它内部使用了什么样的数据结构？这种实现还有什么其他的影响呢？
这里的每个回答都让我受益匪浅，但我只能选择一个，所以我会选择最接近我原问题的回答。谢谢大家提供的信息！
6 个回答
我觉得这是个常见的误解，set 查找（或者说哈希表）并不是 O(1) 的复杂度。
来自维基百科
在最简单的模型中，哈希函数是完全不确定的，而且表格不会自动调整大小。对于最佳的哈希函数选择，大小为 n 的表格如果使用开放寻址法，就不会发生冲突，可以存放最多 n 个元素，成功查找时只需要一次比较。而如果是大小为 n 的表格使用链式法，且有 k 个键，则最多会有 max(0, k-n) 次冲突，查找时需要O(1 + k/n) 次比较。最糟糕的哈希函数选择会导致每次插入都发生冲突，这样哈希表就退化成线性查找，每次插入平均需要 Ω(k) 次比较，而成功查找时最多需要 k 次比较。
当人们说集合的成员检查是O(1)时，他们指的是平均情况。最糟糕的情况是，当所有的哈希值都发生冲突时，成员检查的时间复杂度是O(n)。你可以查看Python关于时间复杂度的维基页面。
维基百科的文章提到，对于一个不调整大小的哈希表，最好的时间复杂度是O(1 + k/n)。这个结果不直接适用于Python的集合，因为Python的集合使用的是会调整大小的哈希表。
在维基百科的文章中进一步提到，对于平均情况，并假设使用一个简单的均匀哈希函数，时间复杂度是O(1/(1-k/n))，其中k/n可以被一个常数c<1所限制。
大O表示法只关注当n变得非常大的时候的行为。因为k/n可以被一个常数限制，c<1，而且这个常数与n无关，
所以O(1/(1-k/n))不会大于O(1/(1-c))，这相当于O(常数) = O(1)。
因此，假设使用均匀简单的哈希函数，在平均情况下，Python集合的成员检查是O(1)。
根据这个讨论：
实际上，CPython中的集合（set）是用类似字典的方式实现的，只不过字典的值是虚拟的（也就是说，集合的成员是字典的键），并且有一些优化利用了这些虚拟值的特点。
简单来说，set的底层数据结构是哈希表。这就解释了为什么检查一个元素是否在集合中是O(1)的，因为在哈希表中查找一个项目平均来说也是O(1)的操作。
如果你有兴趣的话，可以查看CPython的集合源代码，根据Achim Domma的说法，这段代码最初主要是从dict的实现中剪切和粘贴过来的。
注意：现在，set和dict的实现已经有了很大的不同，所以它们在某些行为（比如顺序是否随机和插入顺序）和性能上也有所差异；不过它们仍然是基于哈希表实现的，所以在平均情况下查找和插入的时间复杂度依然是O(1)，但set不再只是“dict，只是没有值”的简单版本。