前言

LRU算法和LFU算法是屬于頁面置換的一種算法，或者更通俗的說，就是緩存如何淘汰的一種策略。

我們通常在設計一個系統的時候，由于數據庫的讀取速度遠小于內存的讀取速度，所以為了加快讀取速度，會將一部分數據放到內存中，稱為緩存。

但是內存容量是有限的，當你要緩存的數據超出容量，就得有部分數據刪除，這時候哪些數據刪除，哪些數據保留，就是LRU算法和LFU算法要干的事。

什么是LRU算法

LRU算法，全稱Least recently used，即最近最少使用。LRU算法的思想是如果數據最近被訪問過，那么將來被訪問的概率也會很高。

根據這個思想，我們可以想到，實現LRU算法肯定會用到列表/鏈表，目的是保證有序；還有一個是用到哈希表，這是因為緩存經常是key-value鍵值對的形式。

比較簡單的做法是使用列表+哈希表，但是這種方式查詢和插入的時間復雜度都是O(n)，還有一種做法是使用雙向鏈表+哈希表，查詢和插入的時間復雜度都是O(1)，但是耗費的空間資源比較多。

列表+哈希表的實現

如上圖，假設我們使用頭插法，即最近訪問的元素放在最前面，最晚的元素放在最后面，則實現LRU算法的步驟如下：

• 1.初始化一個空列表，如上圖，其容器為5。
• 2.當執行查找（GET）操作時，需要遍歷整個列表，找到key相同的元素，時間復雜度為O(n)
• 3.當執行插入（PUT）操作時，有三種情況：
• 3.1 遍歷列表，如果元素的key存在，更新value的值，并把這個元素放到列表的最前面，從而保證最后面的元素是最晚訪問的。
• 3.2 遍歷列表，如果元素的key不存在，且列表的容量未滿，則把這個元素放到列表的最前面
• 3.3 遍歷列表，如果元素的key不存在，且列表的容量已滿，刪除最后的元素，并把新元素放到最前面

雙向鏈表+哈希表的實現

這應該是面試比較常考的點，面試官可能會問你，如果實現一個時間復雜度為O(1)的LRU緩存？

這種實現的結構如下：

上述LRUCache的m其實就是上圖左邊的HashMap，它的目的是為了實現查找的時間復雜度為O(1)。

如果沒有這個m，則查找元素的時候，需要遍歷雙向鏈表，時間復雜度為O(n)。

而使用雙向鏈表的原因主要是為了實現節點插入/刪除的時間復雜度為O(1)。

那使用單鏈表不行嗎？

如上，使用單鏈表的話，可以實現頭部快速插入新節點，尾部快速刪除舊節點，時間復雜度都是O(1)。

但是對于中間節點，比如我需要節點1的值由2更新為4，這時候除了更新值，還需要將其移動到最前面，而對于單鏈表，它只知道下一個元素，并不知道上一個元素，為了得到上一個元素，它必須遍歷一次鏈表才知道，時間復雜度為O(n)，這就是為什么要用雙向鏈表的原因。

關于這種方式的源碼實現，可以查看Leetcode LRU雙向鏈表實現

什么是LFU算法

LFU算法，全稱Least frequently used，即最不經常使用。LFU算法的思想是一定時期內被訪問次數最少的節點，在將來被訪問到的幾率也是最小的。

由此可以看到，LFU強調的是訪問次數，而LRU強調的是訪問時間。

LFU有兩種實現方式，一是哈希表+平衡二叉樹，二是雙哈希表，下面以雙哈希表為例，說明LFU具體的步驟：

雙哈希表的實現

雙哈希表的實現如下圖：

如上，雙哈希表需要維護兩個哈希表以及一個最少頻次使用的計數minFreq。

第一個哈希表是 freq_table，它的key是訪問的頻次，它的value是一個雙向鏈表，雙向鏈表的每一個節點包含三個元素：key，value，以及count。

第二個哈希表是 key_table，它的key是雙向鏈表中存儲的key，value是對應節點的指針（這樣查找的時間復雜度就是O(1)）。

類比LRU，LFU的步驟如下：

• 1.假設LFU緩存容量為3，且一開始初始化插入三個鍵值對（1，1），（2，2），（3，3）此時每個鍵值對的頻次都是1，所以它們都在同一個雙向鏈表上，如圖四。
• 2.假設這時候查找key=1，由于key_table存儲的是節點的指針，所以可以以O(1)的復雜度得到結果。
• 2.1 注意此時節點1的頻次由1變為2，所以要將節點1移動到頻次為2的鏈表，如圖五
• 2.2 另外，minFreq也要記得同步更新，不過本次操作不用。
• 3.假設這時候插入一個新的鍵值對（4，4），由于它的頻次為1，所以對應鏈表1，它會被插入到鏈表1的最前面，而由于這種操作，所以同鏈表的最后一個元素肯定是最晚插入的。
• 3.1 由于新加的元素導致容量溢出，所以我們要刪除頻次最少，插入時間最晚的，即圖五的（3，3，1）