python - python集合操作的时间复杂度？

Question

Big O中python的每个集合操作的时间复杂度是多少？符号？

我正在使用 Python 的 set type用于对大量项目的操作。我想知道每个操作的性能将如何受到集合大小的影响。例如，add ，以及成员资格测试:

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

谷歌搜索没有找到任何资源，但仔细考虑 Python 的集合实现的时间复杂度似乎是合理的。

如果存在，则提供指向 this 之类的链接会很好。如果没有类似的东西，那么也许我们可以解决它？

求所有集合操作的时间复杂度的加分项。

Answer 1

根据Python wiki: Time complexity , set 被实现为 hash table .因此，您可以期望在 O(1) 平均时间内查找/插入/删除。除非您的哈希表的负载因子太高，否则您将面临冲突和 O(n)。

附:出于某种原因，他们声称删除操作需要 O(n)，这看起来像是一个错误的输入。

附言这对于 CPython 来说是正确的，pypy 是 different story .