手写 LRU 缓存，如何做到 O(1)

用哈希表定位节点，用双向链表维护访问顺序。

原理

哈希表保存键到链表迭代器的映射。链表头表示最近使用，尾部表示最久未用。查询命中时用 splice 将节点移到头部。

开发中的做法

插入时先判断键是否存在，已有节点只需更新值并移动位置。容量满时从尾部取得要淘汰的键，同时更新哈希表和链表。

验证与追问

面试时主动检查容量为零、覆盖旧键和重复读取。复杂度应说明哈希查找是平均 O(1)，并讨论多线程下如何保护两份结构的一致性。

代码片段

items.splice(items.begin(), items, found->second);