所有测试用例超时：如何优化该HashMap实现代码？

我的代码在小输入下运行正常，但超大输入时超时（超过1秒），这是Codesignal的挑战题，提交未通过，求优化思路。试过很多优化都改坏了结果，下面是能正常运行的干净代码。

题目描述 #

要实现一个支持以下操作的HashMap：

• insert x y：插入键为x、值为y的键值对
• get x：返回键x对应的值
• addToKey x：为Map中所有键加上x
• addToValue y：为Map中所有值加上y

给定两组数组：queryTypes是操作名称数组，queries是对应操作的参数数组。执行所有查询，返回所有get操作结果的总和。

示例 #

当queryType = ["insert", "insert", "addToValue", "addToKey", "get"]，query = [[1, 2], [2, 3], [2], [1], [3]]时，solution(queryType, query)输出应为5。
每次查询后的HashMap状态：
第1次查询：{1: 2}
第2次查询：{1: 2, 2: 3}
第3次查询：{1: 4, 2: 5}
第4次查询：{2: 4, 3: 5}
第5次查询：返回结果为5

当前可运行代码 #

from collections import defaultdict

def solution(queryType, query):
    hashmap = defaultdict(int)
    results = []
    updated_keys = set()

    def insert(key, value):
        hashmap[key] = value

    def get(key):
        results.append(hashmap[key])

    def add_to_key(val):
        updated_dict = {}
        for key, value in hashmap.items():
            updated_key = key + val
            updated_dict[updated_key] = value
        hashmap.clear()
        hashmap.update(updated_dict)

    def add_to_value(val):
        nonlocal hashmap
        hashmap = {k: v + val for k, v in hashmap.items()}

    for i in range(len(queryType)):
        op = queryType[i]
        q = query[i]

        if op == "insert":
            insert(*q)
        elif op == "get":
            get(q[0])
        elif op == "addToKey":
            add_to_key(q[0])
        elif op == "addToValue":
            add_to_value(q[0])

    return sum(results)

优化思路 #

核心问题是原代码中addToKey和addToValue操作需要遍历整个HashMap修改所有键值对，时间复杂度为O(n)，当数据量和这类操作次数大时必然超时。可以通过偏移量记录的方式，完全避免遍历修改：

• 维护两个变量：key_offset（所有键的总偏移量）、value_offset（所有值的总偏移量），初始值都为0。
• 所有操作基于偏移量计算真实值，不直接修改HashMap内的存储内容：
  1. insert x y：存储的键为x - key_offset，存储的值为y - value_offset，后续通过偏移量还原真实值。
  2. get x：计算真实存储键为x - key_offset，取出对应值后加上value_offset得到结果，直接累加到总和（省去结果数组的内存开销）。
  3. addToKey x：仅执行key_offset += x，无需遍历HashMap。
  4. addToValue y：仅执行value_offset += y，无需遍历HashMap。

优化后代码示例 #

def solution(queryType, queries):
    hashmap = {}
    total = 0
    key_offset = 0
    value_offset = 0

    for op, q in zip(queryType, queries):
        if op == "insert":
            x, y = q
            hashmap[x - key_offset] = y - value_offset
        elif op == "get":
            x = q[0]
            total += hashmap[x - key_offset] + value_offset
        elif op == "addToKey":
            key_offset += q[0]
        elif op == "addToValue":
            value_offset += q[0]

    return total

优化逻辑说明 #

• 所有操作的时间复杂度均为O(1)（HashMap本身的哈希冲突情况除外），addToKey和addToValue仅做变量累加，彻底消除了遍历开销。
• 去掉了结果数组，直接累加get结果，减少内存占用和数组操作的额外消耗。
• 通过偏移量间接计算真实键值，避免修改HashMap已有内容，逻辑简洁高效。

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