Go语言实现LRU算法

       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