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

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