Go的数据结构与实现【LRU Cache】

介绍

在本文中，我们将用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
}