关于算法:层层拆解带你手写-LFU-算法

读完本文，你不仅学会了算法套路，还能够顺便去 LeetCode 上拿下如下题目：

460.LFU 缓存机制

———–

上篇文章带你手写 LRU 算法写了 LRU 缓存淘汰算法的实现办法，本文来写另一个驰名的缓存淘汰算法：LFU 算法。

LRU 算法的淘汰策略是 Least Recently Used，也就是每次淘汰那些最久没被应用的数据；而 LFU 算法的淘汰策略是 Least Frequently Used，也就是每次淘汰那些应用次数起码的数据。

LRU 算法的外围数据结构是应用哈希链表 LinkedHashMap，首先借助链表的有序性使得链表元素维持插入程序，同时借助哈希映射的快速访问能力使得咱们能够在 O(1) 工夫拜访链表的任意元素。

从实现难度上来说，LFU 算法的难度大于 LRU 算法，因为 LRU 算法相当于把数据依照工夫排序，这个需要借助链表很天然就能实现，你始终从链表头部退出元素的话，越凑近头部的元素就是新的数据，越凑近尾部的元素就是旧的数据，咱们进行缓存淘汰的时候只有简略地将尾部的元素淘汰掉就行了。

而 LFU 算法相当于是把数据依照拜访频次进行排序，这个需要恐怕没有那么简略，而且还有一种状况，如果多个数据领有雷同的拜访频次，咱们就得删除最早插入的那个数据。也就是说 LFU 算法是淘汰拜访频次最低的数据，如果拜访频次最低的数据有多条，须要淘汰最旧的数据。

所以说 LFU 算法是要简单很多的，而且经常出现在面试中，因为 LFU 缓存淘汰算法在工程实际中常常应用，也有可能是应该 LRU 算法太简略了。不过话说回来，这种驰名的算法的套路都是固定的，要害是因为逻辑较简单，不容易写出丑陋且没有 bug 的代码。

那么本文 labuladong 就带你拆解 LFU 算法，自顶向下，逐步求精，就是解决简单问题的不二法门。

要求你写一个类，承受一个 capacity 参数，实现 get 和 put 办法：

