在C#中实现LRU缓存

引言

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)时间复杂度，适用于高性能应用程序。

大家对LRU缓存有什么看法，欢迎留言讨论。

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

作者：Rajiv Singh