LRU 缓存

2021-03-08 986 words 2 minutes

Contents

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例 1：

输入：[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出：[null, null, null, 1, null, -1, null, -1, 3, 4]

解释：

LRUCache lRUCache = new LRUCache(2);

lRUCache.put(1, 1); // 缓存是 {1=1}

lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}

lRUCache.get(1); // 返回 1

lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}

lRUCache.get(2); // 返回 -1 (未找到)

lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}

lRUCache.get(1); // 返回 -1 (未找到)

lRUCache.get(3); // 返回 3

lRUCache.get(4); // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= $10^5$
最多调用 2 * $10^5$ 次 get 和 put

题解

双向链表+HashMap

        
        
        
    
type LRUCache struct {
	Capacity    int
	Len         int
	KeyValueMap map[int]*Node
	Head        *Node
	Tail        *Node
}

type Node struct {
	Key   int
	Value int
	Pre   *Node
	Next  *Node
}

func (this *LRUCache) addNode2Head(node *Node) {
	oldHead := this.Head.Next
	this.Head.Next = node
	node.Pre = this.Head
	node.Next = oldHead
	oldHead.Pre = node
}

func (this *LRUCache) removeNode(node *Node) {
	preNode := node.Pre
	nextNode := node.Next
	preNode.Next = nextNode
	nextNode.Pre = preNode
}

func (this *LRUCache) getLastNode() *Node {
	return this.Tail.Pre
}

func Constructor(capacity int) LRUCache {
	head := &Node{}
	tail := &Node{}
	head.Next = tail
	tail.Pre = head
	return LRUCache{
		Capacity:    capacity,
		Len:         0,
		KeyValueMap: map[int]*Node{},
		Head:        head,
		Tail:        tail,
	}
}

func (this *LRUCache) Get(key int) int {
	node, found := this.KeyValueMap[key]
	if !found {
		return -1
	}
	this.removeNode(node)
	this.addNode2Head(node)
	return node.Value
}

func (this *LRUCache) Put(key int, value int) {
	node, found := this.KeyValueMap[key]
	if found {
		node.Value = value
		this.removeNode(node)
		this.addNode2Head(node)
		return
	}

	newNode := &Node{
		Key:   key,
		Value: value,
	}
	if this.Len >= this.Capacity {
		lastNode := this.getLastNode()
		delete(this.KeyValueMap, lastNode.Key)
		this.removeNode(lastNode)
		this.KeyValueMap[key] = newNode
		this.addNode2Head(newNode)
		return
	}

	this.KeyValueMap[key] = newNode
	this.addNode2Head(newNode)
	this.Len++
}

时间复杂度: 对于 put 和 get 都是 O(1)

空间复杂度: O(capacity)

延伸问题: 该缓存线(协)程安全吗

线(协)程安不安全，需要加锁

        
        
        
    
type LRUCache struct {
	Capacity    int
	Len         int
	KeyValueMap map[int]*Node
	Head        *Node
	Tail        *Node
	RwLock      sync.RWMutex
}

type Node struct {
	Key   int
	Value int
	Pre   *Node
	Next  *Node
}

func (this *LRUCache) addNode2Head(node *Node) {
	oldHead := this.Head.Next
	this.Head.Next = node
	node.Pre = this.Head
	node.Next = oldHead
	oldHead.Pre = node
}

func (this *LRUCache) removeNode(node *Node) {
	preNode := node.Pre
	nextNode := node.Next
	preNode.Next = nextNode
	nextNode.Pre = preNode
}

func (this *LRUCache) getLastNode() *Node {
	return this.Tail.Pre
}

func Constructor(capacity int) LRUCache {
	head := &Node{}
	tail := &Node{}
	head.Next = tail
	tail.Pre = head
	return LRUCache{
		Capacity:    capacity,
		Len:         0,
		KeyValueMap: map[int]*Node{},
		Head:        head,
		Tail:        tail,
	}
}

func (this *LRUCache) Get(key int) int {
	this.RwLock.RLock()
	defer this.RwLock.RUnlock()
	node, found := this.KeyValueMap[key]
	if !found {
		return -1
	}
	this.removeNode(node)
	this.addNode2Head(node)
	return node.Value
}

func (this *LRUCache) Put(key int, value int) {
	this.RwLock.Lock()
	defer this.RwLock.Unlock()
	node, found := this.KeyValueMap[key]
	if found {
		node.Value = value
		this.removeNode(node)
		this.addNode2Head(node)
		return
	}

	newNode := &Node{
		Key:   key,
		Value: value,
	}
	if this.Len >= this.Capacity {
		lastNode := this.getLastNode()
		delete(this.KeyValueMap, lastNode.Key)
		this.removeNode(lastNode)
		this.KeyValueMap[key] = newNode
		this.addNode2Head(newNode)
		return
	}

	this.KeyValueMap[key] = newNode
	this.addNode2Head(newNode)
	this.Len++
}

总结

实现本题的两种操作，需要用到一个哈希表和一个双向链表。在面试中，面试官一般会期望读者能够自己实现一个简单的双向链表，而不是使用语言自带的、封装好的数据结构。

作为后端开发，为什么要用缓存，用缓存的场景大概率是在并发的场景下，并发就要考虑线程安全，面试官可以接着问，如何实现线程安全的LRU缓存。

使用了知识点:

双向链表
HashMap
读写锁