LRU算法

算法思路

可视化链接

https://lrucache.netlify.app/

LRU（Least Recently Used）缓存：容量固定，超出时淘汰最久未使用的项。

核心操作：

• get(key)：命中则返回 value，并将该 key 标记为最近使用；未命中返回 -1。
• put(key, value)：存在则更新并标记为最近使用；不存在则插入，超容量则淘汰最久未使用的项。

数据结构：哈希表（O(1) 查找）+ 双向链表（O(1) 移动/删除）。最近使用的节点靠近链表头，最久未使用的靠近链表尾。

python

class ListNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: ListNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_head(self, node: ListNode) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _pop_tail(self) -> ListNode:
        node = self.tail.prev
        self._remove(node)
        return node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_head(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._add_to_head(node)
        else:
            node = ListNode(key, value)
            self.cache[key] = node
            self._add_to_head(node)
            if len(self.cache) > self.capacity:
                tail = self._pop_tail()
                del self.cache[tail.key]

js

// 双向链表节点定义
class ListNode {
    constructor(key = 0, val = 0) {
        this.key = key;   // 存储键，用于在淘汰节点时从 Map 中删除对应项
        this.val = val;   // 存储值
        this.prev = null; // 指向前一个节点
        this.next = null; // 指向后一个节点
    }
}

// LRU 缓存类
class LRUCache {
    /**
     * @param {number} capacity - 缓存的最大容量
     */
    constructor(capacity) {
        this.capacity = capacity;          // 缓存容量
        this.cache = new Map();            // 哈希表，键 → 链表节点，实现 O(1) 查找
        // 创建两个哨兵节点（虚拟头尾节点），简化边界处理
        this.head = new ListNode();        // 头哨兵，始终在链表最前面，其 next 指向第一个真实节点
        this.tail = new ListNode();        // 尾哨兵，始终在链表最后面，其 prev 指向最后一个真实节点
        this.head.next = this.tail;        // 初始化时头哨兵 next 指向尾哨兵
        this.tail.prev = this.head;        // 尾哨兵 prev 指向头哨兵，此时链表为空
    }

    /**
     * 从双向链表中移除指定节点（不删除节点对象本身）
     * @param {ListNode} node - 要移除的节点
     */
    _remove(node) {
        // 让 node 的前驱节点直接指向 node 的后继节点
        node.prev.next = node.next;
        // 让 node 的后继节点直接指向 node 的前驱节点
        node.next.prev = node.prev;
        // 注意：node 的 prev/next 仍然指向原位置，但已从链表中脱离，后续可以重新插入
    }

    /**
     * 将节点添加到链表头部（头哨兵之后），表示该节点最近被使用
     * @param {ListNode} node - 要添加到头部的节点
     */
    _addToHead(node) {
        // 将 node 的 prev 指向头哨兵
        node.prev = this.head;
        // 将 node 的 next 指向原来头哨兵后面的第一个节点（原第一个真实节点）
        node.next = this.head.next;
        // 原来第一个真实节点的 prev 指向 node
        this.head.next.prev = node;
        // 头哨兵的 next 指向 node，完成插入
        this.head.next = node;
    }

    /**
     * 移除链表末尾的真实节点（尾哨兵的前一个节点），并返回该节点
     * @returns {ListNode} 被移除的尾节点
     */
    _popTail() {
        // 尾哨兵的前一个节点就是最久未使用的节点
        const node = this.tail.prev;
        // 从链表中移除它
        this._remove(node);
        return node;
    }

    /**
     * 获取缓存中指定键的值
     * @param {number} key - 键
     * @returns {number} 值，如果键不存在则返回 -1
     */
    get(key) {
        // 如果键不存在于 Map 中，返回 -1
        if (!this.cache.has(key)) return -1;
        // 从 Map 中取出对应的链表节点
        const node = this.cache.get(key);
        // 将该节点从当前位置移除（可能不在头部）
        this._remove(node);
        // 将该节点添加到链表头部，标记为最近使用
        this._addToHead(node);
        // 返回节点的值
        return node.val;
    }

    /**
     * 插入或更新缓存中的键值对
     * @param {number} key - 键
     * @param {number} value - 值
     */
    put(key, value) {
        // 情况1：键已存在，需要更新值并移动到头部
        if (this.cache.has(key)) {
            const node = this.cache.get(key);
            node.val = value;          // 更新值
            this._remove(node);        // 从原位置移除
            this._addToHead(node);     // 移动到头部（最近使用）
        } else {
            // 情况2：键不存在，创建新节点
            const node = new ListNode(key, value);
            this.cache.set(key, node); // 存入 Map
            this._addToHead(node);     // 添加到链表头部
            // 如果加入后超出容量，需要淘汰最久未使用的节点（即尾节点）
            if (this.cache.size > this.capacity) {
                const tail = this._popTail();      // 移除并获取尾节点
                this.cache.delete(tail.key);       // 从 Map 中删除对应的键
                // 注意：被删除的节点不再被引用，会被垃圾回收
            }
        }
    }
}

go

import "container/list"

type entry struct {
    key, val int
}

type LRUCache struct {
    capacity int
    cache    map[int]*list.Element
    list     *list.List
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        capacity: capacity,
        cache:    make(map[int]*list.Element),
        list:     list.New(),
    }
}

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        c.list.MoveToFront(elem)
        return elem.Value.(*entry).val
    }
    return -1
}

func (c *LRUCache) Put(key int, value int) {
    if elem, ok := c.cache[key]; ok {
        elem.Value.(*entry).val = value
        c.list.MoveToFront(elem)
        return
    }
    elem := c.list.PushFront(&entry{key, value})
    c.cache[key] = elem
    if c.list.Len() > c.capacity {
        back := c.list.Back()
        delete(c.cache, back.Value.(*entry).key)
        c.list.Remove(back)
    }
}