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

 更新时间:2019-04-17 21:47:12   作者:佚名   我要评论(0)

LRU缓存淘汰算法


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

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

相关文章

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

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

    LRU缓存淘汰算法 LRU是最近最少使用策略的缩写,是根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更
    2019-04-17
  • Go系列教程之反射的用法

    Go系列教程之反射的用法

    反射是 Go 语言的高级主题之一。我会尽可能让它变得简单易懂。 本教程分为如下小节。 什么是反射? 为何需要检查变量,确定变量的类型? reflect 包
    2019-04-17
  • 浅谈GoLang几种读文件方式的比较

    浅谈GoLang几种读文件方式的比较

    GoLang提供了很多读文件的方式,一般来说常用的有三种。使用Read加上buffer,使用bufio库和ioutil 库。 那他们的效率如何呢?用一个简单的程序来评测一下:
    2019-04-17
  • Golang常量iota的使用实例

    Golang常量iota的使用实例

    Codes package main import "fmt" type color byte const ( black color = iota red blue ) func test(c color) { fmt.Println(c) } func main() {
    2019-04-17
  • golang实现跨域访问的方法

    golang实现跨域访问的方法

    前端通过Ajax来获取服务器资源时,会存在跨域问题。因为Ajax只能同源使用(预防某些恶意行为),所以当访问不在同一个域中的资源时,就会出现跨域限制。尤其在
    2019-04-17
  • Linux中10个方便的Bash别名

    Linux中10个方便的Bash别名

    有多少次您在命令行上多次输入一个长命令,并希望有一种方法将其保存到以后?这就是Bash别名派上用场的地方。它们允许您将长而神秘的命令浓缩成易于记忆和使用
    2019-04-17
  • 在Linux命令行中列出带有ls文件的技巧

    在Linux命令行中列出带有ls文件的技巧

    我在linux中学到的第一批命令之一是ls。了解系统上文件所在的目录中的内容很重要。不仅能看到和修改全的文件也很重要。 我的第一个linux备忘单是一页Linux手册
    2019-04-17
  • golang顺时针打印矩阵的方法示例

    golang顺时针打印矩阵的方法示例

    题目描述 输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依
    2019-04-17
  • Golang 日期/时间包的使用详解

    Golang 日期/时间包的使用详解

    golang 的日期时间包:time 的使用方式。 time package 包含了 time.Time 时间对象 及 构建此时间对象的一些方法(time.Unix(), time.Parse()) golang 可
    2019-04-17
  • 关于Golang中range指针数据的坑详解

    关于Golang中range指针数据的坑详解

    前言 在Golang中使用 for range 语句进行迭代非常的便捷,但在涉及到指针时就得小心一点了。 下面的代码中定义了一个元素类型为 *int 的通道 ch : pac
    2019-04-17

最新评论