简单几步，实现自己的LRU算法

2020-06-08 本文已影响0人站在海边看远方

LRU算法，即least recently used ，最近最少使用，LRU算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
LRU算法通常用于缓存的淘汰策略实现，由于缓存的内存非常宝贵，所以需要根据某种规则来剔除数据保证内存不被撑满。

我们下面来介绍一种最简单的实现LRU的方法。

代码实现

最简单的实现方式就是使用LinkedHashMap

public class LRUCache<K,V> extends LinkedHashMap<K,V> {

    private final int CACHE_SIZE;

    public LRUCache(int cacheSize) {
        //true 表示让 LinkedHashMap 按照访问顺序来进行排序，最近访问的放在头部，最老访问的放在尾部
        super((int) (Math.ceil(cacheSize/0.75)+1),0.75f,true);
        CACHE_SIZE = cacheSize;
    }
     @Override
     protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        // 当 map 中的数据量大于指定的缓存个数的时候，就自动删除最老的数据。
        return size() > CACHE_SIZE;
     }
}

全部代码如上所示，非常的简洁，不超过10行。
其中有几个点

初始化时，LinkedHashMap的accessOrder参数需要设置成true,表示map元素按照访问顺序进行排序，false表示按照插入顺序进行排序。
2.需要重写removeEldestEntry()方法。

演示效果

我们来演示一下上面的LRU实现，看看能不能达到我们实现LRU的目的。
首先来看一下缓存超出容量最大值的情况

public class LRUCache<K,V> extends LinkedHashMap<K,V> {

   private final int CACHE_SIZE;

   public LRUCache(int cacheSize) {
       //true 表示让 LinkedHashMap 按照访问顺序来进行排序，最近访问的放在头部，最老访问的放在尾部
       super((int) (Math.ceil(cacheSize/0.75)+1),0.75f,true);
       CACHE_SIZE = cacheSize;
   }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
       return size() > CACHE_SIZE;
    }

   public static void main(String[] args) {
        //设置最多缓存3条数据
       LRUCache<String, Integer> lruCache = new LRUCache<>(3);
       lruCache.put("1",1);
       lruCache.put("2",2);
       lruCache.put("3",3);
       for (Map.Entry<String,Integer> e :lruCache.entrySet()) {
           System.out.println(e.getKey()+" : "+e.getValue()+"\t");
       }
       System.out.println(" ");
       
       //缓存满，插入底条数据
       lruCache.put("4",4);

       for (Map.Entry<String,Integer> e :lruCache.entrySet()) {
           System.out.println(e.getKey()+" : "+e.getValue()+"\t");
       }

   }
}

//输出结果，缓存未超过最大容量时，输出顺序如下所示，缓存超过最大容量，删除一条数据
1 : 1   
2 : 2   
3 : 3   

2 : 2   
3 : 3   
4 : 4

从上面的代码看实现了我们在缓存容量超出阈值时删除数据的情况。
下面我们再来看一下访问元素之后，map中元素的排序情况。

public static void main(String[] args) {
        LRUCache<String, Integer> lruCache = new LRUCache<>(3);
        lruCache.put("1",1);
        lruCache.put("2",2);
        lruCache.put("3",3);
        for (Map.Entry<String,Integer> e :lruCache.entrySet()) {
            System.out.println(e.getKey()+" : "+e.getValue()+"\t");
        }
        System.out.println(" ");

        //lruCache.put("4",4);
        lruCache.get("1");

        for (Map.Entry<String,Integer> e :lruCache.entrySet()) {
            System.out.println(e.getKey()+" : "+e.getValue()+"\t");
        }

 }
//输出
1 : 1   
2 : 2   
3 : 3   
 
2 : 2   
3 : 3   
1 : 1

我们访问了key 1，然后map里的元素顺序就调整了。

原理分析

上面我们利用LinkedHashMap简单实现了一下LRU，其中有2个注意点.
一个是LinkedHashMap构造函数中有一个accessOrder要设置成true，表示按照访问顺序排序。看一下LinkedHashMap中这个成员变量的定义。

   /**
    * The iteration ordering method for this linked hash map: <tt>true</tt>
    * for access-order, <tt>false</tt> for insertion-order.
    *
    * @serial
    */
    final boolean accessOrder;

另一个是要重写removeEldestEntry()方法，自定义缓存超出容量的删除策略，我们在上面的实现中判断map.size()是否大于CACHE_SIZE，即map中元素的个数是否超过我们定义的缓存个数最大值，如果比较结果为true,则删除元素，如果为false，则不删除元素。

我们自己实现LRU的时候只需要实现2个条件即可。

源码解析

LinkedHashMap内部维护了一个双向链表，通过accessOrder控制。

元素访问

我们从get方法往里看源码是如何实现的，下面的代码基于jdk1.8。

public V get(Object key) {
        Node<K,V> e;
        //根据key取hash定位node，如果查不到就返回null
        if ((e = getNode(hash(key), key)) == null)
            return null;
        // 如果accessOrder为true
        if (accessOrder)
            //执行此方法
            afterNodeAccess(e);
        return e.value;
    }

LinkedHashMap的get方法也不难，key经过hash查找node，查不到直接返回null,如果查的到，判断是否为accessOrder，然后执行afterNodeAccess方法。
看这个方法之前，我们先来看2个成员变量,根据注释，我们可以看到head存放的是最老的数据，tail存放的是最新的数据

   /**
     * The head (eldest) of the doubly linked list.
   */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
    */
    transient LinkedHashMap.Entry<K,V> tail;

我们来看一下afterNodeAccess这个方法，第一行的注释即表明要将传入的node放到最后

void afterNodeAccess(Node<K,V> e) { // move node to last
        //先定义一个临时变量last
        LinkedHashMap.Entry<K,V> last;
        //如果accessOrder=true &&访问的node e不是尾节点
        if (accessOrder && (last = tail) != e) {
            //将e赋值给变量p,b是p的前驱节点，a是p的后继节点
            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;
            }
            //将p赋值给tail
            tail = p;
            ++modCount;
        }
 }

我们插入的时候，head=("1",1),tail=("3",3),现在get方法访问key=1的node,if条件为true，进入到if语句里面