为何Python字典比集合查找/更新效率更高？三数之和实例验证

一、字典比集合高效的底层逻辑 #

咱们先从Python的底层实现说起：其实set本质上是基于dict实现的——集合里的每个元素，对应字典里的一个键，而值是一个固定的占位符（比如全局的None或者专门的哨兵对象）。那为啥dict反而更快？主要有这几点：

• 优化优先级不同：字典是Python里最常用的数据结构之一，核心开发团队在它身上投入的优化精力远多于集合。比如哈希值缓存、内存布局优化、冲突处理逻辑这些细节，字典的实现都更精细。
• 内存布局与缓存友好性：字典的每个槽位同时存储哈希值、键、值，三者在内存上是连续的；而集合的槽位只存哈希值和元素（相当于字典的键）。这种结构差异会影响CPU缓存的命中率，字典的存取操作更容易被缓存命中，从而减少内存访问的开销。
• 操作逻辑的细微差异：比如判断元素是否存在的in操作，集合的底层实现需要额外处理一些元素唯一性校验的分支逻辑，而字典的查找逻辑更紧凑——毕竟字典天生就是为键的快速查找设计的。

二、你的三数之和代码中集合更慢的具体原因 #

回到你的两段代码，核心差异就是内层循环用dict存值还是用set存值。从测试结果看，dict版本确实更快，具体原因可以拆解为：

1. 哈希冲突处理的效率差异：虽然两者都是哈希表，但字典在处理哈希冲突时的链表/开放寻址逻辑经过更多优化。当出现哈希冲突时，字典的查找路径更短，内存访问的开销更小。
2. 赋值与添加操作的底层开销：dic[nums[j]] = j是字典的赋值操作，而mem.add(nums[j])是集合的添加操作。集合的添加需要先检查元素是否存在（避免重复），而字典的赋值虽然也会先查找键，但覆盖值的逻辑比集合的唯一性校验更简洁，底层的C实现指令更少。
3. 测试场景下的放大效应：你的本地测试中10万次调用差了0.06秒，属于微秒级的差异，但LeetCode的测试用例是大规模的数据集，这种细微的性能差异会被不断放大，最终导致耗时差了200ms左右。

其实要强调的是，两者的性能差异非常小，大部分场景下可以忽略不计，但在对性能敏感的高频操作中，这种差异就会显现出来。

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