目录
- 简单了解 LRU 是什么
- LRU 机制实现分析
- 题目描述
- 详细代码
缓存是在平时开发中最常用的中间件之一，尤其是在 WEB 开发中更为常见，大家最常用的肯定还是 Redis 或者 Memcached 之类的中间件。所以对于自己实现一个 Cache 可能并没有那么熟悉，但是在很多场景下，我们使用一些网络缓存会遇到一些瓶颈，比如说传输数据量比较大，或者传输非常频繁，都可能会导致一些性能瓶颈，尤其是在网络I/O上。所以这种场景下，很可能就需要我们自己在应用内实现一个二级缓存。本文我们就来介绍下一个基于 Go 语言支持 LRU 淘汰策略缓存的实现思路。
简单了解 LRU 是什么
提到 LRU，很多人第一反应会想到 Redis 的淘汰策略，没错，这里的 LRU 和 Redis 使用的 LRU 是相同的概念。
LRU（Least Recently Used）表示的是最近最久未使用，或者也有称为最近最少使用，但是为了避免和 LFU 产生歧义，本文中我们都成为最近最久未使用。下面我们通过一个示例来快速描述下 LRU 的概念（如果已经对 LRU 的概念了解，可以跳过这部分）：
当缓存容量未满时，加入元素则加入到队尾，有元素访问时，则被访问的元素移动到队尾，所以在这个例子中，我们可以认为在队尾的为最近使用的元素，相反在队首的则为最近最久未使用的元素。所以在元素 E 加入后，缓存容量达到最大，此时最近最久未使用的元素为 A，如果再有元素加入时会淘汰掉 A，但是接下来的操作为访问 A 元素，所以此时 A 被移动到队尾，在队首的元素成为了 C，那么接下在 F 元素加入后，C元素被淘汰。
LRU 机制实现分析
在了解 LRU 的概念之后，我们回到主题，就是实现一个 LRU 的缓存。这里我们以开始提到的面试为例：
实现基于内存的满足 LRU 淘汰机制的缓存，并且提供 Set 和 Get 方法
首先我们分析下这个题目，要满足 LRU 的淘汰机制，则缓存一定是限定容量的。其次就是要对性能的分析，既然是作为缓存使用的，那么对于 Set 和 Get 的操作的时间复杂度要求一定要控制在 O(1) 级别。（这里提一个其他问题，我们在解一个问题的时候，一定优先考虑的是最优的实现方式，而不是你认为的最简单的实现方式，这里如果我们使用 O(n) 甚至 O(n^2) 的解法也可以实现，但是这样既不满足实际的使用场景，更不满足面试对你的考核要求）
再回到这个问题，从最开始我们分析的例子中可以看出，在 LRU 的实现中最重要的一点就是要管理缓存中每个元素的时间属性，所以有人就会考虑，给每个元素记录一个时间戳，然后将元素和时间戳信息存入到一个哈希表中，但是这样虽然满足了 O(1) 的元素访问时间复杂度，但是在元素淘汰的时候就需要遍历所有元素来找到最早的那个元素。
所以我们在对这个问题思考的时候，不要对时间这个概念太过于注重，因为我们并不需要知道每个元素的具体时间，而是只需要知道元素之间的先后时间顺序即可。所以这里我们只需要维护每个元素的先后顺序。那么这里有人就会考虑到使用数组或者链表，这两者都是有顺序的。但是对于数组来讲，数组中的元素移动并不是 O(1) 的操作，所以可能链表会更加适合。但是如果使用链表实现的话，要访问缓存中的元素就需要去遍历链表来找到这个元素。
我们再梳理下这个问题实现的要点：
- Set 和 Get 满足 O(1) 时间复杂度
- 元素顺序调整满足 O(1) 时间复杂度
对于要点1，我们可以使用哈希表来实现，对于要点2，我们可以使用链表来实现。这两种结构都没有办法同时满足两个点。所以我们就需要考虑把这两种数据结构结合起来考虑。（如果有对于Java了解的同学，可以参考LinkedHashMap），这种结构细节可以参考下图：
首先创建一个哈希表用了存储键值对，然后将哈希表的 Value 进行链表的关联，这样就可以同时满足上述条件了，而这也是 LRU 的最普遍的实现方式。
题目描述
设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。
它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) – 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。写入数据 put(key, value) – 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
详细代码
type LRUCache struct {
capacity int
m map[int]*Node
head, tail *Node
}
type Node struct {
Key int
Value int
Pre, Next *Node
}
func Constructor(capacity int) LRUCache {
head, tail := &Node{}, &Node{}
head.Next = tail
tail.Pre = head
return LRUCache{
capacity: capacity,
m: map[int]*Node{},
head: head,
tail: tail,
}
}
func (this *LRUCache) Get(key int) int {
// 存在，放到头
if v, ok := this.m[key]; ok {
this.moveToHead(v)
return v.Value
}
// 不存在，返回-1
return -1
}
func (this *LRUCache) Put(key int, value int) {
// 已经存在了
if v, ok := this.m[key];ok{
v.Value = value
this.moveToHead(v)
return
}
if this.capacity==len(this.m){
rmKey := this.removeTail()
delete(this.m ,rmKey)
}
newNode := &Node{Key: key, Value: value}
this.m[key] = newNode
this.addToHead(newNode)
}
func (this *LRUCache) moveToHead(node *Node) {
this.deleteNode(node)
this.addToHead(node)
}
func (this *LRUCache) deleteNode(node *Node) {
node.Pre.Next = node.Next
node.Next.Pre = node.Pre
}
func (this *LRUCache) addToHead(node *Node) {
// 先让node位于现存第一位元素之前
this.head.Next.Pre = node
// 通过node的next指针让原始第一位元素放到第二位
node.Next = this.head.Next
// 捆绑node和head的关系
this.head.Next = node
node.Pre = this.head
}
func (this *LRUCache)removeTail()int{
node := this.tail.Pre
this.deleteNode(node)
return node.Key
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/
到此这篇关于go语言实现LRU缓存的示例代码的文章就介绍到这了,更多相关go语言 LRU缓存内容请搜索悠久资源网以前的文章或继续浏览下面的相关文章希望大家以后多多支持悠久资源网！
您可能感兴趣的文章:
- 基于Golang container/list实现LRU缓存
- golang实现LRU缓存淘汰算法的示例代码
