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 extends LinkedHashMap {
        private int capacity;

        public LRUCache(int capacity) {
            super(capacity, 0.75f, true);
            this.capacity = capacity;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return size() > capacity;
        }

        public static void main(String[] args) {
            LRUCache 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 {

    // 静态内部类，双向链表中的节点类，key理解为页面号，val理解为页面内容
    static class Entry {
        public Entry prev;
        public Entry next;
        public K key;
        public V val;
        public Entry() {}
        public Entry(K key, V val) { this.key = key; this.val = val; }
    }

    private Entry head, tail; // 虚拟头节点和虚拟尾节点
    private final int capacity;     // 缓存容量
    private int size;               // 缓存占用量
    Map> 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 entry = cache.get(key);
        if(entry != null) {
            moveToTail(entry);
            return entry.val;
        } else {
            return null;
        }
    }

    private void put(K key, V val) {
        Entry entry = cache.get(key);
        if(entry != null) {
            // 缓存命中
            entry.val = val;
            moveToTail(entry);
        } else {
            // 缓存未命中
            if(size == capacity) {
                // 缓存已满，删除链表头部节点
                Entry h = head.next;
                deleteEntry(h);
                cache.remove(h.key);
                size--;
            }
            // 添加新页面到链表尾部
            Entry newEntry = new Entry<>(key, val);
            addToTail(newEntry);
            cache.put(key, newEntry);
            size++;
        }
    }

    private void moveToTail(Entry entry) {
        deleteEntry(entry);
        addToTail(entry);
    }

    private void addToTail(Entry entry) {
        if(entry != null) {
            entry.next = tail;
            entry.prev = tail.prev;
            tail.prev.next = entry;
            tail.prev = entry;
        }
    }

    private void deleteEntry(Entry entry) {
        if(entry != null) {
            entry.prev.next = entry.next;
            entry.next.prev = entry.prev;
        }
    }

    public static void main(String[] args) {
        LRUCache 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已被换出，访问不到
    }

}