前言

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

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

但是內(nèi)存容量是有限的，當(dāng)你要緩存的數(shù)據(jù)超出容量，就得有部分數(shù)據(jù)刪除，這時候哪些數(shù)據(jù)刪除，哪些數(shù)據(jù)保留，就是LRU算法和LFU算法要干的事。

什么是LRU算法

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

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

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

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

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

這種實現(xiàn)的結(jié)構(gòu)如下：

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

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

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

那使用單鏈表不行嗎？

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

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

關(guān)于這種方式的源碼實現(xiàn)，可以查看Leetcode LRU雙向鏈表實現(xiàn)

LFU算法，全稱Least frequently used，即最不經(jīng)常使用。LFU算法的思想是一定時期內(nèi)被訪問次數(shù)最少的節(jié)點，在將來被訪問到的幾率也是最小的。

由此可以看到，LFU強調(diào)的是訪問次數(shù)，而LRU強調(diào)的是訪問時間。

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

雙哈希表的實現(xiàn)如下圖：

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

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

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

類比LRU，LFU的步驟如下：

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