【算法】LRU最久未使用算法原理分析和编码实战

• 什么是LRU算法

  • Least Recently Used 淘汰算法以时间作为参考，淘汰最长时间未被使用的数据

  • 如果数据最近被访问过，那么将来被访问的几率也更高；会淘汰最长时间没有被使用的元素（都没人要你了，不淘汰你淘汰谁）

  • 基本原理是：在缓存满时，将最近最久未使用的数据淘汰出缓存，以便给新的数据留出空间。

  • 实现方式可以用：数组、链表等方式

• 新插入的数据放在头部，最近访问过的也移到头部，空间满时将尾部元素删除

• 编码实现

public class LRUCache<K,V> {

    //定义存储key的顺序表
    private LinkedList<K> cacheKey;

    //定规存储数据的map 存储key，value
    private HashMap<K,V> cacheValues;

    //定义缓存的容量
    private int capacity;

    //构造方法初始化缓存
    public LRUCache(int capacity) {
        this.cacheKey = new LinkedList<>();
        this.capacity = capacity;
        this.cacheValues = new HashMap<>();
    }

    //向缓存中put元素
    public void put(K key, V value) {
        //先添加元素，无论有没有这个key，直接进行put
        cacheValues.put(key, value);
        cacheKey.add(0, key);
        //判断长度是否超出最大容量，超出进行淘汰
        if (cacheKey.size() > capacity) {
            //如果容量已满，则删除最后一个key
            K lastKey = cacheKey.get(cacheKey.size() - 1);
            cacheKey.remove(lastKey);
            cacheValues.remove(lastKey);
        }
    }

    //获取指定key的元素的value，并且将这个key放置在队头的位置
    public V get(K key) {
        V data = null;
        if (cacheKey.contains(key)) {
            data = cacheValues.get(key);
            cacheKey.remove(key);
            cacheKey.add(0,key);
        }
        return data;
    }

    //
    public void showList(){
        System.out.println(cacheKey.toString());
    }

    public static void main(String[] args) {
        LRUCache<String,String> cache = new LRUCache<>(5);
        cache.put("A", "任务A");
        cache.put("B", "任务B");
        cache.put("C", "任务C");
        cache.put("D", "任务D");
        cache.put("E", "任务E");
        cache.showList();
        System.out.println("G=" + cache.get("G"));
        System.out.println("C=" + cache.get("C"));
        cache.showList();
        cache.put("F", "任务F");
        cache.showList();
    }

}