如何利用Python的OrderedDict实现一个支持按访问顺序排序的结构？-Python教程-PHP中文网

ordereddict 不支持按访问顺序自动重排序，必须手动调用 move_to_end() 才能实现 lru 行为；其“有序”仅指插入顺序，读取不改变键位置，keys() 仍按插入序返回。

如何利用python的ordereddict实现一个支持按访问顺序排序的结构？

OrderedDict 本身不支持按访问顺序自动重排序，必须手动调用 move_to_end() 才能实现 LRU 行为。

为什么直接用 OrderedDict 无法自动按访问顺序排列

很多人误以为 OrderedDict 的“有序”包含“访问序”，其实它只保证插入顺序。读取一个已存在的键（比如 d['x']）不会改变其位置，keys() 或 items() 返回的顺序仍和插入时一致。

常见错误现象：
- 写了 d['a']; d['b']; d['a']，再遍历 d.keys()，结果仍是 ['a', 'b']，不是 ['b', 'a']
- 用作缓存时，最久未使用的项没被踢出，因为顺序没更新

根本原因：Python 3.7+ 的普通 dict 虽然也保持插入序，但更不支持访问序——OrderedDict 至少提供了 move_to_end() 这个可控出口。

手动维护访问顺序的正确写法

每次读或写后显式调用 move_to_end(key)，把该键移到末尾（默认 last=True），这样最久未访问的总在开头。

Python 3.14.2

Python 3.14.2是Python编程语言在2025年12月5日发布的稳定版本，属于3.14系列的第二个维护更新。该版本包含了18项修复，重点解决了多进程、数据类及正则表达式等模块的回归问题，并修复了CVE-2025-12084等安全漏洞。此版本标志着自由线程模式（移除GIL）正式获得官方支持，是Python发展的重要里程碑。

下载

读操作必须用 get() 或 __getitem__() + move_to_end()，不能只用 d[key] 然后忽略返回值
写操作（包括更新值）后也要 move_to_end()，否则新值虽存在，但位置卡在原处
如果只读不写，可封装成 get_and_touch() 方法避免漏调

示例：

from collections import OrderedDict
<p>class LRUCache(OrderedDict):
def <strong>getitem</strong>(self, key):
value = super().<strong>getitem</strong>(key)
self.move_to_end(key)  # 关键：访问后移至末尾
return value</p><pre class="brush:python;toolbar:false;">def __setitem__(self, key, value):
    if key in self:
        self.move_to_end(key)  # 更新时也要移
    super().__setitem__(key, value)

cache = LRUCache() cache['a'] = 1 cache['b'] = 2 _ = cache['a'] # 触发 move_to_end print(list(cache.keys())) # ['b', 'a']

性能与兼容性注意事项

move_to_end() 是 O(1)，但频繁调用仍有开销；相比 dict，OrderedDict 内存占用高约 10–15%，且 Python 3.7+ 后官方建议仅在需要顺序控制时使用。

如果只要 LRU 缓存，优先考虑 functools.lru_cache 或第三方库如 lru-dict，它们底层用双向链表 + dict，更快更省内存
若需自定义淘汰逻辑（比如按访问频次而非时间），OrderedDict 就不够用了，得换 heapq 或专门的数据结构
Python 3.8+ 中 OrderedDict.popitem(last=False) 可高效弹出最早插入/访问的项，这是实现 LRU 驱逐的关键