如何实现 LRU 缓存：基于LinkedHashMap？

开篇语

哈喽，各位小伙伴们，你们好呀，我是喵手。运营社区：C站/掘金/腾讯云/阿里云/华为云/51CTO；欢迎大家常来逛逛

  今天我要给大家分享一些自己日常学习到的一些知识点，并以文字的形式跟大家一起交流，互相学习，一个人虽可以走的更快，但一群人可以走的更远。

  我是一名后端开发爱好者，工作日常接触到最多的就是Java语言啦，所以我都尽量抽业余时间把自己所学到所会的，通过文章的形式进行输出，希望以这种方式帮助到更多的初学者或者想入门的小伙伴们，同时也能对自己的技术进行沉淀，加以复盘，查缺补漏。

小伙伴们在批阅的过程中，如果觉得文章不错，欢迎点赞、收藏、关注哦。三连即是对作者我写作道路上最好的鼓励与支持！

前言

在很多实际的应用中，尤其是需要缓存数据的场景下，我们经常会遇到 LRU（Least Recently Used，最近最少使用）缓存。LRU 缓存是通过淘汰最久未使用的缓存数据来节省内存空间。对于高效的 LRU 缓存，我们不仅要保证快速的查找、插入和删除操作，还要能够快速地淘汰最久未使用的元素。

在 Java 中，基于 LinkedHashMap 实现 LRU 缓存是非常简便和高效的，因为 LinkedHashMap 本身提供了按照访问顺序迭代的能力，我们可以利用这一特性轻松实现 LRU 缓存。

---

1. LinkedHashMap 简介

LinkedHashMap 是 HashMap 的一个子类，它基于哈希表实现，并且维护了插入顺序或访问顺序。这使得 LinkedHashMap 特别适合于实现缓存，尤其是在需要按访问顺序迭代时。

1.1 LinkedHashMap 的构造方法

• LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder):
  • initialCapacity：初始容量。
  • loadFactor：负载因子。
  • accessOrder：如果设置为 true，则按照访问顺序排序；如果设置为 false，则按照插入顺序排序。

当 accessOrder 设置为 true 时，LinkedHashMap 会在每次访问（get 或 put 操作）时，将访问的元素移动到链表的末尾。这个特性让我们能够轻松地实现 LRU 缓存。

---

2. 基于 LinkedHashMap 实现 LRU 缓存

2.1 设计思路

1. 缓存大小限制：我们需要为缓存设定一个最大容量 capacity，当缓存容量超过该值时，我们就需要淘汰最久未使用的元素。
2. LRU 淘汰规则：在每次插入或访问元素时，我们将该元素移动到链表的末尾，这样链表的头部始终保存着最久未使用的元素。当缓存容量超过限制时，我们可以直接删除链表头部的元素。
3. 使用 LinkedHashMap：利用 LinkedHashMap 中 accessOrder 的特性，结合 removeEldestEntry() 方法来自动删除最久未使用的元素。

2.2 实现步骤

我们可以创建一个继承自 LinkedHashMap 的类，并重写 removeEldestEntry() 方法，该方法会在每次插入新元素时被调用。

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    // 构造函数，初始化容量和 accessOrder
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);  // 第三个参数 true 表示按访问顺序排序
        this.capacity = capacity;
    }

    // 重写 removeEldestEntry 方法，当缓存容量超出时，移除最久未使用的条目
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    // 获取缓存中的值
    public V get(K key) {
        return super.getOrDefault(key, null);
    }

    // 插入缓存值
    public void put(K key, V value) {
        super.put(key, value);
    }
}

2.3 代码说明

• LRUCache 类继承自 LinkedHashMap，并通过构造函数设置了 accessOrder 为 true，这使得每次访问元素时，该元素都会被移到链表的末尾。
• removeEldestEntry() 方法会在每次插入新元素时检查缓存的大小。如果缓存的大小超过了设定的容量，它会返回 true，从而自动移除最久未使用的元素。
• get(K key) 和 put(K key, V value) 方法分别用于获取和插入缓存中的数据。

2.4 测试案例

public class Main {
    public static void main(String[] args) {
        // 创建一个容量为 3 的 LRU 缓存
        LRUCache<Integer, String> cache = new LRUCache<>(3);

        // 向缓存中插入数据
        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");

        // 打印缓存内容
        System.out.println(cache); // 输出: {1=A, 2=B, 3=C}

        // 访问元素 1
        cache.get(1); // 使元素 1 最近访问

        // 插入新的元素，此时缓存超过容量，元素 2 将被移除
        cache.put(4, "D");

        // 打印缓存内容
        System.out.println(cache); // 输出: {3=C, 1=A, 4=D}
    }
}

输出：

{1=A, 2=B, 3=C}
{3=C, 1=A, 4=D}

2.5 解释

1. 初始时，缓存的容量为 3，元素 {1=A, 2=B, 3=C} 被插入缓存。
2. 当访问 get(1) 时，元素 1 被移动到链表的末尾。
3. 当插入元素 4=D 时，由于缓存已经满了，元素 2（最久未访问）被自动删除，最终缓存内容为 {3=C, 1=A, 4=D}。

---

3. LRU 缓存优化

3.1 removeEldestEntry() 方法的灵活性

通过 removeEldestEntry() 方法，我们可以根据不同的需求定制缓存的淘汰规则。例如，我们可以根据某些条件（如元素的大小、元素的过期时间等）来决定是否删除最久未使用的元素。

3.2 内存管理

虽然 LinkedHashMap 的 accessOrder 特性和 removeEldestEntry() 方法让我们能够很方便地实现 LRU 缓存，但也需要注意缓存大小和内存使用的平衡。特别是当缓存需要存储大量数据时，合理设置缓存容量和定期清理缓存非常重要。

---

4. 总结

• 使用 LinkedHashMap 实现 LRU 缓存的方式简洁高效，特别适合需要按访问顺序管理缓存数据的场景。
• 通过重写 removeEldestEntry() 方法，我们能够在缓存超出容量时自动移除最久未使用的元素。
• 这种方法不仅具有较高的性能，还能避免重复的复杂操作，方便开发者实现高效的缓存管理。

LRU 缓存的实现，帮助我们在高效处理数据时保持内存的合理使用，避免内存溢出或缓存过期问题的出现。

… …

文末

好啦，以上就是我这期的全部内容，如果有任何疑问，欢迎下方留言哦，咱们下期见。

… …

学习不分先后，知识不分多少；事无巨细，当以虚心求教；三人行，必有我师焉！！！

wished for you successed ！！！

---

⭐️若喜欢我，就请关注我叭。

⭐️若对您有用，就请点赞叭。
⭐️若有疑问，就请评论留言告诉我叭。

---

版权声明：本文由作者原创，转载请注明出处，谢谢支持！