golang实现LRU缓存淘汰算法的示例代码
LRU缓存淘汰算法
LRU是最近最少使用策略的缩写，是根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
双向链表实现LRU
将Cache的所有位置都用双链表连接起来，当一个位置被访问(get/put)之后，通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表头中。
这样，在多次操作后，最近被访问(get/put)的，就会被向链表头方向移动，而没有访问的，向链表后方移动，链表尾则表示最近最少使用的Cache。
当达到缓存容量上限时，链表的最后位置就是最少被访问的Cache，我们只需要删除链表最后的Cache便可继续添加新的Cache。
代码实现
typeNodestruct{
Keyint
Valueint
pre*Node
next*Node
}
typeLRUCachestruct{
limitint
HashMapmap[int]*Node
head*Node
end*Node
}
funcConstructor(capacityint)LRUCache{
lruCache:=LRUCache{limit:capacity}
lruCache.HashMap=make(map[int]*Node,capacity)
returnlruCache
}
func(l*LRUCache)Get(keyint)int{
ifv,ok:=l.HashMap[key];ok{
l.refreshNode(v)
returnv.Value
}else{
return-1
}
}
func(l*LRUCache)Put(keyint,valueint){
ifv,ok:=l.HashMap[key];!ok{
iflen(l.HashMap)>=l.limit{
oldKey:=l.removeNode(l.head)
delete(l.HashMap,oldKey)
}
node:=Node{Key:key,Value:value}
l.addNode(&node)
l.HashMap[key]=&node
}else{
v.Value=value
l.refreshNode(v)
}
}
func(l*LRUCache)refreshNode(node*Node){
ifnode==l.end{
return
}
l.removeNode(node)
l.addNode(node)
}
func(l*LRUCache)removeNode(node*Node)int{
ifnode==l.end{
l.end=l.end.pre
}elseifnode==l.head{
l.head=l.head.next
}else{
node.pre.next=node.next
node.next.pre=node.pre
}
returnnode.Key
}
func(l*LRUCache)addNode(node*Node){
ifl.end!=nil{
l.end.next=node
node.pre=l.end
node.next=nil
}
l.end=node
ifl.head==nil{
l.head=node
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。