【图解版】力扣第146题：LRU缓存

一、LRU算法

1. 基本概念

在 LRU 算法中，首部节点的含义是最近最常访问的节点，而不是使用频率最高的节点。LRU（Least Recently Used） 是一种基于最近使用时间而非使用频率的缓存淘汰算法，核心思想是：最近使用的数据应该优先保留，最近很久未使用的数据应该被淘汰。
2. LRU 和 LFU 的区别：

• LRU（Least Recently Used）：基于数据的使用时间，最近访问的节点会移动到链表头部，而最久未访问的节点会被淘汰。它只关注末了一次访问的时间，不记录具体的访问次数。
  
• LFU（Least Frequently Used）：基于数据的使用频率，频率最高的节点会优先保留，频率最低的节点会被淘汰。
  

3. 为什么 LRU 不需要记录使用频率？

在 LRU 算法中，只需要维护每个节点的访问顺序，而不需要记录节点的访问次数。每次访问某个节点时，将该节点移动到链表的头部，而最久未使用的节点则天然在链表尾部。所以要获取最近访问的节点，直接访问链表的头部节点即可。
二、Golang代码实现

1. type LRUCache struct {
2.     size int
3.     capacity int
4.     cache map[int]*DLinkedNode
5.     head, tail *DLinkedNode
6. }
8. type DLinkedNode struct {
9.     key, val int
10.     prev, next *DLinkedNode
11. }
13. func initDLinkedNode(key, val int) *DLinkedNode {
14.     return &DLinkedNode{
15.         key: key,
16.         val: val,
17.     }
18. }
20. func Constructor(capacity int) LRUCache {
21.     l := LRUCache{
22.         cache: map[int]*DLinkedNode{},
23.         head: initDLinkedNode(0, 0),
24.         tail: initDLinkedNode(0, 0),
25.         capacity: capacity,
26.     }
27.     l.head.next = l.tail
28.     l.tail.prev = l.head
29.     return l
30. }
32. func (this *LRUCache) addToHead(node *DLinkedNode) {
33.     node.prev = this.head
34.     node.next = this.head.next
35.     this.head.next.prev = node
36.     this.head.next = node
37. }
39. func (this *LRUCache) removeNode(node *DLinkedNode) {
40.         // 将节点从链表中单独抽出来
41.     node.prev.next = node.next
42.     node.next.prev = node.prev
43. }
45. func (this *LRUCache) moveToHead(node *DLinkedNode) {
46.     this.removeNode(node)
47.     this.addToHead(node)
48. }
50. func (this *LRUCache) removeTail() *DLinkedNode {
51.     node := this.tail.prev
52.     this.removeNode(node)
53.     delete(this.cache, node.key)
54.     return node
55. }
57. // 通过cache的map关系，找到对应的值，该值存储在node的val属性中。
58. func (this *LRUCache) Get(key int) int {
59.         // 如果key是不存在的，那就返回-1
60.     if _, ok := this.cache[key]; !ok {
61.         return -1
62.     }
63.     node := this.cache[key]
64.     this.moveToHead(node)
65.     return node.val
66. }
69. func (this *LRUCache) Put(key int, val int)  {
70.     if _, ok := this.cache[key]; !ok {
71.         node := initDLinkedNode(key, val)
72.         this.cache[key] = node
73.         this.addToHead(node)
74.         this.size++
75.         if this.size > this.capacity {
76.             removed := this.removeTail()
77.             delete(this.cache, removed.key)
78.             this.size--
79.         }
80.     } else {
81.         node := this.cache[key]
82.         node.val = val
83.         this.moveToHead(node)
84.     }
85. }

复制代码

三、代码图解

1. LRUCache、DLinkedNode两个结构体

1. type LRUCache struct {
2.     size int
3.     capacity int
4.     cache map[int]*DLinkedNode
5.     head, tail *DLinkedNode
6. }
8. type DLinkedNode struct {
9.     key, val int
10.     prev, next *DLinkedNode
11. }

复制代码

map理解为一个存储键值对映射的地方，来（1,1），就存储（1,1），来（2,2），就存储（2,2）。
至于这些（key，val）的顺序，就用链表来控制。为了方便插入、删除节点，所以采用双向链表。
将map和双向链表联合起来，就是将map的val值设置为DoubleNode类型（双向链表类型），DoubleNode里面设置有key，val两个属性（不是映射哦），这里的key和map的key是一样大小的值。
末了的结果就是：通过map的key找到DoubleNode节点，然后找到该节点里面的val属性，至于（key，val）的顺序，是由双向链表去排的，map就是个映射到节点的地方，找到节点，就即是找到val。
2. 初始化结构体对象

1. func initDLinkedNode(key, value int) *DLinkedNode {
2.     return &DLinkedNode{
3.         key: key,
4.         value: value,
5.     }
6. }
8. func Constructor(capacity int) LRUCache {
9.     l := LRUCache{
10.         cache: map[int]*DLinkedNode{},
11.         head: initDLinkedNode(0, 0),
12.         tail: initDLinkedNode(0, 0),
13.         capacity: capacity,
14.     }
15.     l.head.next = l.tail
16.     l.tail.prev = l.head
17.     return l
18. }

复制代码

3. addToHead函数

1. func (this *LRUCache) addToHead(node *DLinkedNode) {
2.     node.prev = this.head
3.     node.next = this.head.next
4.     this.head.next.prev = node
5.     this.head.next = node
6. }

复制代码

注意：这里关于节点的顺序，其实是在结构体外去排的，这个节点的顺序并不是排在两个结构体内的哦。
4. removeNode函数

1. // 将节点从链表中单独抽出来
2. func (this *LRUCache) removeNode(node *DLinkedNode) {
3.     node.prev.next = node.next
4.     node.next.prev = node.prev
5. }

复制代码

5. moveToHead函数

1. func (this *LRUCache) moveToHead(node *DLinkedNode) {
2.     this.removeNode(node)
3.     this.addToHead(node)
4. }

复制代码

把node节点从链表中打断，抽出来，然后将node节点移到this.head后面
6. removeTail函数

1. func (this *LRUCache) removeTail() *DLinkedNode {
2.     node := this.tail.prev
3.     this.removeNode(node)
4.     delete(this.cache, node.key)
5.     return node
6. }

复制代码

因为map的key无法直接获得，而node.key和map的key一样，所以用node.key。
7. Get函数

1. // 通过cache的map关系，找到对应的值，该值存储在node的val属性中。
2. func (this *LRUCache) Get(key int) int {
3.         // 如果key是不存在的，那就返回-1
4.     if _, ok := this.cache[key]; !ok {
5.         return -1
6.     }
7.     node := this.cache[key]
8.     this.moveToHead(node)
9.     return node.val
10. }

复制代码

8. Put函数

1. func (this *LRUCache) Put(key int, val int)  {
2.     if _, ok := this.cache[key]; !ok {
3.         node := initDLinkedNode(key, val)
4.         this.cache[key] = node
5.         this.addToHead(node)
6.         this.size++
7.         if this.size > this.capacity {
8.             removed := this.removeTail()
9.             delete(this.cache, removed.key)
10.             this.size--
11.         }
12.     } else {
13.         node := this.cache[key]
14.         node.val = val
15.         this.moveToHead(node)
16.     }
17. }

复制代码

!ok是表现如果map里面的key为空，那就创建一个相应的新节点，让map存储一下key和该节点的映射关系，然后将该节点插入到链表头部，
如果超过LRUCahce的容量，就删除末了一个节点。
如果map里面的key不是空的，那就更新一下map存储的节点，然后将其移动到头部。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。