为什么不用 MemoryCache
直接上手写 LRU/LFU？
MemoryCache是 .NET 内置的线程安全缓存，支持过期策略和内存压力回收，但它不暴露访问频次或访问顺序的底层控制点，也无法定制驱逐逻辑（比如严格按 LFU 计数淘汰，或带权重的 LRU）。当你需要：精确控制淘汰行为、避免 GC 压力（如高频小对象）、做缓存命中率热力分析、或嵌入到低延迟服务中时，就得自己实现。
用 LinkedList<t></t>
+ Dictionary<k linkedlistnode>></k>
实现 O(1) LRU
核心是把“最近使用”映射为链表头，“最久未用”固定在尾。每次
Get就把对应节点移到头；
Set时若已存在就更新值并移至头，否则新建节点插入头，超容则删尾节点。
关键陷阱：
LinkedListNode<t></t>持有对
T的引用，但
Dictionary的 value 是节点本身 —— 别误存值或键，否则无法 O(1) 定位 多线程下必须加锁，
ConcurrentDictionary不能直接替代
Dictionary，因为你要原子地「查字典 + 移动节点」，得用
lock或
ReaderWriterLockSlim不要在
LinkedList上反复调用
Find—— 那是 O(N)，彻底毁掉设计初衷
public class LRUCache<K, V>
{
private readonly int _capacity;
private readonly Dictionary<K, LinkedListNode<(K, V)>> _map;
private readonly LinkedList<(K, V)> _list;
public LRUCache(int capacity)
{
_capacity = capacity;
_map = new Dictionary<K, LinkedListNode<(K, V)>>();
_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<k int freq datetime lastused></k>+ 线性扫描找 min freq → O(N)，不可接受。
标准解法是双哈希结构：
Dictionary<k value int freq linkedlistnode> node)></k>：存值、频次、以及它在频次链表中的位置
Dictionary<int linkedlist>></int>：按频次分组，每个频次对应一个 LRU 链表（用于同频次下淘汰最久未用者） 维护一个全局
minFreq，每次淘汰只看
_freqLists[minFreq].First
每次
Get：从原频次链表删节点 → 加入
freq+1链表 → 更新
minFreq（如果原链表空了且等于
minFreq，则
minFreq++）
注意：
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<telement tpriority></telement>不适合这里 —— 它不支持 O(1) 修改优先级，每次更新频次都要重新入队，退化成 O(log N)。
