Python如何实现固定大小字典按插入顺序自动覆盖最早元素

核心实现思路 #

通过继承Python内置字典类实现自定义固定大小字典，完全兼容普通字典的读写语法，无需修改原有写入逻辑，所有操作时间复杂度均为O(1)，性能远高于遍历删除的方案。

代码实现 #

自定义固定大小字典类 #

class FixedSizeDict(dict):
    def __init__(self, max_size: int, *args, **kwargs):
        self.max_size = max_size
        super().__init__(*args, **kwargs)
        # 初始化时如果传入的键值对超过上限，提前淘汰最早插入的条目
        while len(self) > self.max_size:
            self.pop(next(iter(self)))

    def __setitem__(self, key, value):
        # 新增键时如果已达容量上限，先删除最早插入的键
        if key not in self and len(self) >= self.max_size:
            self.pop(next(iter(self)))
        super().__setitem__(key, value)

使用示例 #

# 定义字典容量上限
MAX_SIZE = 10

# 替换原有字典初始化逻辑，原有写入foo的代码无需任何修改
foo = FixedSizeDict(MAX_SIZE, {
    "369610": "a", "109122": "a", "907897": "a", "333291":"a", 
    "381819": "a", "387583": "a", "677430": "a", "660221": "a", 
    "118095":"a", "612172": "a"
})

print(len(foo))  # 输出 10

foo["223533"] = "a"  # 自动淘汰最早插入的键"369610"
foo["601336"] = "a"  # 自动淘汰次早插入的键"109122"

print(len(foo))  # 输出仍为 10

适配与扩展说明 #

• 如果你使用的是Python 3.7以下版本，将父类替换为collections.OrderedDict，将淘汰逻辑替换为self.popitem(last=False)即可实现完全一致的效果。
• 如果需要实现「更新已有键时，将该键调整为最新插入顺序（避免被马上淘汰）」的需求，修改__setitem__逻辑即可：

def __setitem__(self, key, value):
    # 已存在的键先删除再插入，更新插入顺序
    if key in self:
        del self[key]
    elif len(self) >= self.max_size:
        self.pop(next(iter(self)))
    super().__setitem__(key, value)

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