• 如何利用LinkedHashMap实现LRU
  • 发布于 2个月前
  • 301 热度
    0 评论
前言
LRU是Least Recently Used的缩写,即最近最少使用,当超过容量时,自动删除最近最少使用的项目。LRU在android开发中最常见的就是图片加载框架中的缓存逻辑。在java中可以利用LinkedListMap很方便的实现LRU,如下:
class LRUCache extends LinkedHashMap<Integer, Integer> {
    //堆代码 duidaima.com
    //LinkedHashMap实现了按访问排序和移除最近最少,但是默认是不使用的,需要我们改造一下
    private int capacity;

    public LRUCache(int capacity) {
        //这里的第三个参数true就是使用访问排序,这样每次访问都是更新链表
        //注意,这里的第一个参数是map的初始大小,并不是限定容量
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        //这个函数默认返回false,如果不重写这个方法,永远不会进行清除
        //所以这里要重写一下,判断是否进行清除。
        return size() > capacity;
    }
}
那么这其中的原理是什么呢?

原理
首先就是LinkedHashMap,它与HashMap的区别就是在Map的结构外还有一个链表结构,Map的每个key-value都会以Node的形式同时存储在Map和链表中。当put一个key和value时,加入Map的同时,也加入链表尾部,这样实现了有序(HashMap本来是无序的)。这里就不展开说了,简单知道有这个链表就可以了,正是这个链表完成了LRU的实现。

简单来说就是get(使用了)的时候将该Node从链表中移除,并添加到链表尾部。put的时候,检查Map的容量,如果超出了,就从移除链表头部Node(时间最久的,即最近最少使用),同时从map中移除。
那么代码中是如何实现的?

先看get函数,这个函数LinkedHashMap进行了重写:
public V get(Object var1) {
    Node var2;
    if ((var2 = this.getNode(hash(var1), var1)) == null) {
        return null;
    } else {
        if (this.accessOrder) {
            this.afterNodeAccess(var2);
        }

        return var2.value;
    }
}

public V getOrDefault(Object var1, V var2) {
    Node var3;
    if ((var3 = this.getNode(hash(var1), var1)) == null) {
        return var2;
    } else {
        if (this.accessOrder) {
            this.afterNodeAccess(var3);
        }

        return var3.value;
    }
}
可以看到有这么一段代码:
if (this.accessOrder) {
    this.afterNodeAccess(var3);
}
这里的accessOrder就是LinkedHashMap的三参数构造函数super(capacity, 0.75F, true)中的第三个参数,是否使用访问排序。

默认是false,如果为ture就使用访问排序,这时候get函数就会调用afterNodeAccess,这个函数是HashMap的,但是在HashMap中是个空函数,没有任何实现:
void afterNodeAccess(HashMap.Node<K, V> var1) {
}
所以如果使用HashMap,这个访问排序就没有什么意义。但是在LinkedHashMap中对这个函数进行了重写:
void afterNodeAccess(Node<K, V> var1) {
    LinkedHashMap.Entry var2;
    if (this.accessOrder && (var2 = this.tail) != var1) {
        LinkedHashMap.Entry var3 = (LinkedHashMap.Entry)var1;
        LinkedHashMap.Entry var4 = var3.before;
        LinkedHashMap.Entry var5 = var3.after;
        var3.after = null;
        if (var4 == null) {
            this.head = var5;
        } else {
            var4.after = var5;
        }

        if (var5 != null) {
            var5.before = var4;
        } else {
            var2 = var4;
        }

        if (var2 == null) {
            this.head = var3;
        } else {
            var3.before = var2;
            var2.after = var3;
        }
        
        this.tail = var3;
        ++this.modCount;
    }

}
简单来说就是将get函数访问的这个Node从链表中移除,添加到结尾。所以可以看到,如果想实现LRU,accessOrder就必须为true,否则无效。

