python set

线上的某一个业务模块常规的执行时间大概是这样的

📊 总体统计: 完成的 xxx 总数: 379 最短耗时: 0.190 秒 最长耗时: 2815.415 秒 平均耗时: 67.626 秒 中位数耗时: 9.585 秒 标准差: 258.304 秒

⏱️ 耗时分布: < 1秒: 33 次 ( 8.7%) 1-5秒: 101 次 ( 26.6%) 5-10秒: 64 次 ( 16.9%) 10-30秒: 99 次 ( 26.1%) 30-60秒: 9 次 ( 2.4%) 1-5分钟: 62 次 ( 16.4%) 5-10分钟: 2 次 ( 0.5%) 10-30分钟: 6 次 ( 1.6%) > 30分钟: 3 次 ( 0.8%)

里面有一段逻辑用了 set 来计算交集, 子集, 不过 set 里放的是基本数据类型, 比如: int, str

某次迭代增加了一个功能, 就想着是不是可以把对象放到 set 里面去, 这样代码会简单一些

新版本本地功能测试通过了, 但是线上运行的时候, 发现性能下降了很多, 某些场景会超过90分钟

把对象放set里面的性能问题

set 的存储

set 内部使用 hash table 存储元素

hash 值决定元素在内存中的存储位置 hash 值不缓存, 每次都重新计算

Hash 冲突处理

Python 的 dict 和 set 底层是用 开放寻址法（Open Addressing）中的 探查（probing）机制 来解决冲突的。

当多个元素有相同 hash 值时 需要用__eq__方法进一步比较确认 这要求每次操作都要准确的 hash 值

具体什么时候计算 hash？

添加元素 (add, update): 每个新元素计算1次 hash 查找元素 (in 操作): 每次查找计算1次 hash 删除元素 (remove, discard): 每次删除计算1次 hash 集合运算 (并集|、交集&、差集-): 每个参与运算的元素计算1次 hash set 扩容时: 所有现有元素需要重新计算 hash 重新分布

hash 的优化

内置类型优化：

int、str等基本类型有高度优化的hash实现 整数的hash计算几乎是O(1)时间 字符串使用SipHash算法，快速且安全

🔢 整数(int)的hash:

  • 小整数(-5到256): 直接使用数值作为hash
  • 大多数整数: hash(n) ≈ n (在合理范围内)
  • 非常大的数: 使用更复杂的数学算法
  • 性能: 非常快，基本是O(1)时间

C语言实现：

CPython中set的核心操作用C实现 hash计算速度非常快

实际性能影响 从你附件中的代码可以看到：

基本类型: hash计算极快（纳秒级），几乎无感知 简单对象: hash计算较快（微秒级），影响很小 复杂对象: 如果__hash__方法复杂，可能有明显影响

优先使用基本类型作为set元素（int, str, tuple等） 自定义类的__hash__方法要简单高效 避免在hash计算中做复杂操作 使用@dataclass(frozen=True)可以获得优化的hash实现

Python 中的 set（集合）数据结构的底层实现主要基于哈希表（Hash Table）。

CPython（Python 的官方实现）使用**开放寻址法（Open Addressing）和线性探测法（Linear Probing）**来解决哈希冲突。当发生冲突时，系统会尝试在哈希表的其他位置寻找空槽位来存储元素。

O(1) 平均时间复杂度：由于哈希表的特性，set 在平均情况下进行成员资格检查（in 操作）、添加（add）和删除（remove）操作的时间复杂度都是 O(1)。但在最坏情况下（例如所有元素都发生哈希冲突并被存储在同一个“桶”中），时间复杂度可能退化为 O(n)。

总结来说，Python set 的底层实现是一个高效的哈希表，它利用哈希函数和冲突解决机制来存储和管理无序且唯一的元素，从而提供了快速的查找和操作性能。

唯一性保证：每次添加都要检查重复 → 需要O(1)查找

为什么 set 里面放对象慢

  • 复杂的hash计算，需要处理多个属性, hash质量直接影响性能
  • 坏hash对象：大量冲突，性能退化到O(n)
  • 优化方向：好的__hash__和__eq__实现

性能的关键：

  • 好的hash函数 → 均匀分布 → 少冲突 → 快速操作
  • 坏的hash函数 → 聚集分布 → 多冲突 → 性能退化

开放寻址法（Open Addressing）

在哈希表中，开放寻址法是一种用于解决哈希冲突的策略。当两个不同的键被映射到哈希表中的同一个位置（即哈希冲突）时，开放寻址法不会使用链表或其他结构来存储冲突的元素，而是 在哈希表内继续寻找下一个空槽位 来存放该元素。

探查策略

线性探查（Linear Probing） 查找序列：h, h+1, h+2, h+3, …

优点：实现简单；

缺点：可能导致主聚集（Primary Clustering） —— 冲突元素会堆积，影响性能。

二次探查（Quadratic Probing） 查找序列：h, h+1², h+2², h+3², …（实际是 h + i² mod table_size）

优点：减少主聚集；

缺点：可能无法探查到所有槽位。

双重哈希（Double Hashing） 查找序列：h1(key), h1(key) + i*h2(key)

使用两个哈希函数 h1 和 h2；

通常效果最好，冲突分布较均匀。

Python 使用的策略 Python 的 dict 和 set 实现是基于 开放寻址法，具体采用了：

变种的二次探查（quadratic probing）；

并结合了 随机化偏移量，减少攻击者构造大量哈希冲突的可能性；

使用了特殊的优化，如 perturbation 技术来改善性能。