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需要涉及的数据结构：双向链表、哈希表。
1.1、数据结构定义
现在，我们将基本的数据结构定义出来，并且定义个构造器函数。
type Node struct {
Next, Pre *Node
key, valint
}
type DoubleLinkList struct {
Head *Node
Tail *Node
}
type LRUcache struct {
doubleList DoubleLinkList
KeyToNodemap*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*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
//添加到链表中，头节点之后
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; 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; 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，做到当没有节点的时候，就可以沉睡等待被唤醒。（一个优化的点）
接下来，我们一一修改时间。
2.1、数据结构修改
原本的node需要添加过期时间的记录，以及为了实现最小堆，需要添加index下标，记录在堆的位置。
type Node struct {
Next, Pre *Node
key, valint
index int
expire time.Time
}接着是LRUcache，添加一个最小堆结构，然后还需要添加锁，以及sync.Cond。
附带实现这个最小堆（使用container/heap）
// 最小堆实现
type MinHeap []*Node
func (h MinHeap) Less(i, j int) bool { return h.expire.Before(h.expire) }
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Swap(i, j int) {
h, h = h, h
h.index, h.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
node.index = -1
*h = old[:n-1]
return node
}然后是结构的修改，和构造器修改
type LRUcache struct {
doubleList DoubleLinkList
KeyToNodemap*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*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
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; 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、RemoveTail修改
在将要修改的Put操作中，若节点未过期也需要被弹出链表，那么需要同步修改heap，防止到时候产生二次删除引发的指针越界问题。
func (c *LRUcache) RemoveTail() {
//获取尾部节点
node := c.doubleList.Tail.Pre
heap.Remove(&c.expHeap, node.index) //从堆中删除这个节点
//移除
c.RemoveNode(node)
}2.5、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; 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.6、代码全览
package mainimport ( "container/heap" "fmt" "sync" "time")type Node struct { Next, Pre *Node key, valint 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.expire.Before(h.expire) }
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Swap(i, j int) {
h, h = h, h
h.index, h.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
node.index = -1
*h = old[:n-1]
return node
}type LRUcache struct {
doubleList DoubleLinkList
KeyToNodemap*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*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
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
//添加到链表中，头节点之后
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
heap.Remove(&c.expHeap, node.index) //从堆中删除这个节点
//移除
c.RemoveNode(node)
}func (c *LRUcache) Get(key int) int {
//修改1
c.mu.Lock()
defer c.mu.Unlock()
//查询节点是否存在
if node, ok := c.KeyToNode; 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; 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功能保持不变。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]