JavaScript實現(xiàn)LRU緩存的三種方式詳解

更新時間：2022年06月28日 08:21:48 作者：諸葛小愚

LRU全稱為Least?Recently?Used，即最近使用的。針對的是在有限的內存空間內，只緩存最近使用的數(shù)據(jù)（即get和set的數(shù)據(jù)）。本文介紹了JavaScript實現(xiàn)LRU緩存的三種方式，需要的可以參考一下

LRU全稱為Least Recently Used，即最近使用的。針對的是在有限的內存空間內，只緩存最近使用的數(shù)據(jù)（即get和set的數(shù)據(jù)），超過有限內存空間的數(shù)據(jù)將會被刪除。這個在面試題中也是常會被問到的內容，接下來就看看怎么來實現(xiàn)。

分析

從定義來看，LRU至少有兩個特性：通過鍵值對讀寫、有序。實現(xiàn)鍵值對讀寫，一般我們會使用哈希表來表示，注意哈希表是一個邏輯結構，實際上我們需要使用object、map等來實現(xiàn)；數(shù)據(jù)有序，即最近使用的數(shù)據(jù)放在前面，已經(jīng)過時的數(shù)據(jù)放在后面或被刪除，并且支持數(shù)據(jù)是可排序的，我們可以想到數(shù)組、鏈表、map之類的數(shù)據(jù)格式。因此，我們有三種方式可以實現(xiàn)LRU緩存：

Map
Object + Array
LinkedList

使用Map實現(xiàn)LRU緩存

Map對象保存的是鍵值對，并且可以記住鍵的原始插入順序。

const map = new Map();
map.set(2, 2);
map.set(1, 2);
console.log(map); // Map(2) {2 => 2, 1 => 2}，按照原始的插入順序
const obj = new Object();
obj[2] = 2;
obj[1] = 1
console.log(obj); // {1: 1, 2: 2}，不會按照原始的插入順序

那么我們就可以根據(jù)Map的特性實現(xiàn)LRU，下面是原理圖：

實現(xiàn)代碼：

class LRUCache {
    data = new Map(); // 數(shù)據(jù)map
    constructor(length) {
    if (length < 1) throw new Error('長度不能小于1')
        this.length = length
    }

    set(key, value) {
        const data = this.data;
        // 如果存在該對象,則直接刪除
        if (data.has(key)) {
            data.delete(key);
        }
        // 將數(shù)據(jù)對象添加到map中
        data.set(key, value);
        if (data.size > this.length) {
            // 如果map長度超過最大值,則取出map中的第一個元素,然后刪除
            const delKey = data.keys().next().value
            data.delete(delKey);
        }
    }
    get(key) {
        const data = this.data;
        // 數(shù)據(jù)map中沒有key對應的數(shù)據(jù),則返回null
        if (!data.has(key)) return null;
        const value = data.get(key);
        // 返回數(shù)據(jù)前,先刪除原數(shù)據(jù),然后在添加,就可以保持在最新
        data.delete(key);
        data.set(key, value);
        return value;
    }
}

測試一下：

const lruCache = new LRUCache(2);
lruCache.set('1', 1); // Map(1) {1 => 1}
lruCache.set('2',2); // Map(2) {1 => 1, 2 => 2}
console.log(lruCache.get('1')); // Map(2) {2 => 2, 1 => 1}
lruCache.set('3',3); // Map(2) {1 => 1, 3 => 3}
console.log(lruCache.get('2')); // null
lruCache.set('4',4); // Map(2) {3 => 3, 4 => 4}
console.log(lruCache.get('1')); // null
console.log(lruCache.get('3')); // Map(2) {4 => 4, 3 => 3}
console.log(lruCache.get('4')); // Map(2) {3 => 3, 4 => 4}

運行結果：

使用Map基本上就可以實現(xiàn)LRU緩存，并且其兼容性還可以，除了IE兼容性差點：

如果不使用Map，那么還可以使用什么方式實現(xiàn)LRU緩存呢？

使用Object + Array實現(xiàn)LRU緩存

剛剛我們也分析了，LRU需要滿足兩點：鍵值對和可排序，這兩點可以分別對應到Object和Array，那么我們是不是就可以以此為思路實現(xiàn)呢？答案是可以的，實現(xiàn)代碼：

