前言

昨天在 leetcode 460 上學習LFU演算法，看見一個大佬寫的O(1) 解法 —— 存盤頻次的HashMap改為直接用雙向鏈表（最優實作 13ms 雙100%），印象頗深，隔了一天之后照著他的思路自己也手寫實作了LFU，和原版略有不同，不過思路很值得講

原始碼

點擊這里獲取原始碼，別忘了點個Star哦~

一、思路

一般來說，我們理解的鏈表都是這樣的：

我們可以通過雙鏈表實作LRU，但是LFU呢？它比LRU要多出一個“訪問頻次”的屬性，只靠雙鏈表似乎并不能滿足LFU的設計需求

那么我們用很多條鏈表來做這件事怎么樣？既可以通過鏈表的特性保證訪問時間和順序的關系，又可以讓每個鏈表記錄一個頻次，里面存放的都是對應頻次的資料：

在每條鏈表中又按照頻次大小順序連接著，這也可以形容為“鏈鏈表”，用代碼來講，就是：LinkedList<LinkedList<Node>>

那么要如何使用這多重鏈表呢

• 在已有多條鏈表分別存盤資料的情況下，put操作時，在頻次最大的鏈表上進行頭插（快取滿時，要洗掉頻次最小的鏈表的尾節點）
• 在快取為空時，put操作時，讓快取生成一條頻次為0的鏈表，并在該鏈表上進行頭插
• 在put，get操作命中快取時，讓快取中被命中的資料節點移動到（當前頻次+1）的頻次鏈表上
• 若頻次最小的鏈表僅剩的節點被洗掉，則洗掉頻次最小的鏈表（即對“鏈鏈表”進行尾刪

二、核心定義

1. 類的層次

在我的容器設計中，我的類定義的層次如下

// 最外層，LFU快取容器類
public class MultiLinkedListLFU<K, V> {
	// 中間層，多重鏈表類
	private class MultiLinkedList {
		// 最內層，鏈表節點類
		class Entry {
		
		}
	}
}

2. 鏈表節點類

我的鏈表節點類存放鍵值對，如下

        class Entry {
            K key;
            V val;

            Entry pre, next;

            Entry(K key, V val) {
                this.key = key;
                this.val = val;
            }
        }

沒什么特別的，不熟的同學建議復習下雙向鏈表

3. 多重鏈表類

1）類的欄位

        /**
         * 記錄被訪問的頻次
         */
        int freq;

        /**
         * 前/后鏈表
         */
        MultiLinkedList pre, next;

        /**
         * 當前鏈表的頭/尾節點
         */
        Entry head, tail;

        /**
         * 當前鏈表的長度
         */
        private int size;

這個類的實體是一條鏈表，每條鏈表都記錄著頻次的欄位freq，并且有前后指標MultiLinkedList pre, next指向其自身的上一條/下一條鏈表，除此之外，頭/尾節點和鏈表長度的欄位基本上都是一條雙向鏈表要記錄的欄位

2）構造方法

        /**
         * 無參構造方法
         */
        MultiLinkedList() {
        }

        /**
         * 有參構造方法
         *
         * @param freq
         */
        MultiLinkedList(int freq) {
            this.freq = freq;
        }

有參構造方法為實體記錄傳入的頻次，無參則默認生成頻次為0的實體

3）方法實作

a. 添加資料方法put

        /**
         * 添加資料方法
         *
         * @param key
         * @param val
         */
        void put(K key, V val) {
            // 鏈表為空/不為空，分情況討論
            if (size == 0) {
                head = new Entry(key, val);
                tail = head;
                ++size;
            } else {
                addToHead(new Entry(key, val));
            }
        }

addToHead方法就是頭插方法

b. 洗掉指定key的節點方法

        /**
         * 通過key洗掉指定節點
         *
         * @param key
         */
        boolean removeEntryByKey(K key) {
            Entry entry = findEntryByKey(key);
            if (entry == null) {
                //未找到指定節點，洗掉失敗
                return false;
            } else {
                // 當前key得到的節點是尾節點時，直接尾刪
                if (key.equals(tail.key)) {
                    removeLast();
                    // 當前key得到的節點是頭節點時，直接頭刪
                } else if (key.equals(head.key)) {
                    removeFirst();
                } else {
                    removeEntry(entry);
                }
                return true;
            }
        }

頭刪removeFirst()，尾刪removeLast，頭插addToHead，洗掉指定節點removeEntry(Entry entry)等方法在往期文章都有提到，就不再贅述

*c. toString方法

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (Entry cur = head; cur != null; cur = cur.next) {
                sb.append(cur.key)
                        .append("->");
            }
            return sb.substring(0, sb.length() - 2).toString();
        }

