使用C++和Go实现LRU缓存
LRU缓存介绍
LRU是Least Recently Used ，就是最近使用过的数据最有可能会继续使用的。很长时间没有用过的数据就认为是之后不会再用到了。在容量有限的情况下，如果数据存满了，又有新的数据过来了。那么就要把最久没被使用的给删了。
LeeCode上有个老哥举例很生动
举个简单的例子，安卓手机都可以把软件放到后台运行，比如我先后打开了「设置」「手机管家」「日历」，那么现在他们在后台排列的顺序是这样的：
但是这时候如果我访问了一下「设置」界面，那么「设置」就会被提前到第一个，变成这样：
假设我的手机只允许我同时开 3 个应用程序，现在已经满了。那么如果我新开了一个应用「时钟」，就必须关闭一个应用为「时钟」腾出一个位置，关那个呢？
按照 LRU 的策略，就关最底下的「手机管家」，因为那是最久未使用的，然后把新开的应用放到最上面：
LRU的操作
对于一个LRU缓存来说都是有一个缓冲区的大小(capacity),可以向缓存中放数据 put(key,val),也可以从缓存中拿到数据get(key),注意在put和get的时候都是O(1)的时间复杂度.
/* 缓存容量为 2 */ LRUCache cache = new LRUCache(2); // 你可以把 cache 理解成一个队列 // 假设左边是队头，右边是队尾 // 最近使用的排在队头，久未使用的排在队尾 // 圆括号表示键值对 (key, val)
cache.put(1, 1); // cache = [(1, 1)]
cache.put(2, 2); // cache = [(2, 2), (1, 1)]
cache.get(1); // 返回 1 // cache = [(1, 1), (2, 2)] // 解释：因为最近访问了键 1，所以提前至队头 // 返回键 1 对应的值 1
cache.put(3, 3); // cache = [(3, 3), (1, 1)] // 解释：缓存容量已满，需要删除内容空出位置 // 优先删除久未使用的数据，也就是队尾的数据 // 然后把新的数据插入队头
cache.get(2); // 返回 -1 (未找到) // cache = [(3, 3), (1, 1)] // 解释：cache 中不存在键为 2 的数据
cache.put(1, 4);
// cache = [(1, 4), (3, 3)] // 解释：键 1 已存在，把原始值 1 覆盖为 4 // 不要忘了也要将键值对提前到队头
LRU的设计
根据上述的描述,对于put和get为O(1)的时间复杂度的数据结构要进行设计
- 题目中有"最近使用",就说明数据是有序的,这个有序是相对于使用的时间而言的
- 要在某个位置进行O(1)的插入
- 查找也是O(1)
要同时满足以上的条件单一的数据结构肯定是不行的.对于查找是来说可以使用哈希表来满足条件,有序可以使用链表,但是要进行O(1)的插入,就要使用双链表了,单链表不能进行O(1)的时间复杂度的插入.
LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样：
借助这个结构，我们来逐一分析上面的 3 个条件：
1、如果我们每次默认从链表尾部添加元素，那么显然越靠尾部的元素就是最近使用的，越靠头部的元素就是最久未使用的,如果容量满了之后,要删的也是删除头部的。
2、对于某一个 key，我们可以通过哈希表快速定位到链表中的节点，从而取得对应 val,也就是哈希表存的是值所对应的结点的地址,通过这个地址就可以拿到对应的val。
3、链表显然是支持在任意位置快速插入和删除的，改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 key 快速映射到任意一个链表节点，然后进行插入和删除。
也许读者会问，为什么要是双向链表，单链表行不行？另外，既然哈希表中已经存了 key，为什么链表中还要存 key 和 val 呢，只存 val 不就行了？
想的时候都是问题，只有做的时候才有答案。这样设计的原因，必须等我们亲自实现 LRU 算法之后才能理解，所以我们开始看代码吧～
代码实现
c++
虽然系统中实现了双向链表,但是这里还是想自己实现一遍.
实现Node
1struct Node{
2 int key;
3 int val;
4 Node *pre; // 指向之前的结点
5 Node *next;// 指向之后的结点
6 Node(int key,int val):key(key),val(val){}
7}
实现双向链表
1struct DoubleList{
2private:
3 Node *head; // 头结点,不存数据
4 Node *tail; // 尾结点,不存数据
5 int size; // 元素的个数
6
7public:
8 DoubleList(){
9 head = new Node(0,0);
10 tail = new Node(0,0);
11 size = 0;
12 head->next = tail; // 头结点的next指向尾结点
13 tail->pre = head; // 尾结点的pre指向头结点
14 }
15
16 // 在尾部添加元素
17 void addTail(Node *x){
18 x->pre = tail->pre; // 插入的之前的指向尾巴的前结点
19 x->next = tail; // 插入的next指向尾结点
20 tail->pre->next = x; // 尾巴之前的结点的next指向x
21 tail->pre = x; // 尾巴之前的变为x
22 size++;
23 }
24
25 // 移除某个结点
26 void remove(Node *x) {
27 x->pre->next = x->next;
28 x->next->pre = x->pre;
29 size--;
30 }
31
32 // 移除头结点
33 Node *removeFirst() {
34 if (head == nullptr) {
35 return nullptr;
36 }
37 Node *first = head->next;
38 remove(first);
39 return first;
40 }
41
42
43 int len() {
44 return size;
45 }
46}
到这里就能回答刚才「为什么必须要用双向链表」的问题了，因为我们需要删除操作。删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)。
注意我们实现的双链表 API 只能从尾部插入，也就是说靠尾部的数据是最近使用的，靠头部的数据是最久为使用的。
实现LRU
LRU中要使用到之前实现的链表和哈希表。
1struct LRU {
2 map<int, Node *> *m;
3 DoubleList *cache;
4 int cap;
5
6 // 初始化
7 LRU(int cap) {
8 this->cap = cap;
9 m = new map<int, Node *>;
10 cache = new DoubleList();
11 }
12
13// 封装底层的接口
14private:
15 // 将某个key提升为最近使用的
16 void makeRecently(int key) {
17 auto item = m->find(key);
18 if (item == m->end()) {
19 return;
20 }
21 // 先删除
22 cache->remove(item->second);
23 // 再加到链表的尾部
24 cache->addLast(item->second);
25 }
26 // 添加最近使用过的元素
27 void addRecently(int key, int val) {
28 Node *x = new Node(key, val);
29 // 添加到尾部
30 cache->addLast(x);
31 // 在map中也要添加
32 m->insert(pair<int, Node *>(key, x));
33 }
34
35 // 删除某个缓存
36 void deleteKey(int key) {
37 auto temp = m->find(key);
38 // 如果没有找到就算了
39 if (temp == m->end()) {
40 return;
41 }
42 // 在链表和map中都删除
43 cache->remove(temp->second);
44 m->erase(key);
45 }
46
47 // 删除最久没被使用的
48 void removedLeastRecently() {
49 // 链表删除头
50 Node *deleteNode = cache->removeFirst();
51 // map 直接删除
52 m->erase(deleteNode->key);
53 }
54
55// 封装对外的get和set
56public:
57 int get(int key) {
58 auto temp = m->find(key);
59 if (temp == m->end()) {
60 return -1;
61 }
62 // 找到之后要提升
63 makeRecently(key);
64 return temp->second->val;
65 }
66
67 void put(int key, int val) {
68 auto temp = m->find(key);
69 // 如果找到了 就是要修改值
70 if (temp != m->end()) {
71 // 先删除key
72 deleteKey(key);
73 // 再添加
74 addRecently(key, val);
75 return;
76 }
77 // 容量超了就删除最久没有使用的
78 if (cap == cache->len()) {
79 removedLeastRecently();
80 }
81 addRecently(key, val);
82 }
83};
c++另一个版本
使用iterator迭代器进行实现
1class LRUCache {
2public:
3 LRUCache(int capacity) : cap(capacity) {
4 }
5
6 int get(int key) {
7 // 如果没有就返回-1
8 if (map.find(key) == map.end()) return -1;
9 auto keyAndValue = *map[key];
10 cache.erase(map[key]);
11 cache.push_front(keyAndValue);
12 map[key] = cache.begin();
13 return keyAndValue.second;
14 }
15
16 void put(int key, int value) {
17 // 如果缓存中没有
18 if (map.find(key) == map.end()) {
19 // 缓存中满了
20 if (cache.size() == cap) {
21 // 删除头部的元素，也就是最久没被使用的
22 map.erase(cache.back().first);
23 cache.pop_back();
24 }
25 } else {
26 // 如果缓存中有就删除
27 cache.erase(map[key]);
28 }
29 // 重新插在末尾
30 cache.push_front({key, value});
31 map[key] = cache.begin();
32 }
33
34private:
35 int cap;
36 // 一个双向链表，存顺序
37 list<pair<int, int>> cache;
38 // 加速访问
39 unordered_map<int, list<pair<int, int>>::iterator> map;
40};
这个版本不用实现双向链表，只需要自己手动调用就行
go
和之前c++1.0版本一样自己实现一个双向链表，之后使用自带的map。这次使用了1.18的泛型进行实现。
Node
1// 通用的结点，保存的val可以是任何类型
2type Node[T any] struct {
3 Val T
4 Pre *Node[T]
5 Next *Node[T]
6}
7
8func NewNode[T any](val T) *Node[T] {
9 return &Node[T]{
10 Val: val,
11 }
12}
13
14// 一个key-value的数据结构
15type KeyValue[Key, Value any] struct {
16 Key Key
17 Value Value
18}
double-list
1// 链表的数据结构
2// 使用的时候要给传入Node中val的类型
3type DoubleList[T any] struct {
4 head *Node[T] // 头结点
5 tail *Node[T] // 尾巴结点
6 size int
7}
8
9func NewDoubleList[T any]() *DoubleList[T] {
10 dl := DoubleList[T]{
11 head: new(Node[T]),
12 tail: new(Node[T]),
13 size: 0,
14 }
15 dl.head.Next = dl.tail
16 dl.tail.Pre = dl.head
17 return &dl
18}
19
20// 在尾巴插入一个结点
21func (dl *DoubleList[T]) PushBack(node *Node[T]) {
22 node.Pre = dl.tail.Pre
23 node.Next = dl.tail
24 dl.tail.Pre.Next = node
25 dl.tail.Pre = node
26 dl.size++
27}
28
29// 删除一个结点
30func (dl *DoubleList[T]) Remove(node *Node[T]) {
31 if node == nil || node.Pre == nil || node.Next == nil {
32 return
33 }
34 node.Pre.Next = node.Next
35 node.Next.Pre = node.Pre
36 dl.size--
37}
38
39// 返回头结点
40func (dl *DoubleList[T]) Front() *Node[T] {
41 if dl.head == nil {
42 return nil
43 }
44 return dl.head.Next
45}
46
47// 删除头结点
48func (dl *DoubleList[T]) PopFront() {
49 if dl.head == nil {
50 return
51 }
52 dl.Remove(dl.head.Next)
53 return
54}
55
56// 返回链表长度
57func (dl *DoubleList[T]) Size() int {
58 return dl.size
59}
LRU实现
1var (
2 NotFoundErr = errors.New("not found")
3)
4
5// lru的数据结构
6type lru[K comparable, Value any] struct {
7 // lock sync.RWMutex
8 data map[K]*Node[KeyValue[K, Value]]
9 cache *DoubleList[KeyValue[K, Value]]
10 cap int
11}
12
13func NewLRU[K comparable, Value any](cap int) *lru[K, Value] {
14 return &lru[K, Value]{
15 data: make(map[K]*Node[KeyValue[K, Value]]),
16 cache: NewDoubleList[KeyValue[K, Value]](),
17 cap: cap,
18 }
19}
20
21// 提升某个结点
22func (lru *lru[K, Value]) makeRecently(key K) {
23 find, ok := lru.data[key]
24 if !ok {
25 return
26 }
27 lru.cache.Remove(find)
28 lru.cache.PushBack(find)
29}
30
31// 新添加一个结点
32func (lru *lru[K, Value]) addRecently(key K, value Value) {
33 node := NewNode[KeyValue[K, Value]](KeyValue[K, Value]{Key: key, Value: value})
34 lru.cache.PushBack(node)
35 lru.data[key] = node
36}
37
38// 删除某个结点
39func (lru *lru[K, Value]) deleteKey(key K) {
40 find, ok := lru.data[key]
41 if !ok {
42 return
43 }
44 lru.cache.Remove(find)
45 delete(lru.data, key)
46}
47
48// 删除最久没有使用的
49func (lru *lru[K, Value]) removerLeastRecently() {
50 head := lru.cache.Front()
51 lru.cache.PopFront()
52 delete(lru.data, head.Val.Key)
53}
54
55// Put
56func (lru *lru[K, Value]) Put(key K, val Value) {
57 _, ok := lru.data[key]
58 if ok {
59 lru.deleteKey(key)
60 }
61 if lru.cap == lru.cache.Size() {
62 lru.removerLeastRecently()
63 }
64 lru.addRecently(key, val)
65}
66
67// Get
68func (lru *lru[K, Value]) Get(key K) (Value, error) {
69 find, ok := lru.data[key]
70 if !ok {
71 var t Value
72 return t, NotFoundErr
73 }
74 lru.makeRecently(key)
75 return find.Val.Value, nil
76}