NiceOffer

八股文解析

手撕：LRU Cache 实现（Go/Java）

发布于 2026-08-03

算法手撕LRU八股文

手撕：LRU Cache 实现（Go/Java）

一句话结论

  • 哈希表 + 双向链表 是标准解：get / put 均 O(1)
  • 关键边界：get 不存在返回 -1；put 满时淘汰尾部；key 已存在时更新并移到头部

面试标准答法

数据结构选择

  • 哈希表：map[key]*Node，O(1) 定位节点
  • 双向链表：维护使用顺序，头部为最新，尾部为最久未用

为什么不用单向链表？删除任意节点需要前驱指针，单向链表 O(n)。

Go 实现模板

type LRUCache struct {
    capacity int
    cache    map[int]*Node
    head, tail *Node
}

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

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

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

func (l *LRUCache) Put(key int, value int) {
    if node, ok := l.cache[key]; ok {
        node.value = value
        l.moveToHead(node)
        return
    }
    node := &Node{key: key, value: value}
    l.cache[key] = node
    l.addToHead(node)
    if len(l.cache) > l.capacity {
        removed := l.removeTail()
        delete(l.cache, removed.key)
    }
}

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

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

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

func (l *LRUCache) removeTail() *Node {
    node := l.tail.prev
    l.removeNode(node)
    return node
}

Java 实现思路

  • 自定义 Node 类 + HashMap<Integer, Node>
  • 或用 LinkedHashMap（面试能手写尽量手写）

关键边界

场景处理
get 不存在返回 -1，不动链表
put 已存在更新 value，移到头部
put 已满先加头部，再删尾部，并删哈希表
capacity = 0直接忽略所有操作

常见追问

追问要点
为什么用双向链表？删除任意节点 O(1)，单向链表需找前驱 O(n)
并发场景怎么办？加互斥锁，或分片（如 Guava Cache 的 segment）
LFU 怎么实现？哈希表 + 频次哈希表 + 频次双向链表，或最小堆
Redis 淘汰策略有 LRU 吗？有近似 LRU：maxmemory-policy allkeys-lru

面试回答模板（30 秒版）

延伸准备

  • 能手撕 LFU（LeetCode 460）
  • 能解释 LinkedHashMap 的 accessOrder 参数
  • 能说出 Guava Cache / Caffeine 的并发 LRU 实现思路

相关阅读