LRU 缓存：哈希表与双向链表的组合设计

这篇来自我补“LRU 缓存：哈希表与双向链表的组合设计”基础时的一次复盘。我之前的问题是：LRU 是我第一次明显感受到组合数据结构价值的地方：单独的哈希表和链表都不够，放在一起刚好补上彼此短板。等我把输入、状态变化和边界条件分别写出来之后，原来看似突然出现的规则就有了来路。

LRU 是 Least Recently Used，意思是淘汰最近最少使用的数据。它不是一个单独的基础数据结构，而是哈希表和双向链表组合出来的工程结构。

它从哪里来

LRU 来自内存与缓存容量有限时的页面置换研究。局部性原理说明最近访问过的数据往往还会被再次访问，于是“淘汰最久未使用者”成为自然策略。工程实现后来稳定为哈希表负责定位、双向链表负责维护新旧顺序。

LRU 的核心设计

LRU 缓存结构

图：哈希表负责 O(1) 查找，双向链表负责 O(1) 移动和淘汰

LRU 要同时满足两个目标：

get(key) 能快速找到缓存值。
每次访问后，能把该元素移动到最近使用位置。
容量满时，能快速删除最久未使用元素。

单独使用数组、链表或哈希表都不够。

为什么是哈希表 + 双向链表

结构	能力	不足
哈希表	快速查找 key	不维护访问顺序
单向链表	能维护顺序	删除中间节点需要前驱
双向链表	快速移动和删除节点	不能按 key 快速定位

所以 LRU 使用：

HashMap<K, Node>：根据 key 找节点。
DoublyLinkedList：从头到尾表示新到旧。

基础实现

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0);
    private final Node tail = new Node(0, 0);

    LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToHead(node);
        return node.value;
    }

    void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
            return;
        }
        Node created = new Node(key, value);
        map.put(key, created);
        addAfterHead(created);
        if (map.size() > capacity) {
            Node removed = removeTail();
            map.remove(removed.key);
        }
    }
}

节点结构：

class Node {
    int key;
    int value;
    Node prev;
    Node next;

    Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

链表操作：

void remove(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

void addAfterHead(Node node) {
    node.next = head.next;
    node.prev = head;
    head.next.prev = node;
    head.next = node;
}

void moveToHead(Node node) {
    remove(node);
    addAfterHead(node);
}

Node removeTail() {
    Node node = tail.prev;
    remove(node);
    return node;
}

虚拟头尾节点能减少空链表、头节点、尾节点的边界判断。

工程场景

LRU 常用于：

本地热点数据缓存。
图片、页面、接口结果缓存。
数据库连接或对象池的闲置淘汰。
浏览器缓存和操作系统页面置换思想。

真实工程里还要考虑：

并发安全。
过期时间 TTL。
最大内存而不是最大条数。
缓存击穿、穿透、雪崩。
分布式缓存的一致性。

我的分析

LRU 是学习“组合数据结构”的经典例子。它提醒我们：真实业务里很少只靠一个结构解决问题。哈希表提供定位能力，链表提供顺序维护能力，两个组合后才满足 O(1) 查询、移动、淘汰。

面试题

LRU 为什么需要双向链表？
哈希表中为什么要保存节点，而不是只保存值？
虚拟头尾节点解决了什么边界问题？
LRU 的 get 操作为什么也要移动节点？
工程中的缓存淘汰只用 LRU 够不够？