实现 LRU 缓存

问题

实现一个 LRU（Least Recently Used）缓存函数，当缓存达到上限时，自动删除最近最少使用的数据。

LRU 缓存常用于浏览器缓存站点信息，当内存有限时，优先删除最不常用的数据。

需求：

• put(key, value) 方法写入缓存，相同 key 则覆盖
• 缓存达到上限时，删除最久未使用的数据
• get(key) 方法读取缓存，并将该数据标记为最近使用
• get 操作时间复杂度为 O(1)

解答

数据结构选择

使用 Map 实现，因为：

• Map 的遍历顺序就是插入顺序，新数据在后，旧数据在前
• Map 的查找是 O(1) 复杂度
• 最前面的数据就是最久未使用的数据

完整实现

class LRUCache {
    constructor(n) {
        this.size = n; // 最大缓存数量
        this.data = new Map(); // 缓存空间
    }
    
    put(domain, info) {
        // 如果 key 已存在，先删除旧数据
        if (this.data.has(domain)) {
            this.data.delete(domain);
            this.data.set(domain, info); // 重新插入到末尾
            return;
        }
        
        // 如果缓存已满，删除最久未使用的数据（第一个）
        if (this.data.size >= this.size) {
            const firstKey = this.data.keys().next().value;
            this.data.delete(firstKey);
        }
        
        this.data.set(domain, info); // 写入新数据
    }
    
    get(domain) {
        // 如果数据不存在，返回 false
        if (!this.data.has(domain)) {
            return false;
        }
        
        // 获取数据并移动到末尾（标记为最近使用）
        const info = this.data.get(domain);
        this.data.delete(domain);
        this.data.set(domain, info);
        
        return info;
    }
}

使用示例

const cache = new LRUCache(3);

cache.put('site1.com', 'info1');
cache.put('site2.com', 'info2');
cache.put('site3.com', 'info3');

cache.get('site1.com'); // 'info1'，site1 变为最近使用

cache.put('site4.com', 'info4'); // 缓存已满，删除 site2（最久未使用）

cache.get('site2.com'); // false，已被删除

关键点

• Map 的遍历顺序即插入顺序，利用这个特性维护使用顺序
• 删除数据时从 Map 前面删除，因为最前面是最久未使用的
• 更新数据时先删除再插入，将数据移到末尾表示最近使用
• Map.keys().next().value 获取第一个 key，时间复杂度 O(1)
• 读取数据后也要移动到末尾，保持 LRU 语义正确