【图解版】力扣第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[int]*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[int]*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[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] = 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[key]
        node.val = val
        this.moveToHead(node)
    }
}

三、代码图解

1. LRUCache、DLinkedNode两个结构体

type LRUCache struct {
    size int
    capacity int
    cache map[int]*DLinkedNode
    head, tail *DLinkedNode
}

type DLinkedNode struct {
    key, val int
    prev, 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.tail
    l.tail.prev = l.head
    return l
}

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
}

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

4. removeNode函数

// 将节点从链表中单独抽出来
func (this *LRUCache) removeNode(node *DLinkedNode) {
    node.prev.next = node.next
    node.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.prev
    this.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是不存在的，那就返回-1
    if _, 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] = 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[key]
        node.val = val
        this.moveToHead(node)
    }
}

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

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

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