首页 > web前端 > js教程 > 正文

使用 Javascript 实现 LRU 缓存

王林
发布: 2024-08-26 21:31:02
原创
1003 人浏览过

LRU Cache Implementation using Javascript

介绍

LRU 代表最近最少使用。 LRU 缓存是一种缓存,当缓存达到其容量时,最近最少使用的条目将被删除。

  • 使用LRU缓存的主要原因是为了提高访问数据的性能。从缓存访问数据通常比从主内存或远程服务器检索数据更快。
  • 通过将最近使用的数据存储在缓存中,增加了缓存命中的机会,从而提高了数据检索的速度。

仅供参考:

  • 映射数据结构用于模仿哈希表的行为。这允许高效的查找、插入和删除操作。
  • 实现了双链表以实现元素之间的轻松移动。这提供了双向遍历(向前和向后)并执行恒定时间插入和删除的能力。
  • 这两种数据结构的结合可以实现高效的操作,利用哈希表和双链表的优点。

以下是如何在 JavaScript 中实现 LRU 缓存的基本示例:

// Why we need this LRU
class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

//Least Recently used
class LRU {
    constructor() {
     this.head = this.tail = null;
     this.map = new Map();
     this.size = 0; // Why I added size, because may be in future we can say if capacity reach to the size, we will remove the tail first and then insert.
    }

    get(key) {
        if (this.map.has(key)) {
            const node = this.map.get(key);

            if (node !== this.head) {
                this.remove(node);
                this.insert(node);
            }

            return node.value;
        }

        return -1;
    }

    update(key, value) {
        if (this.map.has(key)) {
            let node = this.map.get(key);
            node.value = value;

            if (node !== this.head) {
                this.remove(node);
                this.insert(node);
            }

            return node.value;
        } else {
            console.log('Key not found'); 
            // Here we can check for capacity if available we can call insert
            // if capacity is not available we will remove the tail and then insert.
        }
    }

    remove(node) {
        if (node === this.tail) {
            this.tail = this.tail.prev;
        }

        const prevNode = node.prev;
        const nextNode = node.next;

        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    insert(key, value) {
        const newNode = new Node(key, value);
        this.map.set(key, newNode);
        if (this.head === null) {
            this.head = this.tail = newNode;
            this.size = 1;
            return;
        }
        // We need to insert at the Begining
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head= newNode;
        this.size++;
        return;
    }
}

const test = new LRU();
test.insert('A', 20);
test.insert('B', 10);
test.insert('C', 5);
test.insert('D', 7);

console.log(test);
console.log('------------------');
console.log('C ---> ', test.get('C'));
console.log('D ---> ', test.get('D'));

console.log('D ---> ', test.update('B', 100));

/*
LRU {
  tail: <ref *1> Node {
    key: 'A',
    value: 20,
    next: null,
    prev: Node { key: 'B', value: 10, next: [Circular *1], prev: [Node] }
  },
  head: <ref *2> Node {
    key: 'D',
    value: 7,
    next: Node { key: 'C', value: 5, next: [Node], prev: [Circular *2] },
    prev: null
  },
  map: Map(4) {
    'A' => <ref *1> Node {
      key: 'A',
      value: 20,
      next: null,
      prev: [Node]
    },
    'B' => Node { key: 'B', value: 10, next: [Node], prev: [Node] },
    'C' => Node { key: 'C', value: 5, next: [Node], prev: [Node] },
    'D' => <ref *2> Node {
      key: 'D',
      value: 7,
      next: [Node],
      prev: null
    }
  },
  size: 4
}
------------------
C --->  5
D --->  7
D --->  100
B --->  100
*/
登录后复制

如果您有任何疑问,请随时与我联系。

以上是使用 Javascript 实现 LRU 缓存的详细内容。更多信息请关注PHP中文网其他相关文章!

来源:dev.to
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!