当 CPython 设置 `in` 运算符是 O(n) 时？

Question

我正在阅读CPython中集合操作的时间复杂度，并了解到集合运算in符的平均时间复杂度为 O(1)，最坏情况下的时间复杂度为 O(n)。我还了解到最坏的情况不会发生在 CPython 中，除非集合的哈希表的负载因子太高。

这让我想知道，在 CPython 实现中什么时候会发生这种情况？是否有一个简单的演示代码，它显示了一个具有明显可见的 O(n) 时间复杂度的in运算符的集合？

Answer 1

负载因子是一个红鲱鱼。在 CPython 中，set（和 dicts）会自动调整大小以将负载因子保持在 2/3 以下。您无法在 Python 代码中做任何事情来阻止它。

O(N)当大量元素具有完全相同的哈希码时，就会发生行为。然后它们映射到同一个哈希桶，并将查找退化为线性搜索的慢速形式。

设计这种坏元素的最简单方法是创建一个具有可怕散列函数的类。像，例如，未经测试：

class C:
    def __init__(self, val):
        self.val = val
    def __eq__(a, b):
        return a.val == b.val
    def __hash__(self):
        return 3

然后hash(C(i)) == 3不管 的值i。

要对内置类型执行相同操作，需要深入了解其 CPython 实现细节。例如，这里有一种方法可以使用相同的哈希码创建任意数量的不同整数：

>>> import sys
>>> M = sys.hash_info.modulus
>>> set(hash(1 + i*M) for i in range(10000))
{1}

这表明创建的一万个不同的整数都具有哈希码 1。