lru（最近最少使用）缓存是一种缓存，当缓存超出其容量时，它会逐出最近最少访问的项目。它在内存有限且您只想缓存最常访问的数据的场景中非常有用。
在 javascript 中，lru 缓存可以使用 map（用于快速查找和维护插入顺序）和双向链表（用于两端高效插入和删除）的组合来实现。但是，为了简单起见，我们将在以下实现中使用 map。
这是 lru 缓存的 javascript 实现：
class lrucache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new map(); // using map to maintain key-value pairs
}
// get the value from the cache
get(key) {
if (!this.cache.has(key)) {
return -1; // if the key is not found, return -1
}
// key is found, move the key to the most recent position
const value = this.cache.get(key);
this.cache.delete(key); // remove the old entry
this.cache.set(key, value); // reinsert to update its position (most recently used)
return value;
}
// add or update the value in the cache
put(key, value) {
if (this.cache.has(key)) {
// if the key already exists, remove it to update its position
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
// if the cache is at capacity, delete the least recently used item
const leastrecentlyusedkey = this.cache.keys().next().value;
this.cache.delete(leastrecentlyusedkey);
}
// insert the new key-value pair (most recent)
this.cache.set(key, value);
}
}
说明：
构造函数：lrucache类用给定的容量进行初始化，它使用map来存储缓存的键值对。地图会跟踪插入顺序，这有助于识别最近最少使用 (lru) 的项目。
获取（密钥）：
- 如果缓存中存在该键，该方法将返回其值，并通过先删除该键然后重新插入该键将键移动到最近的位置。
- 如果键不存在，则返回-1。
put（键，值）：
- 如果缓存中已存在该密钥，则会删除该密钥并重新插入它（将其位置更新为最近使用的位置）。
- 如果缓存达到其容量，它将删除最近最少使用的键（map 中的第一个键）。
- 最后，新的键值对被添加到缓存中。
使用示例：
const lruCache = new LRUCache(3); // Cache with a capacity of 3 lruCache.put(1, 'one'); // Add key 1 lruCache.put(2, 'two'); // Add key 2 lruCache.put(3, 'three'); // Add key 3 console.log(lruCache.get(1)); // Output: 'one' (key 1 becomes the most recently used) lruCache.put(4, 'four'); // Cache is full, so it evicts key 2 (least recently used) console.log(lruCache.get(2)); // Output: -1 (key 2 has been evicted) console.log(lruCache.get(3)); // Output: 'three' (key 3 is still in the cache) console.log(lruCache.get(4)); // Output: 'four' (key 4 is in the cache)
