使用LinkedHashMap实现LRU算法

LinkedHashMap是比HashMap多了一个链表的结构。与HashMap相比LinkedHashMap维护的是一个具有双重链表的HashMap，LinkedHashMap支持2中排序一种是插入排序，即插入是什么顺序，读出来的就是什么顺序。一种是使用排序，最近使用的会移至尾部例如 key1 key2 key3 key4，使用key3后为 key1 key2 key4 key3了。accessOrder为true表示使用顺序，false表示插入顺序。

基于LinkedHashMap的使用顺序的特性，我们可以用来实现LRU算法（Mybatis的LRU算法也是这样实现的）

bigSize表示缓存最大容量，超过这个值最近最少使用的key，将会被移除。

public class LruCache extends LinkedHashMap<Object, Object> {

    private int bigSize;

    public LruCache(int bigSize) {
        this(1024, 0.75F, true,8);
    }
    public LruCache(int initialCapacity, float loadFactor, boolean accessOrder , int bigSize) {
        super(initialCapacity, loadFactor, accessOrder);
        this.bigSize=bigSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
        boolean toBig=size() > bigSize;
        if (toBig){
            System.out.println("移除："+eldest.getKey());
        }
        return toBig;
    }
}

测试

public class Main {

    public static void main(String[] args) {
        LruCache lruCache = new LruCache(8);
        //先插入8个值
        for (int i = 0; i < 8; i++) {
            lruCache.put("key" +i , ""+i);
        }

        System.out.println(lruCache.toString());
        //操作前3个值
        for (int i = 0; i < 3; i++) {
            lruCache.put("key" +i , ""+i);
        }
        System.out.println(lruCache.toString());
       //当map中的值超过bigSize
        for (int i = 9; i < 11; i++) {
            lruCache.put("key" +i , ""+i);
        }
        System.out.println(lruCache.toString());

    }
}

结果如下,当我们重新访问前3个值后，他们会被放到链表最后。前面的值会被移除。

{key0=0, key1=1, key2=2, key3=3, key4=4, key5=5, key6=6, key7=7}
{key3=3, key4=4, key5=5, key6=6, key7=7, key0=0, key1=1, key2=2}
移除：key3
移除：key4
{key5=5, key6=6, key7=7, key0=0, key1=1, key2=2, key9=9, key10=10}