在 C# 中实现 LRU 缓存

一. 介绍

LRU（Least Recently Used，最近最少使用）缓存是一种用于存储有限数量项目的数据结构。当缓存达到其容量时，最少使用的项目将首先被移除。本文将讲解如何在C#中使用字典和双向链表来实现一个高效的LRU缓存。

二. 实现细节

在C#中，LRU缓存类可以通过字典和双向链表的组合来实现。字典提供O(1)时间复杂度的查询和更新操作，而双向链表则用于维护缓存项目的使用顺序。

1. 手动双向链表实现

手动双向链表通过显式管理每个节点的前后指针来实现LRU缓存。当缓存中的某个项目被访问或更新时，节点会被移动到链表的尾部，表示最近使用。最少使用的节点则位于链表的头部，当缓存超出容量时，该节点会被移除。

2. 代码实现

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; // 如果没找到，返回-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; // 初始化值
    }
}

3. 代码解释

• LRUCache 类定义了缓存的容量、使用字典和双向链表来管理缓存项目的使用顺序。
• MoveToTail 方法用于将一个节点移动到链表的尾部，表示最近使用。
• RemoveNode 方法用于从链表中移除节点。
• AddToTail 方法用于将节点添加到链表的尾部。
• Get 方法用于从缓存中获取值，如果存在则将节点移动到尾部。
• Put 方法用于向缓存中添加或更新值，当缓存满时移除最少使用的项。

4. 效率与适用场景

此实现中的Get和Put方法均为O(1)时间复杂度，非常适合需要高性能的应用场景，例如在Web缓存系统中，LRU缓存可以减少服务器的压力，提升数据访问的速度。

三. 使用示例

LRUCache cache = new LRUCache(2); // 创建一个容量为2的LRU缓存

cache.Put(1, 1); // 缓存中添加键值对(1, 1)
cache.Put(2, 2); // 缓存中添加键值对(2, 2)
Console.WriteLine("Get key 1: " + cache.Get(1)); // 返回1，缓存状态更新为：(2,2), (1,1)
cache.Put(3, 3); // 添加(3, 3)，缓存达到容量，移除最少使用的键2
Console.WriteLine("Get key 2: " + cache.Get(2)); // 返回-1，键2已被移除
cache.Put(4, 4); // 添加(4, 4)，移除最少使用的键1
Console.WriteLine("Get key 1: " + cache.Get(1)); // 返回-1，键1已被移除
Console.WriteLine("Get key 3: " + cache.Get(3)); // 返回3
Console.WriteLine("Get key 4: " + cache.Get(4)); // 返回4

4. 输出

Get key 1: 1
Get key 2: -1
Get key 1: -1
Get key 3: 3
Get key 4: 4

四. 结论

通过本文的讲解，我们成功在C#中实现了一个基于字典和双向链表的LRU缓存。此实现的Get和Put操作均为O(1)时间复杂度，适用于需要高效管理缓存的场景。