1. 算法介绍
LRU（Least Recently Used）算法是一种常见的缓存替换算法，用于管理缓存中的数据项。它的核心思想是将最近最少使用的数据项（最久未被访问的数据项）替换出缓存，以便为新的数据项腾出空间。
LRU算法通常基于以下原则工作：
-
维护访问顺序： LRU算法维护一个数据项的访问顺序。当某个数据项被访问时，它会被移动到队列的最前面（或者叫做"最近使用"的位置）。
-
替换最远的数据项： 当需要替换缓存中的数据项时，LRU算法会选择队列中位于末尾的数据项，因为它们是最近最少使用的。
-
常用数据项保持在缓存中： LRU算法的目标是确保经常访问的数据项保持在缓存中，以提高缓存的命中率，减少对底层存储的访问。
LRU算法的实现方式可以有多种，包括使用双向链表、哈希表或其他数据结构。以下是一个基本的LRU算法实现步骤：
- 使用双向链表（或其他适当的数据结构）来维护数据项的访问顺序，其中链表头表示最近使用的数据项，链表尾表示最久未使用的数据项。
- 当某个数据项被访问，将其移动到链表头。
- 当需要替换数据项时，选择链表尾的数据项进行替换，并从链表中移除。
- 为了更快地查找数据项，可以使用哈希表将数据项的键映射到链表节点的位置。
LRU算法在缓存管理和数据库系统中经常被使用，它有助于确保常用的数据可以快速访问，提高系统性能。然而，实际的LRU实现可能会因系统需求和性能考虑而有所不同。
2. 使用Java实现（使用LinkedHashMap）
以下是一个简单的Java实现LRU（Least Recently Used）缓存算法的示例。LRU缓存算法用于保持最近使用的数据项，并在容量不足时替换最久未使用的数据项。
在这个示例中，我们继承了LinkedHashMap，并设置了accessOrder为true，以便按访问顺序排序。在removeEldestEntry方法中，我们控制了是否需要删除最旧的元素，当缓存大小超过容量时，会删除最旧的元素。
这个示例演示了如何创建一个LRU缓存，向其添加元素，访问元素以更新其访问时间，并在需要时删除最旧的元素，以保持缓存容量。请注意，Java标准库中的LinkedHashMap可以方便地实现LRU缓存算法。
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LRUCache(int capacity) {
// 设置accessOrder为true，以便按访问顺序排序
super(capacity, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
// 在添加新元素时，控制是否需要删除最旧的元素
return size() > capacity;
}
public static void main(String[] args) {
// 创建一个容量为3的LRU缓存
LRUCache<String, Integer> lruCache = new LRUCache<>(3);
lruCache.put("one", 1);
lruCache.put("two", 2);
lruCache.put("three", 3);
System.out.println("Current cache content: " + lruCache);
lruCache.get("one"); // 访问"one"，使其成为最近使用的
lruCache.put("four", 4); // 添加新元素，触发删除最旧的元素
System.out.println("Updated cache content: " + lruCache);
}
}
3. 使用Java实现（手写）
/**
* @author 曹见朋
* @create 2023-10-27-9:15
*/
public class LRUCacheDemo {
// 1.构造一个Node结点
class Node<K,V>{
K key;
V value;
Node<K,V> prev;
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
class DoubleLinkList<K,V>{
Node<K,V> head;
Node<K,V> tail;
public DoubleLinkList() {
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 int cacheSize;
Map<Integer,Node<Integer,Integer>> map;
DoubleLinkList<Integer,Integer> doubleLinkList;
public LRUCacheDemo(int cacheSize) {
this.cacheSize = cacheSize;
map=new HashMap<>();
doubleLinkList=new DoubleLinkList<>();
}
public int get(int key){ // 获取
if(!map.containsKey(key)){ // 不存在
return -1;
}
Node<Integer, Integer> integerIntegerNode = map.get(key);
doubleLinkList.removeNode(integerIntegerNode);
doubleLinkList.addHead(integerIntegerNode);
return integerIntegerNode.value;
}
public void put(int key,int value){
if(map.containsKey(key)){//已经存在该key
Node<Integer, Integer> integerIntegerNode = map.get(key);
integerIntegerNode.value=value;
map.put(key,integerIntegerNode);
doubleLinkList.removeNode(integerIntegerNode);
doubleLinkList.addHead(integerIntegerNode);
}else {
if (map.size()==cacheSize) {//满了
Node<Integer,Integer> lastNode=doubleLinkList.getLast();
map.remove(lastNode.key);
doubleLinkList.removeNode(lastNode);
}
//新增
Node<Integer, Integer> objectObjectNode = new Node<>();
map.put(key,objectObjectNode);
doubleLinkList.addHead(objectObjectNode);
}
}
}
