当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实现细节。例如，这是一种使用相同的哈希码创建任意数量的不同整数的方法：

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

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

Answer 2

您可以在此处查看set来源，这会有所帮助：https://github.com/python/cpython/blob/723f71abf7ab0a7be394f9f7b2daa9ecdf6fb1eb/Objects/setobject.c#L429-L441

很难设计一个具体的例子，但是幸运的是，理论很简单:)该集合使用值的hash来存储密钥，只要hash足够独特，就可以按预期获得O(1)性能。

如果出于某种奇怪的原因，您的所有项目都具有不同的数据，但哈希值相同，则会发生冲突，因此必须分别检查所有项目。

为了说明，您可以将集合看作是这样的字典：

import collection


your_set = collection.defaultdict(list)


def add(value):
    your_set[hash(value)].append(value)


def contains(value):
    # This is where your O(n) can occur, all values the same hash()
    values = your_set.get(hash(value), [])
    for v in values:
        if v == value:
            return True
    return False