作者：labuladong

上篇文章算法題就像搭樂高：手把手帶你拆解 LRU 算法寫了 LRU 緩存淘汰算法的實現(xiàn)方法，本文來寫另一個著名的緩存淘汰算法：LFU 算法。

從實現(xiàn)難度上來說，LFU 算法的難度大于 LRU 算法，因為 LRU 算法相當(dāng)于把數(shù)據(jù)按照時間排序，這個需求借助鏈表很自然就能實現(xiàn)，你一直從鏈表頭部加入元素的話，越靠近頭部的元素就是新的數(shù)據(jù)，越靠近尾部的元素就是舊的數(shù)據(jù)，我們進(jìn)行緩存淘汰的時候只要簡單地將尾部的元素淘汰掉就行了。

而 LFU 算法相當(dāng)于是淘汰訪問頻次最低的數(shù)據(jù)，如果訪問頻次最低的數(shù)據(jù)有多條，需要淘汰最舊的數(shù)據(jù)。把數(shù)據(jù)按照訪問頻次進(jìn)行排序，而且頻次還會不斷變化，這可不容易實現(xiàn)。

所以說 LFU 算法要復(fù)雜很多，labuladong 進(jìn)字節(jié)跳動的時候就被面試官問到了 LFU 算法。

話說回來，這種著名的算法的套路都是固定的，關(guān)鍵是由于邏輯較復(fù)雜，不容易寫出漂亮且沒有 bug 的代碼。

那么本文 labuladong 就帶你拆解 LFU 算法，自頂向下，逐步求精。

一、算法描述

要求你寫一個類，接受一個capacity參數(shù)，實現(xiàn)get和put方法：

classLFUCache{
//構(gòu)造容量為capacity的緩存
publicLFUCache(intcapacity){}
//在緩存中查詢key
publicintget(intkey){}
//將key和val存入緩存
publicvoidput(intkey,intval){}
}

get(key)方法會去緩存中查詢鍵key，如果key存在，則返回key對應(yīng)的val，否則返回 -1。

put(key, value)方法插入或修改緩存。如果key已存在，則將它對應(yīng)的值改為val；如果key不存在，則插入鍵值對(key, val)。

當(dāng)緩存達(dá)到容量capacity時，則應(yīng)該在插入新的鍵值對之前，刪除使用頻次（后文用freq表示）最低的鍵值對。如果freq最低的鍵值對有多個，則刪除其中最舊的那個。

//構(gòu)造一個容量為2的LFU緩存
LFUCachecache=newLFUCache(2);

//插入兩對(key,val)，對應(yīng)的freq為1
cache.put(1,10);
cache.put(2,20);

//查詢key為1對應(yīng)的val
//返回10，同時鍵1對應(yīng)的freq變?yōu)?
cache.get(1);

//容量已滿，淘汰freq最小的鍵2
//插入鍵值對(3,30)，對應(yīng)的freq為1
cache.put(3,30);

//鍵2已經(jīng)被淘汰刪除，返回-1
cache.get(2);

二、思路分析

一定先從最簡單的開始，根據(jù) LFU 算法的邏輯，我們先列舉出算法執(zhí)行過程中的幾個顯而易見的事實：

1、調(diào)用get(key)方法時，要返回該key對應(yīng)的val。

2、只要用get或者put方法訪問一次某個key，該key的freq就要加一。

3、如果在容量滿了的時候進(jìn)行插入，則需要將freq最小的key刪除，如果最小的freq對應(yīng)多個key，則刪除其中最舊的那一個。

好的，我們希望能夠在 O(1) 的時間內(nèi)解決這些需求，可以使用基本數(shù)據(jù)結(jié)構(gòu)來逐個擊破：

1、使用一個HashMap存儲key到val的映射，就可以快速計算get(key)。

HashMapkeyToVal;

2、使用一個HashMap存儲key到freq的映射，就可以快速操作key對應(yīng)的freq。

HashMapkeyToFreq;

3、這個需求應(yīng)該是 LFU 算法的核心，所以我們分開說。

3.1、首先，肯定是需要freq到key的映射，用來找到freq最小的key。

