为何dict.items()支持快速查找？探究其实现机制

先看这个场景：
我们定义一个百万级的字典：

d = {i:i for i in range(1,1000001)}

把d.items()存入变量x，再创建一个包含相同键值对元组的列表：

l = [(i, i) for i in range(1,1000001)]

对比(1000001, 1000001) in x和(1000001, 1000001) in l的耗时，差异非常明显——前者是快速查找，后者则要遍历整个列表。

原本以为x是基于元组哈希的类set结构，但当字典的值换成不可哈希的列表时：

d = {i:[i,i+1] for i in range(1,1000001)}

此时(n, [n, n+1]) in d.items()依然能实现快速查找，这是怎么做到的？

核心原因：dict_items是字典视图，而非集合/普通列表 #

d.items()返回的并不是集合或列表，而是字典视图对象（dict_items），它的查找逻辑完全依赖字典本身的哈希表，而非遍历所有键值对：

• 当执行(key, value) in dict_items时，Python的底层步骤是：
  1. 先通过字典的哈希表快速检查key是否存在（这一步是O(1)时间复杂度）
  2. 如果key存在，取出字典中对应的实际值，和传入的value做相等性比较（用==，而非哈希匹配）
  3. 如果key不存在，直接返回False

这就意味着：

• 不管字典的值是否可哈希，只要键是可哈希的（字典的键本身就要求可哈希），就能通过键快速定位，再做值的比较
• 而列表的in操作是逐个遍历元素，每个元素都要完整比较元组的键和值，时间复杂度是O(n)，所以百万级数据下耗时会差几个数量级

耗时对比代码 #

import time

def for_dict_items(n):
    #d = {i:i for i in range(1, n+1)}
    d = {i:[i, i+1] for i in range(1, n+1)}
    di = d.items()
    st = time.time()
    x = (n, [n, n+1]) in di
    et = time.time()
    return (et - st)


def for_tuples_list(n):
    #l = [(i, i) for i in range(1, n+1)]
    l = [(i,[i, i+1]) for i in range(1, n+1)]
    st = time.time()
    x = (n, [n, n+1]) in l
    et = time.time()
    return (et - st)


k = 1000000

t1 = for_dict_items(k)
t2 = for_tuples_list(k)

print(t1, t2, t2/t1, sep = "\n")

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