转载

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里面的元素数量超过指定的大小，开始删除最近最少使用的元素，为后续新增的元素腾出位置来。