高效缓存管理：Java 实现 LRU 淘汰算法
1、LRU 简介
LRU，全称 Least Recently Used，是一种缓存淘汰策略。在缓存中存储数据时，如果缓存满了，就需要淘汰一些数据来腾出空间。LRU算法认为最近使用频率较低的数据应该被淘汰，以此来保留热点数据，提高缓存命中率。
LRU 算法的实现方式通常是通过维护一个双向链表和一个哈希表。哈希表中存储数据的键值和对应节点在双向链表中的位置，链表的头部是最近使用的节点，尾部是最久未使用的节点。当有新的数据被访问时，先在哈希表中查找是否已存在该节点，如果存在则将节点移动到链表头部，如果不存在则新建一个节点并添加到链表头部，同时在哈希表中添加键值对。当缓存满时，将链表尾部的节点移除，同时在哈希表中删除对应的键值对。
LRU 算法的优点是实现简单，易于理解和维护，适用于多种场景，比如缓存、数据库等。缺点是在特定的场景下性能可能不如其他淘汰策略，比如 LFU 算法等。此外，LRU 算法在处理热点数据集合时可能会出现“抖动”，即数据在热点和非热点之间频繁移动，导致缓存命中率下降。针对这个问题，一些改进的 LRU 算法，比如 2Q 算法、ARC 算法等，被提出。
2、常见的缓存淘汰算法
常见的缓存淘汰算法有以下几种：
-
先进先出（FIFO）：按照缓存中数据进入的顺序，先进先出的淘汰数据。
-
最近最少使用（LRU）：根据缓存中数据的使用时间，最近最少使用的数据被淘汰。即最近一段时间内没有被访问的数据先被淘汰。
-
最不经常使用（LFU）：根据缓存中数据的使用次数，使用次数最少的数据被淘汰。
-
时间轮算法（TTL）：根据缓存中数据的存活时间（time-to-live，TTL），在数据过期后淘汰。
-
随机算法：随机淘汰一些数据。
以上算法各有优缺点，应根据实际情况选择合适的淘汰策略。例如，FIFO算法容易实现，但是不够智能，会将一些较重要的数据误淘汰；而LRU算法智能化程度更高，但是实现复杂度相对较高。
3、Java 实现 LRU
3.1、定义一个双向链表节点类
/*** <h1>定义一个双向链表节点类</h1>* 包含一个 key 和一个 value 属性，用于存储键值对。* */
public class ListNode {public Integer key;public Object value;public ListNode prev;public ListNode next;// 构造方法public ListNode(int key, Object value) {this.key = key;this.value = value;this.prev = null;this.next = null;}
}
3.2、定义一个双向链表类
import java.util.HashMap;
import java.util.Map;/*** <h1>定义一个双向链表类</h1>* 包含一个头节点和一个尾节点，用于存储双向链表中的数据。* */
public class LRUCache {// 定义缓存容量private final int capacity;// 定义一个 HashMap 用于快速定位元素private final Map<Integer, ListNode> cache;// 定义头结点和尾节点private ListNode head, tail;/*** <h2>构造方法</h2>* */public LRUCache(int capacity) {// 初始化容量this.capacity = capacity;cache = new HashMap<>(capacity);// 初始化头结点和尾节点，并让它们相互指向this.head = new ListNode(-1, -1);this.tail = new ListNode(-1, -1);this.head.next = tail;this.tail.prev = head;}/*** <h2>将指定结点移到头结点之后</h2>* */private void moveNodeToHead(ListNode node) {// 如果 node 本来就是头结点，直接返回if (node == head.next) {return;}// 如果 node 不是尾节点，将 node 从双向链表中删除if (node.next != null && node.prev != null) {node.prev.next = node.next;node.next.prev = node.prev;}// 将node插入到头结点之后node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}/*** <h2>获取 key 对应的 value</h2>* */public Object getValue(int key) {// 如果 map 中没有该 key，返回-1if (!cache.containsKey(key)) {return -1;}// 将对应结点移到头结点之后，并返回对应 valueListNode node = cache.get(key);moveNodeToHead(node);return node.value;}/*** <h2>添加元素</h2>* */public void putValue(Integer key, Object value) {// 如果 key 已经存在，将对应结点移到头结点之后，更新 valueif (cache.containsKey(key)) {ListNode node = cache.get(key);moveNodeToHead(node);node.value = value;}// 如果 key 不存在，新建一个结点，添加到头结点之后，并将其加入到 map 中else {ListNode newNode = new ListNode(key, value);cache.put(key, newNode);newNode.next = head.next;newNode.prev = head;head.next.prev = newNode;head.next = newNode;// 如果容量已经达到上限，将尾节点之前的结点删除if (cache.size() > capacity) {ListNode lastNode = tail.prev;cache.remove(lastNode.key);lastNode.prev.next = tail;tail.prev = lastNode.prev;}}}/*** <h2>打印 LRU 缓存信息</h2>* */public String printLog() {String result = "";ListNode node = this.head.next;while( node.next != null ) {result += node.key + " = " + node.value;if( node.next.key != -1) {result += ", ";}node = node.next;}return result;}
}3.3、定义一个单元测试类
/*** <h1>定义一个单元测试类</h1>* */
public class LRUTest {public static void main(String[] args) {LRUCache lruCache = new LRUCache(5);System.out.println("初始状态：" + lruCache.printLog());lruCache.putValue(1, "V1");System.out.println("新增键 1：" + lruCache.printLog());lruCache.putValue(2, "V2");System.out.println("新增键 2：" +lruCache.printLog());lruCache.putValue(3, "V3");System.out.println("新增键 3：" +lruCache.printLog());lruCache.getValue(1);System.out.println("查询键 1：" +lruCache.printLog() + "，注意：链表数据位置变化");lruCache.putValue(4, "V4");System.out.println("新增键 4：" +lruCache.printLog());lruCache.putValue(5, "V5");System.out.println("新增键 5：" +lruCache.printLog());lruCache.getValue(4);System.out.println("查询键 4：" +lruCache.printLog() + "，注意：链表数据位置变化");lruCache.putValue(6, "V6");System.out.println("新增键 6：" +lruCache.printLog());System.out.println("最终状态：" + lruCache.printLog());}
}单元测试输出结果
初始状态：
新增键 1：1 = V1
新增键 2：2 = V2, 1 = V1
新增键 3：3 = V3, 2 = V2, 1 = V1
查询键 1：1 = V1, 3 = V3, 2 = V2，注意：链表数据位置变化
新增键 4：4 = V4, 1 = V1, 3 = V3, 2 = V2
新增键 5：5 = V5, 4 = V4, 1 = V1, 3 = V3, 2 = V2
查询键 4：4 = V4, 5 = V5, 1 = V1, 3 = V3, 2 = V2，注意：链表数据位置变化
新增键 6：6 = V6, 4 = V4, 5 = V5, 1 = V1, 3 = V3
最终状态：6 = V6, 4 = V4, 5 = V5, 1 = V1, 3 = V3
这个实现使用了一个双向链表和一个 HashMap 来实现 LRU 缓存。HashMap 用于快速查找节点，双向链表用于维护节点顺序，从而实现 LRU 策略。
在这个实现中，LRUCache 类型的缓存具有固定的容量，当缓存达到容量限制时，最近最少使用的节点会被移除。使用 getValue 方法获取节点时，如果节点存在，它将被移动到链表的头部以表示它是最近使用的节点。使用 putValue 方法添加节点时，如果节点已存在，则它的值将被更新并移动到链表的头部。如果节点不存在，则将新节点添加到链表的头部。如果添加后缓存超出了容量限制，则最后一个节点将被删除。
这就是 LRU 算法的基本思想：缓存中数据的使用是不断变化的，而缓存大小是有限的，因此需要通过一定的淘汰策略来保证缓存中数据的有效性和及时性。
总的来说，LRU 算法是一种比较简单、高效的缓存淘汰策略，它能够快速判断出最近最少使用的数据，并及时淘汰，从而保证了缓存中数据的有效性和及时性。在实际开发中，我们可以根据具体的场景和需求，结合不同的数据结构和算法来实现 LRU 算法。