Java中的LRU Cache实现与LinkedHashMap

实现方法：1、LinkedHashMap。2、双向链表+Map
cache写机制：Write-through、write-behind、write-around、cache-aside

1、LinkedHashMap

构造函数如下：

 public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

accessOrder默认是false，是按照加入顺序存储的，传入true即设置为按照最新访问顺序存储。
LinkedHashMap使用双向链表来存储LRU的访问顺序，使用父类即HashMap来的结构来保存数据，比如双向链表定义如下：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;   //********
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

在HashMap的put实现 中，最后一行为

afterNodeInsertion(evict);

该函数由子类实现，在LinkedHashMap中该函数实现了移除最久未使用元素的功能：

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);
    }
}

2、双向链表+Map

可以看出LinkedHashMap就是使用双向链表+Map的形式实现LRU缓存的，那如果自己实现应该怎么写呢？
一般遇到的使用缓存有很多种场景，比如为了减少读数据库操作，下面的例子就是对应这种场景。还有比如重量级对象重用，这个就是cache没有的时候就new一个，同时更新cache。

package com.timer.database;
import com.timer.database.bean.DSimpleJob;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LRUCache {

    private Map<String,DSimpleJob> cache = new HashMap<>();
    private LinkedList<String> list = new LinkedList<>();
    private int capcity;

    LRUCache(int capcity){
        this.capcity = capcity;
        Runtime.getRuntime().addShutdownHook(new Thread(this::flushCache));  //保证在JVM关闭前将cache的数据保存到数据库
    }

    public DSimpleJob get(String key) {
        if(cache.containsKey(key)) {
            resetToHead(key);
            return cache.get(key);
        } else {         //这里可以不实现直接返回null，由调用者自己从数据库读，然后自己调用set更新cache
            if(cache.size()<capcity) {
                resetToHead(key);
                return insertNew(key);
            }else {
                cacheFull();
                return  insertNew(key);
            }
        }
    }

    public void set(String key,DSimpleJob simpleJob) {
        if(cache.containsKey(key)) {
            resetToHead(key);
            return;
        }

        if(cache.size()<capcity) {
            resetToHead(key);
        }else {
            cacheFull();
            resetToHead(key);
        }
        cache.put(key,simpleJob);
    }

    private void resetToHead(String key) {
        list.remove(key);
        list.addFirst(key);
    }

    private void cacheFull() {
        String oldest = list.removeLast();
        cache.remove(oldest);
    }

    private DSimpleJob insertNew(String key) {
        //这里应该是从数据库读，然后更新，这里为了方便直接new一个了
        DSimpleJob index = new DSimpleJob();
        cache.put(key,index);
        return index;
    }

    public void setCapcity(int capcity) {
        if(this.capcity>capcity) {
            flushCache();   //将缓存数据更新到数据库
            decreaseCap();
        } else {
            this.capcity = capcity;
        }
    }

    public void clear() {
        flushCache();
        list.clear();
        cache.clear();
    }
    private void flushCache() {
        //....
    }
}