LinkedHashMap实现LRU算法

2021-12-05 23:35:24 浏览数 (2)

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，将会被移除。

代码语言：txt复制
public class LruCache extends LinkedHashMap<Object, Object> {
代码语言：txt复制
    private int bigSize;
代码语言：txt复制
    public LruCache(int bigSize) {
代码语言：txt复制
        this(1024, 0.75F, true,8);
代码语言：txt复制
    }
代码语言：txt复制
    public LruCache(int initialCapacity, float loadFactor, boolean accessOrder , int bigSize) {
代码语言：txt复制
        super(initialCapacity, loadFactor, accessOrder);
代码语言：txt复制
        this.bigSize=bigSize;
代码语言：txt复制
    }
代码语言：txt复制
    @Override
代码语言：txt复制
    protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
代码语言：txt复制
        boolean toBig=size() > bigSize;
代码语言：txt复制
        if (toBig){
代码语言：txt复制
            System.out.println("移除：" eldest.getKey());
代码语言：txt复制
        }
代码语言：txt复制
        return toBig;
代码语言：txt复制
    }
代码语言：txt复制
}

测试

代码语言：txt复制
public class Main {
代码语言：txt复制
    public static void main(String[] args) {
代码语言：txt复制
        LruCache lruCache = new LruCache(8);
代码语言：txt复制
        //先插入8个值
代码语言：txt复制
        for (int i = 0; i < 8; i  ) {
代码语言：txt复制
            lruCache.put("key"  i , "" i);
代码语言：txt复制
        }
代码语言：txt复制
        System.out.println(lruCache.toString());
代码语言：txt复制
        //操作前3个值
代码语言：txt复制
        for (int i = 0; i < 3; i  ) {
代码语言：txt复制
            lruCache.put("key"  i , "" i);
代码语言：txt复制
        }
代码语言：txt复制
        System.out.println(lruCache.toString());
代码语言：txt复制
       //当map中的值超过bigSize
代码语言：txt复制
        for (int i = 9; i < 11; i  ) {
代码语言：txt复制
            lruCache.put("key"  i , "" i);
代码语言：txt复制
        }
代码语言：txt复制
        System.out.println(lruCache.toString());
代码语言：txt复制
    }
代码语言：txt复制
}

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

代码语言：txt复制
{key0=0, key1=1, key2=2, key3=3, key4=4, key5=5, key6=6, key7=7}
代码语言：txt复制
{key3=3, key4=4, key5=5, key6=6, key7=7, key0=0, key1=1, key2=2}
代码语言：txt复制
移除：key3
代码语言：txt复制
移除：key4
代码语言：txt复制
{key5=5, key6=6, key7=7, key0=0, key1=1, key2=2, key9=9, key10=10}
hashmap 缓存 编程算法

0 人点赞