讀完本文，你不僅學(xué)會了算法套路，還可以順便去 LeetCode 上拿下如下題目：

460.LFU緩存機(jī)制

-----------

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

LRU 算法的淘汰策略是 Least Recently Used，也就是每次淘汰那些最久沒被使用的數(shù)據(jù)；而 LFU 算法的淘汰策略是 Least Frequently Used，也就是每次淘汰那些使用次數(shù)最少的數(shù)據(jù)。

LRU 算法的核心數(shù)據(jù)結(jié)構(gòu)是使用哈希鏈表 LinkedHashMap，首先借助鏈表的有序性使得鏈表元素維持插入順序，同時(shí)借助哈希映射的快速訪問能力使得我們可以在 O(1) 時(shí)間訪問鏈表的任意元素。

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

PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。

而 LFU 算法相當(dāng)于是把數(shù)據(jù)按照訪問頻次進(jìn)行排序，這個(gè)需求恐怕沒有那么簡單，而且還有一種情況，如果多個(gè)數(shù)據(jù)擁有相同的訪問頻次，我們就得刪除最早插入的那個(gè)數(shù)據(jù)。也就是說 LFU 算法是淘汰訪問頻次最低的數(shù)據(jù)，如果訪問頻次最低的數(shù)據(jù)有多條，需要淘汰最舊的數(shù)據(jù)。

所以說 LFU 算法是要復(fù)雜很多的，而且經(jīng)常出現(xiàn)在面試中，因?yàn)?LFU 緩存淘汰算法在工程實(shí)踐中經(jīng)常使用，也有可能是應(yīng)該 LRU 算法太簡單了。不過話說回來，這種著名的算法的套路都是固定的，關(guān)鍵是由于邏輯較復(fù)雜，不容易寫出漂亮且沒有 bug 的代碼。

那么本文 labuladong 就帶你拆解 LFU 算法，自頂向下，逐步求精，就是解決復(fù)雜問題的不二法門。

一、算法描述

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

class LFUCache {
    // 構(gòu)造容量為 capacity 的緩存
    public LFUCache(int capacity) {}
    // 在緩存中查詢 key
    public int get(int key) {}
    // 將 key 和 val 存入緩存
    public void put(int key, int val) {}
}

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

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

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

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

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

// 查詢 key 為 1 對應(yīng)的 val
// 返回 10，同時(shí)鍵 1 對應(yīng)的 freq 變?yōu)?2
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í)行過程中的幾個(gè)顯而易見的事實(shí)：

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

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

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

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

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

HashMap<Integer, Integer> keyToVal;

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

HashMap<Integer, Integer> keyToFreq;

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 對 key 是一對多的關(guān)系，即一個(gè) freq 對應(yīng)一個(gè) key 的列表。

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

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

HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
int minFreq = 0;

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

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

PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。

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

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

class LFUCache {
    // key 到 val 的映射，我們后文稱為 KV 表
    HashMap<Integer, Integer> keyToVal;
    // key 到 freq 的映射，我們后文稱為 KF 表
    HashMap<Integer, Integer> keyToFreq;
    // freq 到 key 列表的映射，我們后文稱為 FK 表
    HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
    // 記錄最小的頻次
    int minFreq;
    // 記錄 LFU 緩存的最大容量
    int cap;

    public LFUCache(int capacity) {
        keyToVal = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqToKeys = new HashMap<>();
        this.cap = capacity;
        this.minFreq = 0;
    }

    public int get(int key) {}

    public void put(int key, int val) {}

}

三、代碼框架

LFU 的邏輯不難理解，但是寫代碼實(shí)現(xiàn)并不容易，因?yàn)槟憧次覀円S護(hù) KV 表，KF 表，FK 表三個(gè)映射，特別容易出錯(cuò)。對于這種情況，labuladong 教你三個(gè)技巧：

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

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

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

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

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

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

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

image

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

public void put(int key, int val) {
    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 不存在，需要插入 */
    /* 容量已滿的話需要淘汰一個(gè) 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 表，FK 表這三個(gè)映射巧妙完成這兩個(gè)函數(shù)。

四、LFU 核心邏輯

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

private void removeMinFreqKey() {
    // freq 最小的 key 列表
    LinkedHashSet<Integer> keyList = freqToKeys.get(this.minFreq);
    // 其中最先被插入的那個(gè) key 就是該被淘汰的 key
    int deletedKey = 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 對應(yīng)的 key 列表就為空了，也就是 minFreq 變量需要被更新。如何計(jì)算當(dāng)前的 minFreq 是多少呢？

PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。

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

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

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

private void increaseFreq(int key) {
    int freq = 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, new LinkedHashSet<>());
    freqToKeys.get(freq + 1).add(key);
    // 如果 freq 對應(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 肯定會涉及 FK 表和 KF 表，所以我們分別更新這兩個(gè)表就行了。

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

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

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

＿＿＿＿＿＿＿＿＿＿＿＿＿

我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目，建議收藏！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標(biāo)星！