Meta 手写LRU Cache：双链表、更新与零容量

题目重点：用哈希表和双向链表实现get/put，维护最近使用次序和容量边界。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

capacity非负整数；get命中与put已有键都刷新最近使用，缺失返回None，因此值不允许None。没有TTL、按权重容量或线程安全保证。
链表头是最久未用、尾是最近使用；head/tail哨兵不计容量。

解题路线

map[key]直接定位Node，Node含key/value/prev/next；get摘下节点并接到tail前，无需扫描。节点保留key，淘汰时可以从map删除对应键。
put已有键只更新value并刷新，不创建第二个节点或增加容量。新键创建节点后若超容量，移除head.next并删map。capacity0不缓存任何项，get总缺失。
两个不变量：map恰好对应真实链表节点；所有真实节点正向/反向链接一致。_remove与_recent封装固定指针写入，减少分支并避免头尾特殊情况。
复杂度均摊O(1)依赖哈希查找平均性能，链表操作固定次指针更新。不能使用普通list.remove或dict遍历最旧项后仍称O(1)。
并发get也会改链表，需要整次操作互斥或专门并发设计。锁范围涵盖map和链表，只有map加锁会让两个get同时摘同节点损坏结构。TTL过期与LRU淘汰是不同策略，可在此结构外增加到期索引。

手动走一遍

容量2：put(a,1)、put(b,2)顺序[a,b]；get(a)变[b,a]；put(c,3)淘汰b。put(a,4)不增加节点，只刷新a；capacity0时put任意值后仍空。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

class Node:
    def __init__(self,key=None,value=None):
        self.key=key;self.value=value;self.prev=None;self.next=None

class LRUCache:
    """Nonnegative capacity; missing -> None, values not None; no thread safety."""
    def __init__(self,capacity):
        if capacity<0:raise ValueError('negative capacity')
        self.capacity=capacity;self.items={};self.head=Node();self.tail=Node()
        self.head.next=self.tail;self.tail.prev=self.head

    def _remove(self,node):
        node.prev.next=node.next;node.next.prev=node.prev

    def _recent(self,node):
        node.prev=self.tail.prev;node.next=self.tail
        self.tail.prev.next=node;self.tail.prev=node

    def get(self,key):
        node=self.items.get(key)
        if node is None:return None
        self._remove(node);self._recent(node);return node.value

    def put(self,key,value):
        if value is None:raise ValueError('None reserved for missing')
        if self.capacity==0:return
        node=self.items.get(key)
        if node is not None:
            node.value=value;self._remove(node);self._recent(node);return
        node=Node(key,value);self.items[key]=node;self._recent(node)
        if len(self.items)>self.capacity:
            victim=self.head.next;self._remove(victim);del self.items[victim.key]

复杂度

get/put均摊O(1)，空间O(capacity)。Thread-safe版本一次全局锁序列化，吞吐不是自动O(1)无竞争；按字节权重缓存需一个put可能淘汰多个节点，应算摊销。

易错点与追问

容易失分的边界

更新已有键另创建节点会留下孤立旧节点，map/链表不一致。
get缺失也刷新或put相同值不刷新，违背既定规则。

继续深挖

LRU与LFU的淘汰依据如何不同？频繁扫描大量一次性键会怎样污染LRU？
配置服务中LRU怎样与version/TTL配合？淘汰策略本身不保证新鲜度。