前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >js实现 LRU 算法

js实现 LRU 算法

作者头像
蓓蕾心晴
发布2022-09-24 14:52:45
1.3K0
发布2022-09-24 14:52:45
举报
文章被收录于专栏:前端小叙前端小叙

方式一: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
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-08-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档