• 企业400电话
  • 微网小程序
  • AI电话机器人
  • 电商代运营
  • 全 部 栏 目

    企业400电话 网络优化推广 AI电话机器人 呼叫中心 网站建设 商标✡知产 微网小程序 电商运营 彩铃•短信 增值拓展业务
    golang实现LRU缓存淘汰算法的示例代码

    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
      }
    }

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

    您可能感兴趣的文章:
    • java LRU算法介绍与用法示例
    • 工程师必须了解的LRU缓存淘汰算法以及python实现过程
    • JS 实现缓存算法的示例(FIFO/LRU)
    • Nodejs基于LRU算法实现的缓存处理操作示例
    • c++实现的常见缓存算法和LRU
    • Android图片缓存之Lru算法(二)
    • Python实现LRU算法的2种方法
    • JAVA实现LRU算法的参考示例
    上一篇:go json转换实践中遇到的坑
    下一篇:浅谈GoLang几种读文件方式的比较
  • 相关文章
  • 

    © 2016-2020 巨人网络通讯 版权所有

    《增值电信业务经营许可证》 苏ICP备15040257号-8

    golang实现LRU缓存淘汰算法的示例代码 golang,实现,LRU,缓存,淘汰,