Javascript 手写 LRU 算法

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

一、基本要求

  1. 固定大小:限制内存使用。
  2. 快速访问:缓存插入和查找操作应该很快,最好是 O(1) 时间。
  3. 在达到内存限制的情况下替换条目:缓存应该具有有效的算法来在内存已满时驱逐条目。

二、数据结构

下面提供两种实现方式,并完成相关代码。

2.1 Map

在 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 = 5     constructor(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 定义节点类

包含 prevnextdata 三个属性,分别用以存储指向前后节点的引用,以及当前节点要存储的数据。

{     prev: Node     next: Node     data: { key: string, data: any} } 

4.2 定义链表类

包含 headtail 属性,分别指向链表的 头节点尾节点

当从链表中读取数据时,需要将当前读取的数据移动到链表头部;添加数据时,将新节点插入到头部;当链表节点数量大于限定的阀值,需要从链表尾部删除节点。

{     head: Node     next: Node     moveNodeToHead(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: LinkLine     map: Map     size: Number     set(key, value)     get(key) } 

4.6 代码实现

class LinkNode {     prev = null     next = null     constructor(key, value) {         this.data = { key, value }     } }  class LinkLine {      head = null     tail = null      constructor() {         const headNode = new LinkNode('head', 'head')         const tailNode = new LinkNode('tail', 'tail')          headNode.next = tailNode         tailNode.prev = headNode          this.head = headNode         this.tail = tailNode     }      moveNodeToFirst(node) {         node.prev.next = node.next         node.next.prev = node.prev         this.insertNodeToFirst(node)     }      insertNodeToFirst(node) {         const second = this.head.next         this.head.next = node         node.prev = this.head         node.next = second         second.prev = node     }      delete(node) {         node.prev.next = node.next         node.next.prev = node.prev     }      deleteLastNode() {         const last = this.tail.prev         this.tail.prev = last.prev         last.prev.next = this.tail         return last     } }  class LRUCache {     linkLine = null     map = {}     size = 5      constructor(size) {         this.size = size || this.size         this.linkLine = new LinkLine     }      get(key) {         let value         if (this.map[key]) {             const node = this.map[key]             value = node.value             this.linkLine.moveNodeToFirst(node)         }         return value     }      set(key, value) {         if (this.map[key]) {             const node = this.map[key]             node.value = value             this.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         }            } } 

https://gauliang.github.io/blogs/2022/lru-algorithm/

发表评论

相关文章

当前内容话题