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, 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，做到当没有节点的时候，就可以沉睡等待被唤醒。（一个优化的点）
接下来，我们一一修改时间。
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功能保持不变。
