目录

本文设计和实现一个LRU（最近最少使用）缓存数据结构。

按照LRU的概念，我们需要做到:

  1. PUT数据的时候，如果数据不存在，加入到cache中
  2. PUT数据的时候，如果超过cache大小，删除最常不用的key
  3. GET数据的时候，如果数据存在，当前key被激活为最近刚使用的

为了实现上边的操作，我们可以使用一个有序列表用来存储key和value对，刚加入或者刚刚被读取过的放在列表的头上； 当空间不够，需要删除的时候，直接删除链表尾部的键值对。

同时，为了在取数据的时候，能够快速的用O(1)的时间直接找到对应的键值对，另外用一个map存储对应关系，map的key对应的值就是键值对的地址。

接下去用golang简单的实现LRU的cache。

LRU格式定义

通过上边的描述，能很快的得到LRU的结构定义：

// LRU implements a fixed size LRU cache
type LRU struct {
	size      int
	cacheList *list.List
	items     map[interface{}]*list.Element
}

size表示cache总体的大小，cacheList是一个链表，用来存具体的键值对， items是一个map，能够通过key快速的取到对应的键值对的地址。

我们另外定义键值对的格式：

// item defines the item in the LRU list
type cacheItem struct {
	key   interface{}
	value interface{}
}

PUT放入新值

往LRU cache放入值的时候，需要先判断是否已经存在了这个key，如果已经存在了， 就对这个key进行更新，放入新的值；如果不存在，需要新建一个键值对，将新的键值对放到链表的头部，同时将key和地址加入到map。

如果放入值后空间不够用了，需要删除最老的键值对。

// Put add item to LRU cache, if the key already exists, update the value
func (c *LRU) Put(key, value interface{}) {
	// check if the key exists
	if item, ok := c.items[key]; ok {
		// move the item to the front
		c.cacheList.MoveToFront(item)
		// update the item value
		item.Value.(*cacheItem).value = value
		return
	}

	// add new item
	item := &cacheItem{key, value}
	item1 := c.cacheList.PushFront(item)
	c.items[key] = item1

	//check if the cache is full
	if c.cacheList.Len() > c.size {
		c.removeOldest()
	}
}

removeOldest就是用来删除最老的键值对，稍后描述它的实现。

GET取值

取值的过程相对比较简单，只要在map中查看是否有对应的key，没有的话返回空；有的话返回对应的值，同时需要把对应键值对挪动到链表的头部，因为它刚被访问了。

// Get return the value of the key, nil if not exists
func (c *LRU) Get(key interface{}) (value interface{}, err error) {
	if item, ok := c.items[key]; ok {
		c.cacheList.MoveToFront(item)
		return item.Value.(*cacheItem).value, nil
	}
	return nil, errors.New("empty")
}

删除最老的值

删除最老的值，直接取链表的最后一个节点进行删除，删除的时候既要删除链表中的这个节点，也要同时删除map中的对应关系。

func (c *LRU) removeOldest() {
	item := c.cacheList.Back()
	if item != nil {
		c.removeItem(item)
	}
}

// removeItem . remove item in the LRU cache
func (c *LRU) removeItem(item *list.Element) {
	// remove item from list
	c.cacheList.Remove(item)
	kv := item.Value.(*cacheItem)
	// delete key in the map
	delete(c.items, kv.key)
}

删除对应key

删除key的时候，先通过key在map中找对对应的地址，然后调用上边的removeItem函数进行删除。

// Del . delete the key in LRU cache, return true if exists, else return false
func (c *LRU) Del(key interface{}) bool {
	if item, ok := c.items[key]; ok {
		c.removeItem(item)
		return true
	}
	return false
}

总体的代码实例可以参见：https://github.com/harleylau/go-lru