JavaScript怎么實現LRU算法

今天小編給大家分享一下JavaScript怎么實現LRU算法的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

LRU簡介

least Recently Used 最近最少使用，用于操作系統內存管理，在前端開發中常用于優化頁面性能和資源利用率。

直接翻譯就是“最不經常使用的數據，重要性是最低的，應該優先刪除”

以下是在前端中使用LRU算法的幾個應用場景：

前端路由：在單頁應用（SPA）中，通過將路由信息保存在緩存中，可以避免每次訪問頁面時都需要重新加載數據，從而提高頁面響應速度和用戶體驗。

圖片懶加載：對于大型圖片庫，可以使用LRU算法對已加載的圖片進行緩存，當一個新圖片需要被加載時，可以先檢查該圖片是否已經在緩存中存在，如果存在則直接從緩存中獲取，否則從服務器加載。

數據緩存：對于需要頻繁讀取的數據或者需要復雜計算才能得出結果的數據，可以使用LRU算法對其進行緩存，以減少重復計算的時間。

字體應用：對于網站上使用的字體文件，可以使用LRU算法將最常用的字體文件存儲在緩存中，從而加快頁面渲染速度和節省網絡流量。

總之，LRU算法可用于提升前端應用的性能和用戶體驗，但需要根據具體的應用場景選擇合適的算法并進行合理的配置。

如何實現

那么如何實現一個LRU 算法呢？我們一起看看leetcode 146這道題目

設計一個LRU類，實現get put 方法

題目簡單描述：

請你設計并實現一個滿足 LRU (最近最少使用) 緩存 約束的數據結構。

實現 LRUCache 類：

• LRUCache(int capacity) 以 正整數 作為容量 capacity 初始化 LRU 緩存

• int get(int key) 如果關鍵字 key 存在于緩存中，則返回關鍵字的值，否則返回 -1 。

• void put(int key, int value) 如果關鍵字 key 已經存在，則變更其數據值 value ；如果不存在，則向緩存中插入該組 key-value 。如果插入操作導致關鍵字數量超過 capacity ，則應該 逐出 最久未使用的關鍵字。

實現思路

我們使用一個map 來緩存數據。

當獲取數據key 時，優先判斷是否存在于map，如果在我們先拿到這個值存為temp，然后從map中刪除，重新set進map中

當插入數據時，優先判斷是否存在于map，如果不存在，直接set，如果存在，刪除后哦嗎，重新set

這樣我們保證最近使用的都在map 的最下層，當內存超出時，直接刪除map 頂層元素即可

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

var LRUCache = function(capacity) {
	this.capacity = capacity
  this.map = new Map()
}

LRUCache.prototype.get = function(key) {
  if(this.map.has(key)) {
    let temp = this.map.get(key)
    this.map.delete(key)
    this.map.set(key,temp)
    return temp
  } else {
    return -1
  }

}
LRUCache.prototype.put = function(key, value) {
	if(this.map.has(key)) {
    this.map.delete(key)
  }
  this.map.set(key,value)
  if(this.map.size > this.capacity) {
    this.map.delete(this.map.keys().next().value)
  }
}

缺陷

雖然該實現使用了 Map 對象，但是在最壞情況下，如果哈希函數分布不均勻，可能會導致哈希沖突，使得某些操作的時間復雜度變為 O(n)。因此，在實際應用中，如果需要高效地處理大規模數據，建議使用雙向鏈表或其他更高效的數據結構。

假設有一個哈希表，大小為 5，使用的哈希函數為 key % 5。現在插入以下 6 個鍵值對：

{key: 1, value: 'a'}
{key: 2, value: 'b'}
{key: 3, value: 'c'}
{key: 4, value: 'd'}
{key: 6, value: 'e'}
{key: 11, value: 'f'}

根據給定的哈希函數 key % 5，可以將每個鍵映射到哈希表中的一個桶。具體來說，將鍵除以 5 并取余數，以得到它應該插入的桶的索引。

使用這個哈希函數，將上述六個鍵值對插入哈希表中，得到以下結果：

