在我第一次写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
}有疑问加站长微信联系（非本文作者）
