# Go语言实现LRU算法

xcltapestry · · 4658 次点击 · · 开始浏览

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

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

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