JavaScript手写LRU算法的示例代码

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

一、基本要求

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

二、数据结构

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

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 定义节点类

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

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

4.2 定义链表类

包含head、tail属性，分别指向链表的头节点和尾节点。

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

{
  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)

如果 map 中存在当前 key，则修改当前节点的值，然后从链表中把当前节点移动到链表头部；

否则：

判断当前链表节点数量是否达到了存储上线，如果是，则删除链表尾部的节点。同时从 map 中移除相应的节点引用；

创建新节点，然后插入到链表头部，并添加 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
      }       
  }
}

关于JavaScript手写LRU算法的示例代码的文章就介绍至此，更多相关JavaScript LRU算法内容请搜索编程宝库以前的文章，希望以后支持编程宝库！

 前言嗯，，，跟之前封装“全局 Loading”的出发点基本一样，因为产品觉得 ElementUI 提供的默认上传组件，使用“照片墙” ...