如何使用 JavaScript 实现一个简单的 LRU (Least Recently Used) 缓存？

推荐答案

-- -------------------- ---- -------
----- -------- -
  --------------------- -
    ------------- - ---------
    ---------- - --- ------ -- --------------
  -

  -------- -
    -- ---------------------- -
      ------ ---
    -
    ----- ----- - --------------------
    -----------------------
    ------------------- ------- -- ----- --- ------------
    ------ ------
  -

  -------- ------ -
      ------------------------
          -----------------------
      -
      -------------------------
      -- ---------------- - -------------- -
        -------------------------------------------------- -- ------------
      -
  -
-

-- ----
----- -------- - --- ------------
--------------- ---
--------------- ---
----------------------------- -- -- -
--------------- ---    --  ----- -
----------------------------- -- -- -- -----
----------------- ------- -
----------------------------- -- ----
----------------------------- -----
----------------------------- -----

本题详细解读

缓存策略：LRU

LRU (Least Recently Used) 是一种常见的缓存淘汰策略。其核心思想是：当缓存空间不足时，优先淘汰最近最少使用的数据，保留最近经常使用的数据。

实现思路

1. 数据结构选择:

   • 使用 Map 数据结构来存储缓存数据。 Map 可以保持插入顺序，这对于实现 LRU 策略非常重要。
   • Map 的 get, set, delete 方法时间复杂度均为 O(1)，满足高效访问要求。

2. 核心操作:

   • get(key):

     • 如果 key 存在于 Map 中：
       • 获取 key 对应的 value。
       • 将 key 从 Map 中删除。
       • 将 key 重新插入到 Map 的末尾（表示最近使用）。
       • 返回 value。
     • 如果 key 不存在，返回 -1。

   • put(key, value):

     • 如果key存在于Map中，先删除该key。
     • 将 key 和 value 插入到 Map 的末尾（表示最近使用）。
     • 如果 Map 的大小超过了 capacity，则删除 Map 中第一个元素（即最久未使用）。这里使用this.cache.keys().next().value获取队头key。

代码解析

• constructor(capacity):

  • 初始化缓存的容量 capacity 和一个 Map 实例 cache。

• get(key):

  • 检查 key 是否存在于 cache 中。
  • 如果存在，获取 value，并将其对应的 key 移动到 cache 的末尾，然后返回 value。
  • 如果不存在，返回 -1。

• put(key, value):

  • 如果key存在于Map中，先删除该key。
  • 将 key 和 value 插入到 cache 的末尾。
  • 如果缓存已满，删除 cache 中最老的（第一个） key-value 对。

为什么选择 Map？

• 保持插入顺序: Map 对象会记住键的原始插入顺序。这对于实现 LRU 策略至关重要，因为我们需要知道哪个元素是最近最少使用的。
• 高效查找: Map 对象的 get, set, delete 方法时间复杂度均为 O(1)，可以快速访问和操作缓存中的元素。
• **方便删除最早插入元素:**可以通过this.cache.keys().next().value方便的获取到最先插入的key，再通过delete删除。

时间复杂度

• get(key): O(1)
• put(key, value): O(1)

空间复杂度

• O(capacity) 缓存最多存储capacity个元素