3.2、將freq最小的key刪除，那你就得快速得到當(dāng)前所有key最小的freq是多少。想要時間復(fù)雜度 O(1) 的話，肯定不能遍歷一遍去找，那就用一個變量minFreq來記錄當(dāng)前最小的freq吧。

3.3、可能有多個key擁有相同的freq，所以freq對key是一對多的關(guān)系，即一個freq對應(yīng)一個key的列表。

3.4、希望freq對應(yīng)的key的列表是存在時序的，便于快速查找并刪除最舊的key。

3.5、希望能夠快速刪除key列表中的任何一個key，因為如果頻次為freq的某個key被訪問，那么它的頻次就會變成freq+1，就應(yīng)該從freq對應(yīng)的key列表中刪除，加到freq+1對應(yīng)的key的列表中。

HashMap>freqToKeys;
intminFreq=0;

介紹一下這個LinkedHashSet，它滿足我們 3.3，3.4，3.5 這幾個要求。你會發(fā)現(xiàn)普通的鏈表LinkedList能夠滿足 3.3，3.4 這兩個要求，但是由于普通鏈表不能快速訪問鏈表中的某一個節(jié)點，所以無法滿足 3.5 的要求。

LinkedHashSet顧名思義，是鏈表和哈希集合的結(jié)合體。鏈表不能快速訪問鏈表節(jié)點，但是插入元素具有時序；哈希集合中的元素?zé)o序，但是可以對元素進(jìn)行快速的訪問和刪除。

那么，它倆結(jié)合起來就兼具了哈希集合和鏈表的特性，既可以在 O(1) 時間內(nèi)訪問或刪除其中的元素，又可以保持插入的時序，高效實現(xiàn) 3.5 這個需求。

綜上，我們可以寫出 LFU 算法的基本數(shù)據(jù)結(jié)構(gòu)：

classLFUCache{
//key到val的映射，我們后文稱為KV表
HashMapkeyToVal;
//key到freq的映射，我們后文稱為KF表
HashMapkeyToFreq;
//freq到key列表的映射，我們后文稱為FK表
HashMap>freqToKeys;
//記錄最小的頻次
intminFreq;
//記錄LFU緩存的最大容量
intcap;

publicLFUCache(intcapacity){
keyToVal=newHashMap<>();
keyToFreq=newHashMap<>();
freqToKeys=newHashMap<>();
this.cap=capacity;
this.minFreq=0;
}

publicintget(intkey){}

publicvoidput(intkey,intval){}

}

三、代碼框架

LFU 的邏輯不難理解，但是寫代碼實現(xiàn)并不容易，因為你看我們要維護(hù)KV表，KF表，F(xiàn)K表三個映射，特別容易出錯。對于這種情況，labuladong 教你三個技巧：

1、不要企圖上來就實現(xiàn)算法的所有細(xì)節(jié)，而應(yīng)該自頂向下，逐步求精，先寫清楚主函數(shù)的邏輯框架，然后再一步步實現(xiàn)細(xì)節(jié)。

2、搞清楚映射關(guān)系，如果我們更新了某個key對應(yīng)的freq，那么就要同步修改KF表和FK表，這樣才不會出問題。

3、畫圖，畫圖，畫圖，重要的話說三遍，把邏輯比較復(fù)雜的部分用流程圖畫出來，然后根據(jù)圖來寫代碼，可以極大減少出錯的概率。

下面我們先來實現(xiàn)get(key)方法，邏輯很簡單，返回key對應(yīng)的val，然后增加key對應(yīng)的freq：

publicintget(intkey){
if(!keyToVal.containsKey(key)){
return-1;
}
//增加key對應(yīng)的freq
increaseFreq(key);
returnkeyToVal.get(key);
}

增加key對應(yīng)的freq是 LFU 算法的核心，所以我們干脆直接抽象成一個函數(shù)increaseFreq，這樣get方法看起來就簡潔清晰了對吧。

下面來實現(xiàn)put(key, val)方法，邏輯略微復(fù)雜，我們直接畫個圖來看：

這圖就是隨手畫的，不是什么正規(guī)的程序流程圖，但是算法邏輯一目了然，看圖可以直接寫出put方法的邏輯：

