基于LinkedHashMap实现LRU缓存

LRU,Least Recently Used,即最近最少使用,LRU缓存是经常使用的缓存淘汰策略之一。

我们可以使用LinkedHashMap的特性很容易实现LRU缓存。

1、访问排序

基于LinkedHashMap实现LRU缓存

 LinkedHashMap的构造方法中,有个accessorder参数,传true时,在调用get方法获取值时会对获取的值进行排序:

基于LinkedHashMap实现LRU缓存

 afterNodeAccess方法会将节点移至链表尾部:

基于LinkedHashMap实现LRU缓存

 afterNodeAccess方法实际是HashMap提供的扩展点,子类可以去重写这些扩展点来实现节点插入、访问和插入时额外的操作,上述代码既是LinkedHashMap的实现。

基于LinkedHashMap实现LRU缓存

2、removeEldestEntry方法

基于LinkedHashMap实现LRU缓存

 该方法默认返回false,此方法是在插入节点后调用

基于LinkedHashMap实现LRU缓存

 我们可以重写removeEldestEntry方法,当插入元素个数大于链表size时,返回true,此时就会移除表头元素。

基于以上2个特性,编写LruCache代码如下:

public class LruCache {

    private Map<Object, Object> cacheMap;
    private int size = 5;

    public LruCache() {
        cacheMap = new LinkedHashMap<Object, Object>(size, .75f, true) {
            /**
             * 当put进新的值方法返回true时,移除该map中最老的键和值
             * @param eldest
             * @return
             */
            @Override
            protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
                return size() > size;
            }
        };
    }

    public Object get(Object key) {
        return cacheMap.get(key);
    }

    public void put(Object key, Object value) {
        cacheMap.put(key, value);
    }

    public void remove(Object key) {
        cacheMap.remove(key);
    }

    public void clear() {
        cacheMap.clear();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        cacheMap.forEach((k, v)-> {
            sb.append("(").append(k).append(",").append(v).append(")");
        });
        return sb.toString();
    }

    public static void main(String[] args) {
        LruCache cache = new LruCache();
        for (int i = 0; i < 10; i++) {
            cache.put(i, i);
            // 这里对第0个元素调用get方法,不会被淘汰
            cache.get(0);
            System.out.println(cache);
        }
    }

}

运行结果如下:

 基于LinkedHashMap实现LRU缓存

 可以看出,我们一直get(0), (0,0)一直排在表尾,当缓存超过设定size时,表首元素会被淘汰。

mybatis中使用lru缓存也是基于LinkedHashMap去实现的,大家有兴趣可以了解下。

上一篇:LinkedHashMap类


下一篇:odoo13 异常提醒与onchange