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是@L_136_0@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类型访问。

大佬总结

以上是大佬教程为你收集整理的golang LRU实现(使用双向链表实现)全部内容，希望文章能够帮你解决golang LRU实现(使用双向链表实现)所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。