为何Python集合与字典查找的摊还最坏时间复杂度为O(N)？

核心问题 #

Python中集合的item in set、字典的d.get(item)操作，平均时间复杂度是O(1)，但摊还最坏时间复杂度为O(N)，根源在于二者底层都是哈希表，而哈希表可能发生哈希冲突。

先澄清：哈希冲突≠元素重复 #

集合确实不允许重复值，但哈希冲突和元素重复是完全不同的概念：

• 元素重复：两个元素的__eq__返回True，集合会自动去重，只保留一个。
• 哈希冲突：两个不同的元素（__eq__返回False），经过哈希函数计算后得到了相同的哈希值。比如"apple"和"banana"不是重复值，但如果哈希函数设计得不好，它们的哈希值可能完全相同，这就会引发冲突。

哈希冲突如何让时间复杂度从O(1)变O(N)？ #

哈希表的核心是通过哈希值快速定位元素的存储位置：

1. 正常情况：计算元素的哈希值→映射到数组下标→直接访问对应位置，这个过程是O(1)。
2. 发生冲突时：多个元素被映射到同一个数组下标，Python会用链表（或当链表过长时转为红黑树）来存储这些冲突元素。
3. 极端冲突场景：当哈希表的负载因子（元素总数/哈希表容量）过高，且所有元素的哈希值都相同，所有元素都会被放到同一个链表中。此时查找元素需要遍历整个链表，时间复杂度直接退化为O(N)。

Python的哈希表会在负载因子达到阈值（默认0.7）时自动扩容，重新哈希所有元素来减少冲突，但扩容是摊还操作——在扩容前的极端冲突场景下，查找操作就会出现O(N)的情况。

集合冲突的代码示例 #

我们可以构造一个自定义类，让所有实例的哈希值都相同，但实例本身是不同的元素，这样添加到集合后会全部产生冲突：

class BadHash:
    def __init__(self, val):
        self.val = val  # 每个实例有唯一的val，确保是不同元素
    def __hash__(self):
        return 1  # 所有实例返回相同哈希值，强制冲突
    def __eq__(self, other):
        # 只有val相同才判定为相等
        return isinstance(other, BadHash) and self.val == other.val

# 往集合里添加1000个不同的冲突元素
s = set()
for i in range(1000):
    s.add(BadHash(i))

# 查找某个元素，此时需要遍历整个冲突链表
target = BadHash(500)
print(target in s)  # 输出True，但查找过程是O(N)级别的

字典冲突的代码示例 #

字典的键同样依赖哈希值，用相同的自定义类作为键，就能模拟字典的冲突场景：

class BadHash:
    def __init__(self, val):
        self.val = val
    def __hash__(self):
        return 1
    def __eq__(self, other):
        return isinstance(other, BadHash) and self.val == other.val

# 往字典里添加1000个冲突的键值对
d = {}
for i in range(1000):
    d[BadHash(i)] = f"value_{i}"

# 查找某个键，需要遍历冲突链表
target_key = BadHash(500)
print(d.get(target_key))  # 输出"value_500"，查找过程为O(N)

内容的提问来源于stack exchange，提问作者Autumn Nguyen