摘要：最簡(jiǎn)單的一種緩存算法，設(shè)置緩存上限，當(dāng)達(dá)到了緩存上限的時(shí)候，按照先進(jìn)先出的策略進(jìn)行淘汰，再增加進(jìn)新的。隊(duì)列算法實(shí)現(xiàn)緩存需要一個(gè)對(duì)象和一個(gè)數(shù)組作為輔助數(shù)組記錄進(jìn)入順序先進(jìn)先出，刪除隊(duì)列第一個(gè)元素?zé)o論存在與否都對(duì)中的賦值，最近最少使用算法。

最簡(jiǎn)單的一種緩存算法，設(shè)置緩存上限，當(dāng)達(dá)到了緩存上限的時(shí)候，按照先進(jìn)先出的策略進(jìn)行淘汰，再增加進(jìn)新的 k-v 。

使用了一個(gè)對(duì)象作為緩存，一個(gè)數(shù)組配合著記錄添加進(jìn)對(duì)象時(shí)的順序，判斷是否到達(dá)上限，若到達(dá)上限取數(shù)組中的第一個(gè)元素key，對(duì)應(yīng)刪除對(duì)象中的鍵值。

/**
 * FIFO隊(duì)列算法實(shí)現(xiàn)緩存
 * 需要一個(gè)對(duì)象和一個(gè)數(shù)組作為輔助
 * 數(shù)組記錄進(jìn)入順序
 */
class FifoCache{
    constructor(limit){
        this.limit = limit || 10
        this.map = {}
        this.keys = []
    }
    set(key,value){
        let map = this.map
        let keys = this.keys
        if (!Object.prototype.hasOwnProperty.call(map,key)) {
            if (keys.length === this.limit) {
                delete map[keys.shift()]//先進(jìn)先出，刪除隊(duì)列第一個(gè)元素
            }
            keys.push(key)
        }
        map[key] = value//無論存在與否都對(duì)map中的key賦值
    }
    get(key){
        return this.map[key]
    }
}

module.exports = FifoCache

LRU（Least recently used，最近最少使用）算法。該算法的觀點(diǎn)是，最近被訪問的數(shù)據(jù)那么它將來訪問的概率就大，緩存滿的時(shí)候，優(yōu)先淘汰最無人問津者。

算法實(shí)現(xiàn)思路：基于一個(gè)雙鏈表的數(shù)據(jù)結(jié)構(gòu)，在沒有滿員的情況下，新來的 k-v 放在鏈表的頭部，以后每次獲取緩存中的 k-v 時(shí)就將該k-v移到最前面，緩存滿的時(shí)候優(yōu)先淘汰末尾的。

雙向鏈表的特點(diǎn)，具有頭尾指針，每個(gè)節(jié)點(diǎn)都有 prev(前驅(qū)) 和 next(后繼) 指針分別指向他的前一個(gè)和后一個(gè)節(jié)點(diǎn)。

關(guān)鍵點(diǎn)：在雙鏈表的插入過程中要注意順序問題，一定是在保持鏈表不斷的情況下先處理指針，最后才將原頭指針指向新插入的元素，在代碼的實(shí)現(xiàn)中請(qǐng)注意看我在注釋中說明的順序注意點(diǎn)！

class LruCache {
    constructor(limit) {
        this.limit = limit || 10
        //head 指針指向表頭元素，即為最常用的元素
        this.head = this.tail = undefined
        this.map = {}
        this.size = 0
    }
    get(key, IfreturnNode) {
        let node = this.map[key]
        // 如果查找不到含有`key`這個(gè)屬性的緩存對(duì)象
        if (node === undefined) return
        // 如果查找到的緩存對(duì)象已經(jīng)是 tail (最近使用過的)
        if (node === this.head) { //判斷該節(jié)點(diǎn)是不是是第一個(gè)節(jié)點(diǎn)
            // 是的話，皆大歡喜，不用移動(dòng)元素，直接返回
            return returnnode ?
                node :
                node.value
        }
        // 不是頭結(jié)點(diǎn)，鐵定要移動(dòng)元素了
        if (node.prev) { //首先要判斷該節(jié)點(diǎn)是不是有前驅(qū)
            if (node === this.tail) { //有前驅(qū)，若是尾節(jié)點(diǎn)的話多一步，讓尾指針指向當(dāng)前節(jié)點(diǎn)的前驅(qū)
                this.tail = node.prev
            }
            //把當(dāng)前節(jié)點(diǎn)的后繼交接給當(dāng)前節(jié)點(diǎn)的前驅(qū)去指向。
            node.prev.next = node.next
        }
        if (node.next) { //判斷該節(jié)點(diǎn)是不是有后繼
            //有后繼的話直接讓后繼的前驅(qū)指向當(dāng)前節(jié)點(diǎn)的前驅(qū)
            node.next.prev = node.prev
            //整個(gè)一個(gè)過程就是把當(dāng)前節(jié)點(diǎn)拿出來，并且保證鏈表不斷，下面開始移動(dòng)當(dāng)前節(jié)點(diǎn)了
        }
        node.prev = undefined //移動(dòng)到最前面，所以沒了前驅(qū)
        node.next = this.head //注意?。?！ 這里要先把之前的排頭給接到手?。。?！讓當(dāng)前節(jié)點(diǎn)的后繼指向原排頭
        if (this.head) {
            this.head.prev = node //讓之前的排頭的前驅(qū)指向現(xiàn)在的節(jié)點(diǎn)
        }
        this.head = node //完成了交接，才能執(zhí)行此步！不然就找不到之前的排頭啦！
        return IfreturnNode ?
            node :
            node.value
    }
    set(key, value) {
        // 之前的算法可以直接存k-v但是現(xiàn)在要把簡(jiǎn)單的 k-v 封裝成一個(gè)滿足雙鏈表的節(jié)點(diǎn)
        //1.查看是否已經(jīng)有了該節(jié)點(diǎn)
        let node = this.get(key, true)
        if (!node) {
            if (this.size === this.limit) { //判斷緩存是否達(dá)到上限
                //達(dá)到了，要?jiǎng)h最后一個(gè)節(jié)點(diǎn)了。
                if (this.tail) {
                    this.tail = this.tail.prev
                    this.tail.prev.next = undefined
                    //平滑斷鏈之后，銷毀當(dāng)前節(jié)點(diǎn)
                    this.tail.prev = this.tail.next = undefined
                    this.map[this.tail.key] = undefined
                    //當(dāng)前緩存內(nèi)存釋放一個(gè)槽位
                    this.size--
                }
                node = {
                    key: key
                }
                this.map[key] = node
                if(this.head){//判斷緩存里面是不是有節(jié)點(diǎn)
                    this.head.prev = node
                    node.next = this.head
                }else{
                    //緩存里沒有值，皆大歡喜，直接讓head指向新節(jié)點(diǎn)就行了
                    this.head = node
                    this.tail = node
                }
                this.size++//減少一個(gè)緩存槽位
            }
        }
        //節(jié)點(diǎn)存不存在都要給他重新賦值啊
        node.value = value
    }
}

module.exports = LruCache

具體的思路就是如果所要get的節(jié)點(diǎn)不是頭結(jié)點(diǎn)（即已經(jīng)是最近使用的節(jié)點(diǎn)了，不需要移動(dòng)節(jié)點(diǎn)位置）要先進(jìn)行平滑的斷鏈操作，處理好指針指向的關(guān)系，拿出需要移動(dòng)到最前面的節(jié)點(diǎn)，進(jìn)行鏈表的插入操作。