leetcode146-LRU缓存

leetcode 146

思路

什么是LRU缓存？

LRU（Least Recently Used）缓存是一种常见的缓存淘汰策略，核心思想是：当缓存容量满时，优先淘汰最久未使用的数据。LeetCode 146 题要求实现一个支持get和put操作的 LRU 缓存，且操作时间复杂度需为 O (1)

核心思路

在 JavaScript 中，Map对象天然具备键值对插入顺序保留的特性，且map.keys().next().value可获取最早插入的键（最久未使用）。利用这一点，可很好实现删除最久未使用数据的功能

• 访问顺序维护：每次访问键时，通过delete+set将其移到 Map 末尾（表示最近使用）
• 淘汰策略：容量满时，删除 Map 的第一个键（最早插入的键）

关键操作解析

1. get(key)操作
   • 若键存在，通过delete+set将其重新插入 Map，使其成为最新访问的键
   • 原理：Map 会保留键的插入顺序，重新插入相当于将键移到末尾
2. put(key, val)操作
   • 若键已存在，同样通过delete+set更新值并刷新顺序。
   • 若键不存在且容量满，通过map.keys().next().value获取最早插入的键（最久未使用）并删除，再插入新键

时间复杂度：O(1) 空间复杂度: O(capacity)

实现

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cacheMap = new Map();
    }

    get(key) {
        const isExit = this.cacheMap.has(key);
        if (isExit) {
            const val = this.cacheMap.get(key);
            this.cacheMap.delete(key);
            this.cacheMap.set(key, val);
            return val;
        }
        return -1;
    }

    put(key, val) {
        const isExit = this.cacheMap.has(key);
        if (isExit) {
            this.cacheMap.delete(key)
            this.cacheMap.set(key, val)
        } else {
            if (this.capacity <= this.cacheMap.size) {
                // 超出缓存容量，删除最久未使用的key
                const first = this.cacheMap.keys().next().value;
                this.cacheMap.delete(first)
            }
            this.cacheMap.set(key, val)
        }
    }
}