class LRUCacheObjArr {
    length = 0; // 定義列表最大長度
    dataObj = {}; // 使用對象暫存數(shù)據(jù),在可保證get時間復雜度為O(1)
    dataArr = []; // 使用數(shù)組解決有序的問題
    constructor(length) {
        if (length < 1) throw new Error('參數(shù)非法')
        this.length = length;
    }
    get(key) {
        if (!this.dataObj[key] || !this.dataArr.length) return null;
        // 需要將訪問到的值,重新放在數(shù)組的最末尾,表示最新的數(shù)據(jù)
        const index = this.dataArr.findIndex(item => item.key === key);
        // 先刪除原數(shù)據(jù),然后push到數(shù)組末尾
        this.dataArr.splice(index, 1);
        this.dataArr.push(this.dataObj[key]);
        // 返回值,對象是無序的,我們只需要保證里面的數(shù)據(jù)是最新的即可
        return this.dataObj[key].value;
    }
    set(key, value) {
        // 定義對象數(shù)據(jù)
        const obj = {key, value};
        const index = this.dataArr.findIndex(item => item.key === key);
        // 判斷是否為新增還是修改
        if (index !== -1) {
            // 如果已存在數(shù)據(jù),則先刪除,然后push到末尾
            this.dataArr.splice(index, 1);
            this.dataArr.push(obj);
        } else {
            // 如果不存在數(shù)據(jù),則數(shù)組直接push
            this.dataArr.push(obj);
        }
        // 對象新增或者修改同一個對象
        this.dataObj[key] = obj;
        // 判斷新增數(shù)據(jù)后,是否超過最大長度
        if (this.dataArr.length > this.length) {
            // 數(shù)組是有序的,超長后直接從頭部刪除,并且獲取刪除的數(shù)據(jù)
            const tmp = this.dataArr.shift();
            // 數(shù)據(jù)對象里面也應該刪除當前刪除的對象,避免被再次取到
            delete this.dataObj[tmp.key];
        }
    }
}

我們使用同樣的測試案例測試一下：

const lruCache = new LRUCacheObjArr(2);
lruCache.set('1', 1); // dataArr(1) [obj1], dataObj(1) {'1': obj1}
lruCache.set('2',2); // dataArr(2) [obj1,  obj2], dataObj(2) {'1': obj1, '2': obj2}
console.log(lruCache.get('1')); // dataArr(2) [obj2,  obj1], dataObj(2) {'1': obj1, '2': obj2}
lruCache.set('3',3); // dataArr(2) [obj1,  obj3], dataObj(2) {'1': obj1, '3': obj3}
console.log(lruCache.get('2')); // null
lruCache.set('4',4); // dataArr(2) [obj3,  obj4], dataObj(2) {'3': obj3, '4': obj4}
console.log(lruCache.get('1')); // null
console.log(lruCache.get('3')); // dataArr(2) [obj4,  obj3], dataObj(2) {'3': obj3, '4': obj4}
console.log(lruCache.get('4')); // dataArr(2) [obj3,  obj4], dataObj(2) {'3': obj3, '4': obj4}

運行結果：

使用對象+數(shù)組的方式，雖然可以實現(xiàn)效果，但是由于會頻繁操作數(shù)組，因此會犧牲一些性能，而且實現(xiàn)起來也沒有Map方便。除了使用數(shù)組+對象，其實我們還可以使用雙向鏈表的方式實現(xiàn)LRU。

使用雙向鏈表實現(xiàn)LRU

雙向鏈表，顧名思義就是兩個方向的鏈表，這有別于單向鏈表。直接看圖可能更直觀一點：

雙向鏈表在移動元素時，會比單向鏈表復雜一點,，例如我們想把B和C節(jié)點交換一下位置，其過程如下：

這對應到LRU有什么意義呢？雙向鏈表是有序的，每一個節(jié)點都知道其上一個或者下一個節(jié)點；其存值的方式也是使用鍵值對的方式，因此完全可以實現(xiàn)LRU。

