本文主要记录两种常用的缓存算法 LRU 与 LFU 的定义，以及两个算法的基础实现（C#）。
LRU Cache
LRU 全称 Least Recently Used（最近最少使用），当缓存溢出时选择最近最少使用的对象进行淘汰。
LeetCode-中等-146-LRU缓存机制
可以使用双向链表来实现 LRU 机制；
get 方法：
- key 不存在则返回 -1；
- key 存在则返回对应的 value，并将该节点移动到链表尾部（即该节点置为最近使用的节点）。
put 方法：
- key 存在则更新对应的 value，并将该节点从链表中移除，然后添加到链表尾部；
- key 不存在则直接将新的键值对添加到链表尾部。
这样一来链表头部的对象就是最近最少使用的对象了，当缓存溢出时，直接移除链表头部的对象即可。
双向链表添加和删除节点的时间复杂度为 O(1)，但是查找 key 的时间复杂度是 O(n)，为了使 get 方法和 put 方法的时间复杂度达到 O(1)，可以使用哈希表辅助进行实现。通过哈希表查找到 key 对应的链表中的节点，然后再对节点进行操作即可。
代码
Pair 类
即键值对。
1
2
3
4
5
6
7
8
9
10
11
12
| public class Pair
{
public Pair(int key, int value)
{
Key = key;
Value = value;
}
public int Key { get; }
public int Value { get; set; }
}
|
LRUCache 类
字段
1
2
3
4
5
6
| public class LRUCache
{
private readonly int _capacity;
private readonly LinkedList<Pair> _cache;
private readonly Dictionary<int, LinkedListNode<Pair>> _nodeDic;
}
|
方法
构造方法
1
2
3
4
5
6
| public LRUCache(int capacity)
{
_capacity = capacity;
_cache = new LinkedList<Pair>();
_nodeDic = new Dictionary<int, LinkedListNode<Pair>>(capacity);
}
|
获取元素 Get
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int Get(int key)
{
_nodeDic.TryGetValue(key, out var node);
if (node == null) {
return -1;
}
_cache.Remove(node);
_cache.AddLast(node);
return node.Value.Value;
}
|
添加元素 Put
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public void Put(int key, int value)
{
_nodeDic.TryGetValue(key, out var node);
if (node != null) {
node.Value.Value = value;
_cache.Remove(node);
_cache.AddLast(node);
}
else {
if (_cache.Count == _capacity) {
_nodeDic.Remove(_cache.First.Value.Key);
_cache.RemoveFirst();
}
node = new LinkedListNode<Pair>(new Pair(key, value));
_nodeDic.Add(key, node);
_cache.AddLast(node);
}
}
|
LFU Cache
LFU 全称 Least Frequently Used（最近最不常使用），当缓存溢出时选择最近最不常使用的对象进行淘汰。
LeetCode-困难-460-LFU缓存
相比于 LRU 算法多了一个条件，即对象的使用频率（frequency）；
因此，可以使用多个双向链表来实现，每个链表对应不同的频次，链表及其频率作为键值对存入哈希表中；
当节点被访问时，将节点从旧链表中移除，频率 +1，然后加入对应频率的新链表中。
代码
Pair 类
在键值对的基础上，新增了该对象的使用频率。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Pair
{
public Pair(int key, int value)
{
Key = key;
Value = value;
Frequency = 1;
}
public int Key { get; }
public int Value { get; set; }
public int Frequency { get; internal set; }
}
|
LFUCache 类
字段
1
2
3
4
5
6
7
| public class LFUCache
{
private readonly int _capacity;
private readonly Dictionary<int, LinkedList<Pair>> _cache;
private readonly Dictionary<int, LinkedListNode<Pair>> _listDic;
private int _minFrequency;
}
|
方法
构造方法
1
2
3
4
5
6
| public LFUCache(int capacity)
{
_capacity = capacity;
_cache = new Dictionary<int, LinkedList<Pair>>(capacity);
_listDic = new Dictionary<int, LinkedListNode<Pair>>(capacity);
}
|
获取元素 Get
1
2
3
4
5
6
7
8
9
10
11
12
| public int Get(int key)
{
_listDic.TryGetValue(key, out var node);
if (node == null) {
return -1;
}
VisitNode(node);
return node.Value.Value;
}
|
添加元素 Put
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| public void Put(int key, int value)
{
if (_capacity == 0) {
return;
}
_listDic.TryGetValue(key, out var node);
if (node != null) {
node.Value.Value = value;
VisitNode(node);
}
else {
if (_listDic.Count == _capacity) {
var list = _cache[_minFrequency];
_listDic.Remove(list.First.Value.Key);
list.RemoveFirst();
}
node = new LinkedListNode<Pair>(new Pair(key, value));
_listDic.Add(key, node);
_cache.TryGetValue(1, out var corList);
if (corList == null) {
corList = new LinkedList<Pair>();
_cache.Add(1, corList);
}
corList.AddLast(node);
_minFrequency = 1;
}
}
|
访问节点 VisitNode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| private void VisitNode(LinkedListNode<Pair> node)
{
var list = _cache[node.Value.Frequency];
list.Remove(node);
if (list.Count == 0 && node.Value.Frequency == _minFrequency) {
_minFrequency = node.Value.Frequency + 1;
}
++node.Value.Frequency;
_cache.TryGetValue(node.Value.Frequency, out var corList);
if (corList == null) {
corList = new LinkedList<Pair>();
_cache.Add(node.Value.Frequency, corList);
}
corList.AddLast(node);
}
|