publicvoidput(intkey,intval){
if(this.cap<=?0)?return;

????/*?若?key?已存在，修改對應(yīng)的?val?即可?*/
????if?(keyToVal.containsKey(key))?{
????????keyToVal.put(key,?val);
????????//?key?對應(yīng)的?freq?加一
????????increaseFreq(key);
????????return;
????}

????/*?key?不存在，需要插入?*/
????/*?容量已滿的話需要淘汰一個?freq?最小的?key?*/
????if?(this.cap?<=?keyToVal.size())?{
????????removeMinFreqKey();
????}

????/*?插入?key?和?val，對應(yīng)的?freq?為?1?*/
????//?插入?KV?表
????keyToVal.put(key,?val);
????//?插入?KF?表
????keyToFreq.put(key,?1);
????//?插入?FK?表
????freqToKeys.putIfAbsent(1,?new?LinkedHashSet<>());
freqToKeys.get(1).add(key);
//插入新key后最小的freq肯定是1
this.minFreq=1;
}

increaseFreq和removeMinFreqKey方法是 LFU 算法的核心，我們下面來看看怎么借助KV表，KF表，F(xiàn)K表這三個映射巧妙完成這兩個函數(shù)。

四、LFU 核心邏輯

首先來實現(xiàn)removeMinFreqKey函數(shù)：

privatevoidremoveMinFreqKey(){
//freq最小的key列表
LinkedHashSetkeyList=freqToKeys.get(this.minFreq);
//其中最先被插入的那個key就是該被淘汰的key
intdeletedKey=keyList.iterator().next();
/*更新FK表*/
keyList.remove(deletedKey);
if(keyList.isEmpty()){
freqToKeys.remove(this.minFreq);
//問：這里需要更新 minFreq 的值嗎？
}
/*更新KV表*/
keyToVal.remove(deletedKey);
/*更新KF表*/
keyToFreq.remove(deletedKey);
}

刪除某個鍵key肯定是要同時修改三個映射表的，借助minFreq參數(shù)可以從FK表中找到freq最小的keyList，根據(jù)時序，其中第一個元素就是要被淘汰的deletedKey，操作三個映射表刪除這個key即可。

但是有個細(xì)節(jié)問題，如果keyList中只有一個元素，那么刪除之后minFreq對應(yīng)的key列表就為空了，也就是minFreq變量需要被更新。如何計算當(dāng)前的minFreq是多少呢？

實際上沒辦法快速計算minFreq，只能線性遍歷FK表或者KF表來計算，這樣肯定不能保證 O(1) 的時間復(fù)雜度。

但是，其實這里沒必要更新minFreq變量，因為你想想removeMinFreqKey這個函數(shù)是在什么時候調(diào)用？在put方法中插入新key時可能調(diào)用。而你回頭看put的代碼，插入新key時一定會把minFreq更新成 1，所以說即便這里minFreq變了，我們也不需要管它。

下面來實現(xiàn)increaseFreq函數(shù)：

privatevoidincreaseFreq(intkey){
intfreq=keyToFreq.get(key);
/*更新KF表*/
keyToFreq.put(key,freq+1);
/*更新FK表*/
//將key從freq對應(yīng)的列表中刪除
freqToKeys.get(freq).remove(key);
//將key加入freq+1對應(yīng)的列表中
freqToKeys.putIfAbsent(freq+1,newLinkedHashSet<>());
freqToKeys.get(freq+1).add(key);
//如果freq對應(yīng)的列表空了，移除這個freq
if(freqToKeys.get(freq).isEmpty()){
freqToKeys.remove(freq);
//如果這個freq恰好是minFreq，更新minFreq
if(freq==this.minFreq){
this.minFreq++;
}
}
}

更新某個key的freq肯定會涉及FK表和KF表，所以我們分別更新這兩個表就行了。

和之前類似，當(dāng)FK表中freq對應(yīng)的列表被刪空后，需要刪除FK表中freq這個映射。如果這個freq恰好是minFreq，說明minFreq變量需要更新。

能不能快速找到當(dāng)前的minFreq呢？這里是可以的，因為我們剛才把key的freq加了 1 嘛，所以minFreq也加 1 就行了。

至此，經(jīng)過層層拆解，LFU 算法就完成了。