LRU算法
LRU（Least Recently Used）算法可以使用哈希表和双向链表来实现。哈希表用于快速查找数据，双向链表用于记录数据的访问顺序。以下是LRU算法的具体实现：
- 使用一个哈希表和一个双向链表来实现缓存。
- 哈希表中的key是数据的键值，value是对应节点在双向链表中的位置。
- 双向链表中，头部是最近访问过的数据，尾部是最久未被访问的数据。
- 当需要获取缓存数据时，先通过哈希表查找是否存在缓存数据。如果存在，则将对应节点移动到链表头部；否则，返回null。
- 当需要插入新的数据到缓存时，先检查缓存是否已满。如果已满，则删除双向链表的尾部节点，并从哈希表中删除该节点；然后再将新数据插入到链表头部，并在哈希表中添加新节点。
- 当需要删除缓存数据时，先通过哈希表查找节点位置，然后从链表中删除该节点，并同时从哈希表中删除对应项。
总之，LRU算法通过维护一个哈希表和一个双向链表来实现缓存淘汰策略。当缓存满时，将最久未被访问的数据从缓存中删除，保留最近访问过的数据。这样可以有效减少缓存命中率的损失，提高系统性能
LRU 如何实现
最近最少使用策略 LRU（Least Recently Used）是一种缓存淘汰算法，是一种缓存淘汰机制。
使用双向链表实现的队列，队列的最大容量为缓存的大小。在使用过程中，把最近使用的页面移动到队列头，最近没有使用的页面将被放在队列尾的位置
使用一个哈希表，把页号作为键，把缓存在队列中的节点的地址作为值，只需要把这个页 对应的节点移动到队列的前面，如果需要的页面在内存中，此时需要把这个页面加载到内 存中，简单的说，就是将一个新节点添加到队列前面，并在哈希表中跟新相应的节点地 址，如果队列是满的，那么就从队尾移除一个节点，并将新节点添加到队列的前面。
1、概念：其实解释起来很简单，LRU就 是Least Recently Used的缩写，翻译过来就是“最近最少使用”。也就是说LRU算法会将最近最少用的缓存移除，让给最新使⽤的缓存。⽽往往最常读取的，也就是读取次数最多的，所以利⽤好LRU算法，我们能够提供对热点数据的缓存效率，能够提⾼缓存服务的内存使⽤率。
2、实现：
1、思路：
i. 限制缓存大小
ii. 查询出最近最晚⽤的缓存
iii. 给最近最少⽤的缓存做⼀个标识
2、代码：
LinkedHashMap来实现的LRU算法的缓存
package com.lc.lru;
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int capacity;
public LRUCache(int capacity) {
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) {
LRUCache<Integer, String> cache = new LRUCache<>(2);
cache.put(1, "One");
cache.put(2, "Two");
System.out.println(cache); // 输出：{1=One, 2=Two}
cache.put(3, "Three");
System.out.println(cache); // 输出：{2=Two, 3=Three}
cache.get(2);
System.out.println(cache); // 输出：{3=Three, 2=Two}
}
}
HashMap实现LRU算法的缓存
import java.util.HashMap;
import java.util.Map;
/**
* @Desc 采用LRU置换算法的缓存
* @Author lc
* @Date 2022/4/3 19:44
*/
public class LRUCache<K, V> {
// 静态内部类，双向链表中的节点类，key理解为页面号，val理解为页面内容
static class Entry<K, V> {
public Entry<K, V> prev;
public Entry<K, V> next;
public K key;
public V val;
public Entry() {}
public Entry(K key, V val) { this.key = key; this.val = val; }
}
private Entry<K, V> head, tail; // 虚拟头节点和虚拟尾节点
private final int capacity; // 缓存容量
private int size; // 缓存占用量
Map<K, Entry<K, V>> cache; // 哈希表，记录双向列表节点的地址值
public LRUCache(int capacity) {
this.capacity = capacity;
initCache();
}
// 初始化LRU缓存
private void initCache() {
head = new Entry<>();
tail = new Entry<>();
head.next = tail;
tail.prev = head;
size = 0;
cache = new HashMap<>(this.capacity);
}
private V get(K key) {
Entry<K, V> entry = cache.get(key);
if(entry != null) {
moveToTail(entry);
return entry.val;
} else {
return null;
}
}
private void put(K key, V val) {
Entry<K, V> entry = cache.get(key);
if(entry != null) {
// 缓存命中
entry.val = val;
moveToTail(entry);
} else {
// 缓存未命中
if(size == capacity) {
// 缓存已满，删除链表头部节点
Entry<K, V> h = head.next;
deleteEntry(h);
cache.remove(h.key);
size--;
}
// 添加新页面到链表尾部
Entry<K, V> newEntry = new Entry<>(key, val);
addToTail(newEntry);
cache.put(key, newEntry);
size++;
}
}
private void moveToTail(Entry<K, V> entry) {
deleteEntry(entry);
addToTail(entry);
}
private void addToTail(Entry<K, V> entry) {
if(entry != null) {
entry.next = tail;
entry.prev = tail.prev;
tail.prev.next = entry;
tail.prev = entry;
}
}
private void deleteEntry(Entry<K, V> entry) {
if(entry != null) {
entry.prev.next = entry.next;
entry.next.prev = entry.prev;
}
}
public static void main(String[] args) {
LRUCache<Integer, String> cache = new LRUCache<>(2);
cache.put(1,"可口可乐");
cache.put(2,"雪碧");
System.out.println("页面1的内容：" + cache.get(1));
cache.put(3,"果粒橙"); // 此时缓存已满，且页面2最久未被使用（因为cache.get(1)访问了页面1），页面2被置换成页面3
System.out.println("页面2的内容：" + cache.get(2)); // 页面2已被换出，访问不到
}
}