实现 LRU 缓存

问题

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

解答

需求分析

LRU（Least Recently Used）缓存的核心逻辑：

• 提供 put 方法写入缓存数据，格式为 {域名: 信息}
• 缓存达到上限时，删除最近最少使用的数据
• 提供 get 方法读取缓存，被读取的数据要移动到最近使用位置
• get 操作的时间复杂度要求 O(1)

数据结构选择

使用 Map 实现，原因：

• Map 的遍历顺序就是插入顺序，新数据在后，旧数据在前
• Map 支持 O(1) 的查找操作
• 删除最不常用数据时，直接删除第一个元素即可

完整实现

class LRUCache {
    constructor(n) {
        this.size = n; // 最大缓存数量
        this.data = new Map(); // 缓存空间
    }
    
    put(domain, info) {
        // 如果已存在，先删除旧数据
        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 的第一个元素
• 移动数据到末尾的操作：先删除再重新插入
• get 和 put 操作都要更新数据的使用顺序
• 严格控制缓存数量不超过上限 n