参考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
最低的键值对有多个,则删除其中最旧的那个。
先从最简单的开始,根据 LFU 算法的逻辑,我们先列举出算法执行过程中的几个需求:
get(key)
方法时,要返回该key
对应的val
。get
或者put
方法访问一次某个key
,该key
的freq
就要加一。freq
最小的key
删除,如果最小的freq
对应多个key
,则删除其中最旧的那一个。能够在 O(1) 的时间内解决这些需求,可以使用基本数据结构来逐个击破:
使用一个HashMap
存储key
到val
的映射,就可以快速计算get(key)
。
HashMap<Integer, Integer> keyToVal;
使用一个HashMap
存储key
到freq
的映射,就可以快速操作key
对应的freq
。
HashMap<Integer, Integer> keyToFreq;
这个需求应该是 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) {} }
我们要维护KV
表,KF
表,FK
表三个映射,特别容易出错,有三个技巧:
key
对应的freq
,那么就要同步修改KF
表和FK
表,这样才不会出问题。先来实现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 算法的核心
首先来实现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
即可。
这里没必要更新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++; } } }
当FK
表中freq
对应的列表被删空后,需要删除FK
表中freq
这个映射。如果这个freq
恰好是minFreq
,说明minFreq
变量需要更新。
能不能快速找到当前的minFreq
呢?这里是可以的,因为我们刚才把key
的freq
加了 1 嘛,所以minFreq
也加 1 就行了。