LRU go language implementation
LRU 算法:
获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1
写入数据 put(key, value) - 如果密钥已经存在,则变更其数据值;如果密钥不存在,则插入该组「密钥/数据值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间
type LRUCache struct {
list *list.List
tag map[int]*list.Element
capacity int
}
type Item struct {
key int
value int
}
func Constructor(capacity int) LRUCache {
return LRUCache {
list.New(),
make(map[int]*list.Element),
capacity,
}
}
func (this *LRUCache) Get(key int) int {
value := -1
// 命中,将当前元素移到list首部,且返回改key对应的value
if this.tag[key] != nil {
element := this.tag[key]
value = element.Value.(Item).value
this.list.Remove(element)
element = this.list.PushFront(Item{key, value})
// 元素移位后更新tag
this.tag[key] = element
}
return value
}
func (this *LRUCache) Put(key int, value int) {
// 如果key已经存在,则删除原值,在首部插入新值
if this.tag[key] != nil {
element := this.tag[key]
this.list.Remove(element)
element = this.list.PushFront(Item{key, value})
this.tag[key] = element
} else {
// 如果key不存在,则插入新值。先判断是否将要达到上限
if this.list.Len() >= this.capacity {
element := this.list.Back()
this.tag[element.Value.(Item).key] = nil
this.list.Remove(element)
}
element := this.list.PushFront(Item{key, value})
this.tag[key] = element
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/