什么是LRU，如何用JavaScript实现LRU缓存机制

842字
4分钟
2024-08-08
- 技术

简介

LRU 是 Least Recently Used 的缩写，是一种缓存淘汰策略。当缓存达到其存储上限时，LRU 会移除最久未使用的条目。该策略基于这样一个假设：最近使用的数据很可能在将来还会被使用，而最久未使用的数据很可能不会再被使用。

LRU缓存的JavaScript实现

在 JavaScript 中实现一个 LRU 缓存，可以使用 Map 结合 双向链表 来实现。Map 保证了元素的插入顺序，双向链表有助于高效地将最近使用的元素移到表头和删除最久未使用的元素。

代码实现

以下是一个简单的 LRU 缓存实现：

1
// 定义双向链表节点类
2
class Node {
3
  constructor(key, value) {
4
    this.key = key;
5
    this.value = value;
6
    this.prev = null;
7
    this.next = null;
8
  }
9
}
10

11
// 定义LRU缓存类
12
class LRUCache {
13
  constructor(capacity) {
14
    this.capacity = capacity; // 缓存容量
15
    this.map = new Map(); // 存储缓存数据
16
    this.head = new Node(null, null); // 虚拟头节点
17
    this.tail = new Node(null, null); // 虚拟尾节点
18
    this.head.next = this.tail;
19
    this.tail.prev = this.head;
20
  }
21

22
  // 获取缓存值
23
  get(key) {
24
    if (!this.map.has(key)) {
25
      return -1; // 如果缓存中没有该键，返回-1
26
    }
27

28
    const node = this.map.get(key);
29
    this._remove(node); // 从双向链表中移除节点
30
    this._add(node); // 将节点添加到链表尾部（表示最近使用）
31

32
    return node.value;
33
  }
34

35
  // 添加或更新缓存值
36
  put(key, value) {
37
    if (this.map.has(key)) {
38
      this._remove(this.map.get(key)); // 如果缓存中已存在该键，先删除旧节点
39
    }
40

41
    const newNode = new Node(key, value);
42
    this._add(newNode); // 将新节点添加到链表尾部
43
    this.map.set(key, newNode);
44

45
    if (this.map.size > this.capacity) {
46
      const lruNode = this.head.next; // 获取最久未使用的节点
47
      this._remove(lruNode); // 从链表中移除最久未使用的节点
48
      this.map.delete(lruNode.key); // 从缓存中删除最久未使用的键
49
    }
50
  }
51

52
  // 从双向链表中移除节点
53
  _remove(node) {
54
    node.prev.next = node.next;
55
    node.next.prev = node.prev;
56
  }
57

58
  // 将节点添加到双向链表尾部
59
  _add(node) {
60
    node.prev = this.tail.prev;
61
    node.next = this.tail;
62
    this.tail.prev.next = node;
63
    this.tail.prev = node;
64
  }
65
}

示例使用

1
const lru = new LRUCache(2);
2

3
lru.put(1, 1);
4
lru.put(2, 2);
5
console.log(lru.get(1)); // 输出 1
6
lru.put(3, 3); // 淘汰键 2
7
console.log(lru.get(2)); // 输出 -1 (未找到)
8
lru.put(4, 4); // 淘汰键 1
9
console.log(lru.get(1)); // 输出 -1 (未找到)
10
console.log(lru.get(3)); // 输出 3
11
console.log(lru.get(4)); // 输出 4

代码解释

Node 类：用于双向链表节点，包含 key 和 value 以及 prev 和 next 指针。
LRUCache 类：管理缓存的主要类，初始化时设置容量 capacity 并创建一个 Map 和两个哨兵节点 head 和 tail。
get 方法：从缓存中获取值，如果存在则将节点移动到尾部（表示最近使用）。
put 方法：将新值插入缓存，若缓存已存在该键值对，则先删除旧节点。插入新节点后，检查是否超过容量，若超过则移除最前面的节点（表示最久未使用）。
_remove 方法：从双向链表中删除节点。
_add 方法：将节点添加到双向链表尾部。