关于lrucache:LRU缓存机制实现Go版本

在我第一次写 LRU 时，应用 map+ 列表 的模式，map 使得 get 和 set 的工夫复杂度为 O(1)，列表保护插入元素的程序，当 get 或 set 元素时，将元素挪动或插入到队头；当达到 LRU 缓存容量下限时，将列表尾部元素去除掉。

然而在列表中调整元素程序时，工夫复杂度达不到 O(1)。

明天写了一个改进版，应用 map+ 双向链表 的模式。map 存储 key 和链表节点的指针，双向链表中既存储 key 也存储 value。map 仍然用来使 get 和 set 的工夫复杂度为 O(1)，当须要将元素挪动到队头时，仅需通过 map 找到节点，将节点左右连贯打断，而后插入到队头，当删除元素或队头插入元素时，仅需找到头尾节点再进行插入或删除就能够了。这样取代列表后，工夫复杂度变为 O(1)。

援用一张图来阐明这个构造。

操作流程：

get 操作：

• 在 map 中存在：将元素挪动至链表头节点，返回 value 值
• 在 map 中不存在：返回 -1

set 操作：

• 在 map 中存在：批改节点中 value 的值，而后将节点挪动到链表头节点
• 在 map 中不存在：
• • 没有达到 cap 下限：构建节点，map 中存储此节点，而后将节点插入到头节点
  • 达到 cap 下限：先删除链表队尾元素，删除 map 中的 key。而后构建节点，map 中存储此节点，而后将节点插入到头节点

代码：

package main

import "fmt"

// map 用来 get 和 set，双向链表放弃绝对程序
// 为什么用双向链表？因为在删除节点时，以及插入到头部时，工夫复杂度都是 1

type Node struct {
    pre *Node
    next *Node
    key int // 不便删除 map 中的 key
    value int //
}

type lruCache struct {
    cap int  // 存储容量，达到容量后再插入则须要删除元素
    headNode *Node  // 双向链表头节点，tailNode *Node  // 双向链表尾节点，nodeMap map[int]*Node  // 使得 get、set 操作工夫复杂度为 1
}

func (l *lruCache) get(k int) int {node := l.nodeMap[k]
    if node == nil{return -1}
    // 获取元素，并将此元素挪动到 head 头地位
    headNode := l.headNode
    // 将节点截取
    node.pre.next = node.next
    node.next.pre = node.pre
    // 而后将此节点插入到头节点
    headNode.next.pre = node
    node.next = headNode.next
    headNode.next = node
    node.pre = headNode

    v := node.value
    return v
}

func (l *lruCache) set(k, v int) {node := l.nodeMap[k]
    // 第一种状况，k 在 map 中不存在，直接插入到头节点
    if node == nil{// 思考 lru 的容量，达到容量后则要删除尾部元素(间接让尾部元素的指针断开)
        if len(l.nodeMap) == l.cap {
            lastNode := l.tailNode.pre
            lastNode.pre.next = l.tailNode
            l.tailNode.pre = lastNode.pre
            lastNode.pre = nil
            lastNode.next = nil
            // map 中也要删除
            deleteKey := lastNode.key
            delete(l.nodeMap, deleteKey)
        }
        newNode := &Node{
            pre:   l.headNode,
            next:  l.headNode.next,
            key:   k,
            value: v,
        }
        l.headNode.next = newNode
        newNode.next.pre = newNode
        // map 中设置值
        l.nodeMap[k] = newNode
    }else{
        // 第二种状况，key 在 map 中存在。将 map 的值更改，而后将此值挪动到头部
        node.value = v
        // 将节点截取
        node.pre.next = node.next
        node.next.pre = node.pre
        // 而后将此节点插入到头节点
        firstNode := l.headNode
        secondNode := l.headNode.next
        firstNode.next = node
        secondNode.pre = node
        node.next = secondNode
        node.pre = firstNode
    }

}



func main() {
    head := &Node{
        pre: nil,
        next: nil,
        key: 0,
        value: 0,
    }
    tail := &Node{
        pre: nil,
        next: nil,
        key: 0,
        value: 0,
    }
    head.next = tail
    tail.pre = head
    lru := lruCache{
        cap: 2,
        headNode: head,
        tailNode: tail,
        nodeMap: make(map[int]*Node),
    }
    lru.set(1,1)
    lru.set(2, 2)
    re := lru.get(1)
    fmt.Println(re)  // 1
    lru.set(3,3)
    re = lru.get(2)
    fmt.Println(re)  // -1
    re = lru.get(3)
    fmt.Println(re)  // 3
    lru.set(4, 4)
    re = lru.get(1)
    fmt.Println(re)  // -1
    re = lru.get(3)
    fmt.Println(re)  // 3
    re = lru.get(4)
    fmt.Println(re)  // 4
}