LRU 缓存机制

很多人第一次学 LRU 的时候都会觉得：

“不就是删掉最久没用的数据吗？”

结果真正开始手写：

put()
get()
删除节点
移动节点
更新 map
维护顺序

写着写着：

链表断了
map 没删
节点丢了
时间复杂度炸了

最后人也快没了。

所以这篇文章，我们不搞那种“背模板式讲解”，而是真正从思维逻辑出发，把 LRU 一次性彻底讲懂。

---

一、LRU 到底是什么？

LRU 全称：

Least Recently Used
最近最少使用

简单来说就是：

谁最久没被使用，谁就先被淘汰

---

举个真实场景

假设你手机后台现在开着：

微信 -> 网易云 -> 设置

这里规定：

左边 = 最久没使用
右边 = 最近刚使用

这时候你点了一下微信。

后台顺序立马变成：

网易云 -> 设置 -> 微信

因为：

微信刚被访问
所以它现在是“最近使用”

---

接着：

你又打开了 B站。

但系统最多只能挂 3 个应用。

这时候怎么办？

系统会直接：

踢掉 网易云

因为：

它已经最久没被使用了

最后变成：

设置 -> 微信 -> B站

这其实就是：

LRU 的核心思想

---

二、为什么 LRU 难写？

因为题目要求：

get 和 put 的时间复杂度必须是 O(1)

这就意味着：

不能遍历
不能排序
不能暴力删除

普通数据结构很难同时满足：

• 快速查找

• 维护访问顺序

• 快速插入删除

比如：

---

数组

查找慢：

O(n)

删除也慢：

后面元素全得移动

---

普通链表

虽然插入删除快。

但：

查找节点还是 O(n)

---

HashMap

查找确实快：

O(1)

但问题是：

它没有顺序

根本不知道：

谁最近访问
谁最久没访问

---

所以：

单个数据结构根本解决不了 LRU

于是经典组合就出现了：

HashMap + 双向链表

---

三、整体结构长什么样？

整体结构其实不复杂：

HashMap<Integer, Node>

负责：

O(1) 查找节点

同时：

DoubleLinkedList

负责：

维护访问顺序

---

整体结构如下：

map:

1 -> node1
2 -> node2
3 -> node3


链表:

head <-> 1 <-> 2 <-> 3 <-> tail

这里规定：

越靠近 tail
说明越新

也就是说：

head 后面：
最久未使用

tail 前面：
最近刚使用

---

四、为什么必须是双向链表？

很多人第一反应：

单链表不行吗？

其实不行。

因为：

LRU 需要频繁删除节点

而删除节点的时候：

必须找到它前面的节点

单链表删除：

需要遍历找前驱
时间复杂度 O(n)

直接废掉。

但双向链表：

node.prev

直接拿到前驱节点。

删除复杂度：

O(1)

---

五、为什么 Node 必须存 key？

这个地方很多人第一次都会踩坑。

很多人会写：

class Node{
    int val;
}

然后删除最旧节点的时候：

链表删掉了

但问题来了：

map 怎么删？

因为：

你根本不知道这个节点对应哪个 key

所以：

Node 必须同时保存 key 和 value

---

六、定义节点

先定义双向链表节点：

class Node{

    int key;
    int val;

    Node prev;
    Node next;

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

结构大概长这样：

┌──────────────┐
│ key = 1      │
│ val = 100    │
│ prev         │
│ next         │
└──────────────┘

---

七、实现双向链表

这里使用：

虚拟头尾节点

原因很简单：

不用处理各种 null 边界

代码会稳定很多。

---

链表结构：

head <-> node1 <-> node2 <-> tail

---

代码如下：

class DoubleList{

    private Node head;
    private Node tail;

    private int size;

    public DoubleList(){

        head = new Node(0,0);
        tail = new Node(0,0);

        head.next = tail;
        tail.prev = head;

        size = 0;
    }

    // 尾插
    public void addLast(Node x){

        x.prev = tail.prev;
        x.next = tail;

        tail.prev.next = x;
        tail.prev = x;

        size++;
    }

    // 删除节点
    public void remove(Node x){

        x.prev.next = x.next;
        x.next.prev = x.prev;

        size--;
    }

    // 删除最旧节点
    public Node removeFirst(){

        if(head.next == tail){
            return null;
        }

        Node first = head.next;

        remove(first);

        return first;
    }

    // 获取链表大小
    public int size(){
        return size;
    }
}

---

八、开始实现 LRU

整体结构：

class LRUCache {

    // key -> Node
    private HashMap<Integer,Node> map;

    // 双向链表
    private DoubleList cache;

    // 容量
    private int cap;

