如何使用 ECMAScript 2016 的 Map 数据结构实现 LRU 缓存-JavaScript中文网-JavaScript教程资源分享门户

前言

随着互联网的不断发展，数据量的急剧增加，很多应用都需要使用缓存来提高访问性能。而 LRU 缓存机制是一种经典的缓存算法，也是缓存实现的基础之一。本文将介绍如何使用 ECMAScript 2016 的 Map 数据结构实现 LRU 缓存。

LRU 缓存算法

LRU（Least Recently Used）算法是一种常用的缓存淘汰算法。显然，当缓存容量达到上限时，需要淘汰一些缓存项以腾出空间存储新的数据。那么如何选择被淘汰的缓存项？LRU 算法的策略是淘汰最近最少使用的缓存项，也就是说，每次缓存被访问，就将该缓存项移到缓存列表的最前端，从而始终保持缓存列表的最后一项是最近最少使用的缓存项。

ECMAScript 2016 的 Map 数据结构

Map 是 ECMAScript 2015 引入的新的数据结构，它类似于对象，但具有更好的可扩展性和更好的性能。与对象相比，Map 具有以下优点：

支持任意类型的键，而对象的键只能是字符串或符号。
能够直接获取 Map 的长度，而对象需要手动计算属性个数。
存储的键值对可以保持原有的顺序。

Map 的常用方法有：

set(key, value)：设置键值对。
get(key)：获取键对应的值。如果键不存在，返回 undefined。
has(key)：判断是否包含某个键。
delete(key)：删除指定键的键值对。
clear()：删除所有键值对。
entries()：返回一个迭代器，遍历 Map 中的键值对。

要实现 LRU 缓存，我们需要用到上面提到的 set、get 和 delete 方法。

实现 LRU 缓存

接下来，我们来介绍如何使用 Map 实现 LRU 缓存。首先，我们需要使用 Map 存储缓存项，键为缓存项的键，值为缓存项的值。其次，我们需要记录每个缓存项的访问顺序，可以使用一个数组来实现。访问顺序的数组中，越靠后的项表示越早被访问到的缓存项。

下面是使用 Map 实现 LRU 缓存的示例代码：

// javascriptcn.com 代码示例
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
    this.recentlyUsedKeys = [];
  }

  get(key) {
    if (this.cache.has(key)) {
      // 将该缓存项移到最前面
      const index = this.recentlyUsedKeys.indexOf(key);
      this.recentlyUsedKeys.splice(index, 1);
      this.recentlyUsedKeys.unshift(key);
      return this.cache.get(key);
    }
    return undefined;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      // 如果已存在该缓存项，更新值并将其移到最前面
      const index = this.recentlyUsedKeys.indexOf(key);
      this.recentlyUsedKeys.splice(index, 1);
      this.recentlyUsedKeys.unshift(key);
      this.cache.set(key, value);
    } else {
      // 如果不存在该缓存项，添加到缓存中并将其移到最前面
      if (this.cache.size >= this.capacity) {
        // 缓存已满，删除最近最少使用的缓存项
        const oldestKey = this.recentlyUsedKeys.pop();
        this.cache.delete(oldestKey);
      }
      this.recentlyUsedKeys.unshift(key);
      this.cache.set(key, value);
    }
  }
}

在这个示例代码中，LRUCache 类实现了 get 和 put 方法。get 方法用于获取缓存项的值，如果不存在该缓存项，则返回 undefined；put 方法用于向缓存中添加或更新缓存项的值。每次 get 或 put 操作都会将操作的缓存项移到最前面。

总结

本文介绍了如何使用 ECMAScript 2016 的 Map 数据结构实现 LRU 缓存。通过实现 LRUCache 类，我们可以用 Map 存储缓存项，用数组记录访问顺序，从而实现 LRU 算法。在实际应用中，还可以根据需求修改 LRUCache 类，例如增加过期时间等功能。

来源：JavaScript中文网，转载请注明来源本文地址：https://www.javascriptcn.com/post/65335f607d4982a6eb6e60de