引言

在計算機科學中，緩存是一種重要的技術，用于提高數據訪問速度和系統性能。然而，由于緩存空間有限，當緩存滿了之后，就需要一種智能的策略來決定哪些數據應該保留，哪些應該被淘汰。LFU（Least Frequently Used，最少使用）算法就是一種常見的緩存淘汰策略，它基于數據項的訪問頻率來進行優化管理。

LFU算法簡介

LFU算法的核心思想是優先淘汰那些訪問頻率最低的數據項。在緩存達到容量限制時，LFU算法會移除那些被訪問次數最少的緩存條目。如果多個條目的訪問次數相同，則根據它們最早被訪問的時間進行決策，優先刪除最早被訪問的條目。

LFU算法的工作原理

LFU算法通常需要兩種數據結構來實現：

哈希表：提供O(1)時間復雜度的數據訪問和插入。此時哈希表需要兩個，一個記錄key和當前節點的映射，一個記錄頻率和節點的映射
雙向鏈表：維護數據項的使用順序，最近使用的在頭部，最久未使用的在尾部。

數據訪問和插入的流程如下：

獲取數據（Get）：從緩存中獲取數據，如果數據存在（緩存命中），則更新數據使用的頻率，也就是頻率+1，同時要刪除當前節點之前對應的頻率映射；如果數據不存在（緩存未命中），返回 -1。
插入數據（Put）：將數據放入緩存，如果數據已經存在，則更新數據值并更新數據使用的頻率；如果數據不存在，則將數據插入放入緩存中，并將最低頻率設置為1。如果緩存已滿，首先需要移除緩存中的元素，然后再插入。

LFU算法的實現

import java.util.HashMap;public class LFUCache {static class Node{int key, value, freq = 1;Node prev, next;Node(int key, int value){this.key = key;this.value = value;}}// 鍵到節點的映射private HashMap<Integer, Node> keyToNode = new HashMap<>();// 頻率到虛擬頭節點的映射private HashMap<Integer, Node> freqToDummy = new HashMap<>();// 最小訪問頻率private int minFreq;// 容量private int capacity;public LFUCache(int capacity) {this.capacity = capacity;}private Node newList() {Node dummy = new Node(0, 0);dummy.prev = dummy;dummy.next = dummy;return dummy;}/*** 根據鍵獲取值。* 該方法首先嘗試從keyToNode映射中獲取給定鍵對應的節點。如果節點不存在，說明該鍵不存在于數據結構中，方法將返回-1。* 如果節點存在，則該方法會執行刪除操作（del）和頻率更改操作（changeFreq），然后再返回節點的值。* 這種設計可能是為了在獲取值的同時，根據獲取情況動態調整數據結構，例如實現一種基于頻率的緩存淘汰策略。** @param key 需要獲取值的鍵。* @return 鍵對應的值，如果鍵不存在，則返回-1。*/public int get(int key) {// 嘗試從映射中獲取給定鍵對應的節點。Node node = keyToNode.get(key);// 如果節點不存在，說明鍵不存在于數據結構中，返回-1。if(node == null) return -1;// 修改節點的頻率信息，changeFreq(node);// 返回節點的值。return node.value;}/*** 插入一個鍵值對到緩存中。* 如果鍵已經存在，則更新其值，并根據更新后的頻率進行調整。* 如果緩存已滿，則移除最低頻率的鍵值對，并插入新的鍵值對。** @param key 插入或更新的鍵。* @param value 插入或更新的值。*/public void put(int key, int value) {// 嘗試從映射中獲取現有的節點Node node = keyToNode.get(key);if(node != null){// 如果節點存在，更新其值，并準備進行頻率更新操作node.value = value;changeFreq(node);return;}// 如果緩存已滿，需要移除最低頻率的節點以騰出空間if(keyToNode.size() == capacity){Node cur = freqToDummy.get(minFreq);Node delNode = cur.prev;keyToNode.remove(delNode.key);del(delNode);if(cur.prev == cur) freqToDummy.remove(minFreq);}// 創建新節點，并插入到映射和頻率鏈表中node = new Node(key, value);keyToNode.put(key, node);insert(1, node);minFreq = 1;}/*** 修改節點的頻率。* 此方法用于更新給定節點的頻率，并相應地調整頻率列表和最小頻率的值。* 如果更新后的頻率導致原有的頻率列表頭部節點成為一個孤立節點（即它的前向和后向指針都指向自己），* 則該節點將從頻率列表中移除，并且如果該頻率原本是最低頻率，則最小頻率值將增加。* 最后，使用更新后的頻率將節點插入到頻率列表的適當位置。** @param node 需要更新頻率的節點。*/void changeFreq(Node node){// 1、先刪除節點del(node);// 根據當前節點的頻率獲取頻率鏈表的頭部節點Node cur = freqToDummy.get(node.freq);// 檢查當前頻率的鏈表是否為空（即頭部節點的前向指針是否指向自己）if(cur.prev == cur){// 如果鏈表為空，則從映射中移除該頻率，并檢查是否需要調整最小頻率值freqToDummy.remove(node.freq);if(minFreq == node.freq){minFreq++;}}// 3、插入到新位置insert(++node.freq, node);}/*** 將給定節點插入到特定頻率鏈表中。* 此函數假設頻率對應的鏈表已經存在，或者如果不存在，則會創建一個新的鏈表。* 插入操作在鏈表的頭部進行，以保持節點按頻率排序。** @param key 節點的鍵值，用于確定節點應插入到哪個頻率鏈表。* @param node 要插入的節點。*/void insert(int key, Node node){// 根據頻率獲取或創建對應的頻率鏈表的頭節點。// 獲取頻率的頭節點Node cur = freqToDummy.computeIfAbsent(key, k -> newList());node.prev = cur;node.next = cur.next;cur.next.prev = node;cur.next = node;}/*** 從雙向鏈表中刪除給定節點。* 此函數不返回任何值，因為它操作的是鏈表的內部結構。* 它接受一個參數 node，該參數是需要被刪除的節點。** @param node 需要被刪除的節點。*/void del(Node node){/* 將給定節點的前一個節點的next指針指向給定節點的后一個節點，從而在鏈表中向前斷開給定節點。 */node.next.prev = node.prev;/* 將給定節點的后一個節點的prev指針指向給定節點的前一個節點，從而在鏈表中向后斷開給定節點。 */node.prev.next = node.next;}}