成都网站建设备案,双语网站费用,沈阳网站设计开发公司,wordpress的主题在哪个文件夹文章目录 LRU实现 LRU
优先去除最久没有访问到的数据。
实现
通过组合哈希表#xff08;Hash Table#xff09;和双向链表#xff08;Doubly Linked List#xff09;实现 LRU 缓存。并且以 O(1) 的时间复杂度执行 get 和 put 操作核心是对节点的新增、访问都会让节点移动… 文章目录 LRU实现 LRU
优先去除最久没有访问到的数据。
实现
通过组合哈希表Hash Table和双向链表Doubly Linked List实现 LRU 缓存。并且以 O(1) 的时间复杂度执行 get 和 put 操作核心是对节点的新增、访问都会让节点移动到双向链表头部当容量超过时直接删除尾部节点即可
class LRUCache {constructor(capacity) {// 容量this.capacity capacity;this.cache new Map();// 用于记录访问顺序的双向链表声明空的头节点和尾节点this.head {};this.tail {};// 头和尾相连this.head.next this.tail;this.tail.prev this.head;}get(key) {const map this.cache;if (!map.has(key)) {return -1;}// 每次把使用的节点放到链表的头部const node map.get(key);this._moveToHead(node);return node.value;}put(key, value) {const map this.cache;// 如果 key 已存在更新并移动到双向链表头部if (map.has(key)) {const node map.get(key);node.value value;this._moveToHead(node);} else {if (map.size this.capacity) {// 缓存容量已满移除尾部节点const leastUsedKey this.tail.prev.key;this._removeNode(this.tail.prev);map.delete(leastUsedKey);}// 创建新节点和更新 HashMap并移动到链表头部const newNode this._addNode({ key, value });map.set(key, newNode);}}// 双向链表删除节点_removeNode(node) {node.prev.next node.next;node.next.prev node.prev;}// 删除双向链表旧节点位置然后移动到头部_moveToHead(node) {this._removeNode(node);this._addNode(node);}// 添加节点并移动到头部_addNode(node) {node.prev this.head;node.next this.head.next;this.head.next.prev node;this.head.next node;return node;}
}// 使用示例
const cache new LRUCache(2);
cache.put(1, 10);
console.log(cache.get(1)); // 10
cache.put(2, 20);
cache.put(3, 30);
console.log(cache.get(1)); // -1
