使用JavaScript怎么實現一個緩存算法

這篇文章給大家介紹使用JavaScript怎么實現一個緩存算法，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

FIFO

最簡單的一種緩存算法，設置緩存上限，當達到了緩存上限的時候，按照先進先出的策略進行淘汰，再增加進新的 k-v 。

使用了一個對象作為緩存，一個數組配合著記錄添加進對象時的順序，判斷是否到達上限，若到達上限取數組中的第一個元素key，對應刪除對象中的鍵值。

/**
 * FIFO隊列算法實現緩存
 * 需要一個對象和一個數組作為輔助
 * 數組記錄進入順序
 */
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()]//先進先出，刪除隊列第一個元素
      }
      keys.push(key)
    }
    map[key] = value//無論存在與否都對map中的key賦值
  }
  get(key){
    return this.map[key]
  }
}

module.exports = FifoCache

LRU

LRU（Least recently used，最近最少使用）算法。該算法的觀點是，最近被訪問的數據那么它將來訪問的概率就大，緩存滿的時候，優先淘汰最無人問津者。

算法實現思路：基于一個雙鏈表的數據結構，在沒有滿員的情況下，新來的 k-v 放在鏈表的頭部，以后每次獲取緩存中的 k-v 時就將該k-v移到最前面，緩存滿的時候優先淘汰末尾的。

雙向鏈表的特點，具有頭尾指針，每個節點都有 prev(前驅) 和 next(后繼) 指針分別指向他的前一個和后一個節點。

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

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

module.exports = LruCache

關于使用JavaScript怎么實現一個緩存算法就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。