[TypeScript]手擼LFU

最近做筆試的時候遇到了要手擼LFU的題目，LFU在vue源碼里還是有使用的，例如keep-alive的實現機制就是基于它來搞的。不多說了，直接上代碼。

代碼

// 雙向鏈表node
class DoubleLinkNode {key: number;val: number;freq: number;prev?: DoubleLinkNode | null;next?: DoubleLinkNode | null;constructor(key, val, freq) {this.freq = freq;this.key = key;this.val = val;}
}// 雙向鏈表
class DoubleLink {size: number;head: DoubleLinkNode | null;tail: DoubleLinkNode | null;constructor() {this.size = 0;this.head = null;this.tail = null;}// 刪除一個節點remove(node: DoubleLinkNode) {// 空鏈表if (this.size < 1) {return;}// 只有一個元素if (this.size === 1) {this.size = 0;this.head = null;this.tail = null;return;}// 刪的是頭結點if (node === this.head) {const nextNode = node.next;nextNode.prev = null;this.head = nextNode;this.size--;return;}// 刪的是尾結點if (node === this.tail) {const prevNode = node.prev;prevNode.next = null;this.tail = prevNode;this.size--;return;}// 正常刪中間節點const prevNode = node.prev;const nextNode = node.next;prevNode.next = nextNode;nextNode.prev = prevNode;this.size--;}// 在尾部插入一個節點addLast(node: DoubleLinkNode) {// 空鏈表if (this.size === 0) {this.head = node;this.tail = node;} else {// 非空鏈表const curTail = this.tail;curTail.next = node;node.prev = curTail;this.tail = node;}this.size++;}// 是否是空鏈表isEmpty() {return this.size === 0;}
}// 實現LFU緩存
class LFUCache {keyToNodeMap: Map<number, DoubleLinkNode>;freqToKeysMap: Map<number, DoubleLink>;capacity: number;minFreq: number;constructor(capacity: number) {this.keyToNodeMap = new Map();this.freqToKeysMap = new Map();this.capacity = capacity;this.minFreq = 0;}get(key: number): number {if (!this.keyToNodeMap.has(key)) {return -1;}const node = this.keyToNodeMap.get(key);// 增加頻次this.increaseFreq(node);return node.val;}put(key: number, value: number): void {// key已經存在if (this.keyToNodeMap.has(key)) {// 修改對應的node的val即可const node = this.keyToNodeMap.get(key);node.val = value;this.increaseFreq(node);} else {// key不存在// 容量滿了if (this.keyToNodeMap.size >= this.capacity) {// 刪除最小頻次中最久沒使用的this.removeMinFreqKey();}// ------------正式開始插入------------const newNode = new DoubleLinkNode(key, value, 1);this.keyToNodeMap.set(key, newNode);if (!this.freqToKeysMap.get(1)) {this.freqToKeysMap.set(1, new DoubleLink());}// 維護頻次表const link = this.freqToKeysMap.get(1);link.addLast(newNode);// 插入新 key 后最小的 freq 肯定是 1this.minFreq = 1;}}// 增加頻次increaseFreq(node: DoubleLinkNode) {const oldFreq = node.freq;const newFreq = node.freq + 1;node.freq = newFreq;// 維護頻次表const oldFreqLink = this.freqToKeysMap.get(oldFreq);// 從舊頻次表中刪除這個nodeoldFreqLink.remove(node);if (oldFreqLink.isEmpty()) {this.freqToKeysMap.delete(oldFreq);// 如果這個頻次正好是最低頻次，記得更新最小頻次if (this.minFreq === oldFreq) {this.minFreq = newFreq;}}// 維護新頻次表if (!this.freqToKeysMap.get(newFreq)) {this.freqToKeysMap.set(newFreq, new DoubleLink());}const newFreqLink = this.freqToKeysMap.get(newFreq);newFreqLink.addLast(node);}// 刪除最小頻次中最久沒使用的removeMinFreqKey() {const minFreqLink = this.freqToKeysMap.get(this.minFreq);// 其中最先被插入的那個 node 就是該被淘汰的 nodeconst deletedNode = minFreqLink.head;// 維護最小頻次mapminFreqLink.remove(deletedNode);if (minFreqLink.isEmpty()) {this.freqToKeysMap.delete(this.minFreq);}// key表中刪除對應Nodethis.keyToNodeMap.delete(deletedNode.key);}// log調試方法print() {console.log('keyToNodeMap: ', this.keyToNodeMap);console.log('freqToKeysMap: ', this.freqToKeysMap);}
}

思路

LFU（Least Frequently Used）緩存是一種緩存淘汰策略，它根據元素的使用頻率來決定哪些元素應該被淘汰。在你提供的代碼中，LFUCache 類實現了這種策略，下面是它的工作原理的詳細描述：

1. 數據結構：

   • DoubleLinkNode：表示雙向鏈表中的節點，包含鍵（key）、值（val）和頻率（freq）。
   • DoubleLink：表示雙向鏈表，包含頭尾節點以及鏈表的大小。
   • Map：keyToNodeMap 用于存儲鍵到節點的映射，freqToKeysMap 用于存儲頻率到鍵的映射。

2. 構造函數：

   • 初始化 LFUCache 時，設置緩存的容量（capacity），并初始化鍵到節點的映射和頻率到鍵的映射。

3. get 方法：

   • 檢查鍵是否存在于 keyToNodeMap 中。
   • 如果存在，找到對應的節點，并調用 increaseFreq 方法來增加節點的使用頻率。
   • 返回節點的值。

4. put 方法：

   • 檢查鍵是否已存在：
     • 如果存在，更新節點的值，并增加頻率。
     • 如果不存在，并且緩存已滿，則調用 removeMinFreqKey 方法來刪除最小頻率的鍵。
   • 創建新節點，并將其添加到 keyToNodeMap 和 freqToKeysMap 中。

5. increaseFreq 方法：

   • 增加節點的使用頻率。
   • 從舊頻率的鏈表中刪除節點，并檢查是否需要更新最小頻率。
   • 將節點添加到新頻率的鏈表中。

6. removeMinFreqKey 方法：

   • 找到最小頻率鏈表的頭節點，即最久未使用的節點。
   • 從鏈表中刪除該節點，并更新 freqToKeysMap。
   • 從 keyToNodeMap 中刪除對應的鍵。

7. print 方法：

   • 用于調試，打印當前的鍵到節點映射和頻率到鍵的映射。

這種實現方式確保了：

• 每個鍵的使用頻率都被跟蹤。
• 當緩存達到容量限制時，最少使用頻率的鍵將被淘汰。
• 通過雙向鏈表，可以快速地添加和刪除節點，同時保持鏈表的順序。

這種緩存策略適用于那些需要平衡訪問頻率和最近使用情況的場景。