algorithms►leetcode

031-LRU缓存(hash或双向链表)

146.LRU缓存-Medium

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

什么是LRU缓存？

LRU（Least Recently Used，最近最少使用）是一种常见的缓存淘汰算法。当缓存空间不足时，它会优先淘汰那些最近最少使用的数据，保留最近访问过的数据。

LRU缓存的工作原理

  1. 访问数据：当访问缓存中的数据时，该数据会被移动到”最近使用”的位置（通常是链表头部或尾部）
  2. 插入数据：当插入新数据时，它会被放在”最近使用”的位置
  3. 淘汰数据：当缓存达到容量上限时，会从”最近最少使用”的位置移除数据

LRU缓存的实现

通常使用哈希表（快速查找）和双向链表（维护访问顺序）的组合来实现LRU缓存：

  • 哈希表：提供O(1)时间复杂度的数据查找
  • 双向链表：维护数据的访问顺序，最近访问的在头部，最久未访问的在尾部

下面是采用Map对象（哈希表）来达到O(1)时间复杂度：

1.哈希表完整实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // 使用Map来存储键值对
  }

  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }
    // 获取值
    const value = this.cache.get(key);
    // 删除原有位置
    this.cache.delete(key);
    // 重新插入到末尾（表示最近使用）
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    // 如果key已存在，先删除
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } 
    // 插入新值
    this.cache.set(key, value);
    // 如果超出容量，删除最久未使用的（即Map中的第一个元素）
    //！！！map没有length属性
    if (this.cache.size > this.capacity) {
      // Map.keys()返回一个迭代器，next()获取iterator的第一个object，object的value属性对应的真正要取的key值
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
  }
}

使用示例

1
2
3
4
5
6
7
8
9
10
11
const lru = new LRUCache(2); // 容量为2

lru.put(1, 1);              // 缓存是 {1=1}
lru.put(2, 2);              // 缓存是 {1=1, 2=2}
console.log(lru.get(1));    // 返回 1
lru.put(3, 3);              // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
console.log(lru.get(2));    // 返回 -1 (未找到)
lru.put(4, 4);              // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
console.log(lru.get(1));    // 返回 -1 (未找到)
console.log(lru.get(3));    // 返回 3
console.log(lru.get(4));    // 返回 4

2.使用双向链表的实现（更接近底层原理）

1. 基本结构

[双向链表]：维护访问顺序
head <-> [最近使用的] <-> ... <-> [最久未使用的] <-> tail

[哈希表]：快速查找
{key: 链表节点地址}

2. 访问数据（get操作）

原始状态：
head <-> A <-> B <-> C <-> tail

访问B后：
head <-> B <-> A <-> C <-> tail

3. 插入数据（put操作）

容量=3，当前状态：
head <-> B <-> A <-> C <-> tail

插入D时：
1. 添加到头部：head <-> D <-> B <-> A <-> C <-> tail
2. 发现容量超限（4>3）
3. 移除尾部C：head <-> D <-> B <-> A <-> tail

实现步骤

1. 定义双向链表节点

1
2
3
4
5
6
7
8
class ListNode {
  constructor(key, value) {
    this.key = key;    // 用于删除哈希表项
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

2. 初始化LRU缓存

1
2
3
4
5
6
7
8
9
10
11
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = {};           // 哈希表
    this.size = 0;            // 当前大小
    this.head = new ListNode(); // 伪头部
    this.tail = new ListNode(); // 伪尾部
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
}

3. 实现辅助方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 添加到头部
_addToHead(node) {
  node.prev = this.head;
  node.next = this.head.next;
  this.head.next.prev = node;
  this.head.next = node;
}

// 移除节点
_removeNode(node) {
  node.prev.next = node.next;
  node.next.prev = node.prev;
}

// 移动节点到头部
_moveToHead(node) {
  this._removeNode(node);
  this._addToHead(node);
}

// 移除尾部节点
_removeTail() {
  const node = this.tail.prev;
  this._removeNode(node);
  return node; // 返回被移除的节点，用于删除哈希表项
}

4. 实现get和put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
get(key) {
  if (!(key in this.map)) return -1;
  
  const node = this.map[key];
  this._moveToHead(node); // 移动到头部表示最近使用
  return node.value;
}

put(key, value) {
  if (key in this.map) {
    // 已存在则更新值并移动
    const node = this.map[key];
    node.value = value;
    this._moveToHead(node);
  } else {
    // 创建新节点
    const node = new ListNode(key, value);
    this.map[key] = node;
    this._addToHead(node);
    this.size++;
    
    // 检查容量
    if (this.size > this.capacity) {
      const removed = this._removeTail();
      delete this.map[removed.key];
      this.size--;
    }
  }
}

3.实现要点总结

