方式一:map实现
class LRU {constructor(size) {this.size = size;this.cache = new Map();}get(key) {if (this.cache.has(key)) {const value = this.cache.get(key);this.cache.delete(key);this.cache.set(key, value);return value;}return -1;}put(key, val) {if (this.cache.has(key)) {this.cache.delete(key);}if (this.cache.size >= this.size) {// 如果当前缓存的map 的长度超出限制,则删除最前面的一个映射keys.next().value 可以拿到第一个映射的 keythis.cache.delete(this.cache.keys().next().value);}this.cache.set(key, val);} } const lruCache = new LRU(2); lruCache.put(1, 1); lruCache.put(2, 2); const res1 = lruCache.get(1); lruCache.put(3, 3); const res2 = lruCache.get(2); lruCache.put(4, 4); const res3 = lruCache.get(1); const res4 = lruCache.get(3); const res5 = lruCache.get(4);console.log("LRU", res1, res2, res3, res4, res5); // 1 -1 -1 3 4
方式二:map+双向链表
class DoubleNode {constructor(element) {this.element = element;this.next = null;this.prev = null;} } class LRUCache2 {constructor(capacity) {this.capacity = capacity;this.size = 0;this.cache = new Map();this.head = new DoubleNode();this.tail = new DoubleNode();this.head.next = this.tail;this.tail.prev = this.head;}get(key) {if (!this.cache.has(key)) {return -1;}const node = this.cache.get(key);this.moveToHead(node);return node.element.value;}put(key, value) {if (!this.cache.has(key)) {const node = new DoubleNode({key,value,});this.cache.set(key, node);this.addToHead(node);this.size++;if (this.size > this.capacity) {const removed = this.removeTail();console.log("removed===", removed);this.cache.delete(removed.element.key);this.size--;}} else {const node = this.cache.get(key);node.element.value = value;this.moveToHead(node);}}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;} }
const lruCache2 = new LRUCache2(2); lruCache2.put(1, 1); lruCache2.put(2, 2); const res11 = lruCache2.get(1); // console.log("res11", res11); lruCache2.put(3, 3); const res22 = lruCache2.get(2); // console.log("res22", res22); lruCache2.put(4, 4); const res33 = lruCache2.get(1); const res44 = lruCache2.get(3); const res55 = lruCache2.get(4);console.log(res11, res22, res33, res44, res55); // 1 -1 -1 3 4