如何以更低时间复杂度合并Python列表中的字典

嗨，这个场景我经常碰到！你当前的实现每次遍历原元素都要扫一遍目标列表，时间复杂度是O(n²)，数据量一大效率就会很低。我们可以用**字典（哈希表）**把时间复杂度降到O(n)——因为字典的键查找是O(1)的常数时间操作，具体做法如下：

基础实现（手动判断） #

先通过字典快速累计每个name的total值，再转换成目标列表格式：

original_list = [
    {"name": "bob", "total": 1},
    {"name": "alice", "total": 5},
    {"name": "eve", "total": 2},
    {"name": "bob", "total": 3},
    {"name": "alice", "total": 2},
    {"name": "alice", "total": 2},
]

# 初始化字典用于累计总和
total_tracker = {}
for entry in original_list:
    name = entry["name"]
    amount = entry["total"]
    # 字典键存在就累加，不存在就初始化
    if name in total_tracker:
        total_tracker[name] += amount
    else:
        total_tracker[name] = amount

# 将字典转换为目标列表结构
result = [{"name": name, "total": total} for name, total in total_tracker.items()]
print(result)

输出结果就是你想要的：

[{'name': 'bob', 'total': 4}, {'name': 'alice', 'total': 9}, {'name': 'eve', 'total': 2}]

更简洁的写法（用collections.defaultdict） #

Python的collections模块里的defaultdict可以帮我们省去判断键是否存在的步骤，自动给不存在的键设置默认值（这里用int的默认值0），代码更清爽：

from collections import defaultdict

original_list = [
    {"name": "bob", "total": 1},
    {"name": "alice", "total": 5},
    {"name": "eve", "total": 2},
    {"name": "bob", "total": 3},
    {"name": "alice", "total": 2},
    {"name": "alice", "total": 2},
]

total_tracker = defaultdict(int)
for entry in original_list:
    total_tracker[entry["name"]] += entry["total"]

result = [{"name": k, "total": v} for k, v in total_tracker.items()]

关于顺序的补充 #

如果你需要保持原列表中name首次出现的顺序：

• Python 3.7及以上版本：普通字典已经是插入有序的，上面的代码直接就能保留顺序
• Python 3.6及以下版本：可以用collections.OrderedDict来替代普通字典，确保顺序不变

为什么这个方法更高效？ #

整个过程只需要遍历原列表一次（O(n)时间），每个字典的查找、更新操作都是O(1)的常数时间，最后转换列表的时间是O(k)（k是不同name的数量，k≤n），所以整体时间复杂度是O(n)，比你原来的O(n²)高效得多，数据量越大，优化效果越明显。

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