原理

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。
相关算法原理参考:https://www.jianshu.com/p/d533d8a66795

实现

基于链表实现,当map容量大于最大值移除头部最旧的对象,当命中key时,把命中对象移到链表结尾。
由于LinkedHashMap非线形安全,所以加入ReentrantLock在读写后加锁。

public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private final Lock lock = new ReentrantLock();

    public LRULinkedHashMap(int maxCapacity) {
        super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
        return size() > maxCapacity;
    }

    @Override
    public V get(Object key) {
        try {
            lock.lock();
            return super.get(key);
        } finally {
            lock.unlock();
        }
    }

    @Override
    public V put(K key, V value) {
        try {
            lock.lock();
            return super.put(key, value);
        } finally {
            lock.unlock();
        }
    }

}

相关测试:

   @Test
    public void test(){
        LRULinkedHashMap map = new LRULinkedHashMap(3);
        map.put(1,1);
        map.put(2,2);
        map.put(3,3);
        System.out.println(map.get(1));
        map.put(4,4);
        System.out.println(JSON.toJSON(map));

    }

打印结果:

1
{"3":3,"1":1,"4":4}