實現(xiàn)代碼：

  class LRUCacheLinked {
      data = {}; // 鏈表數(shù)據(jù)
      dataLength = 0; // 鏈表長度,使用變量保存,可以更快訪問
      listHead = null; // 鏈表頭部
      listTail = null; // 鏈表尾部
      length = 0; // 鏈表最大長度
      // 構造函數(shù)
      constructor(length) {
        if (length < 1) throw new Error('參數(shù)不合法')
        this.length = length;
      }
      set(key, value) {
        const curNode = this.data[key];
        if (curNode == null) {
          // 新增數(shù)據(jù)
          const nodeNew = {key, value};
          // 移動到末尾
          this.moveToTail(nodeNew);
          // 將新增的節(jié)點保存到數(shù)據(jù)對象中,其pre或next將在moveToTail中設置
          this.data[key] = nodeNew;
          // 鏈表長度遞增
          this.dataLength++;
          // 初始化鏈表頭部
          if (this.dataLength === 1) this.listHead = nodeNew;
        } else {
          // 修改現(xiàn)有數(shù)據(jù)
          curNode.value = value;
          // 移動到末尾
          this.moveToTail(curNode);
        }
        // 添加完數(shù)據(jù)后可能會導致超出長度,因此嘗試著刪除數(shù)據(jù)
        this.tryClean();
      }

      get(key) {
        // 根據(jù)key值取出對應的節(jié)點
        const curNode = this.data[key];
        if (curNode == null) return null;
        if (this.listTail === curNode) {
          // 如果被訪問的元素處于鏈表末尾，則直接返回值，且不用修改鏈表
          return curNode.value;
        }
        // 如果是中間元素或者頭部元素，則在獲取前需要將其移動到鏈表尾部,表示最新
        this.moveToTail(curNode);
        return curNode.value;
      }
      // 移動節(jié)點到鏈表尾部
      moveToTail(curNode) {
        // 獲取鏈表尾部
        const tail = this.listTail;
        // 如果當前節(jié)點就是鏈表尾部,則不做處理,直接返回
        if (tail === curNode) return;
        // 1. preNode和nextNode斷絕與curNode之間的關系
        const preNode = curNode.pre;
        const nextNode = curNode.next;
        if (preNode) {
          if (nextNode) {
            // 當前元素的上一個節(jié)點指向其下一個
            preNode.next = nextNode;
          } else {
            // 斷開當前元素與上一個節(jié)點的聯(lián)系
            delete preNode.next;
          }
        }
        if (nextNode) {
          if (preNode) {
            // 當前元素的下一個節(jié)點指向其上一個
            nextNode.pre = preNode;
          } else {
            // 斷開當前元素與下一個節(jié)點的關系
            delete nextNode.pre;
          }
          // 如果當前節(jié)點是鏈表頭部,則需要重新賦值
          if (this.listHead === curNode) this.listHead = nextNode;
        }

        // 2. curNode斷絕與preNode和nextNode之間的關系
        delete curNode.pre
        delete curNode.next

        // 3. 在list末尾,重新建立curNode的新關系
        if (tail) {
          tail.next = curNode;
          curNode.pre = tail;
        }
        // 重新賦值鏈表尾部,保持最新
        this.listTail = curNode;
      }
      tryClean() {
        while(this.dataLength > this.length) {
          const head = this.listHead;
          if (head == null) throw new Error('鏈表缺少頭部');
          const headNext = head.next;
          if (headNext == null) throw new Error('鏈表頭部缺失下一個節(jié)點');
          // 1. 斷絕head和headNext之間的關系
          delete head.next;
          delete headNext.pre;
          // 2. 重新賦值listHead
          this.listHead = headNext;
          // 3. 清理data
          delete this.data[head.key];
          // 4. 重新計數(shù)
          this.dataLength = this.dataLength - 1;
        }
      }
    }

這么一看，雙向鏈表是這三種方式中最復雜的一個。我們使用同樣的案例測試一下：

const lruCache = new LRUCacheLinked(2);
lruCache.set('1', 1);
lruCache.set('2',2);
console.log(lruCache.get('1'));
lruCache.set('3',3);
console.log(lruCache.get('2'));
lruCache.set('4',4);
console.log(lruCache.get('1'));
console.log(lruCache.get('3'));
console.log(lruCache.get('4'));

實現(xiàn)結果：