最简单的LRU算法实现（TJ出品） Nodejs版

好的，让我们来详细分析并实现一个简单的LRU（Least Recently Used）缓存算法。这个算法将根据最近使用的频率来管理缓存中的条目，并且会移除最不常用的条目。

简介

LRU缓存是一种常见的缓存替换策略，它通过移除最久未被访问的条目来保持缓存的大小在一定的限制范围内。这种策略非常适合那些经常访问但数据量较大的场景。

实现代码

我们来实现一个简单的LRU缓存类。这个类包含一个缓存存储（store），一个键列表（keys），以及缓存的最大容量（limit）。以下是具体的实现：

class LRUCache {
  constructor(limit) {
    this.limit = limit;
    this.store = {};
    this.keys = [];
  }

  add(key, value) {
    // 如果key已经存在，则将其移动到keys的末尾
    if (this.keys.includes(key)) {
      const index = this.keys.indexOf(key);
      this.keys.splice(index, 1);
      this.keys.push(key);
    } else {
      // 否则，如果缓存已满，则移除最不常用的条目
      if (this.keys.length >= this.limit) {
        const lruKey = this.keys.shift();
        delete this.store[lruKey];
      }
      this.keys.push(key);
    }

    // 添加或更新缓存条目
    this.store[key] = { value, createdAt: new Date() };
  }

  get(key) {
    if (!this.store[key]) {
      return undefined;
    }

    // 将访问过的key移到keys的末尾
    const index = this.keys.indexOf(key);
    this.keys.splice(index, 1);
    this.keys.push(key);

    return this.store[key].value;
  }
}

// 使用示例
const cache = new LRUCache(3);
cache.add('a', 'valueA');
cache.add('b', 'valueB');
cache.add('c', 'valueC');

console.log(cache.get('a')); // 输出 valueA
cache.add('d', 'valueD'); // 这将导致 'b' 被移除，因为它是最近最少使用的
console.log(cache.get('b')); // 输出 undefined

解释

• add 方法用于向缓存中添加新的键值对。如果键已经存在于缓存中，则将其从keys列表中移除并添加到末尾，表示该键最近被使用。
• 如果缓存已满，则移除keys列表中的第一个元素（即最近最少使用的键），然后将新键添加到末尾。
• get 方法用于获取缓存中的值。如果键存在，则将其从keys列表中移除并添加到末尾，表示该键最近被访问过。

通过这种方式，我们可以有效地管理和维护一个固定大小的LRU缓存。