日期：2026年 01月 17日

標籤： Algorithm Cache Algorithm C# Asp.NET Core

摘要：演算法-快取策略

第一部分：LFU演算法 - 介紹

Step 1：簡介

以下截取於Wiki

Least frequently used (LFU)
The LFU algorithm counts how often an item is needed; those used less often are discarded first. This is similar to LRU, 
except that how many times a block was accessed is stored instead of how recently. 
While running an access sequence, the block which was used the fewest times will be removed from the cache.

簡言之：「使用的頻率最少的會被先淘汰」，最近常被用到的物件權重會持續提高，用此演算法通常適合應用需要長期熱點資料，例如 CDN、DNS 快取
※來源：Wiki

Step 2：優缺點 TODO

優點具有以下：

1. 保留 最常被使用的資料	Frequency 累積能讓真正熱門的 key 長期保留，不會因短期不用而被淘汰。
2. O(1) 高效操作	使用 HashMap + freq-list（多組 LinkedList）可達到 O(1) 操作效率。
3. 適用於熱門資料明確的業務場景	如熱門文章、熱門商品、常用配置參數、熱鍵搜尋結果。
4. 能適應長期穩定熱點資料	越常被存取，留存時間越久，能有效提高快取命中率。

缺點：

1. 實作複雜度較高	難度比 LRU 更高，且必須維護 頻率 → list 結構，並追蹤 key 的頻率。
2. 容易造成老資料霸佔快取	高頻資料可能永久佔位，除非加入「頻率衰減（decay）」機制。
3. 對瞬時爆量變動不敏感	短期熱門的資料可能因 頻率 累積不足而被誤刪。
4. 額外的記憶體與維護成本	多組 LinkedList 會消耗額外空間與運算資源。

Step 3：應用場景說明 TODO

以下列舉生活常見的 LFU Cache 應用，以及補充何種狀況下不合適採用

場景	適合 LFU 的原因	不適用情況	實際生活例子
1. 熱門內容長期固定	頻率能準確累積熱門項目並保留	熱門項目短時間內頻繁變動	熱門文章排行榜、熱門搜尋建議
2. 使用者行為長期穩定	能反映使用者長期偏好	需求依據瞬時行為判斷較多	像手機輸入法常用表情、常用詞彙
3. 熱點資料需要長期保留	長期熱門內容不會被淘汰	近期資料比累積資料重要	網站首頁最熱賣商品
4. 預估長期命中率	高頻資料長駐提升命中	老資料高頻率永久高優先權	YouTube 自動在快取中保留長期高點閱影片
5. 適合資料不會短期爆量干擾	可防止短期爆量資料污染	遇批次大量讀取，cache 被洗掉	避免一次性備份掃描佔用 cache
6. 頻率具代表性	高次數存取即高價值	資料生命週期短、無頻率意義	使用者常用設定（例如語言偏好）
7. 適合冷資料自然淡出	頻率 直接代表資料重要性	只需要記錄近期使用時間	AI 提供個人化常用推薦內容

第二部分：LFU演算法 - 實現

Step 1：完整代碼

完整代碼可以從Source Code下載，此代碼對應於 LeetCode 的 460 題，LFU Cache

主要以下 3 個部分完成，整理複雜度 + 完整代碼框架如下：
※關鍵作法 : (快取主表)Dictionary + (頻率表)LinkedList + (紀錄所有LinkListNode表)LinkedListNode 處理
※透過 LinkedList<int, LinkedList>() => (Key : 頻率) 的方式來實現 Get、Put 達到 O(1) 的效能

1. 快取策略容量上限	空間複雜度 O(n)	LFU 需要 HashMap 紀錄資料，持有 n 項資料，所以空間 O(n)
2. 取值的處理	時間複雜度 O(1)	HashMap 取得節點 = O(1)，再更新頻率表鏈結位置 = O(1)
3. 存值的處理	時間複雜度 O(1)	因為有了頻率表輔助實現 LRU ，因此查找、插入/更新、鏈表調整在 LFU 的處理全部都是 O(1)

