Python有序字典中能否以常数时间删除所有大于指定值的键？

一、删除字典中所有大于3的键 #

给定初始字典：

d = {1: True, 2: False, 3: False, 4: True, 5: False, 6: True, 7: False, 8: False}

要得到仅保留键≤3的字典，有两种常用实现方式：

方式1：先收集待删键再批量删除 #

注意不能直接遍历原字典时删除键（会触发迭代错误），可以先把所有大于3的键存起来，再逐个删除：

# 筛选出所有需要删除的键
keys_to_remove = [k for k in d if k > 3]
# 批量删除键
for k in keys_to_remove:
    del d[k]

执行后d就变为{1: True, 2: False, 3: False}。

方式2：直接生成过滤后的新字典 #

如果不需要保留原字典对象，用字典推导式生成新字典更简洁：

d = {k: v for k, v in d.items() if k <= 3}

二、有序键字典能否在常数时间内完成操作？ #

先明确：Python 3.7+的普通字典本身是插入有序的，但哪怕键是有序的，也无法在常数时间（O(1)）内完成该删除操作。

原因很直接：

• 就算键有序，最多能用二分查找快速定位到第一个大于3的键的位置（这一步是O(log n)时间），但后续删除这些键的过程，不管是逐个删除还是构建新字典，都需要遍历并处理每个待删除的元素，这部分时间和待删除元素的数量挂钩。整体时间复杂度是O(log n + m)（m为待删除键的数量），达不到常数时间的要求。
• 哪怕用collections.OrderedDict这类有序字典，它底层是双向链表加哈希表结构，要删除某个位置后的所有元素，也得遍历这些元素逐个移除，同样做不到一步完成的常数时间操作。

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