Python集合基于哈希表实现，使用开放寻址处理冲突，元素作为键存储，支持高效增删查和去重，依赖可哈希性与相等比较，动态扩容维持性能，平均时间复杂度为O(1)。
Python 集合（set）的底层实现基于 哈希表（hash table），这使得集合在大多数操作上具有高效的性能表现。虽然集合对外表现为无序、去重的元素容器，但其内部结构与字典（dict）非常相似。
哈希表作为核心结构
Python 的 set 使用开放寻址的哈希表来存储元素：
- 每个元素通过其 哈希值 确定在表中的位置。
- 当多个元素哈希到同一个位置时（即发生冲突），Python 使用探测机制（如线性探测的变种）寻找下一个可用槽位。
- 所有元素本身作为“键”直接存入哈希表，没有对应的值——这一点和 dict 不同，dict 存的是键值对，而 set 只存键。
实际上，在 CPython 实现中，set 和 dict 的哈希表逻辑高度相似，但 set 不需要维护额外的 value 指针，因此更节省内存。
去重机制依赖哈希和相等比较
集合自动去重的关键在于两个条件：
立即学习“Python免费学习笔记（深入）”；
- 可哈希性：集合中的元素必须是可哈希的（即实现了 __hash__() 方法），不可变类型如 int、str、tuple 是可以的，而 list、dict 不行。
- 相等性判断：即使两个对象哈希值相同，仍需通过 __eq__() 判断是否真正相等，防止误判。
插入一个元素时，Python 先计算其哈希值找到位置，若该位置已有元素，则比较它们是否相等；如果不等且发生冲突，则继续探测直到找到空位或匹配项。
动态扩容维持性能
随着元素增加，哈希表可能变得密集，导致冲突增多、查找变慢。为了保持 O(1) 的平均时间复杂度：
- 当元素数量超过某个阈值（通常是容量的 2/3 左右），集合会触发 扩容。
- 创建更大的哈希表，并将所有元素重新插入新表（即 rehash）。
- 这个过程虽然耗时，但不频繁，均摊后仍能保证高效操作。
常见操作的时间复杂度
得益于哈希表设计，大部分集合操作都非常快：
- 添加元素（add）：平均 O(1)
- 删除元素（remove/discard）：平均 O(1)
- 查找成员（in）：平均 O(1)
- 集合运算（并集、交集等）：O(len(s1) + len(s2)) 或类似量级
最坏情况（大量哈希冲突）下可能退化为 O(n)，但在实际使用中极为罕见。
基本上就这些。Python 的 set 背后没有魔法，靠的是成熟的哈希表技术，在速度和内存之间取得良好平衡。理解这一点有助于写出更高效的代码，比如避免将不可哈希类型放入集合，或者在大规模数据处理时优先考虑 set 而不是 list 去重。
