在C#中實現LRU緩存，你學會了嗎？

作者：Rajiv Singh 2024-10-16 11:28:42

開發前端

LRUCache?類通過結合字典和雙向鏈表高效管理固定大小的緩存，實現了Get和Put操作的O(1)時間復雜度，適用于高性能應用程序。

引言

LRU（比較少用）緩存是一種數據結構，它存儲有限數量的項目，并在緩存達到容量限制時優先移除最近最少使用的項目。本文介紹了如何在C#中使用字典和雙向鏈表相結合實現LRU緩存。

實現細節

LRUCache類使用字典來實現Get和Put操作的O(1)時間復雜度，并使用雙向鏈表來維護緩存項的使用順序。

以下是實現LRU緩存的兩種方法：

手動雙向鏈表

在LRU緩存中，手動雙向鏈表用于維護緩存項的使用順序。當通過Get方法訪問某個項目或通過Put方法添加/更新項目時，該項目會被移動到鏈表的末尾。這確保了最近使用的項目始終位于鏈表末尾，最近最少使用的項目位于鏈表開頭，當需要移除項目時，首先移除這些項目。

public class LRUCache
{
    int Capacity;
    IDictionary<int, LRUNode> keyValuePairs;
    LRUNode head;
    LRUNode tail;

    public LRUCache(int capacity)
    {
        Capacity = capacity;
        keyValuePairs = new Dictionary<int, LRUNode>();
        head = new LRUNode(0, 0);
        tail = new LRUNode(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    private void MoveToTail(LRUNode node)
    {
        RemoveNode(node);
        AddToTail(node);
    }

    private void RemoveNode(LRUNode node)
    {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

    private void AddToTail(LRUNode node)
    {
        node.next = tail;
        node.prev = tail.prev;
        tail.prev.next = node;
        tail.prev = node;
    }

    public int Get(int key)
    {
        if (keyValuePairs.TryGetValue(key, out LRUNode node))
        {
            MoveToTail(node);
            return node.value;
        }
        return -1;
    }

    public void Put(int key, int value)
    {
        if (!keyValuePairs.TryGetValue(key, out LRUNode node))
        {
            if (keyValuePairs.Count == Capacity)
            {
                LRUNode lru = head.next;
                RemoveNode(lru);
                keyValuePairs.Remove(lru.key);
            }
            LRUNode newNode = new LRUNode(key, value);
            keyValuePairs[key] = newNode;
            AddToTail(newNode);
        }
        else
        {
            node.value = value;
            MoveToTail(node);
        }
    }
}

public class LRUNode
{
    public int key;
    public int value;
    public LRUNode prev;
    public LRUNode next;

    public LRUNode(int key, int value)
    {
        this.key = key;
        this.value = value;
    }
}

手動雙向鏈表是實現LRU緩存的一種強大技術，它提供了高效、可控的緩存項管理。通過手動處理節點及其連接，此方法可確保緩存操作的最佳性能，適用于需要緩存的高性能應用程序。

C#中的內置鏈表

LRUCacheDLL類使用字典和內置的雙向鏈表來實現LRU緩存。這種方法確保Get和Put操作的時間復雜度為O(1)。

類成員

capacity：定義緩存最多能存儲的項目數量。
keyValuePairs：一個字典，將鍵映射到鏈表中的對應節點，允許O(1)時間復雜度的節點訪問。
dll：一個雙向鏈表，維護緩存項的使用順序。最近使用的項目位于鏈表末尾，最近最少使用的項目位于鏈表開頭。

構造函數

public LRUCacheDLL(int capacity)
{
    this.capacity = capacity;
    keyValuePairs = new Dictionary<int, LinkedListNode<(int key, int value)>>();
    dll = new LinkedList<(int key, int value)>();
}

Get方法

public int Get(int key)
{
    if (keyValuePairs.TryGetValue(key, out LinkedListNode<(int key, int value)> node))
    {
        dll.Remove(node);
        dll.AddLast(node);
        return node.Value.value;
    }
    return -1;
}

Put方法

public void Put(int key, int value)
{
    if (keyValuePairs.TryGetValue(key, out LinkedListNode<(int key, int value)> node))
    {
        dll.Remove(node);
        node.Value = (key, value);
        dll.AddLast(node);
    }
    else
    {
        if (keyValuePairs.Count == capacity)
        {
            keyValuePairs.Remove(dll.First.Value.key);
            dll.RemoveFirst();
        }
        keyValuePairs[key] = dll.AddLast((key, value));
    }
}

LRUCacheDLL類通過結合字典和雙向鏈表高效管理固定大小的緩存。這種實現確保Get和Put操作的時間復雜度為O(1)，非常適合高性能應用。

時間復雜度

Get操作：O(1)
Put操作：O(1)

空間復雜度

O(n)，其中n是緩存的容量。

使用示例

LRUCache cache = new LRUCache(2);

cache.Put(1, 1);
cache.Put(2, 2);
Console.WriteLine("Get key 1: " + cache.Get(1));
cache.Put(3, 3);
Console.WriteLine("Get key 2: " + cache.Get(2));
cache.Put(4, 4);
Console.WriteLine("Get key 1: " + cache.Get(1));
Console.WriteLine("Get key 3: " + cache.Get(3));
Console.WriteLine("Get key 4: " + cache.Get(4));

輸出

圖片

在此示例中，緩存初始化為容量2，存儲鍵值對，并在超過容量時移除最近最少使用的項目。

結語

LRUCache類通過結合字典和雙向鏈表高效管理固定大小的緩存，實現了Get和Put操作的O(1)時間復雜度，適用于高性能應用程序。

譯文地址：c-sharpcorner.com/article/implementing-an-lru-cache-in-c-sharp/

作者：Rajiv Singh

責任編輯：武曉燕來源： DotNet開發跳槽

LRUCache 緩存 Put