LRUCache

LRU（Least Recently Used）缓存实现，自动淘汰最近最少使用的项。

函数签名

class LRUCache<K, V> {
  constructor(capacity: number)
  get(key: K): V | undefined
  set(key: K, value: V): void
  has(key: K): boolean
  delete(key: K): boolean
  clear(): void
  get size(): number
  get capacity(): number
}

参数

参数名	类型	必填	说明
capacity	number	是	缓存容量（最大项数）

返回值

类型	说明
LRUCache<K, V>	LRU 缓存实例

工作原理

1. 数据结构：使用 Map 存储键值对（Map 保持插入顺序）

2. get(key)：

   • 检查 key 是否存在
   • 如果存在：
     • 获取值
     • 删除旧项
     • 重新插入（移到最后，表示最近使用）
     • 返回值
   • 如果不存在：返回 undefined

3. set(key, value)：

   • 如果 key 已存在：删除旧项
   • 检查容量是否已满：
     • 如果满：删除 Map 的第一项（最久未使用）
   • 插入新项（在最后）

4. has(key)：检查 key 是否存在

5. delete(key)：删除指定项

6. clear()：清空所有项

LRU 原理：

• Map 的第一项是最久未使用的（LRU）
• Map 的最后一项是最近使用的（MRU）
• 访问时移到末尾，满时删除首项

时间复杂度：所有操作均为 O(1)