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

一、LRU算法

1. 基本概念

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

2. LRU 和 LFU 的区别：

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

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

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

二、Golang代码实现

type LRUCache struct {size intcapacity intcache map[int]*DLinkedNodehead, tail *DLinkedNode
}type DLinkedNode struct {key, val intprev, next *DLinkedNode
}func initDLinkedNode(key, val int) *DLinkedNode {return &DLinkedNode{key: key,val: val,}
}func Constructor(capacity int) LRUCache {l := LRUCache{cache: map[int]*DLinkedNode{},head: initDLinkedNode(0, 0),tail: initDLinkedNode(0, 0),capacity: capacity,}l.head.next = l.taill.tail.prev = l.headreturn l
}func (this *LRUCache) addToHead(node *DLinkedNode) {node.prev = this.headnode.next = this.head.nextthis.head.next.prev = nodethis.head.next = node
}func (this *LRUCache) removeNode(node *DLinkedNode) {// 将节点从链表中单独抽出来node.prev.next = node.nextnode.next.prev = node.prev
}func (this *LRUCache) moveToHead(node *DLinkedNode) {this.removeNode(node)this.addToHead(node)
}func (this *LRUCache) removeTail() *DLinkedNode {node := this.tail.prevthis.removeNode(node)delete(this.cache, node.key)return node
}// 通过cache的map关系，找到对应的值，该值存储在node的val属性中。
func (this *LRUCache) Get(key int) int {// 如果key是不存在的，那就返回-1if _, ok := this.cache[key]; !ok {return -1}node := this.cache[key]this.moveToHead(node)return node.val
}func (this *LRUCache) Put(key int, val int)  {if _, ok := this.cache[key]; !ok {node := initDLinkedNode(key, val)this.cache[key] = nodethis.addToHead(node)this.size++if this.size > this.capacity {removed := this.removeTail()delete(this.cache, removed.key)this.size--}} else {node := this.cache[key]node.val = valthis.moveToHead(node)}
}

三、代码图解

1. LRUCache、DLinkedNode两个结构体

type LRUCache struct {size intcapacity intcache map[int]*DLinkedNodehead, tail *DLinkedNode
}type DLinkedNode struct {key, val intprev, next *DLinkedNode
}

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. 初始化结构体对象

func initDLinkedNode(key, value int) *DLinkedNode {return &DLinkedNode{key: key,value: value,}
}func Constructor(capacity int) LRUCache {l := LRUCache{cache: map[int]*DLinkedNode{},head: initDLinkedNode(0, 0),tail: initDLinkedNode(0, 0),capacity: capacity,}l.head.next = l.taill.tail.prev = l.headreturn l
}

3. addToHead函数

func (this *LRUCache) addToHead(node *DLinkedNode) {node.prev = this.headnode.next = this.head.nextthis.head.next.prev = nodethis.head.next = node
}

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

4. removeNode函数

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

5. moveToHead函数

func (this *LRUCache) moveToHead(node *DLinkedNode) {this.removeNode(node)this.addToHead(node)
}

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

6. removeTail函数

func (this *LRUCache) removeTail() *DLinkedNode {node := this.tail.prevthis.removeNode(node)delete(this.cache, node.key)return node
}

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

7. Get函数

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

8. Put函数

func (this *LRUCache) Put(key int, val int)  {if _, ok := this.cache[key]; !ok {node := initDLinkedNode(key, val)this.cache[key] = nodethis.addToHead(node)this.size++if this.size > this.capacity {removed := this.removeTail()delete(this.cache, removed.key)this.size--}} else {node := this.cache[key]node.val = valthis.moveToHead(node)}
}

!ok是表示如果map里面的key为空，那就创建一个相应的新节点，让map存储一下key和该节点的映射关系，然后将该节点插入到链表头部，

如果超过LRUCahce的容量，就删除最后一个节点。

如果map里面的key不是空的，那就更新一下map存储的节点，然后将其移动到头部。