LRU 与 LFU 算法
- LRU 算法
- LFU 算法
图片来源于网络
1. LRU 算法
LRU 算法是一种缓存淘汰策略，是 Least Recently Used 的缩写，也就是认为最近使用过的数据应该是有用的，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。即把最近最久未使用的页面（数据、内存等）予以淘汰。
力扣 146 题算法描述如下：
LRU 缓存机制
主要是实现以下 API：
class LRUCache {
public LRUCache(int capacity) { }
public int get(int key) { }
public void put(int key, int value) { }
}
1.1 LRU 算法设计分析
要让 put 和 get 方法的时间复杂度为 O(1)，那么 cache 这个数据结构需满足如下必要条件：
-
cache中的元素必须有时序，以区分最近使用的和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置。 - 要在
cache中快速找某个key是否已存在并得到对应的值val。 - 每次访问
cache中的某个key，需要将这个元素变为最近使用的，即cache要支持在任意位置快速插入和删除元素。
哈希表查找快，但数据无固定顺序；链表有顺序之分，插入删除快，但查找慢。结合一下，因此可采用哈希链表 LinkedHashMap。
LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体：
哈希链表
借助这个数结构，是满足上面的 cache 必要条件的：
- 若每次默认从链表尾部添加元素，那么越靠尾部的元素就是最近使用的，越靠头部的元素就是最久未使用的。
- 对于某一个
key，可以通过哈希表快速定位到链表中的节点，从而取得对应val。 - 借助哈希表，可以通过
key快速映射到任意一个链表节点，然后进行插入和删除。
1.2 LRU 算法代码实现
首先构建双链表如下：
/**
* 双链表的节点类
*/
public class Node {
public int key, val;
public Node next, prev;
public Node(int k, int v) {
this.key = k;
this.val = v;
}
}
/**
* 双链表
*/
public class DoubleList {
// 头尾虚节点
private Node head, tail;
// 链表元素数
private int size;
public DoubleList() {
// 初始化双向链表的数据
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
size = 0;
}
// 在链表尾部添加节点 x，时间 O(1)
public void addLast(Node x) {
x.prev = tail.prev;
x.next = tail;
tail.prev.next = x;
tail.prev = x;
size++;
}
// 删除链表中的 x 节点（x 一定存在）
// 由于是双链表且给的是目标 Node 节点，时间 O(1)
public void remove(Node x) {
x.prev.next = x.next;
x.next.prev = x.prev;
size--;
}
// 删除链表中第一个节点，并返回该节点，时间 O(1)
public Node removeFirst() {
if (head.next == tail) return null;
Node first = head.next;
remove(first);
return first;
}
// 返回链表长度，时间 O(1)
public int size() {
return size;
}
}
值得注意的是，这边不能使用单链表而要使用双向链表，因为上面删除操作中，删除一个节点不仅要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)。
上面双链表中只能从尾部插入，即靠尾部的数据是最近使用的，靠头部的数据是最久为使用的。
接着在 LRU 算法中把双向链表和哈希表结合起来：
/**
* LRU 算法: 把双向链表和哈希表结合起来
* <p>
* LRU 算法相当于把数据按照时间排序，借助链表，
* 一直从链表头部加入元素的话，越靠近头部的元素就是新的数据，越靠近尾部的元素就是旧的数据，
* 进行缓存淘汰时只要简单地将尾部的元素淘汰掉
*/
public class LRUCache {
// key -> Node(key, val)
private HashMap<Integer, Node> map;
// Node(k1, v1) <-> Node(k2, v2)...
private DoubleList cache;
// 最大容量
private int cap;
public LRUCache(int capacity) {
this.cap = capacity;
map = new HashMap<>();
cache = new DoubleList();
}
/******** 尽量让 LRU 的主方法 get 和 put 避免直接操作 map 和 cache 的细节 *********/
/**
* 将某个 key 提升为最近使用的
*/
private void makeRecently(int key) {
Node x = map.get(key);
// 先从链表中删除这个节点
cache.remove(x);
// 重新插到队尾
cache.addLast(x);
}
/**
* 添加最近使用的元素
*/
private void addRecently(int key, int val) {
Node x = new Node(key, val);
// 链表尾部就是最近使用的元素
cache.addLast(x);
// 别忘了在 map 中添加 key 的映射
map.put(key, x);
}
/**
* 删除某一个 key
*/
private void deleteKey(int key) {
Node x = map.get(key);
// 从链表中删除
cache.remove(x);
// 从 map 中删除
map.remove(key);
}
/**
* 删除最久未使用的元素
*/
private void removeLeastRecently() {
// 链表头部的第一个元素就是最久未使用的
Node deleteNode = cache.removeFirst();
// 同时别忘了从 map 中删除它的 key
int deleteKey = deleteNode.key;
map.remove(deleteKey);
}
/********************************* 对外方法 ************************************/
public int get(int key) {
if (!map.containsKey(key)) return -1;
// 将该数据提升为最近使用的
makeRecently(key);
return map.get(key).val;
}
public void put(int key, int val) {
if (map.containsKey(key)) {
// 删除旧数据
deleteKey(key);
// 新插入的数据为最近使用的数据
addRecently(key, val);
return;
}
if (cap == cache.size()) {
// 删除最久未使用的元素
removeLeastRecently();
}
// 添加为最近使用的元素
addRecently(key, val);
}
}
值得注意的是，上面 removeLeastRecently 函数中，需要用 deletedNode 得到 deletedKey，即当缓存容量已满，不仅要删除最后一个 Node 节点，还要把 map 中映射到该节点的 key 同时删除，而这个 key 只能由 Node 得到。这也就是为什么要在链表中同时存储 key 和 val。
另外， put 方法稍复杂，其逻辑如下：
put(key, val)
当然，上面 LRU 算法也可用 Java 的内置 LinkedHashMap 来实现：
public class LRUCache {
int cap;
LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if (!cache.containsValue(key)) {
return -1;
}
// 将 key 变为最近使用
makeRecently(key);
return cache.get(key);
}
public void put(int key, int val) {
if (cache.containsValue(key)) {
// 修改 key 的值
cache.put(key, val);
// 将 key 变为最近使用
makeRecently(key);
return;
}
if (cache.size() >= this.cap) {
// 链表头部就是最久未使用的 key
int oldestKey = cache.keySet().iterator().next();
cache.remove(oldestKey);
}
// 将新的 key 添加链表尾部
cache.put(key, val);
}
private void makeRecently(int key) {
int val = cache.get(key);
// 删除 key，重新插入到队尾
cache.remove(key);
cache.put(key, val);
}
}
2. LFU 算法
LFU 算法是一种缓存淘汰策略，是 Least Frequently Used 的缩写，也就是根据数据的历史访问频率来淘汰数据，其核心思想是淘汰访问频次最低的数据，如果访问频次最低的数据有多条，需要淘汰最旧的数据。
力扣 460 题算法描述如下：
LFU 缓存机制
主要是实现以下 API：
class LFUCache {
// 构造容量为 capacity 的缓存
public LFUCache(int capacity) { }
// 在缓存中查询 key
public int get(int key) { }
// 将 key 和 val 存入缓存
public void put(int key, int value) { }
}
2.1 LFU 算法设计分析
根据 LFU 算法的逻辑，列举出算法执行过程中的几个显而易见的事实：
- 调用
get(key)方法时，要返回该key对应的val。 - 只要用
get或put方法访问一次某个key，该key的freq就要加一。 - 若在容量满时进行插入，则需要将
freq最小的key删除，如果最小的freq对应多个key，则删除其中最旧的那一个。
要在 O(1) 的时间内解决这些需求，可使用如下基本数据结构：
- 使用一个
HashMap存储key到val的映射，就可以快速计算get(key)：
// 使用一个HashMap存储key到val的映射 -- KV表
HashMap<Integer, Integer> keyToVal;
- 使用一个
HashMap存储key到freq的映射，就可以快速操作key对应的freq：
// 使用一个HashMap存储key到freq的映射 -- KF表
HashMap<Integer, Integer> keyToFreq;
- 最后一个需求是 LFU 算法的核心：
/**
* freq 到 key 列表的映射 -- FK表
* <p>
* 1、首先，肯定是需要freq到key的映射，用来找到freq最小的key。
* 2、将freq最小的key删除，就得快速得到当前所有key最小的freq是多少。
* 想要时间复杂度 O(1) 的话，需要用一个变量minFreq来记录当前最小的freq。
* 3、可能有多个key拥有相同的freq，所以 freq对key是一对多的关系，即一个freq对应一个key的列表。
* 4、希望freq对应的key的列表是存在时序的，便于快速查找并删除最旧的key。
* 5、希望能够快速删除key列表中的任何一个key，因为如果频次为freq的某个key被访问，
* 那么它的频次就会变成freq+1，就应该从freq对应的key列表中删除，加到freq+1对应的key的列表中。
*/
HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
int minFreq = 0;
LinkedHashSet 是链表和哈希集合的结合体。链表不能快速访问链表节点，但插入元素具有时序；哈希集合中的元素无序，但可以对元素进行快速的访问和删除。
综上， LFU 算法的基本数据结构如下：
class LFUCache {
// key 到 val 的映射
HashMap<Integer, Integer> keyToVal;
// key 到 freq 的映射
HashMap<Integer, Integer> keyToFreq;
// freq 到 key 列表的映射
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) {}
}
2.2 LFU 算法代码实现
LFU 算法的逻辑不难理解，但写代码实现并不容易，对于这种要维护多个映射且容易出错的情况，可用如下技巧：
- 不要企图上来就实现算法的所有细节，而应该自顶向下，逐步求精，先写清楚主函数的逻辑框架，然后再一步步实现细节。
- 搞清楚映射关系，如果更新了某个
key对应的freq，那么就要同步修改 KF表和 FK表，这样才不会出问题。 - 画图，把逻辑比较复杂的部分用流程图画出来，然后根据图来写代码，可以极大减少出错的概率。
首先，实现 get(key) 方法如下：
/**
* 在缓存中查询 key
* <p>
* 返回 key 对应的 val，然后增加 key 对应的 freq
*/
public int get(int key) {
if (!keyToVal.containsKey(key)) {
return -1;
}
// 增加 key 对应的 freq
increaseFreq(key);
return keyToVal.get(key);
}
然后实现 put(key, val) 方法，逻辑稍复杂，其大体流程图如下：
put(key, val)
代码如下：
/**
* 将 key 和 val 存入缓存
*/
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;
}
接着，实现 LFU 算法的核心逻辑 removeMinFreqKey 如下：
/**
* 删除最小频率的 key
* <p>
* 删除某个键 key要同时修改三个映射表，借助 minFreq 参数可以从 FK表 中找到 freq 最小的 keyList，
* 根据时序，其中第一个元素就是要被淘汰的 deletedKey，操作三个映射表删除这个 key 即可
*/
private void removeMinFreqKey() {
// freq 最小的 key 列表
LinkedHashSet<Integer> keyList = freqToKeys.get(this.minFreq);
// 其中最先被插入的那个 key 就是该被淘汰的 key
int deleteKey = keyList.iterator().next();
// 更新 FK 表
keyList.remove(deleteKey);
if (keyList.isEmpty()) {
freqToKeys.remove(this.minFreq);
// 问：这里需要更新 minFreq 的值吗？
// 答：不需要，因为该方法在put方法中插入新key时可能调用，而插入新key时一定会把minFreq更新成 1
}
// 更新 KV 表
keyToVal.remove(deleteKey);
// 更新 KF 表
keyToFreq.remove(deleteKey);
}
最后，实现 increaseFreq 如下：
/**
* 增加 key 对应的 freq
* <p>
* 更新某个 key 的 freq 会涉及 FK表 和 KF表，这边分别更新这两个表即可
*/
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++;
}
}
}
以上，LFU 算法代码就完成了。
参考链接：
