使用 JavaScript 实现简单的 LRU 缓存

作为一名软件工程师，你很可能会遇到各种数据结构都有大放异彩的情况。但有一种数据结构并没有像其他结构那样受到太多关注，但在某些情况下却同样有用（甚至更有用）。这个数据结构就是LRU Cache。

什么是 LRU 缓存？

LRU缓存（即最近最少使用的缓存）是一种数据结构，它按照最近添加或访问的顺序存储信息。

一个通俗的比喻是衣柜里的衣架：穿过的衣服挂起来后，就放在衣架的右侧。随着时间的推移，只要看看衣架左侧，就能轻松判断哪些衣服已经很久没穿过了。

我为什么要使用它？

与其他数据结构相比，使用 LRU 缓存存储信息的主要优势在于附加功能。

计算机科学术语中的缓存可以被认为是存储在内存中可快速访问的位置的最近使用的一块数据，当重复提取相同的数据时，可以获得更快的性能。

如果我们考虑使用 LRU 缓存，那么在用户需要通过数据库搜索信息的应用中，它可能会非常有用。通常情况下，每次用户查找某个内容时，应用都会向数据库发送请求，这会耗费宝贵的时间。但是，如果我们将最近（或最常）搜索的项目存储在 LRU 缓存中，我们就可以快速检查缓存中是否存在搜索到的项目，如果存在，我们可以在更短的时间内检索到它！超级实用。

听起来不错，我们如何构建一个呢？

很高兴你问这个问题！传统的 LRU 缓存是通过将哈希表与双向链表相结合构建的，目的是在恒定的 O(1) 时间内快速查找项并检索最近使用和最近最少使用的项。

但是，如果您对在小规模项目中从头开始快速实现 LRU 缓存感兴趣，那么只需使用 JavaScript 类和Map()对象即可构建一个缓存，但需要花费检索运行时的时间。

最少/最近使用功能将保持不变，这在实践中是数据结构的关键方面。如果您有兴趣了解如何创建此版本的 LRU 缓存，请继续阅读！

1. 建立类和构造函数

我们将使用 JavaScript ES6 类构建我们的 LRU 缓存，如下所示：

class LRUCache {

}

在这个类中，我们将设置一个构造函数，以便每个 LRU 缓存实例都维护相同的结构。我们的缓存将接受一个容量参数，该参数设置缓存的最大增长大小，超过该大小后，我们将从存储中删除最近最少使用的项目，以节省空间并保持结构的有序性。

我们将使用此构造函数来建立缓存本身，使用 JavaScript Map 对象：

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

}

我们在这里使用 Map 对象的原因是 JavaScript Map维护了键和值的插入顺序。这为我们完成了大部分工作！

2. 构建Cache的Get和Put方法

现在，我们将在类中实现两个重要函数：Get和Put，它们将分别检索一个值并将一个键/值对插入到缓存中。

让我们从Get开始：

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

  // Implementing Get method
  get(key) {
    if (!this.cache.has(key)) return undefined;

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

}

让我们分解一下我们上面所做的工作。

1. 我们检查 Map 中是否存在该键。如果不存在，则返回“undefined”（这可以是任何表示检索失败的返回值，例如 -1 或错误消息）。
2. 接下来我们声明一个变量“val”，获取与该键关联的值，并将其分配给该变量。
3. 我们从缓存中删除该键/值对，然后重新设置它。由于我们的映射会保留插入数据的顺序，因此这会将检索到的键/值对放回到最前面（最近使用）的位置。
4. 无论在何处调用此方法，我们都会返回该值以供程序使用。

这就是 Get 方法的全部内容！

现在，我们将实现 Put 方法：

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

  get(key) {
    if (!this.cache.has(key)) return -1;

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

  // Implementing Put method
  put(key, value) {
    this.cache.delete(key);

    if (this.cache.size === this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
      this.cache.set(key, value);
    } else {
      this.cache.set(key, value);
    }
  }

}

让我们将其分解为几个步骤：

1. 第一行检查键是否已存在于 Map 中，如果存在则删除它；调用 .delete() 要么删除键/值对（如果存在），要么返回 undefined 并继续。
2. 如果缓存目前已达到最大容量（cache.size === this.capacity），我们将使用 来删除最近最少使用的键/值对，方法是使用迭代器this.cache.keys().next().value对象获取 Map 的第一个键，并将其作为参数传递给。然后，我们使用传递给 Put 方法的参数在缓存中设置一个新的键/值对。this.cache.delete()
3. 如果我们目前没有达到最大容量，我们只需像平常一样添加新的键/值对。

这就是我们的 Set 方法！

3.实现getLeastRecent和getMostRecent方法

至此，我们已经创建了 LRU 缓存的基本功能，但为了拥有完整的数据结构，还有一步需要完成。我们可能需要检索最近最少使用 (LRU) 或最近最多使用 (MRU) 的值！

为了做到这一点，我们将把 Map 转换为数组，然后分别检索数组的第一个（LRU）和最后一个（MRU）值：

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

  get(key) {
    if (!this.cache.has(key)) return -1;

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

  put(key, value) {
    this.cache.delete(key);

    if (this.cache.size === this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
      this.cache.set(key, value);
    } else {
      this.cache.set(key, value);
    }
  }

  // Implement LRU/MRU retrieval methods
  getLeastRecent() {
    return Array.from(this.cache)[0];
  }

  getMostRecent() {
    return Array.from(this.cache)[this.cache.size - 1];
  }

}

好了！如果你愿意，你可以使用同样的 Array-from-Map 概念来查找第二少用、第三多用等等。

这就是我们的 LRU 缓存！

如果您已经读到这里，非常感谢您花时间查看我的帖子！

我希望它对那些试图学习和理解数据结构的人，或者那些试图在 JavaScript 中实现它们的人有所帮助。😄