為了方便測驗輸出而寫

4. LFU實作類

1）類的欄位

    /**
     * 記錄<鍵key,頻次freq>的哈希圖，用于快速定位節點
     */
    private final HashMap<K, Integer> KEY_FREQ_MAP = new HashMap<>();

    /**
     * 頭/尾鏈表
     */
    private MultiLinkedList headList, tailList;

    /**
     * 容器中鏈表的數量
     */
    private int listAmount;

    /**
     * 容量
     */
    private int capacity;

原作者的HashMap存盤的是<key,Node>，他的Node除了存盤鍵值對以外還存盤頻次，而我的HashMap：private final HashMap<K, Integer> KEY_FREQ_MAP = new HashMap<>();只存盤了key和頻次，在后面的節點查找中時間復雜度會較大

作為“鏈鏈表”套娃的最外層，這里將頭/尾節點的概念應用為頭/尾鏈表:private MultiLinkedList headList, tailList，如果你把一條鏈表當作一個節點來看，那么就很容易說得通了

2）構造方法

    /**
     * 有參構造方法
     *
     * @param capacity
     */
    public MultiLinkedListLFU(int capacity) {
        this.capacity = capacity;
    }

傳入一個容量欄位，供快取容器檢測快取是否滿了即可

3）私有方法

這里我們將“鏈鏈表”做一個定義：

• 頭節點鏈表headList的頻次最高，尾節點鏈表tailList的頻次最低
• 該進行快取淘汰時，對尾節點鏈表tailList進行尾刪，如果此時tailList經過尾刪后長度為0，則對“鏈鏈表”進行尾刪，即洗掉尾節點鏈表
• 插入資料時，在頭節點鏈表headList上進行頭插
• 資料被訪問時，將該資料移動到其所在鏈表list的前一個鏈表list.pre的頭部

a. “鏈鏈表”的尾刪

    /**
     * 洗掉尾鏈表
     */
    private void removeTailList() {
        tailList = tailList.pre;
        tailList.next = null;
        --listAmount;
    }

和常規的鏈表尾刪是一樣的

b. “鏈鏈表”的頭插

    /**
     * 新增一條頻次比當前頭鏈表多1的鏈表，并將其作為新頭鏈表
     */
    private void newHeadList() {
        MultiLinkedList newList = new MultiLinkedList(headList.freq + 1);
        newList.next = headList;
        headList.pre = newList;
        headList = newList;
        ++listAmount;
    }

這里除了要注意頻次的處理以外，和常規的鏈表頭插也是一樣的

c. 基于頻次找到對應鏈表

    /**
     * 基于頻次找到對應鏈表
     *
     * @param freq
     * @return
     */
    private MultiLinkedList findListByFreq(int freq) {
        MultiLinkedList list = headList;
        while (list.freq != freq) {
            list = list.next;
        }
        return list;
    }

暴力的遍歷，做得并不好

d. 對內展示快取中的元素總數

    /**
     * 對內展示快取元素個數
     *
     * @return
     */
    private int getSumSize() {
        int sum = 0;
        for (MultiLinkedList list = headList; list != null; list = list.next) {
            sum += list.size;
        }
        return sum;
    }

遍歷所有鏈表中的size進行求和

e. 資料頻次自增

當資料被訪問后，其頻次就要自增，這是LFU的核心

    /**
     * 鍵值頻次自增
     *
     * @param list
     * @param key
     * @param val
     */
    private void freqIncrease(MultiLinkedList list, K key, V val) {
        // 將節點放置到比原鏈表頻次+1的新鏈表
        // 當list不存在前鏈表，說明list為頭鏈表headList
        if (list.pre == null) {
            newHeadList();
            headList.put(key, val);
            // 記錄到KEY_FREQ_MAP
            KEY_FREQ_MAP.put(key, headList.freq);
        } else {
            // 當list存在前鏈表，將節點在前鏈表上進行頭插
            list.pre.put(key, val);
            // 記錄到KEY_FREQ_MAP
            KEY_FREQ_MAP.put(key, list.pre.freq);
        }
    }

不要忘了讓HashMap存盤最新的頻次

4）實體方法

a. 新增資料的put方法

邏輯較復雜，這里簡單說說：

1. 校驗快取中是否存在傳入的鍵，若存在：
   1. 根據鍵獲取節點所在的頻次，再根據頻次獲取節點
   2. 頻次自增，將該節點移動到其所在鏈表(list)的前鏈表(list.pre)頭部
