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

全文目录：

- 开篇语
- 前言
- 1. LinkedHashMap 简介
- - 1.1 LinkedHashMap 的构造方法
- 2. 基于 LinkedHashMap 实现 LRU 缓存
- - 2.1 设计思路
  - 2.2 实现步骤
  - 2.3 代码说明
  - 2.4 测试案例
  - 2.5 解释
- 3. LRU 缓存优化
- - 3.1 `removeEldestEntry()` 方法的灵活性
  - 3.2 内存管理
- 4. 总结
- 文末

开篇语

哈喽，各位小伙伴们，你们好呀，我是喵手。运营社区：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 设计思路

缓存大小限制：我们需要为缓存设定一个最大容量 capacity，当缓存容量超过该值时，我们就需要淘汰最久未使用的元素。
LRU 淘汰规则：在每次插入或访问元素时，我们将该元素移动到链表的末尾，这样链表的头部始终保存着最久未使用的元素。当缓存容量超过限制时，我们可以直接删除链表头部的元素。
使用 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;// 构造函数，初始化容量和 accessOrderpublic LRUCache(int capacity) {super(capacity, 0.75f, true);  // 第三个参数 true 表示按访问顺序排序this.capacity = capacity;}// 重写 removeEldestEntry 方法，当缓存容量超出时，移除最久未使用的条目@Overrideprotected 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}// 访问元素 1cache.get(1); // 使元素 1 最近访问// 插入新的元素，此时缓存超过容量，元素 2 将被移除cache.put(4, "D");// 打印缓存内容System.out.println(cache); // 输出: {3=C, 1=A, 4=D}}
}