public class LFUCache
{
    private readonly int _capacity;// 設定快取空間上限
    private int _minFreq;// 當前最小頻率值，為了快速查找
    private readonly Dictionary<int, Node> _cache;// 主表：查找 key 對應的節點資訊
    private readonly Dictionary<int, LinkedList<int>> _freqCache;// 頻率鏈表：每個頻率對應一個 LinkedList，存儲該頻率的所有 key
    private readonly Dictionary<int, LinkedListNode<int>> _AllNodeCache;// 所有節點表：快速定位 key 在其頻率鏈表中的節點位置 ※ LFU 能 Get/Put O(1)的關鍵

    /// <summary>
    /// 1. 建構式 - 快取策略容量上限
    /// </summary>
    public LFUCache(int capacity)
    {
    }

    /// <summary>
    /// 2. 取值的處理
    /// </summary>
    public int Get(int key)
    {
    }

    /// <summary>
    /// 3. 存值的處理
    /// </summary>
    public void Put(int key, int value)
    {
    }
}

Step 2：1. 快取策略容量上限

LFU 使用時，需要決定可保存快取的上限，結合 LeetCode 以建構式的方式賦值
與 LRU 不同的是增加了最小頻率的紀錄 _minFreq，應用於刪除頻率最差的物件時，可以達到 O(1)

/// <summary>
/// 1. 建構式 - 快取策略容量上限
/// </summary>
public LFUCache(int capacity)
{
    _capacity = capacity;
    _minFreq = 0;
    _cache = new Dictionary<int, Node>();
    _freqCache = new Dictionary<int, LinkedList<int>>();
    _AllNodeCache = new Dictionary<int, LinkedListNode<int>>();
}

Step 3：2. 取值的處理

取值的處理，每當被檢索到時，將權重提升

/// <summary>
/// 1. 查詢鍵 並獲得 值
/// </summary>
public int Get(int key)
{
    // 1-1. 無對應資料，依照需求返回 -1
    if (!_cache.ContainsKey(key))
        return -1;
    
    var node = _cache[key];
    UpdateFrequency(key, node);
    return node.Value;
}

Step 4：3. 頻率的更新 & 如何提升權重

依序將舊的頻率從頻率表、節點表移除，並放入到更新的頻率中

/// <summary>
/// 3. 更新頻率
/// </summary>            
private void UpdateFrequency(int key, Node node)
{
    // 3-1. 新舊頻率
    int oldFreq = node.Frequency;
    int newFreq = oldFreq + 1;

    // 3-2. 從舊頻率的鏈表中移除
    var listNode = _AllNodeCache[key];
    _freqCache[oldFreq].Remove(listNode);

    // 3-3. 如果舊頻率的鏈表空了，並且是最小頻率，那麼必須直接刷新最小頻率
    if (_freqCache[oldFreq].Count == 0)
    {
        _freqCache.Remove(oldFreq);
        if (_minFreq == oldFreq)
            _minFreq = newFreq;
    }

    // 3-4. 加入新頻率到鏈表中
    node.Frequency = newFreq;

    // 3-5. 首次加入，要給此 [頻率] 初始化
    if (!_freqCache.ContainsKey(newFreq))
        _freqCache[newFreq] = new LinkedList<int>();

    // 3-6. LRU 原則，最近使用的在相同頻率下優先級最高 (放在最前面)
    var newListNode = _freqCache[newFreq].AddFirst(key);
    _AllNodeCache[key] = newListNode;
}

Step 5：4. 存值的處理

存值的處理，當存入時，有 2 個方向，共 3 種情況

是否已存在	是否達到設定上限	處理方式
存在		更新 Key 的 Value 值 並且呼叫 UpdateFrequency() 刷新頻率
不存在	是	移除最舊的資料
不存在	否	新增 Key 的 Value 值 並且 呼叫 UpdateFrequency() 刷新頻率

