Go 简单实现 LRU 缓存

Feb 4, 2022 22:00 · 744 words · 2 minute read Golang

LRU(Least recently used)——优先淘汰最久未被使用访问过的数据。

思路：缓存通常以 HashMap 来提供访问接口，保证常量复杂度的读取性能；以 LinkedList 的节点顺序来表示数据的时间顺序，在每次命中缓存时，将返回的对象调整到链表头；缓存淘汰时从链表尾清理数据。

import "container/list"

type Key interface{}

type Cache struct {
    ll    *list.List
    cache map[Key]*list.Element
}

func New() *Cache {
    return &Cache{
        ll:    list.New(),
        cache: make(map[Key]*list.Element),
    }
}

实现 Add 方法

  • 如果 HashMap 中 key 存在，将链表中的对象移动到表头，并更新 HashMap
  • 如果 HashMap 中 key 不存在，将值作为对象添加到链表头，并键值对插入 HashMap
func (c *Cache) Add(key Key, value interface{}) {
    if c.cache == nil {
        c.ll = list.New()
        c.cache = make(map[Key]*list.Element)
    }

    if ee, ok := c.cache[key]; ok {
        c.ll.MoveToFront(ee)
        ee.Value = value
        return
    }

    ele := c.ll.PushFront(value)
    c.cache[key] = ele
}

实现 Del 方法

  • 如果 HashMap 中 key 存在，删除链表中对应的值对象，并删除 HashMap 中的键值对
func (c *Cache) Del(key Key) {
    if c.cache == nil {
        return
    }

    if ele, ok := c.cache[key]; ok {
        c.ll.Remove(ele)
        delete(c.cache, key)
    }
}

实现 Get 方法

  • 如果 HashMap 中 key 存在，将链表中对应的值对象移动到表头并返回该值
func (c *Cache) Get(key Key) (value interface{}, ok bool) {
    if c.cache == nil {
        return
    }
    if ele, ok := c.cache[key]; ok {
        c.ll.MoveToFront(ele)
        return ele.Value, true
    }
    return
}

实现 RemoveOldest 方法

  • 获取链表尾的元素，并删除 HashMap 中的键值对
func (c *Cache) RemoveOldest() {
    if c.cache == nil {
        return
    }
    ele := c.ll.Back()
    c.ll.Remove(ele)
    // delete(c.cache) @_@
}

那么问题来了，以上实现，无法通过链表中的值对象得知其对应的 key。。。

所以我们在维护链表时，可以将键值对结构化为一个对象作为元素：

type entry struct {
    key   Key
    value interface{}
}

重新实现 Add 方法

func (c *Cache) Add(key Key, value interface{}) {
    if c.cache == nil {
        c.ll = list.New()
        c.cache = make(map[Key]*list.Element)
    }

    if ee, ok := c.cache[key]; ok {
        c.ll.MoveToFront(ee)
        ee.Value.(*entry).value = value
        return
    }

    ele := c.ll.PushFront(&entry{key, value})
    c.cache[key] = ele
}

重新实现 Del 方法

func (c *Cache) Del(key Key) {
    if c.cache == nil {
        return
    }

    if ele, ok := c.cache[key]; ok {
        c.ll.Remove(ele)
        kv := ele.Value.(*entry)
        delete(c.cache, kv.key)
    }
}

重新实现 Get 方法

func (c *Cache) Get(key Key) (value interface{}, ok bool) {
    if c.cache == nil {
        return
    }
    if ele, ok := c.cache[key]; ok {
        c.ll.MoveToFront(ele)
        return ele.Value.(*entry).value, true
    }
    return
}

重新实现 RemoveOldest 方法

通过 entry 结构体就可以拿到值对应的 key，从而删除 HashMap 中的键值对：

func (c *Cache) RemoveOldest() {
    if c.cache == nil {
        return
    }
    ele := c.ll.Back()
    c.ll.Remove(ele)
    kv := ele.Value.(*entry)
    delete(c.cache, kv.key)
}

以上来自于 Golang 官方的 groupcache 项目中的 lru 包，更为详细的实现请查看源码：https://github.com/golang/groupcache/blob/master/lru/lru.go