一文讀懂緩存淘汰算法：LFU 算法

作者：labuladong

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

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

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

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

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

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

一、算法描述

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

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

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

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

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

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

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

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

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

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

二、思路分析

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

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

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

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

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

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

HashMapkeyToVal;

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

HashMapkeyToFreq;

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

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

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

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

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

3.5、希望能夠快速刪除key列表中的任何一個(gè)key，因?yàn)槿绻l次為freq的某個(gè)key被訪問，那么它的頻次就會(huì)變成freq+1，就應(yīng)該從freq對(duì)應(yīng)的key列表中刪除，加到freq+1對(duì)應(yīng)的key的列表中。

HashMap>freqToKeys;
intminFreq=0;

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

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

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

綜上，我們可以寫出 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 的邏輯不難理解，但是寫代碼實(shí)現(xiàn)并不容易，因?yàn)槟憧次覀円S護(hù)KV表，KF表，F(xiàn)K表三個(gè)映射，特別容易出錯(cuò)。對(duì)于這種情況，labuladong 教你三個(gè)技巧：

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

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

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

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

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

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

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

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

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

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

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

????/*?插入?key?和?val，對(duì)應(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表這三個(gè)映射巧妙完成這兩個(gè)函數(shù)。

四、LFU 核心邏輯

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

privatevoidremoveMinFreqKey(){
//freq最小的key列表
LinkedHashSetkeyList=freqToKeys.get(this.minFreq);
//其中最先被插入的那個(gè)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);
}

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

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

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

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

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

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

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

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

能不能快速找到當(dāng)前的minFreq呢？這里是可以的，因?yàn)槲覀儎偛虐裬ey的freq加了 1 嘛，所以minFreq也加 1 就行了。

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