在索引 1 的桶中插入 {key: 1, value: 'a'}

在索引 2 的桶中插入 {key: 2, value: 'b'}

'在索引 3 的桶中插入 {key: 3, value: 'c'}

在索引 4 的桶中插入 {key: 4, value: 'd'}

在索引 1 的桶中插入 {key: 6, value: 'e'}

在索引 1 的桶中插入 {key: 11, value: 'f'}

注意，在將鍵為 6 和 11 的鍵值對插入哈希表時，它們都被映射到索引 1 的桶中。這是因為它們分別與 1 余數相同。

當出現哈希沖突時，即多個鍵被映射到同一桶時

這種情況下，在操作時需要遍歷整個桶來查找指定的鍵值對，因此操作的時間復雜度變為 O(n)。

雙向鏈表+哈希表

那么如何達到O(1)的時間復雜度呢？

那肯定選用 map 查詢。修改，刪除也要盡量 O(1) 完成。搜尋常見的數據結構，鏈表，棧，隊列，樹，圖。樹和圖排除，棧和隊列無法任意查詢中間的元素，也排除。所以選用鏈表來實現。但是如果選用單鏈表，刪除這個結點，需要 O(n) 遍歷一遍找到前驅結點。所以選用雙向鏈表，在刪除的時候也能 O(1) 完成。

核心就是：最近最多使用的節點永遠在鏈表結尾，最近最少使用的節點在鏈表開頭。

雙向鏈表

雙向鏈表的結構

value: 存儲的值

prev: 指向前一個元素的指針

next: 指向下一個元素的指針

Head和Tail是虛擬的頭部和尾部節點，這是為了方便找到鏈表的首末設定的

       ┌──────>┐    ┌───────>┐   ┌───────>┐
  head • (x|"three"|•)  (•|"two"|•)  (•|"one"|x) • tail
               └<────────┘   └<───────┘   └<─────┘

實現思路

1.使用一個Map 對象來存儲鍵值對

2.使用一個雙向鏈表維護鍵值對的順序

3.抽離出一個addToTaill 方法（將節點插入末尾）抽離出一個remove 方法（刪除節點）

4.當執行put 操作時，判斷節點是否在map中

• 如果存在，獲取當前節點值，在雙向鏈表中remove刪除改節點，重新調用 addToTail 添加到末尾

• 如果不存在，建立一個雙向鏈表節點，調用 addToTail 添加到末尾，同時添加進map

• 如果超過容量this.size > this.cap，刪除當前head節點，從map中刪除當前key

5.當執行get 操作時，判斷節點是否在map中

• 如果不存在，返回-1

• 如果存在，獲取當前key,value，重新執行put 操作

class ListNode {
  constructor(key, value) {
    this.key = key;
    this.val = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity = 10) {
    this.capacity = capacity;
    // 實際保存的鍵值對數量
    this.size = 0;
    this.map = {};
    //代表最舊的節點
    this.head = null;
    //代表最新的節點
    this.tail = null;
  }

  get(key) {
    const node = this.map.get(key);
    if (!node) return -1;
    let node = this.map[key];
    this.put(node.key, node.val);
    return node.value;
  }

  put(key, value) {
    if(this.map[key]) {
    	let node = this.map[key]
      node.val = value
      this.remove(node)
      this.addTotail(node)
    } else {
      let node = new ListNode(key,value)
      this.addTotail(node)
      this.map[key] = node
      this.size++
    }
    if (this.size > this.cap) {
      let key = this.head.key;
      this.remove(this.head);
      delete this.map[key];
      this.size--;
    }
  }
  addToTail(node) {
    if(this.tail) {
      this.tail.next = node
      node.prev = this.tail
      this.tail = node
    } else {
      this.tail = node
      this.head = node
    }
  }
  remove(node) {
    if(node.prev) {
      node.prev.next = node.next
    } else {
      this.head = this.head.next
    }
    if(node.next) {
      node.next.prev = node.prev
    } else {
      this.tail = this.tail.prev
    }
    node.prev = node.next = null;
  }
}

以上就是“JavaScript怎么實現LRU算法”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。