LinkedHashMap中LRU算法实现

张勇

我们都知道LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。实际上,Redis缓存和MyBatis二级缓存更新策略算法中就有LRU。

分析LinkedHashMap中的LRU

其实一提到LRU,我们就应该想到LinkedHashMap。LRU是通过双向链表来实现的。当某个位置的数据被命中,通过调整该数据的位置,将其移动至尾部。新插入的元素也是直接放入尾部(尾插法)。这样一来,最近被命中的元素就向尾部移动,那么链表的头部就是最近最少使用的元素所在的位置。
HashMap的afterNodeAccess()、afterNodeInsertion()、afterNodeRemoval()方法都是空实现,留着LinkedHashMap去重写。LinkedHashMap靠重写这3个方法就完成了核心功能的实现。不得不感叹,LinkedHashMap设计之妙。

    // Callbacks to allow LinkedHashMap post-actions
    void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }
   void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        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;
        }
    }

在LinkedHashMap的get()方法中,我们每次获取元素的时候,都要调用afterNodeAccess(e)都要将元素移动到尾部。accessOrder为true,是基于访问排序,accessOrder为基于插入排序。我们想要LinkedHashMap实现LRU功能,accessOrder必须为true。如果accessOrder为false,那就是FIFO了。

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

我们可以看到插入数据的时候,如果removeEldestEntry(first)返回true,按照LRU策略,那么会删除头节点。

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

LinkedHashMap大体的LRU架子都为我们搭好了。那我们怎么去基于LinkedHashMap实现LRU呢。先别慌,我们先看看Mysql-jdbc中的LruCache是怎么实现的。

public class LRUCache extends LinkedHashMap<Object, Object> {  
    private static final long serialVersionUID = 1L;
    protected int maxElements;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75F, true);
        this.maxElements = maxSize;
    }

    protected boolean removeEldestEntry(Entry<Object, Object> eldest) {
        return this.size() > this.maxElements;
    }
}

其实我们只要把accessOrder设置为true,重写removeEldestEntry(eldest)即可。我们在removeEldestEntry(eldest)加上什么时候执行LRU操作的逻辑,比如map里面的元素数量超过指定的大小,开始删除最近最少使用的元素,为后续新增的元素腾出位置来。

结语

希望我的文章对你能有所帮助,谢谢