17370845950

Python set去重依赖哈希表机制：先通过__hash__()定位桶，再用__eq__()判等；元素须可哈希且不可变；自定义类需同时正确定义__hash__和__eq__；动态扩容保障O(1)平均性能。

P

ython 的 set 去重不是靠逐个比对，而是依赖哈希表（hash table）的定位与判等机制协同完成。

哈希值决定存储位置

每个元素插入前，Python 先调用它的 __hash__() 方法得到一个整数哈希值。这个值被映射到哈希表中的某个“桶”（bucket）索引位置。如果该桶为空，元素直接存入；如果已有元素，就进入下一步判断。

• 哈希值不同 → 必定存入不同桶，视为不同元素
• 哈希值相同 → 进入同一桶，还需用 __eq__() 进一步确认是否真相等

相等性判断才是去重关键

仅哈希值相同不足以触发去重。Python 会在同一个桶内遍历已有元素，对每个元素 e 检查两个条件是否同时成立：
hash(x) == hash(e) 且 x == e。
只有两者都为真，才认为 x 是重复项，跳过插入。

• 若只重写 __eq__ 而不重写 __hash__，对象默认按内存地址哈希，可能造成逻辑矛盾（两个相等对象哈希不同，被当成两个元素）
• 若故意让所有对象哈希值相同（如返回固定整数），只要 __eq__ 正确，去重仍有效——但性能会下降，因为所有元素挤进一个桶，退化为线性查找

元素必须可哈希

不可变类型（如 int、str、tuple）天然可哈希；可变类型（如 list、dict、set）不可哈希，尝试加入会直接报 TypeError: unhashable type。

• tuple 可以进 set，但前提是它内部所有元素也都可哈希（例如 (1, [2]) 不行）
• 自定义类要进 set，必须同时正确定义 __hash__ 和 __eq__，且保证“相等对象哈希值一致”

动态扩容保障效率

哈希表初始容量通常为 8，当元素数量超过容量的约 2/3 时自动扩容（翻倍），并重新计算所有元素的哈希位置。这避免了哈希冲突过多导致性能退化。

• 批量构建 set（如 set(lst)）比循环 .add() 更高效，因为前者只需一次 rehash，后者可能多次触发扩容
• 平均时间复杂度为 O(1)，最坏情况（极端哈希碰撞）是 O(n)，但 CPython 的开放寻址策略使这种情况极少见