  1. 双向链表：维护访问顺序，头部是最近使用的，尾部是最久未使用的
  2. 哈希表：实现O(1)时间复杂度的节点查找
  3. 伪头尾节点：简化边界条件处理
  4. 关键操作：
    • 访问节点时移动到头部
    • 插入新节点到头部
    • 满容量时删除尾部节点

通过这种结构，我们实现了所有操作都是O(1)时间复杂度的LRU缓存。

如果你需要更接近底层原理的实现（比如面试中可能会要求），可以使用双向链表+哈希表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class ListNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.size = 0;
    this.cache = {};
    // 使用伪头部和伪尾部节点
    this.head = new ListNode(0, 0);
    this.tail = new ListNode(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key) {
    if (key in this.cache) {
      const node = this.cache[key];
      // 移动到头部
      this.moveToHead(node);
      return node.value;
    }
    return -1;
  }

  put(key, value) {
    if (key in this.cache) {
      // 如果存在，更新值并移动到头部
      const node = this.cache[key];
      node.value = value;
      this.moveToHead(node);
    } else {
      // 创建新节点
      const node = new ListNode(key, value);
      this.cache[key] = node;
      // 添加到头部
      this.addToHead(node);
      this.size++;
      // 检查容量
      if (this.size > this.capacity) {
        // 移除尾部节点
        const removed = this.removeTail();
        delete this.cache[removed.key];
        this.size--;
      }
    }
  }

  addToHead(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

  removeNode(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  moveToHead(node) {
    this.removeNode(node);
    this.addToHead(node);
  }

  removeTail() {
    const node = this.tail.prev;
    this.removeNode(node);
    return node;
  }
}

为什么使用Map实现更简洁？

JavaScript的Map对象保持键值对的插入顺序，这使得我们可以利用这个特性：

  1. 新插入或访问的元素会自动移到”最后”
  2. 第一个元素就是最久未使用的

这种实现方式利用了语言特性，代码更简洁，但在面试中可能会被要求实现更底层的双向链表版本。

时间复杂度分析

  • get操作：O(1) - 哈希表查找 + 链表移动
  • put操作：O(1) - 哈希表插入/更新 + 链表操作

LRU缓存的应用场景

  1. 数据库缓存（如MySQL查询缓存）
  2. 操作系统页面置换
  3. Web服务器缓存
  4. CDN内容分发网络
  5. 浏览器缓存机制

LRU的变种

  1. LRU-K：考虑最近K次访问的历史
  2. 2Q：两个队列，一个用于最近访问，一个用于频繁访问
  3. ARC：自适应缓存替换算法，结合LRU和LFU

优缺点

优点：

  • 实现相对简单
  • 对热点数据友好
  • 时间复杂度优秀（O(1)）

缺点：

  • 对于偶发性的批量操作可能导致缓存污染
  • 需要维护额外的数据结构（哈希表+双向链表）
  • 对于某些访问模式（如循环访问超过缓存大小的数据集）效率不高

LRU缓存因其简单高效的特点，在实际开发中被广泛使用，是面试中常见的数据结构设计题目。