面试题：Python字典删除键值对时的性能考量

Question

假设你有一个非常大的字典（包含百万级别的键值对），要删除其中满足某个条件（例如值大于100）的所有键值对。请分析不同删除方法（如使用循环直接删除、先收集键再批量删除等）的时间复杂度和空间复杂度，并给出你认为最优的实现代码。

Answer 1

1. 不同删除方法分析

使用循环直接删除

• 时间复杂度：由于字典在删除元素时，其内部结构会发生调整，每次删除操作平均时间复杂度为 O(1)，但在最坏情况下可能达到 O(n)。这里要进行 n 次删除操作（n 为满足条件的键值对数量），整体时间复杂度为 O(n)，其中 n 为满足条件需要删除的键值对数量，由于 n 最大可能接近字典元素总数，所以时间复杂度可近似认为是 O(N)，N 是字典总键值对数量。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

先收集键再批量删除

• 时间复杂度：收集键的过程需要遍历一次字典，时间复杂度为 O(N)，然后批量删除这些键，假设每次删除平均时间复杂度为 O(1)，删除操作的时间复杂度也是 O(n)，所以总的时间复杂度为 O(N)，N 是字典总键值对数量。
• 空间复杂度：O(n)，需要额外的空间来存储满足条件的键，n 为满足条件需要删除的键值对数量，最坏情况下 n 接近 N，所以空间复杂度近似为 O(N)。

2. 最优实现代码（Python 示例）

my_dict = {i: i + 1 for i in range(1000000)}  # 模拟百万级字典
keys_to_delete = [key for key, value in my_dict.items() if value > 100]
for key in keys_to_delete:
    del my_dict[key]

这种先收集键再批量删除的方式在实际应用中相对更稳定，因为在遍历字典过程中直接删除可能会导致遍历行为出现异常（在 Python 中，遍历字典时直接删除元素会抛出 RuntimeError），并且时间复杂度在平均和最坏情况下都能保证为 O(N)。同时虽然空间复杂度有所增加，但相对可控，不会出现由于频繁调整字典结构导致性能急剧下降的情况。