Python字典dict.values()时间复杂度是多少？如何通过值查找对应键？

问题1解答：Dict.values()的in操作时间复杂度 #

dict.values()返回的是字典值的视图对象，该对象没有内置哈希索引结构，所以执行x in Dict.values()操作时需要遍历字典的所有值逐一比对匹配，时间复杂度是O(n)，n为字典的键值对总数量。
你给出的示例代码中if 10 in Dict.values():的执行耗时会随字典规模增大线性增长。

问题2解答：值查键的O(1)实现方案 #

原生Python字典只维护了键到值的单向映射，没有内置反向索引，所以不做额外处理的话无法实现O(1)复杂度的值查键操作，只能通过遍历所有键值对实现，时间复杂度为O(n)。

如果需要高频进行值查键操作，且能接受额外的空间开销，可以自行维护反向映射字典实现O(1)查询：

1. 当字典的值唯一时，直接构建反转字典即可：

original_dict = {1:10,2:20,3:30,4:40}
# 构建反向映射
reverse_dict = {v: k for k, v in original_dict.items()}
value = 20
# O(1)查询对应键
key = reverse_dict[value] # 得到2

2. 当值可能重复，需要返回所有匹配键时，反向映射的值存储对应键的列表，同步更新正反两个字典即可：

original_dict = {1:10,2:20,3:10,4:40}
reverse_dict = {}
# 初始化反向映射
for k, v in original_dict.items():
    if v not in reverse_dict:
        reverse_dict[v] = []
    reverse_dict[v].append(k)

value = 10
# O(1)查询所有匹配键
keys = reverse_dict[value] # 得到[1,3]

注意每次修改原字典（新增/删除/更新键值对）时，都需要同步修改反向映射字典，保证两边数据一致。

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