LRU缓存
LRU缓存
LRU 缓存
LRU 缓存算法是 Least Recently Used 的缩写，即最近最少使用。广泛应用于需要高效管理有限缓存空间 并优化数据访问速度的场景。
主要核心逻辑，确定有限空间，插入元素在队列前部，插入时不能超过最大空间。
package lru;
import java.util.HashMap;
public class LRUCache {
// Node 双向链表
private class Node {
// 键
private K key;
// 值
private V value;
// 前置节点
private Node prev;
// 后置节点
private Node next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
public Node(){}
}
// 最大缓存数量
private final Integer maxSize;
// 头节点
private final Node head;
// 尾节点
private final Node tail;
// Hash
private final HashMap map;
// 构造方法
public LRUCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException(“Cache size must be positive”);
}
this.maxSize = maxSize;
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
map = new HashMap();
}
// 获取键值
public V get(K key) {
Node node = map.get(key);
if (node == null) {
return null;
}
// 移动到头节点
nodeToHead(node);
return node.value;
}
// 添加元素
public void put(K key, V value) {
Node node = map.get(key);
if (node != null) {
node.value = value;
nodeToHead(node);
} else {
node = new Node(key, value);
if (map.size() >= maxSize) {
map.remove(tail.prev.key);
removeNode(tail.prev);
}
map.put(key, node);
addHeadNode(node);
}
}
// 节点前置
private void nodeToHead(Node node) {
// 删除这个节点
removeNode(node);
// 加入到头节点
addHeadNode(node);
}
// 添加头节点
private void addHeadNode(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
// 删除节点
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 打印
private void print() {
Node item = head.next;
while (item.next != null) {
System.out.println(item.key + " : " + item.value.toString());
item = item.next;
}
}
public static void main(String[] args) {
LRUCache cache = new LRUCache<>(3);
cache.put(1, “aaa”);
cache.put(2, “bbb”);
cache.put(3, “ccc”);
System.out.println(cache.get(1));
System.out.println(cache.get(2));
cache.put(4, “ddd”);
cache.print();
}
}
在Java中，可以使用LinkedHashMap来实现LRU缓存。LinkedHashMap是一个哈希表和链表的数据结构。
package lru;
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUMap extends LinkedHashMap {
// 防止被修改
private final int maxSize;
// 构造方法：初始化 maxSize 和 LinkedHashMap 参数
public LRUMap(int maxSize) {
super(maxSize, 0.75f, true);
this.maxSize = maxSize;
}
// 重写移除最老条目条件
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > maxSize;
}
public static void main(String[] args) {
LRUMap cache = new LRUMap(3);
cache.put(1, “aaa”);
cache.put(2, “bbb”);
cache.put(3, “ccc”);
System.out.println(cache.get(1));
System.out.println(cache.get(2));
cache.put(4, “ddd”);
System.out.println(“cache = " + cache);
}
}
LinkedHashMap 部分源码：
// 构造方法
// initialCapacity 初始容量，指定哈希表（Entry[] table）的初始桶数量
// loadFactor 负载因子，主要作用 决定哈希表何时触发扩容
// accessOrder 控制键值对的迭代顺序
// true 表示按照访问顺序迭代键值对
// false：插入顺序。条目按插入顺序排列，不受访问操作影响
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
// removeEldestEntry 方法是 LinkedHashMap 提供的一个扩展点，允许开发者通过覆盖该方法实现 自定义淘汰策略（尤其是实现 LRU 缓存）。
// 返回 true，则删除最老的条目（具体“最老”含义由 accessOrder 决定）
// 默认返回 false（不删除任何条目，保持标准 Map 行为）
protected boolean removeEldestEntry(Map.Entry eldest) {
return false;
}
LRU是平衡实现复杂度与效率的通用缓存策略，核心价值在于利用时间局部性，适用于数据访问模式具有“近期重复性”的场景。