考察哈希表与双向链表组合、容量淘汰策略
核心结构
复杂度
代码(JavaScript,借助 Map 保序)
class LRUCache {
constructor(capacity) { this.cap = capacity; this.map = new Map(); }
get(key) {
if (!this.map.has(key)) return -1;
const v = this.map.get(key);
this.map.delete(key); this.map.set(key, v); // 提到最新
return v;
}
put(key, value) {
if (this.map.has(key)) this.map.delete(key);
this.map.set(key, value);
if (this.map.size > this.cap) {
const oldest = this.map.keys().next().value;
this.map.delete(oldest); // 淘汰最久未用
}
}
}
JavaScript 的 Map 会保留插入顺序,删除再插入即可把节点置为最新,迭代首键即最久未用,从而省去手写双向链表。
题目与答案就在本页;收藏、批注和错题重练在应用内