介绍
在本文中，我们将用Go实现LRU Cache。
LRU Cache
最近最少使用（LRU）是一种缓存逐出算法，它按使用顺序组织元素。在LRU中，最长时间没有被使用的元素会被从缓存中逐出。
例如，如果我们有一个容量为三个项目的缓存：
最初，缓存是空的，我们将元素8放入缓存中，元素9和6像以前一样被缓存。但是现在，缓存容量已满，要放入下一个元素，我们必须驱逐缓存中最近最少使用的元素。
在我们用Go实现LRU缓存之前，最好了解一下缓存的一些方面：
- 所有操作都应按O(1)的顺序运行
- 缓存大小有限
- 所有缓存操作都必须支持并发
- 如果缓存已满，添加新项必须调用LRU策略
实现
首先定义一些相关数据结构：
type K int
type V int
type Cache struct {
Key K
Value V
}
type LRUCache struct {
size int
list *list.List
element map[K]*list.Element
}
其中含义如下：
- size：可以存储在缓存中的元素数量
- list：双向链表，使用Go的原生container/list实现
- element：映射存储键和指向存储在列表中的值的指针 我们将实现以下的相关方法：
- Get：获取一个key-value对，如果不存在则返回一个特定值，在这里暂定为-1
- Put：插入一个key-value对
- RecentlyUsed：获取最近使用的value
- Remove：删除一个key-value对
- Clear：清空缓存
Get
由于缓存将value存储在map中，key-value存储在列表中。首先检查key是否存在于map中，返回存储在双向链表中的key对应的value或返回-1。
在返回值的同时，还需要将它移到双向链表的前面，以保持最近最少使用的逻辑。
func (c *LRUCache) Get(key K) V {
if node, ok := c.element[key]; ok {
// hit LRU cache, fetch key value pair
value := node.Value.(*list.Element).Value.(Cache).Value
// move node to the front of list
c.list.MoveToFront(node)
return value
}
return V(-1)
}
Put
将key-value对插入缓存中遵循以下步骤：
- 如果在缓存中找到key，则将其移动到双向链表的前面并更新value
- 否则，检查缓存的当前容量，若溢出，则从双向链表中删除最近最近未使用的条目
- 将新元素存储在列表的前面。
正如上述步骤所定义的，在检查容量时，我们从缓存中删除了后面的元素，它定义了我们最近最少使用的用例。
func (c *LRUCache) Put(key K, value V) {
if node, ok := c.element[key]; ok {
// there is already key in LRU cache, move node to the front of list
c.list.MoveToFront(node)
// update key value pair
node.Value.(*list.Element).Value = Cache{Key: key, Value: value}
} else {
// there is no key in LRU cache
if c.list.Len() == c.size {
// LRU is full
lastKey := c.list.Back().Value.(*list.Element).Value.(Cache).Key
delete(c.element, lastKey)
c.list.Remove(c.list.Back())
}
node := &list.Element{
Value: Cache{
Key: key,
Value: value,
},
}
pointer := c.list.PushFront(node)
c.element[key] = pointer
}
}
RecentlyUsed
返回双向链表中最前面的值。
func (c *LRUCache) RecentlyUsed() V {
return c.list.Front().Value.(*list.Element).Value.(Cache).Value
}
Remove
删除指定的key，如果key存在于缓存中则删除，否则无操作
func (c *LRUCache) Remove(key K) {
if node, ok := c.element[key]; ok {
delete(c.element, key)
c.list.Remove(node)
}
}
Clear
清空缓存，将双向链表和map全部置空
func (c *LRUCache) Clear() {
c.list = nil
c.element = nil
}