手撸高频面试算法LRU缓存，力扣热题

---

一、什么是LRU？

LRU是一种常用的缓存淘汰策略，全称为“Least Recently Used”，即最近最少使用的意思。这种算法主要用于内存管理、浏览器缓存、数据库系统以及其他需要缓存数据的场景中，用来决定当缓存空间不足时应该移除哪些数据项。

LRU的基本思想是：当缓存满时，优先删除最近最少访问的数据项。这里的“最近最少访问”是指在所有缓存中的数据项里，选择那个自上次被访问以来时间最长的数据项进行淘汰。

二、Java的两种实现

在实现上，LRU通常使用双向链表和哈希表结合的方式。每当有一个新的元素加入缓存时，就在链表尾部添加该元素；而当某个元素被访问时，就将这个元素移动到链表的头部。这样，链表的尾部始终是最久未被访问的元素，当需要腾出空间时，就可以直接移除尾部的元素。

1.双向链表和哈希表结合实现

代码如下：

class LRUCache {class Node{ // 定义内部链表节点类int key;int value;Node prev;  //前驱Node next;  //后继public Node(int key, int value) {this.key = key;this.value = value;}}// 定义缓存容量、大小private int capacity;private int size;// 定义头和尾节点，便于链表的操作private Node head;private Node tail;private Map<Integer, Node> cache = new HashMap<>(); // 定义map用于快速查找结果public LRUCache(int capacity) { // 初始化this.capacity = capacity;this.size = 0;this.head = new Node(0, 0);this.tail = new Node(0, 0);this.head.next = this.tail;this.tail.prev = this.head;}public int get(int key) {Node node = cache.get(key);if (node == null) {return -1;}// 移动到链表头部moveToHead(node);return node.value;}public void put(int key, int value) {Node node = cache.get(key);if (node == null) { // 新增node = new Node(key, value);cache.put(key, node);addNode(node);size++;if (size > capacity) { // 超出容量时移除尾节点Node tail = removeTail();cache.remove(tail.key);size--;}} else { // 更新并移动到头节点node.value = value;moveToHead(node);}}private void moveToHead(Node node) {removeNode(node);addNode(node);}// 移除节点private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}// 头插private void addNode(Node node) {node.next = head.next;node.prev = head;head.next.prev = node;head.next = node;}// 移除尾节点private Node removeTail() {Node node = tail.prev;removeNode(node);return node;}

实现说明：

• 用一个双向链表结构和一个hash表结构配合实现，双向链表用于保证数据顺序，hash表用于快速检索数据
• 在查询时需要将数据移动到表头
• 插入时进行链表头插，若数据size大于capacity，则需要移除尾节点
• 更新数据时，将节点移动到头部

2.LinkedHashMap快速实现LRU缓存

代码如下：

class LRUCache extends LinkedHashMap<Integer, Integer>{private int capacity;public LRUCache(int capacity) {super(capacity, 0.75F, true); // 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 size() > capacity;}
}

为什么这么写就能够实现LRU缓存？实际上看过LinkedHashMap源码的小伙伴可能会有所了解。
LinkedHashMap 实现 LRU 的关键在于它的构造函数参数：accessOrder 和 removeEldestEntry 方法。

• accessOrder: 当设置为 true 时，LinkedHashMap 将按照访问顺序而不是插入顺序排序条目。这意味着每次访问一个条目后，它都会被移到链表的末尾，表示它是最新访问的。
• removeEldestEntry: 这是一个可选的方法引用，当 LinkedHashMap 大小超过设定限制时调用此方法。如果返回 true，那么最老的条目（根据 accessOrder 决定的顺序）会被移除。