缓存算法——LRU算法编码实现（Java版）

LRU算法（Last Recently Used），是缓存淘汰算法的其中一种，即最近最久未使用。

在操作系统的内存管理中，有一类很重要的算法就是内存页面置换算法（包括FIFO，LRU,LFU等几种常见页面置换算法）。

事实上，Cache算法和内存页面置换算法的核心思想是一样的：都是在给定一个限定大小的空间的前提下，设计一个原则如何来更新和访问其中的元素。

下面说一下LRU算法的核心思想，LRU算法的设计原则是：
如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰

这里提供两种使用Java的实现方式

---

使用LinkedHashMap

具体实现源码：

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

    private final int CACHE_SIZE;


    /**
     * 构造器，构造缓存的大小，即最多能缓存多少参数
     *
     * 初始化的 initialCapacity 结果+1，是为了在cacheSize小于0.75时除的结果为0，但是这时候要有能存储的元素，所以+1
     * accessOrder：控制访问顺序。用于设置LinkedHashMap在调用 get() 之后的操作。如果设置为true，则每次调用get后会将该元素移动到末尾
     * removeEldestEntry：默认返回为false，在调用 afterNodeInsertion()的内部，调用该方法。也就是说，每次添加元素之后，检查并移除最后一个元素
     *
     *
     * @param cacheSize
     */
    public LRUCache(int cacheSize) {
        super((int) Math.ceil(cacheSize / 0.75)+1, 0.75F, true);
        CACHE_SIZE = cacheSize;
    }

    /**
     * 重写removeEldestEntry
     * 当map中的数据大于指定缓存大小的时候，就删除最老的数据
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > CACHE_SIZE;
    }
}

LinkedHashMap中关键方法的源码：

    // 添加Node之后的操作，可以看到调用了 removeEldestEntry，移除头部元素
    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);
        }
    }

    // 访问Node之后的操作，可以看到，当设置了accessOrder以后，访问元素之后，会把该Node放到尾部
    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事实上已经提供了内存置换的功能，我们利用了其中内置的功能并重写了部分方法后，实现了LRUCache。

需要注意两点：
1、构造器中调用父方法的第三个参数 accessOrder（默认为false），通过源码注释可以知道，这个表示元素的访问模式。true为access-order，false为insertion-order
当accessOrder=true时，用于搭配方法 removeEldestEntry(Map.Entry<K, V> eldest) 使用。

2、受保护方法 removeEldestEntry(Map.Entry<K, V> eldest)，用于判断是否移除最老一个元素。使得Cache可以在元素满之后移除最老的元素。

---

使用HashMap 编码实现LRUCache

具体实现源码：

public class LRUCacheCustom<K,V> {

    // 双链表
    static class CacheNode{
        CacheNode before;
        CacheNode after;
        Object key;
        Object val;
        public CacheNode(){}
    }

    /** 头节点 */
    private CacheNode head;
    /** 尾节点 */
    private CacheNode tail;

    /** 最大元素数 */
    private int maxCapacity;

    /** 用于存储节点数据 */
    private HashMap<K, CacheNode> caches;


    /** 初始化 */
    public LRUCacheCustom(int maxCapacity){
        this.maxCapacity = maxCapacity;
        caches = new HashMap<>(maxCapacity);
        head = new CacheNode();
        tail = new CacheNode();
        head.after = tail;
        tail.before = head;
    }


    public void put(K k, V v){
        CacheNode node = caches.get(k);
        if(node == null){
            node = new CacheNode();
            node.key = k;
        }

        node.val = v;
        moveToFirst(node);
        caches.put(k, node);

        if(caches.size() > maxCapacity){
            caches.remove(tail.before.key);
            removeLast();
        }
    }


    public V get(K k){
        CacheNode node = caches.get(k);
        if(node == null){
            return null;
        }
        Object val = node.val;
        moveToFirst(node);
        return (V) val;
    }


    public void removeLast(){
        CacheNode last = tail.before;
        CacheNode secondLast = tail.before.before;
        secondLast.after = tail;
        tail.before = secondLast;

        // 手动释放内存
        caches.remove(last.key);
        last = null;
    }

    public void moveToFirst(CacheNode node){
        // 先把原来node的前后连起来，如果前后不为null的话。（注意顺序不能错）
        CacheNode nodeBefore = node.before;
        if(node.after != null){
            node.after.before = nodeBefore;
        }
        if(nodeBefore != null ){
            nodeBefore.after = node.after;
        }

        // 然后把node放前面
        CacheNode tmp = head.after;
        head.after = node;
        node.before = head;
        tmp.before = node;
        node.after = tmp;
    }


    @Override
    public String toString() {
        return caches.toString();
    }

    public String getCache(){
        StringBuilder bu = new StringBuilder();
        CacheNode dummy = head;
        while(dummy.after != null){
            bu.append("{key=" + dummy.key);
            bu.append(", val=" + dummy.val);
            bu.append("\n -->");
            dummy = dummy.after;
        }
        return bu.toString();
    }
}

以上代码我已经自测通过
测试代码：

    @Test
    public void lruCacheTest(){
        LRUCacheCustom cacheCustom = new LRUCacheCustom(3);
        cacheCustom.put(1,"AAA");
        cacheCustom.put(2,"BBB");
        cacheCustom.put(3,"CCC");
        System.out.println(cacheCustom.getCache()); // 3 2 1

        cacheCustom.put(4,"DDD");
        System.out.println(cacheCustom.getCache()); // 4 3 2

        // get(2) 将2提升到顶部
        cacheCustom.get(2);
        System.out.println(cacheCustom.getCache()); // 2 4 3

        cacheCustom.put(5,"DDD");
        System.out.println(cacheCustom.getCache()); // 5 2 4
    }

---

参考：
LRU Cache