实现 LRU 缓存

题目描述

实现一个线程安全的 LRU（最近最少使用）缓存。

参考答案

type LRUCache struct {
    capacity int
    cache    map[int]*Node
    head     *Node
    tail     *Node
    mu       sync.Mutex
}

type Node struct {
    key   int
    value int
    prev  *Node
    next  *Node
}

func NewLRUCache(capacity int) *LRUCache {
    head := &Node{}
    tail := &Node{}
    head.next = tail
    tail.prev = head
    
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*Node),
        head:     head,
        tail:     tail,
    }
}

func (lru *LRUCache) Get(key int) int {
    lru.mu.Lock()
    defer lru.mu.Unlock()
    
    if node, ok := lru.cache[key]; ok {
        lru.moveToHead(node)
        return node.value
    }
    return -1
}

func (lru *LRUCache) Put(key, value int) {
    lru.mu.Lock()
    defer lru.mu.Unlock()
    
    if node, ok := lru.cache[key]; ok {
        node.value = value
        lru.moveToHead(node)
    } else {
        node := &Node{key: key, value: value}
        lru.cache[key] = node
        lru.addToHead(node)
        
        if len(lru.cache) > lru.capacity {
            lru.removeTail()
        }
    }
}

func (lru *LRUCache) moveToHead(node *Node) {
    lru.removeNode(node)
    lru.addToHead(node)
}

func (lru *LRUCache) addToHead(node *Node) {
    node.prev = lru.head
    node.next = lru.head.next
    lru.head.next.prev = node
    lru.head.next = node
}

func (lru *LRUCache) removeNode(node *Node) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

func (lru *LRUCache) removeTail() {
    node := lru.tail.prev
    lru.removeNode(node)
    delete(lru.cache, node.key)
}

关键点

1. 双向链表：维护访问顺序，O(1) 移动节点
2. 哈希表：O(1) 查找节点
3. 互斥锁：保证并发安全

复杂度分析

• Get：O(1)
• Put：O(1)
• 空间：O(capacity)