Python中集合按位与(&)操作的时间复杂度及底层实现问询

时间复杂度 #

集合的&操作（求交集）时间复杂度为 O(min(len(a), len(b)))，其中a和b是参与运算的两个集合。Python会自动选取规模更小的集合遍历，对每个元素执行哈希表的O(1)存在性检查（判断是否在另一个集合中），因此整体耗时由较小集合的元素数量决定。

底层实现原理 #

Python集合基于开放寻址哈希表实现，核心逻辑如下：

• 执行a & b时，第一步会比较两个集合的大小，优先遍历元素更少的那个集合。
• 对遍历到的每个元素，利用哈希表的特性完成O(1)时间的存在性校验，检查该元素是否存在于另一个集合中。
• 所有通过校验的元素会被收集起来，构建成一个新的集合返回。
• 若其中一个操作数是frozenset（不可变集合），执行逻辑完全一致，最终返回的结果类型会匹配输入的不可变集合类型。

内容的提问来源于stack exchange，提问作者Blackwidow