当CPython set`in`运算符是O（n）时？

Question

我在读CPython中的time complexity of set operations并了解到集合的in运算符的平均时间复杂度为O（1），最坏情况下的时间复杂度为O（n）。我还了解到最坏的情况不会发生在CPythonunless the set's hash table's load factor is too high。在

这让我想知道，这种情况何时会出现在CPython实现中？是否有一个简单的演示代码，它显示了一个具有in运算符的O（n）时间复杂度的集合？在

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，而不管{}的值是多少。在

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

^{pr2}$

这表明创建的一万个不同的int都具有哈希代码1。在

Answer 2

您可以在这里查看set源代码，它可以帮助：https://github.com/python/cpython/blob/723f71abf7ab0a7be394f9f7b2daa9ecdf6fb1eb/Objects/setobject.c#L429-L441

很难想出一个具体的例子，但幸运的是，理论相当简单：） 集合使用值的hash存储键，只要hash足够唯一，您将获得预期的O(1)性能。在

如果由于某种奇怪的原因，所有的项都有不同的数据，但哈希值相同，则会发生冲突，并且必须分别检查所有这些项。在

为了举例说明，您可以将集合视为这样一个dict：

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