32

LinkedHashMap中LRU算法实现

 5 years ago
source link: http://tech.dianwoda.com/2018/09/04/linkedhashmapzhong-lrude-shi-xian/?amp%3Butm_medium=referral
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

结语

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


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK