Golang从0到1实现简易版expired LRU cache带图解

1、支持Put、Get的LRU实现

想要实现一个带过期时间的LRU，从易到难，我们需要先学会如何实现一个普通的LRU，做到O(1)的Get、Put。

想要做到O(1)的Get，我们很容易想到使用哈希表来存储每个key对应的value；要想实现O(1)的Put，并且能当容量满了的时候自动弹出最久未使用的元素，单纯使用哈希表是比较难实现的，因此我们可以使用一个双向链表，头部存放最新被使用的节点，尾部存放最久未使用的节点。那么哈希表只需要记录key到node的映射，就能让我们快速的追踪到节点在双向链表中的位置。

为了使得双向链表易于维护，我们可以增加两个哨兵节点，分别代表头部和尾部。

到这里，我们就能确定实现一个简单操作的LRU需要涉及的数据结构：双向链表、哈希表。

image-20250422184029048

1.1、数据结构定义

现在，我们将基本的数据结构定义出来，并且定义个构造器函数。

type Node struct {
 Next, Pre *Node
 key, val  int
}

type DoubleLinkList struct {
 Head *Node
 Tail *Node
}

type LRUcache struct {
 doubleList DoubleLinkList
 KeyToNode  map[int]*Node
 cap, cnt   int
}

func Constructor(cap int) *LRUcache {
 head := &Node{}
 tail := &Node{}
 head.Next = tail
 tail.Pre = head
 lru := &LRUcache{
  doubleList: DoubleLinkList{
   Head: head,
   Tail: tail,
  },
  cap:       cap,
  KeyToNode: make(map[int]*Node, cap),
 }
 return lru
}

1.2、方法分析

我们可以先来考虑Put方法。当Put一个(key,value)对的时候，需要先检查是否存在对应的key，若存在，我们就只需要更新这个节点的值并且将节点移动至头部就可以了；若不存在，就需要创建一个节点，添加到头部，若LRUcache满了，就需要移除最久没使用的尾部节点。

再来考虑Get方法，假若我们能获取到key对应的节点，那么就需要将这个节点更新至链表的头部，然后返回值即可；否则，直接返回-1.

从上面的分析我们不难发现，实现Get和Put方法，需要实现三个基本操作：移除一个节点、移除尾部节点、添加节点至头部。

上面的方法，涉及到哈希表的值改变的，也需要一一处理。

接下来我们一一实现。

1.3、添加节点至头部

func (c *LRUcache) AddNode(node *Node) {
 //哈希表注册这个节点
 c.KeyToNode[node.key] = node
 //添加到链表中，头节点之后
 node.Next = c.doubleList.Head.Next
 node.Pre = c.doubleList.Head
 c.doubleList.Head.Next.Pre = node
 c.doubleList.Head.Next = node
 //更新表记录节点数
 c.cnt++
}

执行过程：

  • 注册该节点到哈希表中
  • 将该节点的前后指针正确设置
  • 将原本的第一个节点的Pre指针设置为node
  • 将头节点的Next设置为node
  • 更新cnt计数器

1.4、移除节点

func (c *LRUcache) RemoveNode(node *Node) {
 //哈希表删除节点记录
 delete(c.KeyToNode, node.key)
 //更新链表
 node.Next.Pre = node.Pre
 node.Pre.Next = node.Next
 //更新计数器
 c.cnt--
}

1.5、移除尾部节点

func (c *LRUcache) RemoveTail() {
 //获取尾部节点
 node := c.doubleList.Tail.Pre
 //移除
 c.RemoveNode(node)
}

1.6、Get()

接下来，就可以实现Get和Put方法了。先来实现一下Get

func (c *LRUcache) Get(key int) int{
 //查询节点是否存在
 if node, ok := c.KeyToNode[key]; ok{
  //存在：从链表移除、添加到链表头部
  c.RemoveNode(node)
  c.AddNode(node)
  return node.val
 }else{
  //不存在，返回-1
  return -1
 }
}

1.7、Put()

Put的执行流程也比较简单：

func (c *LRUcache) Put(key int, val int) {
 //检查节点是否存在
 if node, ok := c.KeyToNode[key]; ok {
  //存在：更新节点的值、移除节点、添加节点到头部
  node.val = val
  c.RemoveNode(node)
  c.AddNode(node)
 } else {
  //不存在，先检查容量是否上限
  if c.cnt == c.cap {
   c.RemoveTail() //移除尾部节点
  }
  //容量足够，添加节点
  newNode := &Node{key: key, val: val}
  c.AddNode(newNode)
 }
}

至此，一个简单的LRU就实现了。

2、优雅实现带过期时间的LRU

现在，我们来考虑如何引入过期时间。

首先，我们当然要为每个node添加一个过期时间字段，来记录它什么时候会过期。

对于用户来说，为了保证数据是有效的，每次Get一个值，是不允许用户获取到一个过期对象的。这里可以采用一个懒更新的策略，当调用Get获取到一个节点的时候，应该检查是否已经过期，过期了就应该去除掉这个节点，给用户返回-1。

这样子，我们就已经对用户的值获取有了个最基本的保障，至少不会获取到已经过期的数据。接下来我们就要考虑，如何去实现节点的自动过期删除呢？

要快速的获取到最早要过期的节点，我们可以引入一个过期时间最小堆，位于堆顶的是最早将要过期的节点；然后为了实现“自动管理”，我们可以引入一个协程去打理这个堆，每次发现节点过期了，就让这个协程自己去把节点清理掉就好了。这样子，可以做到当有节点过期了，只需要O(logn)的时间去清理掉节点，Put/Get主流程仍然只需要O（1）的时间复杂度，做到了“优雅高效”。

以为我们引入了协程，这就会有线程安全的问题，所以需要对LRU添加一把锁，来实现对操作的安全访问。

接着，我们希望当LRU存在节点的时候，再进行检查是否过期，为了防止协程长期自旋检查，我们可以为LRUcache添加一个sycn.Cond，做到当没有节点的时候，就可以沉睡等待被唤醒。（一个优化的点）

image-20250422191104449

接下来，我们一一修改时间。

2.1、数据结构修改

原本的node需要添加过期时间的记录，以及为了实现最小堆，需要添加index下标，记录在堆的位置。

type Node struct {
 Next, Pre *Node
 key, val  int
 index int
 expire time.Time
}

接着是LRUcache，添加一个最小堆结构，然后还需要添加锁，以及sync.Cond。

附带实现这个最小堆（使用container/heap）

// 最小堆实现
type MinHeap []*Node

func (h MinHeap) Less(i, j int) bool { return h[i].expire.Before(h[j].expire) }
func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Swap(i, j int) {
 h[i], h[j] = h[j], h[i]
 h[i].index, h[j].index = i, j
}
func (h *MinHeap) Push(x interface{}) {
 n := h.Len()
 node := x.(*Node)
 node.index = n
 *h = append(*h, node)
}
func (h *MinHeap) Pop() interface{} {
 old := *h
 n := old.Len()
 node := old[n-1]
 node.index = -1
 *h = old[:n-1]
 return node
}

然后是结构的修改，和构造器修改

type LRUcache struct {
 doubleList DoubleLinkList
 KeyToNode  map[int]*Node
 cap, cnt   int

 expHeap MinHeap
 mu      sync.Mutex
 expCond sync.Cond
}

func Constructor(cap int) *LRUcache {
 head := &Node{}
 tail := &Node{}
 head.Next = tail
 tail.Pre = head
 lru := &LRUcache{
  doubleList: DoubleLinkList{
   Head: head,
   Tail: tail,
  },
  cap:       cap,
  KeyToNode: make(map[int]*Node, cap),
 }
 heap.Init(&lru.expHeap)//初始化堆
 lru.expCond = *sync.NewCond(&lru.mu)//创建cond
 go lru.expirer()
 return lru
}

2.2、清理协程实现

func (c *LRUcache) expirer() {
 for {
  //获取锁
  c.mu.Lock()
  //若列表没有节点，就沉睡等到被put唤醒
  for c.expHeap.Len() == 0 {
   c.expCond.Wait() //会自动释放锁，等待被唤醒后又尝试获取锁。
  }
  //获取堆顶节点
  node := c.expHeap[0]
  now := time.Now()
  wait := node.expire.Sub(now)
  //如果wait>0，说明还没有过期
  if wait > 0 {
   //沉睡到该节点过期
   c.mu.Unlock()
   time.Sleep(wait)
   //醒来后，要重新执行一次流程
   continue
  }
  //清理这个节点
  heap.Pop(&c.expHeap)
  c.RemoveNode(node)
  c.mu.Unlock()
 }
}

流程：

  • 获取锁
  • 检查队列是否为空，为空则等待被put唤醒
  • 获取堆顶节点，检查是否已经到达过期时间
    • 未到达过期时间，则沉睡，当被唤醒的时候，重新检查堆顶。
  • 到达了过期时间，进行清除操作

2.3、Get修改

现在引入了过期机制后，就需要检查是否过期，以及获取锁才能操作。

func (c *LRUcache) Get(key int) int {
 //修改1
 c.mu.Lock()
 defer c.mu.Unlock()
 //查询节点是否存在
 if node, ok := c.KeyToNode[key]; ok {
  //修改2，检查是否过期
  if time.Now().After(node.expire) {
   //过期了，协程还没有发现，手动帮助删除
   heap.Remove(&c.expHeap, node.index)
   c.RemoveNode(node)
   return -1
  }
  //存在：从链表移除、添加到链表头部
  c.RemoveNode(node)
  c.AddNode(node)
  return node.val
 } else {
  //不存在，返回-1
  return -1
 }
}

修改的点已经标记。

2.4、Put修改

func (c *LRUcache) Put(key int, val int, ttl time.Duration) {
 //修改1
 c.mu.Lock()
 defer c.mu.Unlock()
 //修改2，获取过期时间
 exp := time.Now().Add(ttl)
 //检查节点是否存在
 if node, ok := c.KeyToNode[key]; ok {
  //存在：更新节点的值、移除节点、添加节点到头部
  //修改3，重新设置过期时间
  node.expire = exp

  node.val = val
  c.RemoveNode(node)
  c.AddNode(node)

  //修改4，heap需要fix
  heap.Fix(&c.expHeap, node.index)
 } else {
  //不存在，先检查容量是否上限
  if c.cnt == c.cap {
   c.RemoveTail() //移除尾部节点
  }
  //容量足够，添加节点
  newNode := &Node{key: key, val: val}

  //修改4，设置节点过期时间，添加到堆，唤醒协程
  newNode.expire = exp
  c.AddNode(newNode)
  heap.Push(&c.expHeap, newNode)
  c.expCond.Signal()
 }
}

Put方法的流程：

  • 获取锁
  • 检查节点是否存在
    • 存在：进行节点的移除、节点值更新、节点添加、heap修复
    • 不存在：检查容量，容量超出则移除尾部节点；进行节点的创建，节点的添加，heap的添加，唤醒协程

于是，我们就完成了带过期时间的LRU。

2.5、代码全览

package main

import (
 "container/heap"
 "fmt"
 "sync"
 "time"
)

type Node struct {
 Next, Pre *Node
 key, val  int
 index     int
 expire    time.Time
}

type DoubleLinkList struct {
 Head *Node
 Tail *Node
}

// 最小堆实现
type MinHeap []*Node

func (h MinHeap) Less(i, j int) bool { return h[i].expire.Before(h[j].expire) }
func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Swap(i, j int) {
 h[i], h[j] = h[j], h[i]
 h[i].index, h[j].index = i, j
}
func (h *MinHeap) Push(x interface{}) {
 n := h.Len()
 node := x.(*Node)
 node.index = n
 *h = append(*h, node)
}
func (h *MinHeap) Pop() interface{} {
 old := *h
 n := old.Len()
 node := old[n-1]
 node.index = -1
 *h = old[:n-1]
 return node
}

type LRUcache struct {
 doubleList DoubleLinkList
 KeyToNode  map[int]*Node
 cap, cnt   int

 expHeap MinHeap
 mu      sync.Mutex
 expCond sync.Cond
}

func Constructor(cap int) *LRUcache {
 head := &Node{}
 tail := &Node{}
 head.Next = tail
 tail.Pre = head
 lru := &LRUcache{
  doubleList: DoubleLinkList{
   Head: head,
   Tail: tail,
  },
  cap:       cap,
  KeyToNode: make(map[int]*Node, cap),
 }
 heap.Init(&lru.expHeap)              //初始化堆
 lru.expCond = *sync.NewCond(&lru.mu) //创建cond
 go lru.expirer()
 return lru
}
func (c *LRUcache) expirer() {
 for {
  //获取锁
  c.mu.Lock()
  //若列表没有节点，就沉睡等到被put唤醒
  for c.expHeap.Len() == 0 {
   c.expCond.Wait() //会自动释放锁，等待被唤醒后又尝试获取锁。
  }
  //获取堆顶节点
  node := c.expHeap[0]
  now := time.Now()
  wait := node.expire.Sub(now)
  //如果wait>0，说明还没有过期
  if wait > 0 {
   //沉睡到该节点过期
   c.mu.Unlock()
   time.Sleep(wait)
   //醒来后，要重新执行一次流程
   continue
  }
  //清理这个节点
  heap.Pop(&c.expHeap)
  c.RemoveNode(node)
  c.mu.Unlock()
 }
}
func (c *LRUcache) AddNode(node *Node) {
 //哈希表注册这个节点
 c.KeyToNode[node.key] = node
 //添加到链表中，头节点之后
 node.Next = c.doubleList.Head.Next
 node.Pre = c.doubleList.Head
 c.doubleList.Head.Next.Pre = node
 c.doubleList.Head.Next = node
 //更新表记录节点数
 c.cnt++
}

func (c *LRUcache) RemoveNode(node *Node) {
 //哈希表删除节点记录
 delete(c.KeyToNode, node.key)
 //更新链表
 node.Next.Pre = node.Pre
 node.Pre.Next = node.Next
 //更新计数器
 c.cnt--
}

func (c *LRUcache) RemoveTail() {
 //获取尾部节点
 node := c.doubleList.Tail.Pre
 //移除
 c.RemoveNode(node)
}

func (c *LRUcache) Get(key int) int {
 //修改1
 c.mu.Lock()
 defer c.mu.Unlock()
 //查询节点是否存在
 if node, ok := c.KeyToNode[key]; ok {
  //修改2，检查是否过期
  if time.Now().After(node.expire) {
   //过期了，协程还没有发现，手动帮助删除
   heap.Remove(&c.expHeap, node.index)
   c.RemoveNode(node)
   return -1
  }
  //存在：从链表移除、添加到链表头部
  c.RemoveNode(node)
  c.AddNode(node)
  return node.val
 } else {
  //不存在，返回-1
  return -1
 }
}

func (c *LRUcache) Put(key int, val int, ttl time.Duration) {
 //修改1
 c.mu.Lock()
 defer c.mu.Unlock()
 //修改2，获取过期时间
 exp := time.Now().Add(ttl)
 //检查节点是否存在
 if node, ok := c.KeyToNode[key]; ok {
  //存在：更新节点的值、移除节点、添加节点到头部
  //修改3，重新设置过期时间
  node.expire = exp

  node.val = val
  c.RemoveNode(node)
  c.AddNode(node)

  //修改4，heap需要fix
  heap.Fix(&c.expHeap, node.index)
 } else {
  //不存在，先检查容量是否上限
  if c.cnt == c.cap {
   c.RemoveTail() //移除尾部节点
  }
  //容量足够，添加节点
  newNode := &Node{key: key, val: val}

  //修改4，设置节点过期时间，添加到堆，唤醒协程
  newNode.expire = exp
  c.AddNode(newNode)
  heap.Push(&c.expHeap, newNode)
  c.expCond.Signal()
 }
}
func (c *LRUcache) Print() {
 for node := c.doubleList.Head; node != nil; node = node.Next {
  fmt.Printf("%d -> ", node.key)
 }
 fmt.Println()
}
func main() {
 cache := Constructor(2)
 cache.Put(10, 101, time.Second)
 cache.Print()

 time.Sleep(time.Second)
 fmt.Println(cache.Get(10))

 cache.Put(9, 99, time.Second*2)
 cache.Print()

 cache.Put(7, 77, time.Second)
 cache.Print()

 time.Sleep(2 * time.Second)
 cache.Print()
}

3、测试

func (c *LRUcache) Print() {
 for node := c.doubleList.Head; node != nil; node = node.Next {
  fmt.Printf("%d -> ", node.key)
 }
 fmt.Println()
}
func main() {
 cache := Constructor(2)
 cache.Put(10, 101, time.Second)
 cache.Print()

 time.Sleep(time.Second)
 fmt.Println(cache.Get(10))

 cache.Put(9, 99, time.Second*2)
 cache.Print()

 cache.Put(7, 77, time.Second)
 cache.Print()

 time.Sleep(2 * time.Second)
 cache.Print()
}

输出如下：

0 -> 10 -> 0 -> 
-1
0 -> 9 -> 0 -> 
0 -> 7 -> 9 -> 0 ->
0 -> 0 ->

可以看到，过期的节点已经被成功自动删除了，同时原本的LRU功能保持不变。

From:https://www.cnblogs.com/MelonTe/p/18841473
MelonTe
100+评论
captcha
    相关文章
    1. Tailwind CSS一些你需要记住的原子类
      ！win ！·6天前
      Tailwind CSS一些你需要记住的原子类
      编程知识
    3. MCP星球·6天前
      我们离Agent终极形态又近了一步：全球首个支持谷歌A2A（Agent-to-Agent)协议的智能体注册网站上线Product Hunt，未来智能体协作网络
      AI 的终点，不是更强大的对话，而是一个真正协作的智能体社会。 这种形态已经在悄然出现。 全球首个支持 Google A2A（Agent-to-Agent）协议 的智能体注册与协作平台同步上线Product Hunt，并取得了良好的社区反馈。 A2Astore.co在Product Hunt上的发布
      编程知识
    4. Windows 身份验证协议
      扛枪的书生·6天前
      Windows 身份验证协议
      编程知识
    5. Kevinarcsin001·6天前
      nextflow 基础
      Nextflow 核心知识点与使用指南 一、安装与依赖 环境要求 • Java：Nextflow 需 Java 17+ 环境，可通过 apt-get 或 SDKMAN 安装。 • 操作系统：支持 Linux、macOS，Windows 需通过 WSL2 运行。 安装方式 • 一键安装： curl -
      编程知识
    6. 强化学习框架：OpenRLHF源码解读，模型处理
      Big-Yellow-J·6天前
      强化学习框架：OpenRLHF源码解读，模型处理
      编程知识
    8. firebase studio硬刚cursor,送免费云服务可跑32b大模型
      星仔007·6天前
      firebase studio硬刚cursor,送免费云服务可跑32b大模型
      编程知识
    9. 《Beating Floating Point at its Own Game: Posit Arithmetic》（一）
      江左子固·6天前
      《Beating Floating Point at its Own Game: Posit Arithmetic》（一）
      编程知识
    10. Sentinel源码—8.限流算法和设计模式总结
      东阳马生架构·6天前
      Sentinel源码—8.限流算法和设计模式总结
      编程知识