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

以上就是golang如何实现LRU缓存淘汰算法的示例代码。生活的真谛在于创新,生活的理想在于远大,生活的艺术在于选择,生活的步履在于踏实,生活的乐趣在于追求,生活的安乐在于平淡,人生有时就是一场戏,有高潮,有低谷,每个人在这场戏中的角色是不同的,有的人是主角,有的人是配角,并不是主角就一定有好戏,配角也有出彩的时候,与人相处,追求和谐,就如水一样,无形却能演变五彩缤纷,无味却能演绎万味俱佳。更多关于golang如何实现LRU缓存淘汰算法的示例代码请关注haodaima.com其它相关文章!

您可能有感兴趣的文章
golang并发编程的如何实现

Go语言Telnet回音服务器的如何实现

自己动手用Golang如何实现约瑟夫环算法的示例

用go写的五子棋预测算法的如何实现

如何利用systemd部署golang项目的如何实现方法