LRU 通常使用hash map + doubly linked list实现。在Golange中很简单，使用List保存数据,Map来做快速访问即可.
具体实现了下面几个函数:
func NewLRUCache(cap int)(*LRUCache)
func (lru *LRUCache)Set(k,v interface{})(error)
func (lru *LRUCache)Get(k interface{})(v interface{},ret bool,err error)
func (lru *LRUCache)Remove(k interface{})(bool)
演示:
package main
//LRU Cache
//author:Xiong Chuan Liang
//date:2015-2-3
import (
"fmt"
"github.com/xcltapestry/xclpkg/algorithm"
)
func main(){
lru := algorithm.NewLRUCache(3)
lru.Set(10,"value1")
lru.Set(20,"value2")
lru.Set(30,"value3")
lru.Set(10,"value4")
lru.Set(50,"value5")
fmt.Println("LRU Size:",lru.Size())
v,ret,_ := lru.Get(30)
if ret {
fmt.Println("Get(30) : ",v)
}
if lru.Remove(30) {
fmt.Println("Remove(30) : true ")
}else{
fmt.Println("Remove(30) : false ")
}
fmt.Println("LRU Size:",lru.Size())
}
运行结果:
LRU Size: 3 Get(30) : value3 Remove(30) : true LRU Size: 2
具体的 实现源码:
package algorithm
//LRU Cache
//author:Xiong Chuan Liang
//date:2015-2-3
//"github.com/xcltapestry/xclpkg/algorithm"
import (
"container/list"
"errors"
)
type CacheNode struct {
Key,Value interface{}
}
func (cnode *CacheNode)NewCacheNode(k,v interface{})*CacheNode{
return &CacheNode{k,v}
}
type LRUCache struct {
Capacity int
dlist *list.List
cacheMap map[interface{}]*list.Element
}
func NewLRUCache(cap int)(*LRUCache){
return &LRUCache{
Capacity:cap,
dlist: list.New(),
cacheMap: make(map[interface{}]*list.Element)}
}
func (lru *LRUCache)Size()(int){
return lru.dlist.Len()
}
func (lru *LRUCache)Set(k,v interface{})(error){
if lru.dlist == nil {
return errors.New("LRUCache结构体未初始化.")
}
if pElement,ok := lru.cacheMap[k]; ok {
lru.dlist.MoveToFront(pElement)
pElement.Value.(*CacheNode).Value = v
return nil
}
newElement := lru.dlist.PushFront( &CacheNode{k,v} )
lru.cacheMap[k] = newElement
if lru.dlist.Len() > lru.Capacity {
//移掉最后一个
lastElement := lru.dlist.Back()
if lastElement == nil {
return nil
}
cacheNode := lastElement.Value.(*CacheNode)
delete(lru.cacheMap,cacheNode.Key)
lru.dlist.Remove(lastElement)
}
return nil
}
func (lru *LRUCache)Get(k interface{})(v interface{},ret bool,err error){
if lru.cacheMap == nil {
return v,false,errors.New("LRUCache结构体未初始化.")
}
if pElement,ok := lru.cacheMap[k]; ok {
lru.dlist.MoveToFront(pElement)
return pElement.Value.(*CacheNode).Value,true,nil
}
return v,false,nil
}
func (lru *LRUCache)Remove(k interface{})(bool){
if lru.cacheMap == nil {
return false
}
if pElement,ok := lru.cacheMap[k]; ok {
cacheNode := pElement.Value.(*CacheNode)
delete(lru.cacheMap,cacheNode.Key)
lru.dlist.Remove(pElement)
return true
}
return false
} 附注:
1.key记录在map
2.对于set/get添加或命中的元素移到链表头
3.如总个数大于Cache容量(cap),则将最末的元素移除.
MAIL: xcl_168@aliyun.com
BLOG:http://blog.csdn.net/xcl168
有疑问加站长微信联系（非本文作者）