2. 若不存在：
   1. 檢驗快取是否為空，若是，新增鏈表
   2. 檢驗快取是否滿了，若是，將尾鏈表進行尾刪
   3. 在頭鏈表上頭插新鍵值

    public void put(K key, V val) {
        // 若快取中存在與傳入鍵值相同的值
        if (KEY_FREQ_MAP.containsKey(key)) {
            // 獲取當前key的頻次
            int freq = KEY_FREQ_MAP.get(key);
            // 獲取當前頻次所對應的鏈表list
            MultiLinkedList list = findListByFreq(freq);
            // 在list中刪去指定節點
            list.removeEntryByKey(key);
            // 鍵值頻次自增
            freqIncrease(list, key, val);
        } else {
            // 當剛初始化，容器中尚不存在鏈表時
            if (listAmount == 0) {
                headList = new MultiLinkedList();
                tailList = headList;
                ++listAmount;
            }
            // 當容器滿，尾刪
            if (getSumSize() == capacity) {
                tailList.removeLast();
                //當尾鏈表為空時，洗掉尾鏈表
                if (tailList.isEmpty()) {
                    removeTailList();
                    --listAmount;
                }
            }
            // 剛被添加的資料，頻次為0，從尾鏈表添加
            tailList.put(key, val);
            // 記錄到KEY_FREQ_MAP
            KEY_FREQ_MAP.put(key, 0);
        }
    }

b. 獲取資料值的get方法

邏輯：
1. 查詢快取中是否存在該key，若不存在，回傳控制，若存在，執行步驟2
2. 根據鍵查詢所在的節點，獲取節點中的值
3. 將該資料頻次自增，并移動到其當前鏈表的前鏈表的頭部
4. 回傳傳入鍵對應的值

    /**
     * get方法
     *
     * @param key
     * @return
     */
    public V get(K key) {
        // 當<key,freq>表中不存在查詢key時，回傳空值
        if (!KEY_FREQ_MAP.containsKey(key)) {
            return null;
        }
        // 獲取查詢key的頻次
        int freq = KEY_FREQ_MAP.get(key);
        // 根據頻次找到資料所在鏈表
        MultiLinkedList list = findListByFreq(freq);
        V val = list.findEntryByKey(key).val;
        // 在原位置洗掉原節點
        list.removeEntryByKey(key);
        // 鍵值頻次自增
        freqIncrease(list, key, val);
        // 回傳鏈表中對應鍵的值
        return val;
    }

注意，無論是put方法還是get方法，都屬于資料訪問，記得要讓頻次自增

c. 顯示快取資料個數方法

    /**
     * 對外顯示快取元素個數
     *
     * @return
     */
    public int size() {
        return getSumSize();
    }

呼叫私有方法getSumSize()即可

*d. toString方法

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (MultiLinkedList cur = headList; cur != null; cur = cur.next) {
            sb.append("頻次")
                    .append(cur.freq)
                    .append(":")
                    .append(cur.toString())
                    .append("\n");
        }
        return sb.toString();
    }

遍歷每條鏈表獲取其頻次和其各自的toString，并換行

總結

根據大佬的大致思路實作了LFU，還是有細節沒處理好，但是基本的功能已經實作了

慣例測驗：

public class Test {
    public static void main(String[] args) {
        MultiLinkedListLFU<Integer, String> lfu = new MultiLinkedListLFU<>(5);
        lfu.put(1, "a");
        lfu.put(2, "b");
        lfu.put(3, "c");
        lfu.put(4, "d");
        lfu.put(5, "e");
        lfu.put(2, "y");
        System.out.println(lfu.toString());
        /**
         * output:
         * 頻次1:2
         * 頻次0:5->4->3->1
         */
        System.out.println(lfu.get(1)); // a
        System.out.println(lfu.toString());
        /**
         * output:
         * 頻次1:1->2
         * 頻次0:5->4->3
         */
        lfu.put(6, "f");
        System.out.println(lfu.toString());
        /**
         * output:
         * 頻次1:1->2
         * 頻次0:6->5->4
         */
        lfu.put(4, "x");
        System.out.println(lfu.toString());
        /**
         * output:
         * 頻次1:4->1->2
         * 頻次0:6->5
         */
        System.out.println(lfu.get(6)); // f
        /**
         * output:
         * 頻次1:6->4->1->2
         * 頻次0:5
         */
        System.out.println(lfu.get(4)); // x
        System.out.println(lfu.toString());
        /**
         * output:
         * 頻次2:4
         * 頻次1:6->1->2
         * 頻次0:5
         */
        lfu.put(7, "g");
        System.out.println(lfu.toString());
        /**
         * output:
         * 頻次2:4
         * 頻次1:7->6->1->2
         */
    }
}

有不足之處歡迎大佬留言指教~