LRU 算法

概述LRU 最近最少使用算法，LRU算法主要用于缓存淘汰。主要目的就是把最近最少使用的数据移除内存，以加载其他数据。 原理 添加元素时，放到链表头缓存命中，将元素移动到链表头缓存满了之后，将链表尾的元素删除 LRU算法实现 可以用一个双向链表保存数据 使用hash实现O(1)的访问 groupcache中LRU算法实现（Go语言） https://github.com/golang/groupca

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

原理

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

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

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

源码简单注释：

package lruimport "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_operatorstype 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()}

总结

以上是内存溢出为你收集整理的LRU 算法全部内容，希望文章能够帮你解决LRU 算法所遇到的程序开发问题。

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