在C#中實現LRU緩存，你學會了嗎？
作者：Rajiv Singh
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開發跳槽
