146 LRU缓存

题目描述#

设计一个满足 LRU (最近最少使用) 约束的缓存结构。

它需要支持两类操作：

get(key)：如果 key 存在，返回对应的 value，否则返回 -1
put(key, value)：如果 key 已存在，就更新它的值；如果不存在，就插入一组新的键值对；当容量超出限制时，要删除最近最少使用的那个 key

题目还要求 get 和 put 的平均时间复杂度都要做到 O(1)。

思路#

这道题的关键在于同时满足两个要求：一是要能通过 key 快速找到节点，二是要能快速维护“最近使用顺序”。只靠哈希表只能做到快速查找，没法在 O(1) 时间内把某个元素挪到“最新使用”的位置；只靠链表又没法快速按 key 定位节点。所以这里把两种结构组合起来使用。

这份代码里，cnt 是一个哈希表，负责从 key 直接找到对应的链表节点。双向链表负责维护访问顺序，越靠近头部表示越新，越靠近尾部表示越久没用。为了让头插和删除都更统一，这里用了一个循环双向链表的哑节点 dummy，这样头节点和尾节点都可以通过它来间接拿到，不需要额外分类讨论空链表和单节点链表。

每次执行 get 时，先通过 GetAndPutToTop 查哈希表。如果找到了节点，就先把它从当前位置摘下来，再插到链表头部，表示它刚刚被访问过；如果找不到，直接返回 -1。

每次执行 put 时，也会先尝试通过 GetAndPutToTop 看这个 key 是否已经存在。如果存在，就说明只是更新值，同时这个节点也因为被访问而移动到了头部；如果不存在，就新建一个节点，插到头部，并同步记录到哈希表里。插入完成后如果发现缓存数量超过容量，就把链表尾部那个节点删掉，因为它正是最近最少使用的节点，再把它从哈希表中移除。

整个过程中，哈希表查找、双向链表删除、头插，都是 O(1) 操作，因此 get 和 put 的平均时间复杂度都满足题目要求。

代码#

type Node struct {
	key   int
	value int
	Pre   *Node
	Next  *Node
}

type LRUCache struct {
	capacity int
	dummy    *Node
	cnt      map[int]*Node
}

func Constructor(capacity int) LRUCache {
	dummy := &Node{}
	dummy.Next = dummy
	dummy.Pre = dummy
	return LRUCache{
		capacity: capacity,
		dummy:    dummy,
		cnt:      map[int]*Node{},
	}
}

// 把书放到书本顶部
func (this *LRUCache) PutToTop(node *Node) {
	node.Pre = this.dummy
	node.Next = this.dummy.Next
	this.dummy.Next = node
	node.Next.Pre = node
}

// 把书移除书堆
func (this *LRUCache) DeleteNode(node *Node) {
	node.Pre.Next = node.Next
	node.Next.Pre = node.Pre
}

// 得到key对应的节点，然后把节点放到书本头部
func (this *LRUCache) GetAndPutToTop(key int) *Node {
	node, ok := this.cnt[key]
	if ok == false {
		return nil
	}
	this.DeleteNode(node)
	this.PutToTop(node)
	return node
}

func (this *LRUCache) Get(key int) int {
	node := this.GetAndPutToTop(key)
	if node == nil {
		return -1
	}
	return node.value
}

func (this *LRUCache) Put(key int, value int) {
	node := this.GetAndPutToTop(key)
	if node != nil {
		node.value = value
        return
	}
	// 这里发现是新书
	node = &Node{
		key:   key,
		value: value,
	}
	this.cnt[key] = node
	this.PutToTop(node)
	if len(this.cnt) > this.capacity {
		tailNode := this.dummy.Pre
		this.DeleteNode(tailNode)      // 删除书堆的最后一本书
		delete(this.cnt, tailNode.key) // 删除哈希表中的记录
	}
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */