Python集合操作的时间复杂度？

Question

Python中的集合操作在大O符号下的时间复杂度是什么？

我在处理大量数据时使用Python的集合类型。我想知道每个操作的性能会如何受到集合大小的影响。例如，像添加元素和检查元素是否存在的操作：

myset = set()
myset.add('foo')
'foo' in myset

我在网上搜索了一下，没有找到相关的资料，但我觉得Python集合的时间复杂度应该是经过仔细考虑的。

如果有类似这个的链接就太好了。如果没有这样的资料，也许我们可以一起算出来？

如果能找到所有集合操作的时间复杂度，那就更棒了。

Answer 1

操作 in 的速度应该和容器的大小无关，也就是说，它的时间复杂度应该是 O(1)，前提是有一个好的哈希函数。对于Python中的字符串，这个说法应该是 几乎 成立的。对字符串进行哈希处理是非常重要的，Python在这方面应该做得很好，所以你可以期待接近最佳的效果。

Answer 2

其他回答没有提到集合上的两个重要操作：并集和交集。在最坏的情况下，并集的时间复杂度是O(n+m)，而交集的时间复杂度是O(min(x,y))，前提是集合中没有太多元素有相同的哈希值。你可以在这里找到常见操作的时间复杂度列表：https://wiki.python.org/moin/TimeComplexity

Answer 3

根据Python的维基页面：时间复杂度，集合（set）是用哈希表来实现的。所以你可以期待查找、插入和删除操作的平均时间复杂度是O(1)。不过，如果你的哈希表的负载因子太高，就会出现碰撞，这时候时间复杂度就变成O(n)了。

附注：出于某种原因，他们声称删除操作是O(n)，这看起来像是个笔误。

再附注：这对于CPython是正确的，而pypy则是另一个故事。