python - 当CPython设置 `in`运算符为O(n)吗？

Question

我正在阅读有关CPython中的time complexity of set operations的信息，并了解到集合的in运算符的平均时间复杂度为O(1)，最坏情况下的时间复杂度为O(n)。我还了解到，最糟糕的情况不会在CPython unless the set's hash table's load factor is too high中发生。

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

Answer 1

负载系数是红色鲱鱼。在CPython中，集合(和字典)会自动调整大小，以将负载因子保持在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实现细节。例如，这是一种使用相同的哈希码创建任意数量的不同int的方法:

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

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