python集合操作的时间复杂度？
在 Big O 表示法中，python 的每个集合操作的时间复杂度是多少？
我正在使用 Python 的 set type 对大量项目进行操作。我想知道每个操作的性能将如何受到集合大小的影响。例如，add 和成员资格测试：
myset = set()
myset.add('foo')
'foo' in myset
谷歌搜索并没有找到任何资源，但是仔细考虑 Python 的 set 实现的时间复杂度似乎是合理的。
如果它存在，指向类似 this 的链接会很棒。如果没有这样的东西，那么也许我们可以解决它？
用于查找所有集合操作的时间复杂度的额外标记。
根据 Python wiki: Time complexity，set 被实现为 hash table。因此，您可以期望在 O(1) 平均时间内查找/插入/删除。除非您的哈希表的负载因子太高，否则您将面临冲突和 O(n)。
PS出于某种原因，他们声称删除操作的时间为 O(n)，这看起来像是输入错误。
PPS 这对于 CPython 来说是正确的，pypy 是一个 different story。
操作 in 应该独立于容器的大小，即。 O(1) -- 给定一个最优散列函数。对于 Python 字符串，这应该几乎为真。散列字符串总是至关重要的，Python 应该很聪明，因此您可以期待接近最佳的结果。
其他答案没有谈论集合上的两个关键操作：联合和交叉。在最坏的情况下，联合将采用 O(n+m) 而交集将采用 O(min(x,y))，前提是集合中具有相同哈希的元素不多。可以在此处找到常见操作的时间复杂度列表：https://wiki.python.org/moin/TimeComplexity
