實(shí)現(xiàn)方法：1、LinkedHashMap。2、雙向鏈表+Map
cache寫機(jī)制：Write-through、write-behind、write-around、cache-aside

1、LinkedHashMap

構(gòu)造函數(shù)如下：

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

accessOrder默認(rèn)是false，是按照加入順序存儲(chǔ)的，傳入true即設(shè)置為按照最新訪問(wèn)順序存儲(chǔ)。
LinkedHashMap使用雙向鏈表來(lái)存儲(chǔ)LRU的訪問(wèn)順序，使用父類即HashMap來(lái)的結(jié)構(gòu)來(lái)保存數(shù)據(jù)，比如雙向鏈表定義如下：

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實(shí)現(xiàn) 中，最后一行為

afterNodeInsertion(evict);

該函數(shù)由子類實(shí)現(xiàn)，在LinkedHashMap中該函數(shù)實(shí)現(xiàn)了移除最久未使用元素的功能：

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的形式實(shí)現(xiàn)LRU緩存的，那如果自己實(shí)現(xiàn)應(yīng)該怎么寫呢？
一般遇到的使用緩存有很多種場(chǎng)景，比如為了減少讀數(shù)據(jù)庫(kù)操作，下面的例子就是對(duì)應(yīng)這種場(chǎng)景。還有比如重量級(jí)對(duì)象重用，這個(gè)就是cache沒(méi)有的時(shí)候就new一個(gè)，同時(shí)更新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關(guān)閉前將cache的數(shù)據(jù)保存到數(shù)據(jù)庫(kù)
    }

    public DSimpleJob get(String key) {
        if(cache.containsKey(key)) {
            resetToHead(key);
            return cache.get(key);
        } else {         //這里可以不實(shí)現(xiàn)直接返回null，由調(diào)用者自己從數(shù)據(jù)庫(kù)讀，然后自己調(diào)用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) {
        //這里應(yīng)該是從數(shù)據(jù)庫(kù)讀，然后更新，這里為了方便直接new一個(gè)了
        DSimpleJob index = new DSimpleJob();
        cache.put(key,index);
        return index;
    }

    public void setCapcity(int capcity) {
        if(this.capcity>capcity) {
            flushCache();   //將緩存數(shù)據(jù)更新到數(shù)據(jù)庫(kù)
            decreaseCap();
        } else {
            this.capcity = capcity;
        }
    }

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