set 底层实现：哈希冲突和删除标记怎么处理

做的事：先看删除大量元素后，set会不会缩小

set底层是哈希表，插入时会扩容，但删除呢。

代码s = set(range(1000)) size_full = sys.getsizeof(s) for i in range(990): s.discard(i) size_after_remove = sys.getsizeof(s)

验证：删掉99%的元素，内部表大小纹丝不动

从1000个元素删到只剩10个。

结果1000个元素时占用: 32984 字节 删除990个只剩10个之后占用: 32984 字节（完全没有变化！）

验证了：set只会在插入时按需扩容，删除元素时不会主动收缩内部哈希表——被删除的槽位会被标记成一种特殊状态（常说的"删除标记"/dummy标记，跟"从没用过的空槽"是两种不同的状态），留着以后插入新元素时复用，但整个表的容量不会因为删除而缩小。

验证：哈希值相同的对象，也不会丢数据

故意构造一批hash值全部相同的对象，塞进set。

代码与结果class BadHash: def __hash__(self): return 1 # 故意让所有实例hash值一样 def __eq__(self, other): return self.v == other.v objs = [BadHash(i) for i in range(5)] s2 = set(objs) 结果: {BadHash(0), BadHash(3), BadHash(4), BadHash(1), BadHash(2)} set大小: 5（全部都在！）

5个对象的 __hash__ 全部返回1（完全冲突），但set一个都没丢——底层用开放寻址处理冲突：新元素的哈希槽位如果已经被占用，就按一套探测规则继续找下一个候选槽位，直到找到空位或者碰到 __eq__ 判断出的同一个元素。

验证：冲突不丢数据，但付出了查找变慢的代价

正常分布的哈希 vs 全部冲突的哈希，查找速度差多少。

结果正常set(10万个int)查5万次: 0.0029s 全冲突set(2000个同hash对象)查2000次: 0.2282s

换算成单次查找耗时：正常情况约0.058微秒/次，全冲突情况约114微秒/次——慢了约2000倍。这就是哈希冲突的代价：本该是O(1)的哈希查找，一旦大量元素挤在同一个哈希槽附近，就会退化成接近线性扫描的速度。这也是为什么Python官方文档强调 __hash__ 的实现要让不同对象尽量散列到不同的值——冲突不会让程序出错（set/dict能正确处理），但会拖慢性能。

分步演示：set底层的删除标记与冲突处理

每一步都是本文上面用Python 3.14跑出来的原始结果。