Python set 去重的底层逻辑

Python的set去重基于哈希表，通过__hash__()和__eq__()判断重复，平均时间复杂度O(1)，不保证插入顺序，不可变类型可哈希，可变类型需自定义哈希与相等逻辑。

Python 的 set 去重本质依赖哈希表（hash table）实现，不是逐个比对，而是靠对象的哈希值快速定位和判断是否已存在。

哈希表结构决定去重效率

set 内部是一个开放寻址的哈希表。每个元素根据其 __hash__() 方法计算哈希值，再通过取模映射到固定大小的数组索引位置。插入时：若该位置为空，直接存入；若已存在元素（哈希冲突），则按探测序列找下一个空位。

• 相同值的对象（如 1 和 1.0）只要哈希值相等且 __eq__() 返回 True，就被视为重复
• 不可变类型（int、str、tuple）天然支持哈希；可变类型（list、dict）默认不可哈希，不能放入 set
• 自定义类若要进 set，需正确定义 __hash__ 和 __eq__，且要求“相等对象必须有相同哈希值”

去重过程不显式比较所有元素

插入新元素时，set 不遍历已有全部元素，而是：

• 先算哈希值 → 得到候选桶位置
• 检查该位置是否为空；若非空，先比哈希值，再调用 __eq__ 确认是否真重复
• 平均时间复杂度 O(1)，最坏（大量哈希冲突）退化为 O(n)

为什么顺序不保留？

哈希表按哈希值分布存储，与插入顺序无关。Python 3.7+ 的 dict 保持插入顺序是因为额外维护了顺序数组，但 set 没有这一机制 —— 它只关心“有无”，不记录“何时加入”。所以 set([3,1,2]) 输出可能是 {1, 2, 3}，但这只是哈希分布和扩容历史的结果，不是排序。

实际去重时要注意的细节

看似简单，但容易踩坑：

• float('nan') 的哈希值是固定的，但 nan == na

  

  n 为 False，所以多个 nan 可能被当成不同元素（CPython 中实际会去重，因特殊处理，但行为不保证跨实现一致）
• 字符串大小写敏感：'AbC' 和 'abc' 是两个不同元素，哈希值不同，== 为 False
• 元组去重看内容： (1, [2]) 不可哈希（含 list），但 (1, (2,)) 可以，且 (1, (2,)) 和 (1, (2,)) 被识别为同一元素