Pythonset去重原理与底层实现详解

Python 的 set 去重并非魔法，而是依托底层哈希表的精巧设计：每个元素必须可哈希，通过 hash() 快速定位存储位置，再用 __eq__() 严格校验是否真正重复；它支持平均 O(1) 的高效操作，却对不可变性有硬性要求——list、dict 等可变类型因哈希不稳定而被拒之门外；理解这一“哈希 + 相等”双重机制，不仅能解释为什么 {1, 1.0, True} 只剩一个元素，更能帮你正确实现自定义类去重、规避常见陷阱，并在性能与语义间做出更明智的技术选择。

Python集合（set）去重的本质，是依靠其底层哈希表（hash table）结构实现的：**每个元素必须可哈希，插入时通过哈希值定位存储位置，重复哈希值会触发相等性校验，相同则跳过**。

哈希表是核心存储结构

Python 的 set 底层和 dict 类似，使用开放寻址法（open addressing）的哈希表。它不存键值对，只存哈希后的键（即元素本身）。关键点包括：

• 每个元素调用 hash() 得到一个整数哈希值，再通过掩码运算映射到表中某个索引位置
• 哈希表初始容量较小（如 8），随着元素增多自动扩容（通常翻倍），并重新散列所有元素
• 冲突时（不同元素哈希值映射到同一位置），Python 使用伪随机探测序列寻找下一个空槽，而非链地址法

去重依赖“哈希 + 相等”双重判断

仅哈希值相同不足以判定重复——因为存在哈希碰撞。Python 会在哈希命中位置进一步调用 __eq__() 方法确认是否真正相等：

• 若 hash(a) == hash(b) 且 a == b 为 True，则视为重复，后者不插入
• 因此，自定义类要放入 set，必须同时正确定义 __hash__ 和 __eq__，且逻辑一致（例如不可变属性决定哈希与相等）
• 常见例子：set([1, 1.0, True]) 结果是 {1}，因为三者哈希值相同（hash(1) == hash(1.0) == hash(True)），且 1 == 1.0 == True

不可哈希对象无法加入 set

只有不可变类型（如 int、str、tuple（内含不可变项））默认可哈希；可变类型（如 list、dict、set）不可哈希：

• set([[1,2], [3,4]]) 会抛出 TypeError: unhashable type: 'list'
• 这是设计使然：哈希值需在对象生命周期内稳定，而可变对象内容变化会导致哈希不一致，破坏哈希表结构
• 若需对可变对象去重，可转为不可变表示（如 tuple(lst)）或使用其他策略（如基于 id 或自定义判重逻辑）

去重操作的时间复杂度接近 O(1)

平均情况下，插入、查找、删除单个元素都是 O(1)，所以构建去重集合整体为 O(n)：

• 得益于哈希表的平均常数时间访问，远优于用列表手动遍历去重的 O(n²)
• 最坏情况（大量哈希冲突且表满）可能退化为 O(n)，但 Python 哈希算法和扩容策略使其极难触发
• list(set(lst)) 是常用去重写法，但注意：不保持原始顺序（Python 3.7+ dict 有序，但 set 本身无序）；如需保序，可用 dict.fromkeys(lst).keys()

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于文章的相关知识，也可关注golang学习网公众号。