LFU缓存算法详解（C#语言实现最近最少使用频率缓存机制）

什么是 LFU 缓存算法？

LFU（Least Frequently Used）缓存算法的核心思想是：当缓存满时，优先淘汰那些被访问频率最低的数据项。与 LRU（Least Recently Used）不同，LFU 更关注“使用频率”而非“最近使用时间”。

举个例子：如果一个数据在过去被访问了 10 次，而另一个只被访问了 1 次，那么后者更可能被淘汰。

为什么选择 C# 实现 LFU？

C# 是 .NET 平台的主力语言，广泛用于企业级应用开发。掌握 .NET缓存机制 和自定义缓存策略（如 LFU）对提升系统响应速度和资源利用率至关重要。通过本教程，你不仅能理解 LFU 原理，还能将其集成到实际项目中。

LFU 缓存的设计思路

要高效实现 LFU，我们需要两个关键数据结构：

• 哈希表（Dictionary）：用于 O(1) 时间内查找键对应的值和频率。
• 频率桶（按频率分组的链表）：每个频率对应一个双向链表，存储该频率下的所有键。

此外，我们还需要记录当前最小频率，以便快速找到待淘汰的元素。

C# 实现 LFU 缓存

下面是一个完整的 LFU 缓存类实现：

using System;using System.Collections.Generic;public class LFUCache{    private readonly int capacity;    private int minFreq;    private Dictionary<int, (int value, int freq)> cache;    private Dictionary<int, LinkedList<int>> freqMap;    private Dictionary<int, LinkedListNode<int>> nodeMap;    public LFUCache(int capacity)    {        this.capacity = capacity;        this.minFreq = 0;        this.cache = new Dictionary<int, (int, int)>();        this.freqMap = new Dictionary<int, LinkedList<int>>();        this.nodeMap = new Dictionary<int, LinkedListNode<int>>();    }    public int Get(int key)    {        if (!cache.ContainsKey(key))            return -1;        var (value, freq) = cache[key];        UpdateFrequency(key, freq);        return value;    }    public void Put(int key, int value)    {        if (capacity == 0) return;        if (cache.ContainsKey(key))        {            cache[key] = (value, cache[key].freq);            UpdateFrequency(key, cache[key].freq);        }        else        {            if (cache.Count >= capacity)            {                // 淘汰频率最低且最久未用的元素                var evictList = freqMap[minFreq];                var evictKey = evictList.First.Value;                evictList.RemoveFirst();                cache.Remove(evictKey);                nodeMap.Remove(evictKey);                if (evictList.Count == 0)                    freqMap.Remove(minFreq);            }            cache[key] = (value, 1);            minFreq = 1;            if (!freqMap.ContainsKey(1))                freqMap[1] = new LinkedList<int>();            var newNode = new LinkedListNode<int>(key);            freqMap[1].AddLast(newNode);            nodeMap[key] = newNode;        }    }    private void UpdateFrequency(int key, int oldFreq)    {        // 从旧频率列表中移除        var list = freqMap[oldFreq];        list.Remove(nodeMap[key]);        if (list.Count == 0)        {            freqMap.Remove(oldFreq);            if (minFreq == oldFreq)                minFreq++;        }        // 加入新频率列表        int newFreq = oldFreq + 1;        if (!freqMap.ContainsKey(newFreq))            freqMap[newFreq] = new LinkedList<int>();        var newNode = new LinkedListNode<int>(key);        freqMap[newFreq].AddLast(newNode);        nodeMap[key] = newNode;        cache[key] = (cache[key].value, newFreq);    }}

代码说明

• cache：存储键、值和当前频率。
• freqMap：频率 → 双向链表（存储该频率下的所有 key）。
• nodeMap：快速定位 key 在链表中的节点，便于 O(1) 删除。
• UpdateFrequency：每次访问后更新频率，并维护最小频率 minFreq。

使用示例

class Program{    static void Main()    {        LFUCache cache = new LFUCache(2);        cache.Put(1, 1);        cache.Put(2, 2);        Console.WriteLine(cache.Get(1)); // 输出: 1        cache.Put(3, 3); // 淘汰 key=2（频率为1，且比 key=1 更早）        Console.WriteLine(cache.Get(2)); // 输出: -1（已淘汰）        Console.WriteLine(cache.Get(3)); // 输出: 3        cache.Put(4, 4); // 淘汰 key=1        Console.WriteLine(cache.Get(1)); // 输出: -1        Console.WriteLine(cache.Get(3)); // 输出: 3        Console.WriteLine(cache.Get(4)); // 输出: 4    }}

总结

通过本教程，你已经掌握了 LFU缓存算法 的核心原理，并成功用 C#缓存实现 了一个高效的 LFU 缓存类。这种 最近最少使用频率缓存 策略特别适用于访问模式具有明显“热点数据”的场景。

在实际项目中，你可以基于此扩展支持线程安全、过期时间等功能，进一步完善你的 .NET缓存机制。

希望这篇教程对你有所帮助！如果你有任何问题，欢迎在评论区留言交流。