算法搭积木：一起来拼装 LRU！！！

⭐️前言

读完这篇文章，你不仅学到算法套路，还可以顺手解决如下题目：

146. LRU缓存（中等）

LRU 缓存机制（Least Recently Used Cache）是力扣（LeetCode）上一道非常重要的题目，在技术面试中具有很高的出现频率。它结合了链表的插入删除操作和哈希表的快速查找特性。LRU 缓存问题是许多软件公司 （小中大厂均有所涉猎） 面试中的经典题目，几乎每一位软件工程师都可能在面试过程中遇到。

⭐️LRU解释

LRU算法是一种常用的缓存淘汰策略。它的基本思想很简单：当缓存满了，需要腾出空间时，淘汰最久没有使用的那条数据。尽管原理容易理解，但在面试中写出没有Bug的LRU算法需要一些技巧，需要对底层的数据结构进行细致的拆解和实现。接下来，我会用更清晰、简洁的方式带你一步步手写一个易于理解的 LRU 缓存代码。

🍎场景设定

假设你有一部智能手机，它有 4 个可用的后台应用程序槽位（即缓存容量为 4）。这意味着手机最多可以同时保存 4 个最近使用的应用程序在内存中，以便快速切换。

🍊LRU 工作原理

1. 初始状态：打开微信。
   缓存：[微信]
2. 打开浏览器：
   缓存：[微信, 浏览器]
3. 打开音乐播放器：
   缓存：[微信, 浏览器, 音乐播放器]
4. 打开照片：
   缓存：[微信, 浏览器, 音乐播放器, 照片]
   此时，我们的缓存已满，容量为 4。
5. 打开地图：
   根据 LRU 算法，我们需要移除最近最少使用的应用程序，也就是最久未使用的应用程序。在当前缓存中，最久未使用的是微信。
   新的缓存：[浏览器, 音乐播放器, 照片, 地图]
6. 打开视频播放器：
   再次根据 LRU 算法，我们需要移除最久未使用的应用程序，这次是最久未使用的浏览器。
   新的缓存：[音乐播放器, 照片, 地图, 视频播放器]

说明
在这个例子中，每当打开一个新的应用程序时，如果缓存已满，就会移除最久未使用（即最近最少使用）的应用程序，以腾出空间。

关键点

• 访问顺序：新添加的应用程序总是放在缓存的末尾。
• 更新规则：如果再次访问一个已经存在于缓存中的应用程序，那么该应用程序会被移动到缓存的末尾。
• 移除规则：当缓存满时，移除最前面的应用程序，因为它是最久未使用的。

⭐️力扣题目描述

力扣第146题“LRU缓存”要求我们设计一个缓存系统，接收一个参数 capacity 作为缓存的最大容量，并实现两个核心方法：put(key, val) 和 get(key)。put(key, val) 用来存储键值对，而 get(key) 用来获取对应键的值，如果 key 不存在，返回 -1。

关键在于这两个操作的时间复杂度必须是 O(1)，也就是说无论缓存中有多少数据，操作都要在恒定时间内完成。
接下来通过一个例子来解释 LRU 缓存的具体工作机制。

public static void main(String[] args) {
    // 创建一个容量为3的LRUCache实例
    LRUCache<String, String> cache = new LRUCache<>(3);

    // 向缓存中添加第一个键值对 ("one", "1")
    cache.put("one", "1");
    // 向缓存中添加第二个键值对 ("two", "2")
    cache.put("two", "2");
    // 向缓存中添加第三个键值对 ("three", "3")
    cache.put("three", "3");
    
    // 当添加第四个键值对 ("four", "4") 时，由于缓存已满
    // LRUCache将移除最近最少使用的键值对 "one"
    cache.put("four", "4"); // 此时 "one" 将被移除

    // 获取键 "two" 的值，这将更新 "two" 的使用顺序
    // "two" 现在是最近使用的元素
    cache.get("two"); // 更新 "two" 的位置
    
    // 添加第五个键值对 ("five", "5")
    // 此时缓存将移除最近最少使用的键值对 "three"
    cache.put("five", "5"); // 此时 "three" 将被移除
}

👊LRU算法设计

为了让 put 和 get 方法的时间复杂度达到 O(1)，我们可以归纳出实现 cache 所需的关键条件：

1. cache 中的元素需要按访问顺序排列，以便区分最近使用的和最久未使用的数据。当缓存达到最大容量时，最久未使用的元素必须被移除，给新的数据腾出空间。
2. 我们需要能够快速查找 key，并获取对应的 val。
3. 每次访问 cache 中的某个 key 时，必须将该元素标记为“最近使用的”，也就是说，数据结构要支持在任意位置快速插入和删除元素。

这时候问题来了：什么样的数据结构可以同时满足这些条件呢？哈希表可以快速查找，但无法维持元素的顺序；链表有顺序，可以快速插入和删除，但查找速度慢。结合这两者，我们可以使用一种称为 LinkedHashMap 的数据结构，它结合了哈希表的快速查找和链表的有序性。

LRU缓存算法的核心数据结构就是哈希链表，它是双向链表和哈希表的结合体。这个数据结构长这样：

