转载

Java中LRU的实现

LRU,全程Least Recently Used,即最近最久未使用算法,用于操作系统的页面置换算法,以及一些常见的框架。其原理实质就是当需要淘汰数据时,会选择那些最近没有使用过的数据进行淘汰,换句话说,当某数据被访问时,就把其移动到淘汰队列的队首(也就是最不会被淘汰的位置)

实现

基于这样的原则,我们就可以着手实现了。不过Java已经为我们提供了一个现成的模板,我们站在巨人的肩膀上,可以参考一下Java是如何实现LRU功能的

LinkedHashMap

在LinkedHashMap中,有一个很少用到的构造函数:

public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
复制代码

其中 accessOrder 这一属性,在其他的构造函数中是默认为 false 的,如果我们通过该构造函数将其设为 true 之后,就实现了LRU功能,下面的程序简单了做了下演示:

public static void main(String[] args) {

        int cacheSize = 3;
        // 最大容量 = (缓存大小 / 负载因子)+ 1,保证不会触发自动扩容
        LinkedHashMap<String, String> cache = new LinkedHashMap<String, String>(
                (int)(cacheSize/ 0.75f) + 1, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > cacheSize;
            }
        };

        cache.put("1", "a");
        cache.put("2", "b");
        cache.put("3", "c");

        // head => "1" => "2" => "3" => null

        // put已存在的值,和get方法是一样的效果
        cache.put("1", "a");

        // head => "2" => "3" => "1" => null;

        cache.put("4", "d");

        // head => "3" => "1" => "4" => null;
        
        for (String key: cache.keySet()) {
            System.out.println(key);
        }
    }
复制代码

其实还有很重要的一点,就是需要重写 removeEldestEntry() 这一方法,默认是返回 false 的,当返回 true 时,会移除最久没有使用的节点,所以我们要做的,就是当容量达到缓存限制时,移除LRU算法判定的最近最久未使用节点

可以看到,我们依次插入节点1、2、3后,如果此时再插入节点4,就会导致 removeEldestEntry() 返回为 true ,然后移除队首节点,即节点1。但是我们这里由于中间重复插入了一次节点1,所以会判断节点1是“经常访问的节点”,所以节点1被提到链表最后,队首节点就变成了节点2,当容量超过限制时,会把节点2移除

实现原理

探索LinkedHashMap中LRU的实现原理,我们就要追溯到HashMap中的 putVal 方法,这个方法最后触发了一个回调函数:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // ...
        
            if (e != null) { // existing mapping for key
                // ...
                afterNodeAccess(e);
                return oldValue;
            }
        }
        afterNodeInsertion(evict);
        return null;
    }
复制代码

putVal() 方法在插入后会触发方法的回调,有两种情况:

afterNodeAccess(e)
afterNodeInsertion(evict)

其中,变量e是“撞车”的节点,变量evict在子类不重写 put() 方法的情况下是默认为 true 的,所以我们就把它当作常量来看

然后我们回到,LinkedHashMap中,来看这个两个钩子方法(HashMap中这两个方法实现均为空):

void afterNodeInsertion(boolean evict) {
        LinkedHashMap.Entry<K,V> first;
        // 以下情况满足时,调用removeNode移除最久未使用的节点:
        //      1. evict为true
        //      2. 头结点不为空
        //      3. 符合移除条件:removeEldestEntry返回true
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

    void afterNodeAccess(Node<K,V> e) {
        LinkedHashMap.Entry<K,V> last;
        // 开启LRU模式,且访问的节点不是尾节点,则将被访问的节点置于链表尾
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }
复制代码

显而易见, afterNodeInsertion 负责在 插入 之后判断是否需要移除最近最久未使用的节点(即链表头节点), afterNodeAccess 负责在 访问 某节点之后,将该节点移动到链表尾

afterNodeAccess 中,因为要考虑到各种特殊情况,而且是一个带有头尾节点的双向链表,所以情况判断比较复杂,实际上就是将指定节点移动到队尾,如果自己想实现一个类似的功能可以不做的这么复杂

总结

一般来说,如果想做一个LRU算法实现的话,LinkedHashMap就能满足需要了。要是想自己实现的话,这里提供一个实现的思路:

  1. 用链表存储数据
  2. 一个节点被访问后,将其置于链表尾
  3. 链表头结点就是最近最久未使用的节点,直接移除即可
原文  https://juejin.im/post/5cfe450d51882520724c8cb2
正文到此结束
Loading...