Python 的 set 底层基于哈希表（hash table）实现，和 dict 高度相似，但只存储键（key），不存值（value）。它的核心目标是支持平均 O(1) 时间复杂度的成员检查、插入和删除操作。
哈希表结构：数组 + 桶链（开放寻址法）
CPython 中的 set 使用**开放寻址法（open addressing）**，而非拉链法（chaining）。这意味着：
- 底层是一块连续的内存数组（称为
table），每个槽位（slot）存储一个 hash 值和一个指向元素对象的指针； - 当发生哈希冲突时，不是在槽位后挂链表，而是按固定探测序列（如线性探测或二次探测变种）寻找下一个空闲槽；
- CPython 实际使用的是“伪随机探测”（基于 hash 值扰动的线性探测改进版），兼顾局部性和冲突分散性。
关键字段与内存布局
每个 set 对象内部维护一个 PySetObject 结构体，主要包含：
- table 指针：指向哈希表数组起始地址；
- used：当前已存储的唯一元素个数；
- fill：已占用（含已删除标记）的槽位总数（用于触发扩容）；
-
mask：哈希表长度减一（table size 总是 2 的幂），用于快速取模：
index = hash & mask； -
deleted slots：被删除元素留下的“哑元”（dummy）槽位（值为
NULL或特殊标记），避免探测链断裂。
哈希计算与冲突处理细节
插入一个元素 x 时，流程如下：
立即学习“Python免费学习笔记（深入）”；
- 调用
hash(x)得到哈希值（要求对象可哈希且 hash 稳定）； - 用
hash & mask定位初始索引； - 若该槽为空或为 dummy，直接插入；
- 若槽中已有元素，比较其 hash 值是否相等 → 不等则探测下一个位置；
- 若 hash 相等，再调用
==判断是否真正重复（解决哈希碰撞）。
注意：set 的去重依赖 hash() 和 __eq__() 两个方法协同工作——hash 不同一定不等，hash 相同才需进一步比较。
动态扩容与收缩机制
当 fill / size > 2/3（约 66.7% 负载率）时触发扩容，新 size 为原 size 的 4 倍（最小为 8）；删除大量元素后，若 fill / size 且 size > 50000，则可能缩容。扩容过程会重新哈希所有现存元素，重建 table。
这种策略在空间和时间间做了权衡：避免频繁重哈希，同时控制探测长度增长（负载率越低，平均查找步数越少）。