    public LRUCache(int capacity){

        this.cap = capacity;

        map = new HashMap<>();

        cache = new DoubleList();
    }
}

---

九、先封装核心操作

真正容易出 bug 的地方：

其实不是 get 和 put。

而是：

map 和链表的同步操作

所以：

一定要先抽象 API

---

1. 提升为最近使用

本质：

删除节点
重新插入尾部

图示：

---

原来：

head <-> 1 <-> 2 <-> 3 <-> tail

访问 2 后：

head <-> 1 <-> 3 <-> 2 <-> tail

---

代码：

private void makeRecently(int key){

    Node x = map.get(key);

    cache.remove(x);

    cache.addLast(x);
}

---

2. 添加最近使用元素

private void addRecently(int key,int val){

    Node x = new Node(key,val);

    cache.addLast(x);

    map.put(key,x);
}

---

3. 删除某个 key

private void deleteKey(int key){

    Node x = map.get(key);

    cache.remove(x);

    map.remove(key);
}

---

4. 删除最久未使用元素

图示：

head <-> 1 <-> 2 <-> 3 <-> tail
         ↑
      删除这里

代码：

private void removeLeastRecently(){

    Node deletedNode = cache.removeFirst();

    int deletedKey = deletedNode.key;

    map.remove(deletedKey);
}

---

十、实现 get()

逻辑非常简单：

存在：
返回 value
并提升为最近使用

不存在：
返回 -1

代码：

public int get(int key){

    if(!map.containsKey(key)){
        return -1;
    }

    makeRecently(key);

    return map.get(key).val;
}

---

十一、实现 put()

put 分两种情况。

---

情况一：key 已存在

这时候：

更新 value
并移动到最近使用位置

---

情况二：key 不存在

如果容量已满：

删除最久未使用节点

然后插入新节点。

---

图示：

插入前：

head <-> 1 <-> 2 <-> tail

容量满。

---

插入 3：

先删除：

1

变成：

head <-> 2 <-> tail

再插入：

head <-> 2 <-> 3 <-> tail

---

代码：

public void put(int key,int val){

    // key 已存在
    if(map.containsKey(key)){

        deleteKey(key);

        addRecently(key,val);

        return;
    }

    // 容量满了
    if(cap == cache.size()){

        removeLeastRecently();
    }

    // 插入新节点
    addRecently(key,val);
}

---

十二、完整代码

import java.util.HashMap;

// 双向链表节点
class Node{

    int key;
    int val;

    Node prev;
    Node next;

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


// 双向链表
class DoubleList{

    private Node head;
    private Node tail;

    private int size;

    public DoubleList(){

        head = new Node(0,0);
        tail = new Node(0,0);

        head.next = tail;
        tail.prev = head;

        size = 0;
    }

    // 尾插
    public void addLast(Node x){

        x.prev = tail.prev;
        x.next = tail;

        tail.prev.next = x;
        tail.prev = x;

        size++;
    }

    // 删除节点
    public void remove(Node x){

        x.prev.next = x.next;
        x.next.prev = x.prev;

        size--;
    }

    // 删除最旧节点
    public Node removeFirst(){

        if(head.next == tail){
            return null;
        }

        Node first = head.next;

        remove(first);

        return first;
    }

    // 返回链表大小
    public int size(){
        return size;
    }
}



public class LRUCache {

    // key -> Node
    private HashMap<Integer,Node> map;

    // 双向链表
    private DoubleList cache;

    // 容量
    private int cap;

    public LRUCache(int capacity){

        this.cap = capacity;

        map = new HashMap<>();

        cache = new DoubleList();
    }


    // 获取数据
    public int get(int key){

        if(!map.containsKey(key)){
            return -1;
        }

        // 提升为最近使用
        makeRecently(key);

        return map.get(key).val;
    }


    // 插入数据
    public void put(int key,int val){

        // key 已存在
        if(map.containsKey(key)){

            deleteKey(key);

            addRecently(key,val);

            return;
        }

        // 容量满了
        if(cap == cache.size()){

            removeLeastRecently();
        }

        addRecently(key,val);
    }


    // 提升为最近使用
    private void makeRecently(int key){

        Node x = map.get(key);

        cache.remove(x);

        cache.addLast(x);
    }


    // 添加最近使用元素
    private void addRecently(int key,int val){

        Node x = new Node(key,val);

        cache.addLast(x);

        map.put(key,x);
    }


    // 删除某个 key
    private void deleteKey(int key){

        Node x = map.get(key);

        cache.remove(x);

        map.remove(key);
    }


    // 删除最久未使用元素
    private void removeLeastRecently(){

        Node deletedNode = cache.removeFirst();

        int deletedKey = deletedNode.key;

        map.remove(deletedKey);
    }
}

---

十三、时间复杂度分析

因为：

HashMap 查找 O(1)
双向链表删除 O(1)
双向链表插入 O(1)

所以：

操作	时间复杂度
get	O(1)
put	O(1)

---

十四、总结

LRU 的核心其实只有一句话：

HashMap 负责查找，双向链表负责顺序

其中：

最近访问：
移动到尾部

最久未访问：
删除头部

本质上：

LRU 是典型的“用空间换时间”

也是缓存设计里最经典的一种思想。