Python如何修改字典实现键到链式更新后最终值的映射

我们需要将存在多跳关系的ID映射字典，转换为每个旧ID直接指向最终ID的字典，核心是顺着每个ID的映射链路溯源到终点。

简易实现（适合小数据量场景） #

逻辑直白好懂，直接遍历每个键，不断把值替换成值对应的映射，直到值不在字典的键列表里为止：

j = {'a':'b', 
'c':'d', 
'e':'f', 
'd':'g', 
'h':'i', 
'b':'j', 
'g':'k'}

for old_id in j:
    # 只要当前映射的新ID还存在对应的更新规则，就继续往下找
    while j[old_id] in j:
        j[old_id] = j[j[old_id]]

print(j)
# 输出结果和预期完全一致：{'a': 'j', 'c': 'k', 'e': 'f', 'd': 'k', 'h': 'i', 'b': 'j', 'g': 'k'}

注意：该写法会直接修改原字典，如果需要保留原始字典请先做深拷贝，另外数据量极大时存在重复遍历的性能损耗。

优化实现（适合大数据量场景） #

增加路径缓存，每个ID节点只会被遍历一次，时间复杂度O(n)，同时自带循环引用防护，不会出现a→b, b→a这类异常数据导致的死循环：

def get_final_id_map(origin_map: dict) -> dict:
    final_map = {}
    for current_id in origin_map:
        if current_id in final_map:
            continue
        # 记录当前溯源路径上的所有节点
        trace_path = []
        temp = current_id
        while temp in origin_map:
            if temp in final_map:
                # 碰到已经处理过的节点，直接复用结果
                target = final_map[temp]
                break
            trace_path.append(temp)
            temp = origin_map[temp]
        else:
            # 溯源到终点，temp就是最终ID
            target = temp
        # 给路径上所有节点统一赋值最终ID
        for node in trace_path:
            final_map[node] = target
    return final_map

# 测试
j = {'a':'b', 'c':'d', 'e':'f', 'd':'g', 'h':'i', 'b':'j', 'g':'k'}
result = get_final_id_map(j)
print(result)

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