golang实现lru缓存-阿里云开发者社区

golang实现lru缓存

2023-07-27 70

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： golang实现lru缓存

公众号merlinsea

题目链接：https://leetcode.cn/problems/lru-cache/description/
题目描述：

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1，golang可以返回多关键字，用于标识是否存在
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行

解题思路

首先要求get(key)需要在O(1)的时间复杂度下获取结果，因此这里可以使用map来存储数据，map的key是一个int类型，map的value是一个地址，这个地址指向真正的节点。
另外由于put操作中在数据量超过capacity的时候需要把最久没有使用到的关键字删除，因此可以知道还需要使用双向链表来记录数据。
当put操作的时候发现lru缓存的容量已经满了的情况，需要将tail 的前驱节点（即最久没有访问过的节点）删除。这里的双向链表采用了虚拟头节点和尾节点的编程技巧。
为什么使用双向链表

双向链表每个节点都有前驱和后继节点，可以通过链表的顺序关系可以来判断哪些节点是最近使用的，哪些节点是最早使用的。
双向链表中删除某个节点可以保证O(1)的时间复杂度，首先在map中通过key快速定位下节点信息，得到节点信息以后可以把这个节点通过调整指针指向来使其移动到链表中的第一位【表示最近访问过了】。

代码实现

package lru_cache
// 定义双向链表的节点
type Node struct {
  Key  int
  Val  int
  Pre  *Node
  Next *Node
}
// lru缓存
type LRUCache struct {
  KeyNodeMap map[int]*Node
  Head       *Node
  Tail       *Node
  Capacity   int
}
// 构造器，通过new()可以创建一个指向结构体的指针
func Constructor(capacity int) LRUCache {
  lruCathe := LRUCache{
    KeyNodeMap: make(map[int]*Node),
    Head:       new(Node),
    Tail:       new(Node),
    Capacity:   capacity,
  }
  lruCathe.Head.Next = lruCathe.Tail
  lruCathe.Tail.Pre = lruCathe.Head
  return lruCathe
}
func (this *LRUCache) Get(key int) int {
  nodePtr, ok := this.KeyNodeMap[key]
  if !ok {
    return -1
  }
  // 将结果放到第一个
  this.moveFirst(nodePtr)
  return nodePtr.Val
}
func (this *LRUCache) Put(key int, value int) {
  // 判断是否存在
  nodePtr, ok := this.KeyNodeMap[key]
  if ok {
    // 存在则进行替换
    nodePtr.Val = value
    // 将节点移到最前面
    this.moveFirst(nodePtr)
  } else {
    if this.Capacity == len(this.KeyNodeMap) {
      // 容量已经满了，先删除tail（包括双向链表和map）
      oldNodePtr := this.Tail.Pre
      this.Tail.Pre = oldNodePtr.Pre
      oldNodePtr.Pre.Next = this.Tail
      delete(this.KeyNodeMap, oldNodePtr.Key)
    }
    // 插入
    nodePtr := &Node{
      Key:  key,
      Val:  value,
      Pre:  this.Head,
      Next: this.Head.Next,
    }
    this.Head.Next.Pre = nodePtr
    this.Head.Next = nodePtr
    this.KeyNodeMap[key] = nodePtr
  }
}
 // 将节点nodePtr移动的第一位表示最近访问过的节点
func (this *LRUCache) moveFirst(nodePtr *Node) {
  nodePtr.Pre.Next = nodePtr.Next
  nodePtr.Next.Pre = nodePtr.Pre
  nodePtr.Next = this.Head.Next
  this.Head.Next.Pre = nodePtr
  this.Head.Next = nodePtr
  nodePtr.Pre = this.Head
}

func main() {
  lruCache := lru_cache.Constructor(2)
  lruCache.Put(1, 1)
  lruCache.Put(2, 2)
  v := lruCache.Get(1)
  fmt.Println(v)
  lruCache.Put(3, 3)
  v = lruCache.Get(2)
  fmt.Println(v)
  lruCache.Put(4, 4)
  v = lruCache.Get(1)
  fmt.Println(v)
  v = lruCache.Get(3)
  fmt.Println(v)
  v = lruCache.Get(4)
  fmt.Println(v)
}