LRU 算法

LRU 最近最少使用算法,LRU算法主要用于缓存淘汰。主要目的就是把最近最少使用的数据移除内存,以加载其他数据。

原理

添加元素时,放到链表头
缓存命中,将元素移动到链表头
缓存满了之后,将链表尾的元素删除

LRU算法实现

• 可以用一个双向链表保存数据
• 使用hash实现O(1)的访问

groupcache中LRU算法实现(Go语言)
https://github.com/golang/groupcache/blob/master/lru/lru.go

源码简单注释:

package lru
import "container/list"
// Cache 结构体,定义lru cache 不是线程安全的
type Cache struct {
 // 数目限制,0是无限制 
 MaxEntries int
 // 删除时, 可以添加可选的回调函数
 OnEvicted func(key Key, value interface{})
 ll *list.List // 使用链表保存数据
 cache map[interface{}]*list.Element // map 
}
// Key 是任何可以比较的值 http://golang.org/ref/spec#Comparison_operators
type Key interface{}
type entry struct {
 key Key
 value interface{}
}
// 创建新的cache 对象
func New(maxEntries int) *Cache {
 return &Cache{
 MaxEntries: maxEntries,
 ll: list.New(),
 cache: make(map[interface{}]*list.Element),
 }
}
// 添加新的值到cache里
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里获取值.
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
}
// 删除指定key的元素
func (c *Cache) Remove(key Key) {
 if c.cache == nil {
 return
 }
 if ele, hit := c.cache[key]; hit {
 c.removeElement(ele)
 }
}
// 删除最后访问的元素
func (c *Cache) RemoveOldest() {
 if c.cache == nil {
 return
 }
 ele := c.ll.Back()
 if ele != nil {
 c.removeElement(ele)
 }
}
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)
 }
}
// cache 缓存数
func (c *Cache) Len() int {
 if c.cache == nil {
 return 0
 }
 return c.ll.Len()
}

本文来自:Segmentfault

感谢作者:lidashuang

查看原文:LRU 算法

• 编辑
• 预览