/// <summary>
/// 2. 設定鍵、值
/// </summary>            
public void Put(int key, int value)
{
    // 2-1. 無空間直接釋放
    if (_capacity == 0) 
        return;

    // 2-2. 設定值時，若已存在 Key 的情況，增加頻率值
    if (_cache.ContainsKey(key))
    {
        // 2-3-1. 一定要刷新 Key , Value 因為相同的Key有可能不同的 Value
        var node = _cache[key];
        node.Value = value;

        // 2-3-2. 增加此 Key 的頻率
        UpdateFrequency(key, node);
    }
    else
    {
        // 2-4-1. 如果當前的 Key 已經達到上限，那要進行 LFU 頻率最差的移除
        if (_cache.Count >= _capacity)
        {
            RemoveLFU();
        }

        // 2-4-3. 為新的 Key 添加
        var newNode = new Node
        {
            Key = key,
            Value = value,
            Frequency = 1
        };
        _cache[key] = newNode;

        // 2-4-4. 檢查 1 的頻率表(最小頻率)是否有值
        if (!_freqCache.ContainsKey(1))// 2-4-5. 不存在要為 1 的頻率建 LinkedList
            _freqCache[1] = new LinkedList<int>();

        // 2-4-6. 新加入此頻率必定要設在此 LinkedList 的最優先，並且刷新頻率
        var listNode = _freqCache[1].AddFirst(key);
        _AllNodeCache[key] = listNode;
        _minFreq = 1;
    }

    // 2-4-2. 從最小頻率的鏈表頭部移除（最久未使用）
    void RemoveLFU()
    {                    
        var keysWithMinFreq = _freqCache[_minFreq];
        var keyToRemove = keysWithMinFreq.Last.Value;

        // 2-4-2-1. 刪除 Cache
        _cache.Remove(keyToRemove);

        // 2-4-2.2. 刪除 LinkList 
        keysWithMinFreq.RemoveLast();
        if (keysWithMinFreq.Count == 0)
            _freqCache.Remove(_minFreq);

        // 2-4-2.2. 刪除 LinkListNode 
        _AllNodeCache.Remove(keyToRemove);
    }
} 

Step 6：LeetCode - 成功執行結果

附上此代碼確實可在 LeetCode 上執行 C# 版本

Runtime 範圍	42 ms ~ 91 ms
Runtime Best Beat	67.10%
Memory 範圍	178.90 MB ~ 187.79 MB
Memory Best Beat	95.48%

第三部分：LFU演算法 - 圖解流程

Step 1：初始設定上限

我們設定了最大上限為 2 ，尚未塞入任何資料，初始結構如下：
為了便於說明，LeetCode 用的 Key 是整數，說明用的 Key 為 String，用於區分最小頻率 & Key 的差異

Step 2：新增值 SET - (A, 10)

添加值 KEY = A ; Value = 10，以下是 3 個資料結構的變化

主表	增加 Key : A 與 物件
頻率表	Key : 1 (最小頻率為 1)，內部節點當前只有 A
節點表	當前節點只有 A

Step 3：新增值 SET - (B, 10)

添加值 KEY = B ; Value = 10

主表	增加 Key : B 與 物件
頻率表	Key : 1 (最小頻率仍為 1)，內部節點當前多了 B，並且 LRU 的規則，在 LinkedList 中 B 優先於 A
節點表	當前節點增加 B ，因為頻率相同， A 與 B 節點有前後關係(Pre / Next)

Step 4：取得值 GET - A

查詢 KEY = A ; 因為有存在此 Key 所以得到 10 的值，並且更新權重

主表	未變化
頻率表	Key = A 頻率變為 2 ，要與原本頻率 1 分離，當前最小頻率仍為 1 (裡面只有 Key = B )
節點表	因為 A 節點頻率為 2 與 B 的節點頻率 1 不同，因此解除前後關係(Pre / Next)

Step 6：新增值 SET - (C, 10) - 先刪除

添加值 KEY = C ; Value = 10，但我們要先進行刪除動作，因為最大只能保存 2，放入 Key = C 會超過上限，需移除頻率最小的節點

主表	未變化
頻率表	最小頻率仍為 1，並且裡面的節點只有 B ，因此整個頻率 1 LinkedList 移除
節點表	移除節點 B ，在頻率表中被檢索到

Step 7：新增值 SET - (C, 10)

添加值 KEY = C ; Value = 10

主表	增加 Key : C 與 物件
頻率表	增加了 C 物件，第一次新增必為最小頻率 1 ，因為頻率 1 是空的，於是建立 LinkedList Key : 1 ，內部節點只有 C
節點表	當前節點增加 C

Step 8：取得值 GET - C

查詢 KEY = C ; 因為有存在此 Key 所以得到 10 的值，並且更新權重

主表	未變化
頻率表	Key = C 頻率變為 2 ，要與原本頻率 1 分離，因為 頻率1 沒有任何節點，因此當前最小頻率變為 2
節點表	因為 C 節點頻率為 2 與 A 的節點頻率 2 相同，因此建立了前後關係(Pre / Next)