使用LinkedList实现LRU-白红宇

使用LinkedList实现LRU

阅读量：2353 次

发布时间：2019-05-10

本文共 2769 字，大约阅读时间需要 9 分钟。

LRU（Least Recently Used），即最近最少使用，是一种常用的页面置换算法，如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最近最少使用的数据淘汰。

为什么使用LinkedList实现LRU

我们设计数据结构时需要考虑以下几点：

（1）首先为了快速获取缓存数据，可以考虑哈希表；

（2）其次，为了达到LRU的目的，需要保证数据有序。

链表能达到有序的目的，但是检索慢，最坏的情况下要扫描整个链表；哈希表检索快，但是无序。而Java提供的LinkedHashMap恰好具备这两个特性，LinkedHashMap是HashMap的子类，在完全继承HashMap的哈希特性之外，还具有双向链表的数据结构，以保证数据的顺序。

默认情况下，LinkedHashMap 是按插入顺序维护链表。不过我们可以在初始化 LinkedHashMap，指定 accessOrder 参数为 true，即可让它按访问顺序维护链表。访问顺序的原理上并不复杂，当我们调用get/getOrDefault/replace等方法时，只需要将这些方法访问的节点移动到链表的尾部即可。我们来看看LinkedHashMap（jdk1.8）的源码

public V get(Object key) {
           Node
   
     e;        if ((e = getNode(hash(key), key)) == null)            return null;            // 如果 accessOrder 为 true，则调用 afterNodeAccess 将被访问节点移动到链表最后        if (accessOrder)            afterNodeAccess(e);        return e.value;    }void afterNodeAccess(Node
    
      e) {
    // move node to last        LinkedHashMap.Entry
     
       last;        if (accessOrder && (last = tail) != e) {
               LinkedHashMap.Entry
      
        p =                (LinkedHashMap.Entry
       
        )e, b = p.before, a = p.after;            p.after = null;            // 如果 b 为 null，表明 p 为头节点            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 接在链表的最后                p.before = last;                last.after = p;            }            tail = p;            ++modCount;        }    }

我们来看看LinkedHashMap是什么时候删除的呢？

void afterNodeInsertion(boolean evict) {
    // possibly remove eldest        LinkedHashMap.Entry
   
     first;        //根据条件判断是否移除最近最少被访问的节点        if (evict && (first = head) != null && removeEldestEntry(first)) {
               K key = first.key;            removeNode(hash(key), key, null, false, true);        }    }    // 移除最近最少被访问条件之一，通过覆盖此方法可实现不同策略的缓存    protected boolean removeEldestEntry(Map.Entry
    
      eldest) {
           return false;    }

上面的代码就是通过一些条件，判断是否移除最近最少被访问的节点。当我们基于 LinkedHashMap 实现缓存时，通过覆写removeEldestEntry方法可以实现自定义策略的 LRU 缓存。比如我们可以根据节点数量判断是否移除最近最少被访问的节点，或者根据节点的存活时间判断是否移除该节点等。

扩展：

LRU-K

LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。

相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。数据第一次被访问时，加入到历史访问列表，如果在访问历史列表中没有达到K次访问，则按照一定的规则（FIFO,LRU）淘汰；当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列中删除，将数据移到缓存队列中，并缓存数据，缓存队列重新按照时间排序；缓存数据队列中被再次访问后，重新排序，需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即“淘汰倒数K次访问离现在最久的数据”。LRU-K具有LRU的优点，同时还能避免LRU的缺点，实际应用中LRU-2是综合最优的选择。由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象，因此内存消耗会比LRU要多。

转载地址：http://siwtb.baihongyu.com/

你可能感兴趣的文章