跳到主要内容

实现 LRU 缓存

问题​

如何用 Go 实现一个线程安全的 LRU（Least Recently Used）缓存？

答案​

数据结构：双向链表 + 哈希表​

  • 哈希表：O(1)O(1) 查找
  • 双向链表：O(1)O(1) 移动和删除

完整实现​

type entry struct {
    key   string
    value interface{}
    prev  *entry
    next  *entry
}

type LRUCache struct {
    mu       sync.Mutex
    capacity int
    items    map[string]*entry
    head     *entry // 哨兵头
    tail     *entry // 哨兵尾
}

func NewLRUCache(capacity int) *LRUCache {
    head := &entry{}
    tail := &entry{}
    head.next = tail
    tail.prev = head

    return &LRUCache{
        capacity: capacity,
        items:    make(map[string]*entry),
        head:     head,
        tail:     tail,
    }
}

func (c *LRUCache) Get(key string) (interface{}, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()

    if e, ok := c.items[key]; ok {
        c.moveToFront(e) // 访问后移到头部
        return e.value, true
    }
    return nil, false
}

func (c *LRUCache) Put(key string, value interface{}) {
    c.mu.Lock()
    defer c.mu.Unlock()

    if e, ok := c.items[key]; ok {
        e.value = value
        c.moveToFront(e)
        return
    }

    // 新元素
    e := &entry{key: key, value: value}
    c.items[key] = e
    c.addToFront(e)

    // 超容量，淘汰最久未使用的
    if len(c.items) > c.capacity {
        c.removeLeast()
    }
}

// 移到链表头部（最近访问）
func (c *LRUCache) moveToFront(e *entry) {
    c.removeNode(e)
    c.addToFront(e)
}

func (c *LRUCache) addToFront(e *entry) {
    e.prev = c.head
    e.next = c.head.next
    c.head.next.prev = e
    c.head.next = e
}

func (c *LRUCache) removeNode(e *entry) {
    e.prev.next = e.next
    e.next.prev = e.prev
}

func (c *LRUCache) removeLeast() {
    e := c.tail.prev // 尾部前一个就是最久未使用的
    c.removeNode(e)
    delete(c.items, e.key)
}

带 TTL 的 LRU​

type ttlEntry struct {
    key       string
    value     interface{}
    expireAt  time.Time
    prev, next *ttlEntry
}

func (c *TTLLRUCache) Get(key string) (interface{}, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()

    e, ok := c.items[key]
    if !ok {
        return nil, false
    }

    // 检查是否过期
    if time.Now().After(e.expireAt) {
        c.removeNode(e)
        delete(c.items, key)
        return nil, false
    }

    c.moveToFront(e)
    return e.value, true
}

func (c *TTLLRUCache) Put(key string, value interface{}, ttl time.Duration) {
    // ... 同上，但设置 expireAt = time.Now().Add(ttl)
}

测试​

func TestLRUCache(t *testing.T) {
    cache := NewLRUCache(2)

    cache.Put("a", 1)
    cache.Put("b", 2)

    v, ok := cache.Get("a")
    assert.True(t, ok)
    assert.Equal(t, 1, v)

    cache.Put("c", 3) // 淘汰 b（最久未使用）

    _, ok = cache.Get("b")
    assert.False(t, ok) // b 已被淘汰

    v, _ = cache.Get("c")
    assert.Equal(t, 3, v)
}

常见面试问题​

Q1: 为什么不直接用 map？​

答案：map 没有顺序，无法知道哪个 key 最久未使用。链表维护访问顺序，map 提供快速查找，两者结合才能实现 O(1)O(1) 的 LRU。

Q2: Go 的 container/list 能用吗？​

答案：可以，但面试通常要求手写链表。container/list 使用 interface{}，类型不安全且有拆箱开销，手写实现性能更好。

Q3: LRU 和 LFU 的区别？​

答案：

  • LRU（Least Recently Used）：淘汰最久未访问的
  • LFU（Least Frequently Used）：淘汰访问次数最少的
  • LRU 更简单常用，LFU 对频繁访问的数据更友好

相关链接​