【图解版】力扣第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 int
capacity int
cache map*DLinkedNode
head, tail *DLinkedNode
}
type DLinkedNode struct {
key, val int
prev, next *DLinkedNode
}
func initDLinkedNode(key, val int) *DLinkedNode {
return &DLinkedNode{
key: key,
val: val,
}
}
func Constructor(capacity int) LRUCache {
l := LRUCache{
cache: map*DLinkedNode{},
head: initDLinkedNode(0, 0),
tail: initDLinkedNode(0, 0),
capacity: capacity,
}
l.head.next = l.tail
l.tail.prev = l.head
return l
}
func (this *LRUCache) addToHead(node *DLinkedNode) {
node.prev = this.head
node.next = this.head.next
this.head.next.prev = node
this.head.next = node
}
func (this *LRUCache) removeNode(node *DLinkedNode) {
// 将节点从链表中单独抽出来
node.prev.next = node.next
node.next.prev = node.prev
}
func (this *LRUCache) moveToHead(node *DLinkedNode) {
this.removeNode(node)
this.addToHead(node)
}
func (this *LRUCache) removeTail() *DLinkedNode {
node := this.tail.prev
this.removeNode(node)
delete(this.cache, node.key)
return node
}
// 通过cache的map关系，找到对应的值，该值存储在node的val属性中。
func (this *LRUCache) Get(key int) int {
// 如果key是不存在的，那就返回-1
if _, ok := this.cache; !ok {
return -1
}
node := this.cache
this.moveToHead(node)
return node.val
}
func (this *LRUCache) Put(key int, val int){
if _, ok := this.cache; !ok {
node := initDLinkedNode(key, val)
this.cache = node
this.addToHead(node)
this.size++
if this.size > this.capacity {
removed := this.removeTail()
delete(this.cache, removed.key)
this.size--
}
} else {
node := this.cache
node.val = val
this.moveToHead(node)
}
}
三、代码图解
1. LRUCache、DLinkedNode两个结构体
type LRUCache struct {
size int
capacity int
cache map*DLinkedNode
head, tail *DLinkedNode
}
type DLinkedNode struct {
key, val int
prev, next *DLinkedNode
}
https://i-blog.csdnimg.cn/direct/d7cb23f84b4e41cc9485b95288e7fbc6.png#pic_center
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*DLinkedNode{},
head: initDLinkedNode(0, 0),
tail: initDLinkedNode(0, 0),
capacity: capacity,
}
l.head.next = l.tail
l.tail.prev = l.head
return l
}
https://i-blog.csdnimg.cn/direct/32f88a8ca3274692a3e2ea756470131d.png#pic_center
3. addToHead函数
func (this *LRUCache) addToHead(node *DLinkedNode) {
node.prev = this.head
node.next = this.head.next
this.head.next.prev = node
this.head.next = node
}
https://i-blog.csdnimg.cn/direct/6669fc73a66541e7b2f6b3f89ae95d4f.png
注意：这里关于节点的顺序，其实是在结构体外去排的，这个节点的顺序并不是排在两个结构体内的哦。
4. removeNode函数
// 将节点从链表中单独抽出来
func (this *LRUCache) removeNode(node *DLinkedNode) {
node.prev.next = node.next
node.next.prev = node.prev
}
https://i-blog.csdnimg.cn/direct/37762d90e02b4df095e7472bac8ac0bf.png
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.prev
this.removeNode(node)
delete(this.cache, node.key)
return node
}
https://i-blog.csdnimg.cn/direct/0ba0384fea044cb59b6c78a6a866c40f.png
因为map的key无法直接获得，而node.key和map的key一样，所以用node.key。
7. Get函数
// 通过cache的map关系，找到对应的值，该值存储在node的val属性中。
func (this *LRUCache) Get(key int) int {
// 如果key是不存在的，那就返回-1
if _, ok := this.cache; !ok {
return -1
}
node := this.cache
this.moveToHead(node)
return node.val
}
8. Put函数
func (this *LRUCache) Put(key int, val int){
if _, ok := this.cache; !ok {
node := initDLinkedNode(key, val)
this.cache = node
this.addToHead(node)
this.size++
if this.size > this.capacity {
removed := this.removeTail()
delete(this.cache, removed.key)
this.size--
}
} else {
node := this.cache
node.val = val
this.moveToHead(node)
}
}
!ok是表现如果map里面的key为空，那就创建一个相应的新节点，让map存储一下key和该节点的映射关系，然后将该节点插入到链表头部，
如果超过LRUCahce的容量，就删除末了一个节点。
如果map里面的key不是空的，那就更新一下map存储的节点，然后将其移动到头部。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]