快捷導(dǎo)航

JavaScript手寫LRU算法的示例代碼

更新時間：2022年09月30日 08:25:16 作者：簡道

LRU是Least?Recently?Used的縮寫，即最近最少使用。作為一種經(jīng)典的緩存策略，它的基本思想是長期不被使用的數(shù)據(jù)，在未來被用到的幾率也不大，所以當(dāng)新的數(shù)據(jù)進(jìn)來時我們可以優(yōu)先把這些數(shù)據(jù)替換掉。本文用JavaScript實現(xiàn)這一算法，需要的可以參考一下

LRU 是 Least Recently Used 的縮寫，即最近最少使用。作為一種經(jīng)典的緩存策略，它的基本思想是長期不被使用的數(shù)據(jù)，在未來被用到的幾率也不大，所以當(dāng)新的數(shù)據(jù)進(jìn)來時我們可以優(yōu)先把這些數(shù)據(jù)替換掉。

一、基本要求

固定大?。合拗苾?nèi)存使用。
快速訪問：緩存插入和查找操作應(yīng)該很快，最好是 O(1) 時間。
在達(dá)到內(nèi)存限制的情況下替換條目：緩存應(yīng)該具有有效的算法來在內(nèi)存已滿時驅(qū)逐條目。

二、數(shù)據(jù)結(jié)構(gòu)

下面提供兩種實現(xiàn)方式，并完成相關(guān)代碼。

2.1 Map

在 Javascript 中，Map 的 key 是有序的，當(dāng)?shù)臅r候，他們以插入的順序返回鍵值。結(jié)合這個特性，我們也通過 Map 實現(xiàn) LRU 算法。

2.2 Doubly Linked List

我們也可通過雙向鏈表（Doubly Linked List）維護(hù)緩存條目，通過對鏈表的增、刪、改實現(xiàn)數(shù)據(jù)管理。為確保能夠從鏈表中快速讀取某個節(jié)點的數(shù)據(jù)，我們可以通過 Map 來存儲對鏈表中節(jié)點的引用。

三、Map 實現(xiàn)

在 初始化時 完成兩件事情：

1.配置存儲限制，當(dāng)大于此限制，緩存條目將按照最近讀取情況被驅(qū)逐。

2.創(chuàng)建一個用于存儲緩存數(shù)據(jù)的 Map 。

在 添加數(shù)據(jù) 時：

1.判斷當(dāng)前存儲數(shù)據(jù)中是否包含新進(jìn)數(shù)據(jù)，如果存在，則刪除當(dāng)前數(shù)據(jù)

2.判斷當(dāng)前存儲空間是否被用盡，如果已用盡則刪除 Map 頭部的數(shù)據(jù)。

map.delete(map.keys().next().value)

3.插入新數(shù)據(jù)到 Map 的尾部

基于 Javascript Map 實現(xiàn) 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)
    }
}

四、雙向鏈表實現(xiàn)

4.1 定義節(jié)點類

包含 prev，next，data 三個屬性，分別用以存儲指向前后節(jié)點的引用，以及當(dāng)前節(jié)點要存儲的數(shù)據(jù)。

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

4.2 定義鏈表類

包含 head、tail 屬性，分別指向鏈表的 頭節(jié)點 和 尾節(jié)點。

當(dāng)從鏈表中讀取數(shù)據(jù)時，需要將當(dāng)前讀取的數(shù)據(jù)移動到鏈表頭部；添加數(shù)據(jù)時，將新節(jié)點插入到頭部；當(dāng)鏈表節(jié)點數(shù)量大于限定的閥值，需要從鏈表尾部刪除節(jié)點。

{
    head: Node
    next: Node
    moveNodeToHead(node)
    insertNodeToHead(node)
    deleteLastNode()
}

4.3 定義 LRU 類

為 LRU 定義屬性：linkLine 用以存儲指向鏈表的引用；size 用以配置存儲空間大小限制；

為簡化從鏈表中查找節(jié)點，再定義 map 屬性，用以存儲不同鍵指向鏈表節(jié)點的引用。

定義成員方法，set(key,value) 用以添加數(shù)據(jù)，get(key) 讀取一條數(shù)據(jù)。

4.4 set(key,value)

如果 map 中存在當(dāng)前 key，則修改當(dāng)前節(jié)點的值，然后從鏈表中把當(dāng)前節(jié)點移動到鏈表頭部；

否則：

判斷當(dāng)前鏈表節(jié)點數(shù)量是否達(dá)到了存儲上線，如果是，則刪除鏈表尾部的節(jié)點。同時從 map 中移除相應(yīng)的節(jié)點引用；

創(chuàng)建新節(jié)點，然后插入到鏈表頭部，并添加 map 引用。

4.5 get(key)

如果 map 中存在當(dāng)前 key，從鏈表中讀取節(jié)點，將其移動到鏈表頭部，并返回結(jié)果，否則返回空。

{
    linkLine: LinkLine
    map: Map
    size: Number
    set(key, value)
    get(key)
}

4.6 代碼實現(xiàn)

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
        }       
    }
}

到此這篇關(guān)于JavaScript手寫LRU算法的示例代碼的文章就介紹到這了,更多相關(guān)JavaScript LRU算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: