Python dict查询key速度很慢吗？220万键的in操作是O(logn)吗

你的同事的说法不正确。

• Python dict底层采用哈希表实现，平均场景下in成员判断、键索引取值的时间复杂度均为O(1)，只有极端哈希冲突的最坏场景下才会达到O(n)，不存在*O(logn)*的时间复杂度。*O(logn)*是平衡搜索树类结构（例如C++的std::map）的查询复杂度，和哈希表的实现逻辑完全不同。
• 220万键值对的dict属于非常小的规模，单次查询耗时普遍在百纳秒级别，哪怕单进程每秒执行百万次查询，累计耗时也仅在数百毫秒区间，本身不会成为性能瓶颈。

如果这段代码确实被定位为耗时热点，一般是以下原因导致，而非单次查询本身的复杂度问题：

• 该段代码被循环执行的次数极多，比如千万次、亿次级别，极低的单次耗时被放大后才会凸显性能问题
• 作为查询键的rel_column字符串长度极大，计算哈希值的开销过高，拉长了单次查询的耗时
• 现有写法存在重复查询开销：先做in判断再取值的逻辑，等价于执行了两次哈希查询，可以优化为单次查询写法node_ids = id_map.get(rel_column)，如果返回None就代表键不存在，直接减少一半查询消耗
• 运行过程中dict被频繁增删元素，触发了多次扩容重哈希操作，拉高了整体耗时

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