參考:
緩存算法(頁面替換算法)-LRU LFU FIFO
LRU(最近最少使用)算法根據數據的歷史訪問記錄來刪除數據。其核心思想是，如果壹個數據最近沒有被訪問過，那麽以後也不太可能被訪問。也就是說，當有限的空間被數據填滿時，最長時間沒有被訪問的數據應該被淘汰。
假設序列是4 3 4 2 3 1 4 2。
有三個物理塊。
第壹輪4個調用進入內存4
次級輪3調用存儲器3 4
然後4個調用進入內存4 3
然後2調用內存2 4 3
之後，3調用內存3 2 4
之後將1轉入內存1 3 2 (4因為用的最少所以丟棄)。
之後會轉到內存4 1 3(原理同上)。
最後，2被轉移到內存2 4 1中。
如果我們設計壹個LRU緩存的數據結構，它應該支持兩種操作:
壹種是使用array存儲每個數據項，然後將壹個時間戳與每個鍵相關聯，並在緩存中維護壹個最大時間戳。其設計要點如下:
另壹種是采用hashmap+雙向鏈表的數據結構，其設計要點如下:
對比上壹節的兩種設計思路，不難發現1的設計需要為每個鍵維護壹個時間戳，set和get操作的時間復雜度為O(n)。顯然，隨著數據量的增加，set和get操作的速度越來越慢。在設計2中，使用hashmap+鏈表，set和get操作的時間復雜度僅為O(1)。設計2的具體實現如下。
運行結果如下:
參考:
LRU高速緩存
LRU原理與Redis實現——今日頭條訪談問題