LeetCode中LRU 緩存機制的示例分析

LeetCode中LRU緩存機制的示例分析

引言

在計算機科學中，緩存是一種用于存儲臨時數據的技術，旨在提高數據訪問速度。LRU（Least Recently Used，最近最少使用）是一種常見的緩存淘汰策略，它根據數據的歷史訪問記錄來決定哪些數據應該被保留，哪些數據應該被淘汰。本文將詳細分析LeetCode中LRU緩存機制的實現，并通過示例代碼進行講解。

LRU緩存機制的基本概念

什么是LRU緩存？

LRU緩存是一種基于時間局部性原理的緩存策略。它假設最近被訪問過的數據在未來被再次訪問的概率較高，因此會優先保留這些數據。當緩存空間不足時，LRU緩存會淘汰最久未被訪問的數據。

LRU緩存的工作原理

LRU緩存通常使用一個哈希表和一個雙向鏈表來實現。哈希表用于快速查找緩存中的數據，而雙向鏈表用于維護數據的訪問順序。具體來說：

1. 哈希表：存儲鍵值對，鍵是數據的標識，值是對應鏈表節點的指針。
2. 雙向鏈表：鏈表中的每個節點存儲一個鍵值對，鏈表的頭部表示最近訪問的數據，尾部表示最久未被訪問的數據。

當訪問一個數據時，LRU緩存會執行以下操作：

1. 如果數據在緩存中（即哈希表中存在該鍵），則將對應的鏈表節點移動到鏈表頭部。
2. 如果數據不在緩存中，則將數據插入到鏈表頭部，并更新哈希表。如果緩存已滿，則淘汰鏈表尾部的數據。

LeetCode中的LRU緩存問題

LeetCode上有一道經典的LRU緩存問題，題目編號為146。題目要求實現一個LRU緩存類，支持以下操作：

• LRUCache(int capacity)：初始化緩存，capacity表示緩存的最大容量。
• int get(int key)：如果鍵key存在于緩存中，則返回對應的值，否則返回-1。
• void put(int key, int value)：如果鍵key已經存在，則更新其對應的值；如果鍵不存在，則插入鍵值對。當緩存達到容量時，應該淘汰最久未使用的鍵值對。

示例

輸入：
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

輸出：
[null, null, null, 1, null, -1, null, -1, 3, 4]

解釋：
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 緩存是 {1=1}
lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 該操作會使得鍵 2 作廢，緩存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會使得鍵 1 作廢，緩存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

LRU緩存的實現

數據結構選擇

為了實現LRU緩存，我們需要選擇合適的數據結構。如前所述，哈希表和雙向鏈表是常用的組合。

• 哈希表：用于快速查找鍵值對，時間復雜度為O(1)。
• 雙向鏈表：用于維護鍵值對的訪問順序，時間復雜度為O(1)。

代碼實現

以下是使用Python實現的LRU緩存類：

class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = {}
        self.capacity = capacity
        self.size = 0
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.move_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.move_to_head(node)
        else:
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self.add_to_head(node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.remove_tail()
                del self.cache[removed.key]
                self.size -= 1

    def add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def move_to_head(self, node):
        self.remove_node(node)
        self.add_to_head(node)

    def remove_tail(self):
        node = self.tail.prev
        self.remove_node(node)
        return node

代碼解析

1. DLinkedNode類：定義了雙向鏈表的節點結構，每個節點包含鍵、值、前驅指針和后繼指針。
2. LRUCache類：
   • __init__方法：初始化緩存，設置容量，創建哈希表和雙向鏈表的頭尾節點。
   • get方法：如果鍵存在于緩存中，則將對應的節點移動到鏈表頭部，并返回節點的值；否則返回-1。
   • put方法：如果鍵已經存在，則更新節點的值并將其移動到鏈表頭部；如果鍵不存在，則創建新節點并插入到鏈表頭部，同時更新哈希表。如果緩存已滿，則刪除鏈表尾部的節點，并從哈希表中移除對應的鍵。
   • add_to_head方法：將節點插入到鏈表頭部。
   • remove_node方法：從鏈表中移除指定節點。
   • move_to_head方法：將指定節點移動到鏈表頭部。
   • remove_tail方法：移除鏈表尾部的節點，并返回該節點。

示例分析

讓我們通過一個具體的示例來分析LRU緩存的執行過程。

示例輸入

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

執行過程

1. 初始化緩存：LRUCache(2)，緩存容量為2。
2. 插入鍵值對：put(1, 1)，緩存為{1=1}。
3. 插入鍵值對：put(2, 2)，緩存為{1=1, 2=2}。
4. 獲取鍵值：get(1)，返回1，并將鍵1移動到鏈表頭部，緩存為{2=2, 1=1}。
5. 插入鍵值對：put(3, 3)，緩存已滿，淘汰鍵2，緩存為{1=1, 3=3}。
6. 獲取鍵值：get(2)，返回-1，因為鍵2已被淘汰。
7. 插入鍵值對：put(4, 4)，緩存已滿，淘汰鍵1，緩存為{3=3, 4=4}。
8. 獲取鍵值：get(1)，返回-1，因為鍵1已被淘汰。
9. 獲取鍵值：get(3)，返回3，并將鍵3移動到鏈表頭部，緩存為{4=4, 3=3}。
10. 獲取鍵值：get(4)，返回4，并將鍵4移動到鏈表頭部，緩存為{3=3, 4=4}。

輸出結果

[null, null, null, 1, null, -1, null, -1, 3, 4]

總結

LRU緩存機制是一種高效的緩存淘汰策略，廣泛應用于各種系統中。通過哈希表和雙向鏈表的結合，我們可以實現一個時間復雜度為O(1)的LRU緩存。本文通過LeetCode中的LRU緩存問題，詳細分析了LRU緩存的實現過程，并通過示例代碼展示了其工作原理。希望本文能幫助讀者更好地理解LRU緩存機制，并在實際開發中靈活運用。