面試題目:手寫一個LRU算法實現

一、常見的內存淘汰算法

FIFO 先進先出
- 在這種淘汰算法中，先進?緩存的會先被淘汰
- 命中率很低
LRU

- Least recently used，最近最少使?get

- 根據數據的歷史訪問記錄來進?淘汰數據，其核?思想是“如果數據最近被訪問過，那么將來被訪問的?率也更?”

- LRU算法原理剖析

面試題目:手寫一個LRU算法實現-LMLPHP

LFU
- Least Frequently Used
- 算法根據數據的歷史訪問頻率來淘汰數據，其核?思想是“如果數據過去被訪問多次，那么將來被訪問的頻率也更?”

- LFU算法原理剖析

- - 新加?數據插?到隊列尾部（因為引?計數為1）

- - 隊列中的數據被訪問后，引?計數增加，隊列重新排序；
  - 當需要淘汰數據時，將已經排序的列表最后的數據塊刪除。

面試題目:手寫一個LRU算法實現-LMLPHP

LFU的缺點

復雜度
存儲成本
尾部容易被淘汰

二、手寫LRU算法實現

利用了LinkedHashMap雙向鏈表插入可排序

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

    private int cacheSize;

    public LRUCache(int cacheSize) {
        super(16, 0.75f, true);
        this.cacheSize = cacheSize;
    }

    @Override
    public synchronized V get(Object key) {
        return super.get(key);
    }

    @Override
    public synchronized V put(K key, V value) {
        return super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        boolean f = size() > cacheSize;
        if (f) {
            log.info("LRUCache清除第三方密鑰緩存Key:[{}]", eldest.getKey());
        }
        return f;
    }

    public static void main(String[] args) {
        LRUCache<String, Object> cache = new LRUCache<>(5);
        cache.put("A","A");
        cache.put("B","B");
        cache.put("C","C");
        cache.put("D","D");
        cache.put("E","E");
        System.out.println("初始化:" + cache.keySet());
        System.out.println("訪問值:" + cache.get("C"));
        System.out.println("訪問C后:" + cache.keySet());
        System.out.println("PUT F后:" + cache.put("F","F"));
        System.out.println(cache.keySet());
    }

}

main函數執行效果：

面試題目:手寫一個LRU算法實現-LMLPHP

三、注意事項

LinkedHashMap有五個構造函數

面試題目:手寫一個LRU算法實現-LMLPHP

//使用父類中的構造，初始化容量和加載因子，該初始化容量是指數組大小。
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }
//一個參數的構造
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }
//無參構造
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }
//這個不用多說，用來接受map類型的值轉換為LinkedHashMap
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(m);
        accessOrder = false;
    }
//真正有點特殊的就是這個，多了一個參數accessOrder。存儲順序，LinkedHashMap關鍵的參數之一就在這個，
　　//true：指定迭代的順序是按照訪問順序(近期訪問最少到近期訪問最多的元素)來迭代的。 false：指定迭代的順序是按照插入順序迭代，也就是通過插入元素的順序來迭代所有元素
//如果你想指定訪問順序，那么就只能使用該構造方法，其他三個構造方法默認使用插入順序。
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

View Code

　　參數accessOrder。存儲順序，LinkedHashMap關鍵的參數之一就在這個， true：指定迭代的順序是按照訪問順序(近期訪問最少到近期訪問最多的元素)來迭代的。 false：指定迭代的順序是按照插入順序迭代，也就是通過插入元素的順序來迭代所有元素。

　　如果你想指定訪問順序，那么就只能使用該構造方法，其他三個構造方法默認使用插入順序。

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

LinkedHashMap是非線程安全的，需要加互斥鎖解決并發問題。

四、思考

　　需要根據應用場景確定cacheSize大小，如果實際緩存數量過小，會導致緩存中的數據長期得不到刷新，為防止這種或偶發情況的發生，可配合定時任務如起一個newSingleThreadScheduledExecutor，將上面存儲的value修改封裝為一個對象，里面增加一個時間戳儲存，每次訪問實時更新，定時掃描該隊列將最近30分鐘未訪問的key刪除；還需增加一個初始進入隊列的歷史時間記錄，將超過1小時的數據清除。

奕鋒博客