golang实现LRU缓存淘汰算法

栏目: Go · 发布时间: 5年前

内容简介:LRU是最近最少使用策略的缩写,是根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。将Cache的所有位置都用双链表连接起来,当一个位置被访问(get/put)之后,通过调整链表的指向,将该位置调整到链表头的位置,新加入的Cache直接加到链表头中。这样,在多次操作后,最近被访问(get/put)的,就会被向链表头方向移动,而没有访问的,向链表后方移动,链表尾则表示最近最少使用的Cache。

LRU缓存淘汰算法

LRU是最近最少使用策略的缩写,是根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

双向链表实现LRU

将Cache的所有位置都用双链表连接起来,当一个位置被访问(get/put)之后,通过调整链表的指向,将该位置调整到链表头的位置,新加入的Cache直接加到链表头中。

这样,在多次操作后,最近被访问(get/put)的,就会被向链表头方向移动,而没有访问的,向链表后方移动,链表尾则表示最近最少使用的Cache。

当达到缓存容量上限时,链表的最后位置就是最少被访问的Cache,我们只需要删除链表最后的Cache便可继续添加新的Cache。

代码实现

type Node struct {
    Key int
    Value int
    pre *Node
    next *Node
}

type LRUCache struct {
    limit int
    HashMap map[int]*Node
    head *Node
    end *Node
}

func Constructor(capacity int) LRUCache{
    lruCache := LRUCache{limit:capacity}
    lruCache.HashMap = make(map[int]*Node, capacity)
    return lruCache
}

func (l *LRUCache) Get(key int) int {
    if v,ok:= l.HashMap[key];ok {
        l.refreshNode(v)
        return v.Value
    }else {
        return -1
    }
}

func (l *LRUCache) Put(key int, value int) {
    if v,ok := l.HashMap[key];!ok{
        if len(l.HashMap) >= l.limit{
            oldKey := l.removeNode(l.head)
            delete(l.HashMap, oldKey)
        }
        node := Node{Key:key, Value:value}
        l.addNode(&node)
        l.HashMap[key] = &node
    }else {
        v.Value = value
        l.refreshNode(v)
    }
}

func (l *LRUCache) refreshNode(node *Node){
    if node == l.end {
        return
    }
    l.removeNode(node)
    l.addNode(node)
}

func (l *LRUCache) removeNode(node *Node) int{
    if node == l.end  {
        l.end = l.end.pre
    }else if node == l.head {
        l.head = l.head.next
    }else {
        node.pre.next = node.next
        node.next.pre = node.pre
    }
    return node.Key
}

func (l *LRUCache) addNode(node *Node){
    if l.end != nil {
        l.end.next = node
        node.pre = l.end
        node.next = nil
    }
    l.end = node
    if l.head == nil {
        l.head = node
    }
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

小程序大时代

小程序大时代

即速应用 / 哈尔滨工业大学出版社 / 2018-10 / 58元

2017年1月9日微信小程序的问世,是中国互联网发展史上的又一个里程碑。支付宝、百度、今日头条等各大巨头的陆续进场,无不证明小程序这种轻应用形态已经成为移动互联网的发展趋势。我们希望可以通过这本书,帮助零基础的小程序爱好者,了解小程序的市场走向和生态发展,学会小程序的制作与运营,读懂小程序这个全新物种。 全书分为入门篇、制作篇、运营篇三大篇章。 入门篇首先揭开小程序的神秘面纱,盘点小程......一起来看看 《小程序大时代》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器