1.LRU算法
LRU，全称 Least Recently Used，是一种缓存淘汰策略。在缓存中存储数据时，如果缓存满了，就需要淘汰一些数据来腾出空间。LRU算法认为最近使用频率较低的数据应该被淘汰，以此来保留热点数据，提高缓存命中率。
LRU 算法的实现方式通常是通过维护一个双向链表和一个哈希表。哈希表中存储数据的键值和对应节点在双向链表中的位置，链表的头部是最近使用的节点，尾部是最久未使用的节点。当有新的数据被访问时，先在哈希表中查找是否已存在该节点，如果存在则将节点移动到链表头部，如果不存在则新建一个节点并添加到链表头部，同时在哈希表中添加键值对。当缓存满时，将链表尾部的节点移除，同时在哈希表中删除对应的键值对。
LRU 算法的优点是实现简单，易于理解和维护，适用于多种场景，比如缓存、数据库等。缺点是在特定的场景下性能可能不如其他淘汰策略，比如 LFU 算法等。此外，LRU 算法在处理热点数据集合时可能会出现“抖动”，即数据在热点和非热点之间频繁移动，导致缓存命中率下降。针对这个问题，一些改进的 LRU 算法，比如 2Q 算法、ARC 算法等，被提出。
2.Java 实现 LRU
下面是用Java 实现 LRU。
2.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;
}
}
2.2 定义一个双向链表类
import java.util.HashMap;
import java.util.Map;
/**
* <h1>定义一个双向链表类</h1>
* 包含一个头节点和一个尾节点,用于存储双向链表中的数据。
*/
public class LRUCache {
// 定义缓存容量
private final int capacity;
// 定义一个 Hash表,用于快速定位元素
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,返回-1
if (!cache.containsKey(key)) {
return -1;
}
// 将对应节点移到哨兵头节点之后,并返回对应 value
ListNode node = cache.get(key);
moveNodeToHead(node);
return node.value;
}
/**
* <h2>添加元素</h2>
*/
public void putValue(Integer key, Object value) {
// 如果 key 已经存在,将对应节点移到哨兵头节点之后,更新 value
if (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;
}
}
2.3 定义一个单元测试类
public class LRUCacheTest {
@Test
public void test() {
int capacity = 5;
LRUCache lruCache = new LRUCache(capacity);
System.out.println("初始容量:" + capacity);
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());
}
}
这个实现使用了一个双向链表和一个 HashMap 来实现 LRU 缓存。HashMap 用于快速查找节点，双向链表用于维护节点顺序，从而实现 LRU 策略。
在这个实现中，LRUCache 类型的缓存具有固定的容量，当缓存达到容量限制时，最近最少使用的节点会被移除。使用 getValue 方法获取节点时，如果节点存在，它将被移动到链表的头部以表示它是最近使用的节点。使用 putValue 方法添加节点时，如果节点已存在，则它的值将被更新并移动到链表的头部。如果节点不存在，则将新节点添加到链表的头部。如果添加后缓存超出了容量限制，则最后一个节点将被删除。
这就是 LRU 算法的基本思想：缓存中数据的使用是不断变化的，而缓存大小是有限的，因此需要通过一定的淘汰策略来保证缓存中数据的有效性和及时性。
总的来说，LRU 算法是一种比较简单、高效的缓存淘汰策略，它能够快速判断出最近最少使用的数据，并及时淘汰，从而保证了缓存中数据的有效性和及时性。在实际开发中，我们可以根据具体的场景和需求，结合不同的数据结构和算法来实现 LRU 算法。
评论区