python 的 set 底层基于哈希表实现，采用开放寻址法处理冲突，要求元素可哈希且不可变以保证哈希值稳定，平均时间复杂度为 o(1)。
Python 的 set 类型底层确实基于哈希表（hash table）实现，其核心结构是 CPython 源码中的 PySetObject，内部使用一个动态扩容的哈希表数组（table），每个槽位（bucket）存储一个指向元素的指针，并辅以探查策略解决冲突。
哈希表结构：稀疏数组 + 开放寻址
Python 集合不采用链地址法，而是用「开放寻址法（open addressing）」处理哈希冲突。底层 table 是一个指针数组，初始大小为 8，每个位置可能为：
- NULL：空槽（未使用）
-
dummy：已删除元素占位符（如被
discard()或remove()清除后留下） - 实际元素指针：指向被加入集合的对象（如整数、字符串等不可变对象）
插入时，先计算元素的哈希值（调用 PyObject_Hash()），再对表长取模得到初始索引；若该位置已被占用，就按固定规则（线性探测 + 偏移扰动）向后查找下一个可用槽位。
哈希计算与冲突控制的关键细节
Python 对不同类型的对象有定制哈希算法，例如：
立即学习“Python免费学习笔记（深入）”；
- 整数
n的哈希就是n自身（经符号和模运算调整） - 字符串使用 SipHash 变种（CPython 3.4+），抗哈希碰撞攻击
- 元组递归哈希各元素，要求所有元素可哈希
为避免长链式探测，集合会在装载因子（used / size）超过 2/3 时自动扩容（通常翻倍），并重新散列全部元素。删除操作不缩容，但 dummy 槽位积累过多时也会触发重建。
为什么 set 要求元素可哈希且不可变？
根本原因在于哈希值必须稳定：
- 插入时靠哈希定位槽位，查找时也靠同一哈希值去比对——若对象中途修改导致哈希变化，就再也找不到它了
- 可变对象（如
list、dict）默认无安全哈希实现，且语义上也不适合作为集合成员 - 自定义类可通过实现
__hash__和__eq__支持，但必须保证：一旦加入 set，实例状态不再改变
小结：高效背后的权衡
Python 集合的 O(1) 平均查找/插入/删除，依赖于高质量哈希函数、合理的装载因子控制和紧凑的内存布局。但它牺牲了顺序（插入顺序在 3.7+ dict 有序后，set 仍不保证）、不支持索引，并严格限制元素类型。理解这些，能帮你避开 unhashable type 错误，也明白为何 frozenset 是不可变版本的自然选择。
