c# 如何用 C# 实现一个高性能的内存缓存（LRU, LFU）

MemoryCache 不支持自定义驱逐逻辑，无法实现精确的 LRU/LFU；需手动用 LinkedList+Dictionary 实现 O(1) 淘汰，注意线程安全与节点定位陷阱。

为什么不用 MemoryCache 直接上手写 LRU/LFU？

MemoryCache 是 .NET 内置的线程安全缓存，支持过期策略和内存压力回收，但它不暴露访问频次或访问顺序的底层控制点，也无法定制驱逐逻辑（比如严格按 LFU 计数淘汰，或带权重的 LRU）。当你需要：精确控制淘汰行为、避免 GC 压力（如高频小对象）、做缓存命中率热力分析、或嵌入到低延迟服务中时，就得自己实现。

用 LinkedList + Dictionary> 实现 O(1) LRU

核心是把“最近使用”映射为链表头，“最久未用”固定在尾。每次 Get 就把对应节点移到头；Set 时若已存在就更新值并移至头，否则新建节点插入头，超容则删尾节点。

关键陷阱：

• LinkedListNode 持有对 T 的引用，但 Dictionary 的 value 是节点本身 —— 别误存值或键，否则无法 O(1) 定位
• 多线程下必须加锁，ConcurrentDictionary 不能直接替代 Dictionary，因为你要原子地「查字典 + 移动节点」，得用 lock 或 ReaderWriterLockSlim
• 不要在 LinkedList 上反复调用 Find —— 那是 O(N)，彻底毁掉设计初衷

public class LRUCache
{
    private readonly int _capacity;
    private readonly Dictionary> _map;
    private readonly LinkedList<(K, V)> _list;

    public LRUCache(int capacity)
    {
        _capacity = capacity;
        _map = new Dictionary>();
        _list = new LinkedList<(K, V)>();
    }

    public V? Get(K key)
    {
        if (!_map.TryGetValue(key, out var node)) return default;
        _list.Remove(node);         // O(1)
        _list.AddFirst(node);       // O(1)
        return node.Value.Item2;
    }

    public void Put(K key, V value)
    {
        if (_map.TryGetValue(key, out var node))
        {
            node.Value = (key, value);
            _list.Remove(node);
            _list.AddFirst(node);
        }
        else
        {
            var newNode = _list.AddFirst((key, value));
            _map[key] = newNode;

            if (_map.Count > _capacity)
            {
                var last = _list.Last!;
                _list.RemoveLast();
                _map.Remove(last.Value.Item1);
            }
        }
    }
}

LFU 实现难点：如何 O(1) 更新频次并找到最小频次的候选键？

LFU 要求每个键记录访问次数，并在容量满时淘汰「访问次数最少且最久未用」的项。纯靠 Dictionary + 线性扫描找 min freq → O(N)，不可接受。

标准解法是双哈希结构：

• Dictionary node)>：存值、频次、以及它在频次链表中的位置
• Dictionary>：按频次分组，每个频次对应一个 LRU 链表（用于同频次下淘汰最久未用者）
• 维护一个全局 minFreq，每次淘汰只看 _freqLists[minFreq].First

每次 Get：从原频次链表删节点 → 加入 freq+1 链表 → 更新 minFreq（如果原链表空了且等于 minFreq，则 minFreq++）

腾讯混元文生视频

腾讯发布的AI视频生成大模型技术

下载

注意：minFreq 只增不减，且仅在 Put 新键时重置为 1；Get 不会重置 minFreq 为 1。

性能与取舍：什么时候该用 ConcurrentDictionary？

如果你的缓存读远多于写（比如 >95% 是 Get），且能接受「短暂不一致」（例如两个线程几乎同时 Get 同一 key，都触发回源加载），那么用 ConcurrentDictionary + 无锁 GetOrAdd 回源更轻量 —— 但这就不是严格 LRU/LFU 了。

真正需要强一致 LRU/LFU 的场景（如分布式 session 本地镜像、风控规则热加载），必须用细粒度锁或 ReaderWriterLockSlim，尤其注意 Put 中「删除尾节点 + 更新字典」必须原子。

另外：.NET 6+ 的 System.Collections.Generic.PriorityQueue 不适合这里 —— 它不支持 O(1) 修改优先级，每次更新频次都要重新入队，退化成 O(log N)。