class LFUCache {
    // 结构容量为 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 对应的 val，否则返回 -1。

put(key, value) 办法插入或批改缓存。如果 key 已存在，则将它对应的值改为 val；如果 key 不存在，则插入键值对 (key, val)。

当缓存达到容量 capacity 时，则应该在插入新的键值对之前，删除应用频次（后文用 freq 示意）最低的键值对。如果 freq 最低的键值对有多个，则删除其中最旧的那个。

// 结构一个容量为 2 的 LFU 缓存
LFUCache cache = new LFUCache(2);

// 插入两对 (key, val)，对应的 freq 为 1
cache.put(1, 10);
cache.put(2, 20);

// 查问 key 为 1 对应的 val
// 返回 10，同时键 1 对应的 freq 变为 2
cache.get(1);

// 容量已满，淘汰 freq 最小的键 2
// 插入键值对 (3, 30)，对应的 freq 为 1
cache.put(3, 30);   

// 键 2 曾经被淘汰删除，返回 -1
cache.get(2);

肯定先从最简略的开始，依据 LFU 算法的逻辑，咱们先列举出算法执行过程中的几个不言而喻的事实：

1、调用 get(key) 办法时，要返回该 key 对应的 val。

2、只有用 get 或者 put 办法拜访一次某个 key，该 key 的 freq 就要加一。

3、如果在容量满了的时候进行插入，则须要将 freq 最小的 key 删除，如果最小的 freq 对应多个 key，则删除其中最旧的那一个。

好的，咱们心愿可能在 O(1) 的工夫内解决这些需要，能够应用根本数据结构来一一击破：

1、应用一个 HashMap 存储 key 到 val 的映射，就能够疾速计算 get(key)。

HashMap<Integer, Integer> keyToVal;

2、应用一个 HashMap 存储 key 到 freq 的映射，就能够疾速操作 key 对应的 freq。

HashMap<Integer, Integer> keyToFreq;

3、这个需要应该是 LFU 算法的外围，所以咱们离开说。

3.1、首先，必定是须要 freq 到 key 的映射，用来找到 freq 最小的 key。

3.2、将 freq 最小的 key 删除，那你就得疾速失去以后所有 key 最小的 freq 是多少。想要工夫复杂度 O(1) 的话，必定不能遍历一遍去找，那就用一个变量 minFreq 来记录以后最小的 freq 吧。

3.3、可能有多个 key 领有雷同的 freq，所以 freq 对 key 是一对多的关系，即一个 freq 对应一个 key 的列表。

3.4、心愿 freq 对应的 key 的列表是 存在时序 的，便于疾速查找并删除最旧的 key。

3.5、心愿 可能疾速删除 key 列表中的任何一个 key，因为如果频次为 freq 的某个 key 被拜访，那么它的频次就会变成 freq+1，就应该从 freq 对应的 key 列表中删除，加到 freq+1 对应的 key 的列表中。

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

介绍一下这个 LinkedHashSet，它满足咱们 3.3，3.4，3.5 这几个要求。你会发现一般的链表 LinkedList 可能满足 3.3，3.4 这两个要求，然而因为一般链表不能快速访问链表中的某一个节点，所以无奈满足 3.5 的要求。

LinkedHashSet 顾名思义，是链表和哈希汇合的结合体。链表不能快速访问链表节点，然而插入元素具备时序；哈希汇合中的元素无序，然而能够对元素进行疾速的拜访和删除。

那么，它俩联合起来就兼具了哈希汇合和链表的个性，既能够在 O(1) 工夫内拜访或删除其中的元素，又能够放弃插入的时序，高效实现 3.5 这个需要。

综上，咱们能够写出 LFU 算法的根本数据结构：

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 的逻辑不难理解，然而写代码实现并不容易，因为你看咱们要保护 KV 表，KF 表，FK 表三个映射，特地容易出错。对于这种状况，labuladong 教你三个技巧：

1、不要希图上来就实现算法的所有细节，而应该自顶向下，逐步求精，先写分明主函数的逻辑框架，而后再一步步实现细节。

2、搞清楚映射关系，如果咱们更新了某个 key 对应的 freq，那么就要同步批改 KF 表和 FK 表，这样才不会出问题。

3、画图，画图，画图，重要的话说三遍，把逻辑比较复杂的局部用流程图画进去，而后依据图来写代码，能够极大缩小出错的概率。

上面咱们先来实现 get(key) 办法，逻辑很简略，返回 key 对应的 val，而后减少 key 对应的 freq：

public int get(int key) {if (!keyToVal.containsKey(key)) {return -1;}
    // 减少 key 对应的 freq
    increaseFreq(key);
    return keyToVal.get(key);
}

减少 key 对应的 freq 是 LFU 算法的外围，所以咱们罗唆间接形象成一个函数 increaseFreq，这样 get 办法看起来就简洁清晰了对吧。

上面来实现 put(key, val) 办法，逻辑稍微简单，咱们间接画个图来看：

这图就是顺手画的，不是什么正规的程序流程图，然而算法逻辑高深莫测，看图能够间接写出 put 办法的逻辑：

public void put(int key, int val) {if (this.cap <= 0) return;

    /* 若 key 已存在，批改对应的 val 即可 */
    if (keyToVal.containsKey(key)) {keyToVal.put(key, val);
        // key 对应的 freq 加一
        increaseFreq(key);
        return;
    }

    /* key 不存在，须要插入 */
    /* 容量已满的话须要淘汰一个 freq 最小的 key */
    if (this.cap <= keyToVal.size()) {removeMinFreqKey();
    }

    /* 插入 key 和 val，对应的 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 表这三个映射奇妙实现这两个函数。

首先来实现 removeMinFreqKey 函数：

private void removeMinFreqKey() {
    // freq 最小的 key 列表
    LinkedHashSet<Integer> keyList = freqToKeys.get(this.minFreq);
    // 其中最先被插入的那个 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);
}

删除某个键 key 必定是要同时批改三个映射表的，借助 minFreq 参数能够从 FK 表中找到 freq 最小的 keyList，依据时序，其中第一个元素就是要被淘汰的 deletedKey，操作三个映射表删除这个 key 即可。

然而有个细节问题，如果 keyList 中只有一个元素，那么删除之后 minFreq 对应的 key 列表就为空了，也就是 minFreq 变量须要被更新。如何计算以后的 minFreq 是多少呢？

实际上没方法疾速计算 minFreq，只能线性遍历 FK 表或者 KF 表来计算，这样必定不能保障 O(1) 的工夫复杂度。

然而，其实这里没必要更新 minFreq 变量，因为你想想 removeMinFreqKey 这个函数是在什么时候调用？在 put 办法中插入新 key 时可能调用。而你回头看 put 的代码，插入新 key 时肯定会把 minFreq 更新成 1，所以说即使这里 minFreq 变了，咱们也不须要管它。

上面来实现 increaseFreq 函数：

private void increaseFreq(int key) {int freq = keyToFreq.get(key);
    /* 更新 KF 表 */
    keyToFreq.put(key, freq + 1);
    /* 更新 FK 表 */
    // 将 key 从 freq 对应的列表中删除
    freqToKeys.get(freq).remove(key);
    // 将 key 退出 freq + 1 对应的列表中
    freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
    freqToKeys.get(freq + 1).add(key);
    // 如果 freq 对应的列表空了，移除这个 freq
    if (freqToKeys.get(freq).isEmpty()) {freqToKeys.remove(freq);
        // 如果这个 freq 恰好是 minFreq，更新 minFreq
        if (freq == this.minFreq) {this.minFreq++;}
    }
}

更新某个 key 的 freq 必定会波及 FK 表和 KF 表，所以咱们别离更新这两个表就行了。

和之前相似，当 FK 表中 freq 对应的列表被删空后，须要删除 FK 表中 freq 这个映射。如果这个 freq 恰好是 minFreq，阐明 minFreq 变量须要更新。

能不能疾速找到以后的 minFreq 呢？这里是能够的，因为咱们方才把 key 的 freq 加了 1 嘛，所以 minFreq 也加 1 就行了。

至此，通过层层拆解，LFU 算法就实现了。

关于算法:层层拆解带你手写-LFU-算法

一、算法形容

二、思路剖析

三、代码框架

四、LFU 外围逻辑

Just My Socks（注册教程内含优惠码）

关于算法:层层拆解带你手写-LFU-算法

一、算法形容

二、思路剖析

三、代码框架

四、LFU 外围逻辑

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）