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

包含 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)

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/