Go语言实现 LRU

LRU（Least Recently Used）算法，即最近最少使用算法;其基本思想是，如果一个数据最近被访问过，那么它在未来被访问的概率也会很高；反之，如果一个数据很久都没有被访问过，那么它在未来被访问的概率就相对较低。因此，LRU算法选择淘汰最近最少使用的数据，即选择最长时间没有被访问过的数据进行淘汰。

具体来说，LRU算法通常使用一个双向链表和一个哈希表来实现。双向链表中的节点按照最近访问时间的顺序排列，最近访问的节点排在链表头部，最久未访问的节点排在链表尾部。哈希表中存储每个节点的地址，以便快速查找和删除。

当需要访问一个数据时，LRU算法首先在哈希表中查找该数据，如果存在，则将对应的节点移动到链表头部；如果不存在，则将该数据添加到链表头部，并在哈希表中创建对应的节点。

当需要淘汰数据时，LRU算法选择链表尾部的节点进行淘汰，并在哈希表中删除对应的节点。

golang 实现 LRU 算法：

package lru

import (
    "container/list"
    "errors"
    "sync"
)

// LRU implements a non-thread safe fixed size LRU cache
type LRU struct {
    size      int
    evictList *list.List
    items     map[interface{}]*list.Element
}

// entry is used to hold a value in the evictList
type entry struct {
    key   interface{}
    value interface{}
}

// NewLRU constructs an LRU of the given size
func NewLRU(size int) (*LRU, error) {
    if size <= 0 {
        return nil, errors.New("must provide a positive size")
    }
    c := &LRU{
        size:      size,
        evictList: list.New(),
        items:     make(map[interface{}]*list.Element),
    }
    return c, nil
}

// Add adds a value to the cache.  Returns true if an eviction occured.
func (c *LRU) Add(key, value interface{}) bool {
    // Check for existing item
    if ent, ok := c.items[key]; ok {
        c.evictList.MoveToFront(ent)
        ent.Value.(*entry).value = value
        return false
    }

    // Add new item
    ent := &entry{key, value}
    entry := c.evictList.PushFront(ent)
    c.items[key] = entry

    evict := c.evictList.Len() > c.size
    // Verify size not exceeded
    if evict {
        c.removeOldest()
    }
    return evict
}

// Get looks up a key's value from the cache.
func (c *LRU) Get(key interface{}) (value interface{}, ok bool) {
    if ent, ok := c.items[key]; ok {
        c.evictList.MoveToFront(ent)
        return ent.Value.(*entry).value, true
    }
    return
}

// Remove removes the provided key from the cache, returning if the
// key was contained.
func (c *LRU) Remove(key interface{}) bool {
    if ent, ok := c.items[key]; ok {
        c.removeElement(ent)
        return true
    }
    return false
}

// removeOldest removes the oldest item from the cache.
func (c *LRU) removeOldest() {
    ent := c.evictList.Back()
    if ent != nil {
        c.removeElement(ent)
    }
}

// removeElement is used to remove a given list element from the cache
func (c *LRU) removeElement(e *list.Element) {
    c.evictList.Remove(e)
    kv := e.Value.(*entry)
    delete(c.items, kv.key)
    if c.onEvict != nil {
        c.onEvict(kv.key, kv.value)
    }
}

需要注意的是这个 LRU 实现并不是线程安全的，如果需要线程安全，需要在外层方法加锁，同时，由于 golang 的 lock 并不是可重入的，需要注意避免死锁问题。以下实现中基于 LRU 做了一次封装，实现了线程安全的内存级 LRU-Cache：

完整代码： https://github.com/ArchieYao/leet-code-training/blob/main/src/lru/lru.go

2023/04/27