从头实现LRU

你的名字 2022-03-28 08:44 145阅读 0赞

本文设计和实现一个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][https_github.com_harleylau_go-lru]

[https_github.com_harleylau_go-lru]: https://github.com/harleylau/go-lru