使用 JavaScript 实现 LFU（最少使用）和 LRU（最近最少使用）缓存策略，可以帮助你理解这两种算法的工作原理。下面是这两种缓存策略的实现示例。
总结
LRU（Least Recently Used）
LRU（最近最少使用）缓存算法基于最近使用的原则来管理缓存。以下是一个示例说明如何在 LRU 缓存中插入和访问元素：
假设给你一个数组，最大容量是 6：
- 当前数组状态：[1, 2, 3, 4, 5]
- 插入元素 6，数组变为：[1, 2, 3, 4, 5, 6]
- 使用元素 2，数组变为：[1, 3, 4, 5, 6, 2]（2 被移动到数组末尾，因为它是最近使用的）
- 插入元素 7，数组已经达到最大容量，需要淘汰最久未使用的元素（1）
- 删除元素 1，数组变为：[3, 4, 5, 6, 2, 7]
LFU（Least Frequently Used）
LFU（最少使用）缓存算法基于使用频率来管理缓存。以下是一个示例说明如何在 LFU 缓存中插入和访问元素：
假设给你一个数组，最大容量是 6：
- 当前数组状态：[1, 2, 3, 4, 5]（每个元素的使用频率为 1）
- 插入元素 6，数组变为：[1, 2, 3, 4, 5, 6]
- 使用元素 2，数组状态和使用频率变为：[(1,1), (2,2), (3,1), (4,1), (5,1), (6,1)]（2 的使用频率增加到 2）
- 再次使用元素 2，数组状态和使用频率变为：[(1,1), (2,3), (3,1), (4,1), (5,1), (6,1)]（2 的使用频率增加到 3）
- 插入元素 7，数组已经达到最大容量，需要淘汰使用频率最小的元素（使用频率为 1 的元素）
- 删除使用频率为 1 的元素（1、3、4、5 或 6），假设删除元素 1，数组变为：[(2,3), (3,1), (4,1), (5,1), (6,1), (7,1)]
这样，LFU 算法可以确保淘汰那些使用频率最低的元素，优先保留使用频率较高的元素。
总结
- LRU 算法：基于最近使用的原则管理缓存，最久未使用的元素会被淘汰。适用于需要快速访问最近使用过的元素的场景。
- LFU 算法：基于使用频率管理缓存，使用频率最低的元素会被淘汰。适用于需要根据元素使用频率决定缓存策略的场景。
实现 LRU 缓存策略
LRU 缓存可以通过结合 Map 和 Doubly Linked List 实现。以下是一个 LRU 缓存的简单实现：
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new 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) {
if (this.cache.has(key)) {
this.cache.delete(key);
}
this.cache.set(key, value);
if (this.cache.size > this.capacity) {
this.cache.delete(this.cache.keys().next().value);// delete the first key
}
}
}
// 测试 LRUCache
const lruCache = new LRUCache(3);
lruCache.put(1, 1);
lruCache.put(2, 2);
lruCache.put(3, 3);
console.log(lruCache.get(1)); // 1
lruCache.put(4, 4);
console.log(lruCache.get(2)); // -1 (因为 key 2 已被淘汰)
lruCache.put(5, 5);
console.log(lruCache.get(3)); // -1 (因为 key 3 已被淘汰)
console.log(lruCache.get(4)); // 4
console.log(lruCache.get(5)); // 5
实现 LFU 缓存策略
LFU 缓存相对复杂一些，需要维护每个缓存项的使用频率。我们可以使用一个 Map 来存储缓存项和它们的使用频率，再使用另一个 Map 来存储每个频率对应的缓存项集合。
class LFUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
this.freqMap = new Map();
}
get(key) {
if (!this.cache.has(key)) {
return -1;
}
const value = this.cache.get(key);
const freq = this.freqMap.get(key) || 0;
this.freqMap.set(key, freq + 1);
return value;
}
put(key, value) {
if (this.cache.size >= this.capacity) {
let minFreq = Infinity;
let minKey;
for (let [k, freq] of this.freqMap) {
if (freq < minFreq) {
minFreq = freq;
minKey = k;
}
}
this.cache.delete(minKey);
this.freqMap.delete(minKey);
}
this.cache.set(key, value);
this.freqMap.set(key, (this.freqMap.get(key) || 0) + 1);
}
}
const lfuCache = new LFUCache(3);
lfuCache.put(1, 1);
lfuCache.put(2, 2);
lfuCache.put(3, 3);
console.log(lfuCache.get(1)); // 1
lfuCache.put(4, 4);
console.log(lfuCache.get(2)); // -1 (因为 key 2 已被淘汰)
lfuCache.put(5, 5);
console.log(lfuCache.get(3)); // -1 (因为 key 3 已被淘汰)
console.log(lfuCache.get(4)); // 4
console.log(lfuCache.get(5)); // 5
总结
- LRU 缓存策略：根据最近使用的情况来淘汰最久未使用的项。通过
Map结合Doubly Linked List实现。 - LFU 缓存策略：根据使用频率来淘汰最少使用的项。通过两个
Map实现，一个存储缓存项和它们的使用频率，另一个存储每个频率对应的缓存项集合。
以上示例提供了这两种缓存策略的基本实现，可以根据具体需求进行扩展和优化。
