js实现 LRU 算法

方式一：map实现

代码语言：javascript复制

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 可以拿到第一个映射的 key
            this.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 双向链表

代码语言：javascript复制

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;
    }
}

代码语言：javascript复制

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

map 链表

0 人点赞