Python如何高效实现值为列表的字典的元素到对应键的反向映射

需求说明 #

给定键对应列表的原字典，需要生成反向映射：每个列表中的元素作为键，所有包含该元素的原字典键组成的列表作为值，示例如下：
原字典：

D = {'a': [1,2,3], 'b': [2,3,4], 'c': [3,4,5]}

期望输出：

out = {1: ['a'], 2: ['a', 'b'], 3: ['a', 'b', 'c'], 4: ['b', 'c'], 5: ['c']}

适配场景：原字典共100个键，每个键对应列表长度50~10000。

最高效实现方案 #

核心思路 #

不需要多次遍历所有列表，仅需单次遍历所有列表的所有元素，直接为每个元素关联对应的原字典键即可，时间复杂度为O(T)，T为所有列表的总元素数，是理论上的最优复杂度（必须遍历所有元素至少一次才能完成映射）。

实现代码 #

场景1：原列表内无重复元素

如果每个键对应的列表中不存在重复元素，可直接用defaultdict(list)实现：

from collections import defaultdict

def reverse_dict(original_dict):
    result = defaultdict(list)
    for key, value_list in original_dict.items():
        for elem in value_list:
            result[elem].append(key)
    # 可选：转为普通字典返回
    return dict(result)

场景2：原列表内可能存在重复元素

如果同一个列表内可能出现相同元素，需要做去重处理，避免同一个原键在结果列表中多次出现：

from collections import defaultdict

def reverse_dict_duplicate_safe(original_dict):
    result = defaultdict(set)
    for key, value_list in original_dict.items():
        # 先对当前列表去重，减少无效遍历
        for elem in set(value_list):
            result[elem].add(key)
    # 集合转列表，符合输出格式要求
    return {k: list(v) for k, v in result.items()}

如果需要保留原字典键的出现顺序，可将set(value_list)替换为list(dict.fromkeys(value_list))（Python 3.7+ 支持，去重同时保留元素首次出现顺序），同时将defaultdict(set)改为defaultdict(list)，追加前判断键是否已存在即可。

性能说明 #

按最大规模计算，100个键每个对应10000个元素，总元素量为100万，Python原生实现即可在毫秒级完成运算，无需引入额外第三方依赖。

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