type LRUCache struct {
size int
capacity int
cache map[int]*DLinkedNode
head, tail *DLinkedNode
}
type DLinkedNode struct {
key, value int
prev, next *DLinkedNode
}
func initDLinkedNode(key, value int) *DLinkedNode {
return &DLinkedNode{
key: key,
value: value,
}
}
func Constructor(capacity int) LRUCache {
l := LRUCache{
cache: map[int]*DLinkedNode{},
head: initDLinkedNode(0, 0),
tail: initDLinkedNode(0, 0),
capacity: capacity,
}
l.head.next = l.tail
l.tail.prev = l.head
return l
}
func (this *LRUCache) Get(key int) int {
if _, ok := this.cache[key]; !ok {
return -1
}
node := this.cache[key]
this.moveToHead(node)
return node.value
}
func (this *LRUCache) Put(key int, value int) {
if _, ok := this.cache[key]; !ok {
node := initDLinkedNode(key, value)
this.cache[key] = node
this.addToHead(node)
this.size++
if this.size > this.capacity {
removed := this.removeTail()
delete(this.cache, removed.key)
this.size--
}
} else {
node := this.cache[key]
node.value = value
this.moveToHead(node)
}
}
func (this *LRUCache) addToHead(node *DLinkedNode) {
node.prev = this.head
node.next = this.head.next
this.head.next.prev = node
this.head.next = node
}
func (this *LRUCache) removeNode(node *DLinkedNode) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (this *LRUCache) moveToHead(node *DLinkedNode) {
this.removeNode(node)
this.addToHead(node)
}
func (this *LRUCache) removeTail() *DLinkedNode {
node := this.tail.prev
this.removeNode(node)
return node
}type LFUCache struct {
capacity int // 总容量
size int // 当前缓存大小
LFUMap map[int]*LinkNode // 记录最不经常用,
KeyMap map[int]*LinkNode // get的时候可以找到节点的信息,然后进行更新
minFreq int // 最小频率,用于直接删除
}
type LinkNode struct {
key, val, freq int
next *LinkNode
}
func Constructor(capacity int) LFUCache {
return LFUCache {
capacity: capacity,
size : 0,
LFUMap : make(map[int]*LinkNode),
KeyMap : make(map[int]*LinkNode),
}
}
func (this *LFUCache) Get(key int) int {
// 判断是否存在
if node, ok := this.KeyMap[key]; ok {
// 先删除LFUmap中的node节点
b := this.delFreqNode(node)
// 如果此时的freq没有节点了
// 还要判断当前的freq是不是最小值
// 如果是最小值,则最小值更新freq+1
if b && node.freq == this.minFreq {
this.minFreq++
}
// 然后更新node中的freq
node.freq++
// 通过更新后的freq,找到属于新freq的新的链表
this.updFreqNode(node)
return node.val
}
return -1
}
// 删除要更新的node
func (this *LFUCache)delFreqNode(node *LinkNode) bool {
dummyHead := this.LFUMap[node.freq]
p := dummyHead
freqKeyNode := p.next
for freqKeyNode != nil {
if freqKeyNode == node {
break
}
freqKeyNode = freqKeyNode.next
p = p.next
}
// 删除node
p.next = freqKeyNode.next
return dummyHead.next == nil
}
// 添加要更新的node
// 并返回删除后是否该频率下无节点
func (this *LFUCache)updFreqNode(node *LinkNode) {
if p, ok := this.LFUMap[node.freq]; ok {
// 如果更新后的freq有
// 添加到表头
temp := p.next
p.next = node
node.next = temp
} else {
// 没有要进行初始化
dummyHead := &LinkNode{0,0,0,nil}
this.LFUMap[node.freq] = dummyHead
dummyHead.next = node
node.next = nil
}
}
func (this *LFUCache) Put(key int, value int) {
if this.capacity == 0 {
return
}
// 判断是否存在
if node, ok := this.KeyMap[key]; ok {
// 存在则更新value,同时更新freq
// 先删除LFUmap中的node节点,找到链表头
b := this.delFreqNode(node)
if b && this.minFreq == node.freq {
this.minFreq++
}
// 然后更新node中的freq
node.freq++
// 通过更新后的freq,找到属于新freq的新的链表
this.updFreqNode(node)
node.val = value
} else {
// 不存在
// 先判断内存是否符合
if this.size >= this.capacity {
// 删除最小的freq,且最不经常使用的
// 其实就是尾节点
// 这是不用更新minfreq
node := this.LFUMap[this.minFreq]
p := node.next
for p.next != nil {
p = p.next
node = node.next
}
node.next = p.next
delete(this.KeyMap,p.key)
this.size--
}
// 添加新节点
node := &LinkNode {
key:key,
val:value,
freq:1,
}
// 更新最小min
this.minFreq = 1
this.updFreqNode(node)
this.size++
this.KeyMap[key] = node
}
}
作者：lr_ls
链接：https://leetcode-cn.com/problems/lfu-cache/solution/golang-shuang-hashshi-xian-by-lr_ls-h95c/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。