---

一、什么是LRU？

LRU是Least Recently Used的缩写，意为最近最少使用。它是一种缓存淘汰策略，用于在缓存满时确定要被替换的数据块。LRU算法认为，最近被访问的数据在将来被访问的概率更高，因此它会优先淘汰最近最少被使用的数据块，以给新的数据块腾出空间。

如图所示：

1. 先来3个元素进入该队列
   

2. 此时来了新的元素，因为此时队列中每个元素的使用的次数都相同（都是1），所以会按照LFU的策略淘汰（即淘汰掉最老的那个）
   

3. 此时又来了新的元素，而且是队列是已经存在的，就会将该元素调整为最新的位置。
   

4. 如果此时又来了新的元素，还是”咯咯“，由于”咯咯“已经处于最新的位置，所以大家位置都不变。
   

5. 同理，一直进行上述的循环

---

二、LinkedHashMap 实现LRU缓存

以力扣的算法题为例子：

---

力扣146. LRU 缓存

---

在 jdk 官方的介绍中可以看出，该数据结构天生适合实现 LRU。

代码示例一：

/*** 利用继承 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);}@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {// 重写比较方法return super.size() > capacity;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

代码示例二：

/*** 利用 LinkedHashMap 特点的方式实现LRU缓存*/class LRUCache {// 额定容量private final int CAPACITY;// 使用 LinkedHashMap 的有序排重特点达到要求private final Map<Integer, Integer> map;public LRUCache(int capacity) {// 初始化CAPACITY = capacity;map = new LinkedHashMap<>(CAPACITY);}public int get(int key) {Integer value = map.get(key);if (value != null) {// 存在// 1. 先删除旧的map.remove(key);// 2. 再添加回去，同时更新了 key 的位置和 valuemap.put(key, value);// 3. 返回结果return value;} else {// 不存在return -1;}}public void put(int key, int value) {if (map.size() == CAPACITY) {// 达到最大容量if (!map.containsKey(key)) {// 不存在，就删除头Integer head = map.keySet().iterator().next();map.remove(head);} else {// 存在，就删除自身map.remove(key);}} else {// 还有剩余空间，删除自身map.remove(key);}// 添加新的或 key 更新后的 valuemap.put(key, value);}
}

---

三、手写LRU

代码示例如下：

/*** https://leetcode.cn/problems/lru-cache/description/* 手写 LRU 缓存* Map + 双向链表*/
class LRUCache {// Map 负责查找，构建一个虚拟的双向链表，它里面安装的就是一个个 Node 节点，作为数据载体。// 参考 HashMap 中的存储方式，使用内部 Node 维护双向链表// 1. 构造 Node 节点作为数据载体public static class Node<K, V> {public K key;public V value;public Node<K, V> prev;public Node<K, V> next;public Node() {this.prev = this.next = null;}public Node(K key, V value) {this.key = key;this.value = value;this.prev = this.next = null;}}// 2. 构造一个双向队列，里面存放着 Node 节点// 队头元素最新，队尾元素最旧static class DoubleLinkedList<K, V> {Node<K, V> head;Node<K, V> tail;// 2.1 构造方法public DoubleLinkedList() {head = new Node<>();tail = new Node<>();// 头尾相连head.next = tail;tail.prev = head;}// 2.2 添加到头（头插）public void addHead(Node<K, V> node) {node.next = head.next;node.prev = head;head.next.prev = node;head.next = node;}// 2.3 删除节点public void removeNode(Node<K, V> node) {node.next.prev = node.prev;node.prev.next = node.next;node.next = null;node.prev = null;}// 2.4 获取最后一个节点public Node getLast() {return tail.prev;}}private final int cacheSize;Map<Integer, Node<Integer, Integer>> map;// MapDoubleLinkedList<Integer, Integer> doubleLinkedList;// 双向链表public LRUCache(int capacity) {this.cacheSize = capacity;map = new HashMap<>();doubleLinkedList = new DoubleLinkedList<>();}public int get(int key) {if (map.containsKey(key)) {// 命中，更新双向链表Node<Integer, Integer> node = map.get(key);// 先删除双向链表中的节点doubleLinkedList.removeNode(node);// 再添加到头部doubleLinkedList.addHead(node);return node.value;} else {// 未命中，返回 -1return -1;}}public void put(int key, int value) {if (map.containsKey(key)) {// 更新双向链表Node<Integer, Integer> node = map.get(key);// 新值替换老值，再放回node.value = value;map.put(key, node);// 先删除双向链表中的节点doubleLinkedList.removeNode(node);// 再添加到头部doubleLinkedList.addHead(node);} else {if (map.size() == cacheSize) {// 超出容量，删除双向链表的最后一个节点Node lastNode = doubleLinkedList.getLast();map.remove(lastNode.key);doubleLinkedList.removeNode(lastNode);}// 新增节点Node<Integer, Integer> newNode = new Node<>(key, value);map.put(key, newNode);doubleLinkedList.addHead(newNode);}}
}