LRU,Least Recently Used的缩写,即“最近最少使用”,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。这里,我们基于 LeetCode 146. LRU 缓存 ,使用Golang实现,并使其Get
、Put
操作的时间复杂度均为O(1)。
思路很简单,使用HashMap保存Cache,保证其Get
的复杂度为O(1),使用一个双向链表,保证Put
操作维护使用顺序时的时间复杂度为O(1)。
Get
key存在
- 将节点移至最前面
- 返回value
key不存在
- 返回不存在
Put
Key存在
- 将节点移至最前面
- 更新Value
Key不存在
长度未到上限
- 直接将节点放至最前面
长度打到上限
- 删除最后面的节点
- 将节点放到最前面
代码实现:
package lru
type LRUCache struct {
cache map[int]*LRUNode // 保存cache的hashMap
cap int // 容量
head *LRUNode // 虚拟头节点
end *LRUNode // 虚拟尾结点
}
// 双向链表节点
type LRUNode struct {
key int // Key
value int // Value
pre *LRUNode // 前节点
next *LRUNode // 后节点
}
// 初始化
func Constructor(capacity int) LRUCache {
cache := LRUCache{
cache: make(map[int]*LRUNode),
cap: capacity,
head: newLRUNode(0, 0),
end: newLRUNode(0, 0),
}
cache.head.next = cache.end
cache.end.pre = cache.head
return cache
}
// Get操作
func (c *LRUCache) Get(key int) int {
// 查询节点
node, ok := c.cache[key]
// 不存在,返回-1
if !ok {
return -1
}
// 存在,将节点移到前面
node.removeNode()
node.moveToHead(c.head)
return node.value
}
// Put操作
func (c *LRUCache) Put(key int, value int) {
// 查询节点
node, ok := c.cache[key]
// 节点存在,将节点移到前面,并更新节点
if ok {
node.removeNode()
node.moveToHead(c.head)
node.value = value
return
}
// 节点不存在,需要插入
node = newLRUNode(key, value)
// 判断当前长度,若小于容量,直接插入头部
if len(c.cache) < c.cap {
c.cache[key] = node
node.moveToHead(c.head)
return
}
// 大于等于容量,删除尾部并插入到头部
c.cache[key] = node
delete(c.cache, c.end.pre.key)
c.end.pre.removeNode()
node.moveToHead(c.head)
return
}
// 创建节点
func newLRUNode(key int, value int) *LRUNode {
return &LRUNode{
key: key,
value: value,
}
}
// 节点移除
func (n *LRUNode) removeNode() {
n.pre.next = n.next
n.next.pre = n.pre
n.pre = nil
n.next = nil
}
// 移到虚拟头节点后面(将节点放到前面)
func (n *LRUNode) moveToHead(head *LRUNode) {
head.next.pre = n
n.pre = head
n.next = head.next
head.next = n
}
运行结果:
(所以我为什么这样都要水一篇博客)
4 条评论
想想你的文章写的特别好https://www.ea55.com/
不错不错,我喜欢看 https://www.237fa.com/
不错不错,我喜欢看
陈福蓐:文章真不错http://wap.jst-gpmx.cn/news/29954.html