LRU 缓存：链表与哈希的完美联姻

缓存容量有限，满了该踢谁？LRU（最近最少使用）的策略是：优先淘汰"最久没被访问"的那条。要实现 O(1) 的查找、插入、淘汰，单靠一种结构都不行。

哈希表 alone 不行。哈希表能 O(1) 找到 key，但它不记录"谁最久没用"，踢人时只能瞎踢。

双向链表 alone 也不行。链表能按访问顺序排布、摘除某节点 O(1)，但"给定 key 找到对应节点"要 O(n) 遍历。

两者结合，刚刚好。用哈希表把 key 映射到链表中的节点（O(1) 查找）；用双向链表维护访问顺序：最近访问的节点移到链表一端（代表"新"），最久未访问的自然落在另一端（代表"旧"）。容量满时，直接摘下"旧"端节点并从哈希表删除，O(1) 完成淘汰。命中时，也是 O(1) 摘除再插到"新"端。

这正是 LinkedHashMap（Java）、Redis 的近似 LRU、以及无数缓存系统的底层骨架。链表在这里扮演的角色，是"把顺序这件事变得可以 O(1) 维护"——没有它，LRU 就退化成 O(n)。

图：哈希负责秒查，双向链表负责维护访问顺序

参考代码（Python）

哈希表负责 O(1) 查找，双向链表负责 O(1) 维护访问顺序与淘汰。

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

class LRUCache:
    def __init__(self, cap):
        self.cap=cap; self.cache={}
        self.head=Node(0,0); self.tail=Node(0,0)
        self.head.next=self.tail; self.tail.prev=self.head
    def _remove(self, n):
        n.prev.next=n.next; n.next.prev=n.prev
    def _add(self, n):           # 插到"最近使用"端
        n.prev=self.head; n.next=self.head.next
        self.head.next.prev=n; self.head.next=n
    def get(self, key):
        if key not in self.cache: return -1
        n=self.cache[key]; self._remove(n); self._add(n)
        return n.val
    def put(self, key, val):
        if key in self.cache: self._remove(self.cache[key])
        n=Node(key,val); self._add(n); self.cache[key]=n
        if len(self.cache)>self.cap:
            lru=self.tail.prev; self._remove(lru); del self.cache[lru.key]

关联推荐

• 算法与问题求解入门 — 理解"用对数据结构，复杂度天差地别"
• 哈希表：为什么 Redis、Python 字典都靠它"秒查" — LRU 的另一半功臣
• 算法通关训练营·排序篇 — 系统补齐算法与结构基础