Python 中set（集合）的底层核心是基于开放寻址法实现的哈希表（散列表），本质是一个只存储 key、不存储 value 的简化版字典（dict），以此实现元素唯一性、O (1) 平均复杂度的增删查操作。

一、核心底层结构体

CPython 源码中，集合由两个核心结构体定义，完整描述了其内存布局：

1. 元素槽位结构体 setentry哈希表的最小存储单元，仅存储元素本身和其哈希值（无字典的 value 字段），避免重复计算哈希值，提升性能：

   c

   运行

   typedef struct {
       PyObject *key;  // 指向集合元素的指针
       Py_hash_t hash; // 缓存元素的哈希值
   } setentry;
   

2. 集合主体结构体 PySetObject管理整个哈希表的元信息，控制哈希表的扩容、探测、迭代等核心行为：

   c

   运行

   typedef struct {
       PyObject_HEAD       // Python对象通用头部
       Py_ssize_t fill;    // 已占用槽位数（含活跃元素+已删除标记）
       Py_ssize_t used;    // 活跃元素的实际数量
       Py_ssize_t mask;    // 哈希表容量-1，用于位运算快速取模
       setentry *table;    // 指向哈希表槽位数组的指针
       Py_hash_t hash;     // 仅frozenset使用，缓存整个集合的哈希值
       Py_ssize_t finger;  // 迭代游标，保障迭代时的安全删除
   } PySetObject;
   

二、哈希表基础设计

1. 初始容量：空集合的哈希表初始容量为 8（PySet_MINSIZE），槽位数组长度始终为 2 的整数次幂，方便通过hash & mask快速计算索引，替代取模运算。
2. 槽位的三种状态：
   • 空槽（NULL）：未被使用，是插入操作的终止位；
   • 活跃元素：存储了有效元素的 key 和 hash 值；
   • 墓碑（dummy）：元素被删除后的占位标记，不会被直接清空，避免探测链断裂。

三、核心操作的底层实现

1. 插入元素（add()）与去重逻辑

插入是集合最核心的操作，也是实现元素唯一性的关键，步骤如下：

1. 调用hash()计算待插入元素的哈希值，若元素不可哈希，直接抛出异常；
2. 通过hash & mask计算元素的初始槽位索引；
3. 遍历探测序列，对每个槽位做判断：
   • 若槽位为空 / 墓碑：直接写入元素的 key 和 hash，更新fill和used，插入完成；
   • 若槽位有活跃元素：先对比哈希值，哈希值不同则继续探测；哈希值相同，再用==对比元素本身：
     • 元素相等：判定为重复，直接放弃插入；
     • 元素不相等：哈希碰撞，继续按探测序列查找下一个槽位。

2. 查找元素（in）

1. 计算元素哈希值和初始索引，按探测序列遍历槽位；
2. 遇到活跃元素：哈希值 + 元素均匹配，返回True；不匹配则继续探测；
3. 遇到墓碑：不终止，继续向后探测；
4. 遇到空槽：终止遍历，返回False。

3. 删除元素（remove()/discard()）

1. 按查找逻辑定位到目标元素；
2. 不直接清空槽位，而是将其标记为dummy 墓碑，仅减少used计数，不修改fill；
3. 若元素不存在，remove()抛出异常，discard()无操作。

四、哈希冲突的解决机制

CPython 的集合不使用拉链法，而是采用开放寻址法 + 伪随机扰动探测序列处理哈希冲突：

• 简单线性探测会导致哈希聚集（冲突元素集中在连续槽位），大幅降低性能；
• CPython 使用基于哈希值的perturb扰动函数，生成伪随机的探测序列，公式核心为：

  c

  运行

  i = (i * 5 + perturb + 1) & mask;
  perturb >>= 5;
  

• 该机制能将冲突元素均匀分散到哈希表中，避免聚集，同时兼顾 CPU 缓存局部性，保证访问效率。

五、动态扩容与 Rehash 机制

集合会通过动态扩容控制哈希冲突的概率，核心规则如下：

1. 扩容触发条件：负载因子（fill / 总容量）超过2/3（≈66.7%） 时，强制触发扩容。负载因子过高会导致探测链变长，性能急剧下降。
2. 扩容倍数：
   • 当活跃元素数used ≤ 50000时，新容量为原容量的4 倍；
   • 当活跃元素数used > 50000时，新容量为原容量的2 倍（避免内存浪费）。
3. Rehash 过程：
   • 申请新的槽位数组，重置mask为新容量 - 1；
   • 遍历旧哈希表，跳过墓碑槽位，将所有活跃元素重新计算索引，插入到新表中；
   • 释放旧表内存，更新集合的table、fill、mask等元信息。
   • 扩容后会清理所有 dummy 标记，fill会重置为新的活跃元素数used。

六、核心特性的底层支撑

1. 元素必须可哈希：集合的增删查完全依赖哈希值定位元素，可变类型（列表、字典、集合本身）无法生成固定哈希值，因此不能作为集合元素；不可变类型（int、str、tuple、frozenset）可哈希，可存入集合。
2. 元素唯一性：通过「哈希值预校验 +==最终确认」的双重校验实现，既保证了去重效率，又解决了哈希碰撞导致的误判。
3. 无序性：元素的存储位置由哈希值决定，且扩容时会触发全量 Rehash，元素位置会重新分布，因此集合不保证插入顺序（Python 3.7 + 字典保留插入顺序，但集合始终不保证）。
4. set与frozenset的底层区别：frozenset是不可变集合，初始化后无法增删元素，因此可以预计算并缓存整个集合的哈希值，支持作为字典的 key、嵌套进其他集合中；而可变的set无法生成固定哈希值，不支持这些操作。

七、时间复杂度

表格

最坏情况仅出现在所有元素哈希值完全冲突的极端场景，CPython 3.3 + 默认开启哈希随机化，进程启动时会随机化哈希种子，防止攻击者构造哈希碰撞发起拒绝服务攻击