LinkedHashMap是Java集合中一個常用的容器，它繼承了HashMap, 是一個有序的Hash表。那么該如何基于LinkedHashMap實現(xiàn)一個LRU緩存呢？這也是面試經(jīng)常被問到的題目，主要是考察你對Java集合容器的了解程度以及LinkedHashMap的實現(xiàn)原理。

分析

什么是LRU?

LRU（Least Recently Used）指的是最近最少使用，是一種緩存淘汰算法，淘汰掉那個最少使用的的數(shù)據(jù)。

LinkedHashMap是有序的，它默認通過雙向鏈表維護元素的插入順序，同時，通過構(gòu)造函數(shù)設(shè)置accessOrder屬性為true的情況，維護元素的訪問順序，這里的訪問包括插入、修改、查詢等元素，每次操作都會記錄順序，所以LRU緩存其實是包括訪問的，所以我們需要通過構(gòu)造函數(shù)設(shè)置LinkedHashMap設(shè)置accessOrder為true。
已經(jīng)解決了順序的問題，也就是最近訪問的會在雙向鏈表的尾部，最老的數(shù)據(jù)會在頭部。那么如何刪除頭部的元素呢？其實LinkedHashMap也提供了一個回調(diào)函數(shù)removeEldestEntry，它也會在添加元素的時候調(diào)用，默認返回false，我們可以通過重寫這個方法的邏輯，如果LinkedHashMap大于緩存指定數(shù)量，就進行淘汰。

LRU緩存實現(xiàn)

場景：我們需要設(shè)計一個緩存最多只能存儲10個元素，當(dāng)元素個數(shù)超過10的時候，刪除（淘汰）那些最近最少使用的數(shù)據(jù)，僅保存熱點數(shù)據(jù)。

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

    /**
     * 緩存允許的最大容量
     */
    private final int maxSize;

    public LRUCache(int initialCapacity, int maxSize) {
        // accessOrder必須為true
        super(initialCapacity, 0.75f, true);
        this.maxSize = maxSize;
    }

    // 重寫
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 當(dāng)鍵值對個數(shù)超過最大容量時，返回true，觸發(fā)刪除操作
        return size() > maxSize;
    }

    public static void main(String[] args) {
        LRUCache<String, String> cache = new LRUCache<>(5, 5);
        cache.put("1", "1");
        cache.put("2", "2");
        cache.put("3", "3");
        cache.put("4", "4");
        // 做一次查詢
        cache.get("1");
        cache.put("5", "5");
        cache.put("6", "6");
        cache.put("7", "7");
        System.out.println(cache);
    }

}

運行結(jié)果：