浙江龙网

  1. 首页 > 生活百科 > >

Javascript 手写 LRU 算法

生活百科

LRU 是 Least Recently Used 的缩写，即最近最少使用 。作为一种经典的缓存策略，它的基本思想是长期不被使用的数据，在未来被用到的几率也不大 ， 所以当新的数据进来时我们可以优先把这些数据替换掉 。
一、基本要求

  1. 固定大?。合拗颇诖媸褂?。
  2. 快速访问：缓存插入和查找操作应该很快，最好是 O(1) 时间 。
  3. 在达到内存限制的情况下替换条目：缓存应该具有有效的算法来在内存已满时驱逐条目 。
二、数据结构下面提供两种实现方式，并完成相关代码 。
2.1 Map【Javascript 手写 LRU 算法】在 Javascript 中 ， Map 的 key 是有序的，当迭代的时候，他们以插入的顺序返回键值 。结合这个特性，我们也通过 Map 实现 LRU 算法 。
2.2 Doubly Linked List我们也可通过双向链表（Doubly Linked List）维护缓存条目，通过对链表的增、删、改实现数据管理 。为确保能够从链表中快速读取某个节点的数据，我们可以通过 Map 来存储对链表中节点的引用 。
三、Map 实现在 初始化时 完成两件事情：
  1. 配置存储限制，当大于此限制，缓存条目将按照最近读取情况被驱逐 。
  2. 创建一个用于存储缓存数据的 Map。
在 添加数据 时：
  1. 判断当前存储数据中是否包含新进数据，如果存在，则删除当前数据
  2. 判断当前存储空间是否被用尽，如果已用尽则删除 Map 头部的数据 。map.delete(map.keys().next().value)
  3. 插入新数据到 Map 的尾部
基于 Javascript Map 实现 LRU ， 代码如下：
class LRUCache {size = 5constructor(size) {this.cache = new Map()this.size = size || this.size}get(key) {if (this.cache.has(key)) {// 存在即更新let temp = this.cache.get(key)this.cache.delete(key)this.cache.set(key, temp)return temp}return null}set(key, value) {if (this.cache.has(key)) {this.cache.delete(key)}if (this.cache.size >= this.size) {this.cache.delete(this.cache.keys().next().value)}this.cache.set(key, value)}}四、双向链表实现4.1 定义节点类包含 prev，next，data 三个属性 ， 分别用以存储指向前后节点的引用，以及当前节点要存储的数据 。
{prev: Nodenext: Nodedata: { key: string, data: any}}4.2 定义链表类包含 head、tail 属性，分别指向链表的 头节点 和 尾节点 。
当从链表中读取数据时，需要将当前读取的数据移动到链表头部；添加数据时，将新节点插入到头部；当链表节点数量大于限定的阀值，需要从链表尾部删除节点 。
{head: Nodenext: NodemoveNodeToHead(node)insertNodeToHead(node)deleteLastNode()}4.3 定义 LRU 类为 LRU 定义属性：linkLine 用以存储指向链表的引用；size 用以配置存储空间大小限制；为简化从链表中查找节点，再定义 map 属性，用以存储不同键指向链表节点的引用 。
定义成员方法，set(key,value) 用以添加数据，get(key) 读取一条数据 。
4.4 set(key,value)
  1. 如果 map 中存在当前 key，则修改当前节点的值，然后从链表中把当前节点移动到链表头部；
  2. 否则：
    1. 判断当前链表节点数量是否达到了存储上线，如果是，则删除链表尾部的节点 。同时从 map 中移除相应的节点引用；
    2. 创建新节点 ， 然后插入到链表头部，并添加 map 引用 。
4.5 get(key)如果 map 中存在当前 key，从链表中读取节点，将其移动到链表头部，并返回结果，否则返回空 。
{linkLine: LinkLinemap: Mapsize: Numberset(key, value)get(key)}4.6 代码实现class LinkNode {prev = nullnext = nullconstructor(key, value) {this.data = https://www.huyubaike.com/biancheng/{ key, value }}}class LinkLine {head = nulltail = nullconstructor() {const headNode = new LinkNode('head', 'head')const tailNode = new LinkNode('tail', 'tail')headNode.next = tailNodetailNode.prev = headNodethis.head = headNodethis.tail = tailNode}moveNodeToFirst(node) {node.prev.next = node.nextnode.next.prev = node.prevthis.insertNodeToFirst(node)}insertNodeToFirst(node) {const second = this.head.nextthis.head.next = nodenode.prev = this.headnode.next = secondsecond.prev = node}delete(node) {node.prev.next = node.nextnode.next.prev = node.prev}deleteLastNode() {const last = this.tail.prevthis.tail.prev = last.prevlast.prev.next = this.tailreturn last}}class LRUCache {linkLine = nullmap = {}size = 5constructor(size) {this.size = size || this.sizethis.linkLine = new LinkLine}get(key) {let valueif (this.map[key]) {const node = this.map[key]value = https://www.huyubaike.com/biancheng/node.valuethis.linkLine.moveNodeToFirst(node)}return value}set(key, value) {if (this.map[key]) {const node = this.map[key]node.value = valuethis.linkLine.moveNodeToFirst(node)} else {// 删除最后一个元素if (Object.keys(this.map).length >= this.size) {const lastNode = this.linkLine.deleteLastNode()delete this.map[lastNode.data.key]}const newNode = new LinkNode(key, value)this.linkLine.insertNodeToFirst(newNode)this.map[key] = newNode}}}

推荐阅读


上一篇：20220929-ArrayList扩容机制源码分析

下一篇：day44-反射03