☘️哈希表+双向链表实现LRU算法

许多编程语言都提供了内置的哈希链表或类似 LRU 功能的库函数，不过为了帮助大家更好地理解这个算法的细节，我们先从头手动实现一次 LRU 算法。完成后，我们再使用 Java 内置的 LinkedHashMap 来实现一遍，这样你可以清楚地看到两种方法的异同。

1. 首先要把双链表的节点类结构写出来

class Node {
	// 至于为什么要存储key和val，而不只是存储val，见后文
	public int key , val;
	// 为什么是双向链表呢？单链表不行吗？同样见后文
	public Node next , prev;
	public Node(int k, int v){
		this.key = k;
		this.val = v;
	}
}

2. 构建双链表并实现几个LRU算法必需的API

class DoubleList {
    private Node head, 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++;
    }

    // 删除双链表中的x节点
    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;
    }

}

有些人可能会问：“为什么一定要用双向链表？单向链表不行吗？”

其实，看完代码逻辑后你就会明白，我们需要实现删除操作，而删除某个节点时，不仅要获取这个节点本身，还需要能够操作它的前一个节点。双向链表可以直接找到前驱节点，这样才能 确保删除操作的时间复杂度为 O(1)，而单向链表做不到这一点。

注意：我们每次默认从链表尾部添加元素，那么显然越靠近尾部的元素越是最近使用的，越靠近头部的元素是越久未使用的。

有了双向链表的实现，只需在LRU算法中把它和哈希表结合起来即可。

class LRUCache{
    private HashMap<Integer,Node> map;
    private DoubleList cache;
    private int cap;
    
    public LRUCache(int capacity){
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
}

写到这里，我们暂时不急着实现 LRU 算法的 get 和 put 方法。因为我们需要同时维护一个双向链表 cache 和一个哈希表 map，在操作中可能会不小心遗漏一些步骤。比如，当删除某个 key 时，可能我们在 cache 中删除了对应的 Node，但却忘记在 map 中删除这个 key。

3. 封装双链表和哈希表

解决这个问题最有效的办法就是在这两种数据结构之上提供一层抽象API。

    // 将某个key提升为最近使用的
    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 x = cache.removeFirst();
        int deleteKey = x.key;
        map.remove(deleteKey);
    }

写到这里呢也就知道了前面为什么要在链表中 同时存储key和val，而不只是存储val了。 我们要在removeLeastRecently函数中，需要用x得到deleteKey。也就是说当缓存容量已满，不仅要删除最后一个Node节点，还要把map中映射到该节点的key同时删除，而这个key只能由Node得到。

4. 实现get方法

public int get(int key) {
    if (!map.containsKey(key)) {
        return -1;
    }
    makeRecently(key);
    return map.get(key).val;
}

5. 实现put方法

put方法稍微有点复杂，但思路也很清晰：

public void put(int key, int val) {
    // 有相同的key先删除再添加到末尾，这就包含了makeRecently方法了
    if (map.containsKey(key)) {
        deleteKey(key);
        addRecently(key, val);
        return;
    }

    // 没有相同的key时先判断容量！！！
    if (cap == cache.size()) {
        removeLeastRecently();
    }

    addRecently(key, val);
}

至此你已经完全掌握了LRU算法的原理和实现了。

☘️LinkedHashMap实现LRU算法

最后用Java的内置类型LinkedHashMap来实现LRU算法，逻辑和之前完全一致，这里就不过多解释了：

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}

super(capacity, 0.75F, true) 调用了 LinkedHashMap 的构造函数，其中：

• capacity：初始容量。
• 0.75F：负载因子（决定何时扩展哈希表）。默认值通常为 0.75。
• true：表示按照访问顺序排列条目，这样每次访问（get 或 put）时，条目的顺序都会更新，以便最近使用的条目排在最前，最久未使用的条目排在最后。

removeEldestEntry 方法是 LinkedHashMap 提供的一个钩子方法，用于在每次插入新条目时决定是否需要移除最旧的条目。
当缓存中的条目数量超过 capacity 时，removeEldestEntry 会返回 true，移除最旧的条目（即最久未使用的条目）。这样保证缓存始终遵循 LRU 规则。

✍️总结

在实现 LRU 算法的过程中，我们不仅掌握了如何设计高效的缓存机制，还体验了一次数据结构之间的“跨界合作”。通过结合哈希表和双向链表的优势，我们成功构建了一个能够快速访问和管理数据的缓存系统。

这段代码的旅程如同一场精彩的舞蹈，哈希表在前，引领着我们快速找到每个元素，而双向链表则在后，优雅地处理着元素的顺序与淘汰。每次访问都如同跳过一段旋律，更新着数据的使用频率，确保最近使用的数据总是处于舞台中央。

最重要的是，这次实现让我们理解了高效算法背后的思维方式——在性能和可维护性之间找到平衡。无论是手动实现还是利用 Java 内置的 LinkedHashMap，我们都为自己的编程工具箱增添了一把利器。

在日常编码中，记得保持敏锐的思维和对细节的关注，正如这次 LRU 算法的实现所启示我们的那样。未来的编程之路，期待与更多有趣的挑战相遇！