LRU算法

LRU算法

LRU（Least Recently Used）算法可以使用哈希表和双向链表来实现。哈希表用于快速查找数据，双向链表用于记录数据的访问顺序。以下是LRU算法的具体实现：

1. 使用一个哈希表和一个双向链表来实现缓存。
2. 哈希表中的key是数据的键值，value是对应节点在双向链表中的位置。
3. 双向链表中，头部是最近访问过的数据，尾部是最久未被访问的数据。
4. 当需要获取缓存数据时，先通过哈希表查找是否存在缓存数据。如果存在，则将对应节点移动到链表头部；否则，返回null。
5. 当需要插入新的数据到缓存时，先检查缓存是否已满。如果已满，则删除双向链表的尾部节点，并从哈希表中删除该节点；然后再将新数据插入到链表头部，并在哈希表中添加新节点。
6. 当需要删除缓存数据时，先通过哈希表查找节点位置，然后从链表中删除该节点，并同时从哈希表中删除对应项。
   总之，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;}@Overrideprotected 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被置换成页面3System.out.println("页面2的内容：" + cache.get(2)); // 页面2已被换出，访问不到}}