自动清理
这样实现了访问排序,那么如何实现的自动清理呢?我们来看看put函数,put函数LinkedHashMap没有重写,所以在它的父类HashMap中:
public V put(K var1, V var2) {
    // 堆代码 duidaima.com
    return this.putVal(hash(var1), var1, var2, false, true);
}

final V putVal(int var1, K var2, V var3, boolean var4, boolean var5) {
    HashMap.Node[] var6;
    int var8;
    if ((var6 = this.table) == null || (var8 = var6.length) == 0) {
        var8 = (var6 = this.resize()).length;
    }

    Object var7;
    int var9;
    if ((var7 = var6[var9 = var8 - 1 & var1]) == null) {
        var6[var9] = this.newNode(var1, var2, var3, (HashMap.Node)null);
    } else {
        ...

        if (var10 != null) {
            Object var13 = ((HashMap.Node)var10).value;
            if (!var4 || var13 == null) {
                ((HashMap.Node)var10).value = var3;
            }

            this.afterNodeAccess((HashMap.Node)var10);
            return var13;
        }
    }

    ++this.modCount;
    if (++this.size > this.threshold) {
        this.resize();
    }

    this.afterNodeInsertion(var5);
    return null;
}
这里重点关注链表的逻辑,可以看到如果Map中不存在这个key,就新建一个
if ((var7 = var6[var9 = var8 - 1 & var1]) == null) {
    var6[var9] = this.newNode(var1, var2, var3, (HashMap.Node)null);
} else {
但是如果存在,除了重新赋值之外,还执行了afterNodeAccess,将它移到了链表尾部。
if (var10 != null) {
    ...

    this.afterNodeAccess((HashMap.Node)var10);
    return var13;
}
因为重新赋值就是访问了该元素,所以需要重新排序。

那么这里受不受accessOrder的控制,因为accessOrder是LinkedHashMap的一个变量,而put是HashMap实现的,所以在put的代码中并没有判断accessOrder。但是在上面afterNodeAccess函数的源码中可以看到一开始就判断了accessOrder,所以这里也是受accessOrder的控制的。这也是为什么在get函数中判断了accessOrder,在afterNodeAccess又一次判断的原因。

最后还执行了afterNodeInsertion,这个函数与afterNodeAccess一样,在HashMap中是空函数,没有任何代码。在LinkedHashMap实现了,如下:
void afterNodeInsertion(boolean var1) {
    LinkedHashMap.Entry var2;
    if (var1 && (var2 = this.head) != null && this.removeEldestEntry(var2)) {
        Object var3 = var2.key;
        this.removeNode(hash(var3), var3, (Object)null, false, true);
    }

}
可以看到这个函数实现了移除Map中的元素,这样就实现了清理。但是并不是每次都清理,所以需要removeEldestEntry判断。这个函数是LinkedHashMap的函数,但是在LinkedHashMap中这个函数也是一个空函数,默认返回false
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> var1) {
    return false;
}
所以永远不会清理,这也是我们为什么一定要重写这个函数的原因。通过我们上面的重写,当Map容量大于我们规定的上限时就返回true,这样就执行了清理。
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
    //这个函数默认返回false,如果不重写这个方法,永远不会进行清除
    //所以这里要重写一下,判断是否进行清除。
    return size() > capacity;
}

总结
所以要用LinkedHashMap实现LRU,有两个非常重要的点:
1、accessOrder必须为true。否则链表不会重排。
注意:如果为false,还是可以清理的(下面会说到),这时候如果清理实际上就是清理存入最久的,也就相当于一个普通的队列。

2、必须重写removeEldestEntry。否则永远不会清理。
那么上面提到的一个问题,清理是否受accessOrder影响?是不是accessOrder为false就不清理了?

答案是不影响,重排和清理是互不影响的,在afterNodeInsertion的整个流程中没有accessOrder的出现。所以上面提到了,如果accessOrder为false也可以清理,只不过清理的是存入最久的(忽略访问),并不是LRU算法。
用户评论