golang LRU实现(使用双向链表实现)

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

lru.go

type Key interface{}

type entry struct {
    key    Key
    value interface{}  
}       

type Cache Struct {
    MaxEntries int
    OnEvicted func(key Key,value interface{})
    ll    *list.List
    cache map[interface{}]*list.Element
}

定义了Key,entry,Cache类型，
Key：interface{}类型，在Go中interface{}可以指向任意对象，也就任意对象都是先这个接口，你可以把它看成Java/C#中的Object,C/C++中的void*。
Cache：MaxEntires表示Cache中最大可以有的KV数，OnEvicted是一个回调函数，在触发淘汰时调用，ll是一个链表，cache是一个map，key为interface{}， value为list.Element其指向的类型是entry类型。
通过数据结构我们可以猜到LRU的实现，Get一次放到list头，每次Add的时候判断是否满，满则淘汰掉list尾的数据

// 创建一个Cache
func New(maxEntries int) *Cache {
	return &Cache{
		MaxEntries: maxEntries,ll:         list.New(),cache:      make(map[interface{}]*list.Element),}
}
// 向Cache中插入一个KV，如果缓存已满，则删除最久为使用的对象。
func (c *Cache) Add(key Key,value interface{}) {
	if c.cache == nil {
		c.cache = make(map[interface{}]*list.Element)
		c.ll = list.New()
	}
	if ee,ok := c.cache[key]; ok {
		c.ll.MoveToFront(ee)
		ee.Value.(*entry).value = value
		return
	}
	ele := c.ll.PushFront(&entry{key,value})
	c.cache[key] = ele
	if c.MaxEntries != 0 && c.ll.Len() > c.MaxEntries {
		c.RemoveOldest()
	}
}
// 从Cache中获取一个key对应的value，并把key移动到列表的开头。表示最近使用过。
func (c *Cache) Get(key Key) (value interface{},ok bool) {
	if c.cache == nil {
		return
	}
	if ele,hit := c.cache[key]; hit {
		c.ll.MoveToFront(ele)
		return ele.Value.(*entry).value,true
	}
	return
}

// 从Cache中删除一个key
func (c *Cache) Remove(key Key) {
	if c.cache == nil {
		return
	}
	if ele,hit := c.cache[key]; hit {
		c.removeElement(ele)
	}
}

// 从Cache中删除最久未被访问的数据
func (c *Cache) RemoveOldest() {
	if c.cache == nil {
		return
	}
	ele := c.ll.Back()
	if ele != nil {
		c.removeElement(ele)
	}
}
// 获取当前Cache中的元素个数
func (c *Cache) Len() int {
	if c.cache == nil {
		return 0
	}
	return c.ll.Len()
}

//删除缓存中的元素，私有方法
func (c *Cache) removeElement(e *list.Element) {
	c.ll.Remove(e)
	kv := e.Value.(*entry)
	delete(c.cache,kv.key)
	if c.OnEvicted != nil {
		c.OnEvicted(kv.key,kv.value)
	}
}

这里我们看到了Go中如何实现一个类的成员方法，在func之后加类，在Go中接口的实现并不是和Java中那样子，而是只要某个类只要实现了某个接口的所有方法，即可认为该类实现了该接口。
类似的比如说在java中有2个接口名字不同，即使方法相同也是不一样的，而Go里面认为这是一样的。
另外Go中开头字母大写的变量名，类名，方法名表示对外可知，小写开头的表示对外不暴露。
另外类实这种代码ele.Value.(*entry).value，其中(*entry)表示将Value转成*entry类型访问。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!