基于LinkedHashMap手写LRU淘汰策略

上一篇 <<<JDK8的HashMap中红黑树左旋右旋原理图解
下一篇 >>>

LRU(最近最少使用)缓存淘汰算法一般用于缓存场景，当缓存满的时候，把最少使用的数据清掉。

方案1：当key使用的时候，count值+1，最后遍历key的count值，把最小的key清理出去。缺点是数据量大时遍历效率低
方案2：基于LinkedHashMap有序集合实现
原理：访问key的时候，就会将该key存放到链表最后的位置，链表最开头位置说明最近最少使用的

public class ManualLruAlgorithm<K, V> extends LinkedHashMap<K, V> {
    /**
     * 容量
     */
    private int capacity;

    public ManualLruAlgorithm(int capacity) {
        // 末尾accessOrder设置为true，表示访问顺序，当有访问时，key被挪到末尾，最前面是最少使用的数据
        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) {
        ManualLruAlgorithm<String, String> lruCache = new ManualLruAlgorithm<>(3);
        lruCache.put("a","a");
        lruCache.put("b","b");
        lruCache.put("c","c");
        lruCache.put("d","d");
        // 打印结果：bcd，a已被淘汰
        lruCache.forEach((k, v) -> {
            System.out.print(k );
        });
        System.out.println();
        lruCache.put("c","e");
        // 打印结果：bdc，c已被挪到末尾
        lruCache.forEach((k, v) -> {
            System.out.print(k );
        });
    }
}