方便记忆和理解的LFU Java代码

LFU简介

LFU 算法相当于是淘汰访问频次最低的数据，如果访问频次最低的数据有多条，需要淘汰最旧的数据。

最不经常使用（LFU） Least Frequently Used

put逻辑

参考 labuladong

代码（结合了两份代码的优点）

算法题就像搭乐高：手把手带你拆解 LFU 算法

力扣

结合了两份代码的优点：

labuladong代码好理解，不过用了3个hash表，有些繁琐。

力扣官方给出的题解用了Node将频率作为缓存的一个属性，不过代码有冗余。

class LFUCache {
    int minfreq, capacity;// o1得到最小频率 方便快速删除
    Map<Integer, Node> keyTable; // 键 + 值，以及对应的频率
    Map<Integer, LinkedList<Node>> freqTable;
    // 频次 + 节点链表 通过频率可以得到该频率下的所有缓存
    // 如果只有一个缓存  那么删除即可
    // 如果有多个 从缓存中找到 最近最久未使用的 删除
    public LFUCache(int capacity) {
        this.minfreq = 0;
        this.capacity = capacity;
        keyTable = new HashMap<>();;
        freqTable = new HashMap<>();
    }

    public int get(int key) {
        if (capacity == 0 || !keyTable.containsKey(key)) {
            return -1;
        }
        Node node = keyTable.get(key);
        increaseFreq(key);
        return node.val;
    }

    private void increaseFreq(int key) {
        Node node = keyTable.get(key);
        int val = node.val, freq = node.freq;
        freqTable.get(freq).remove(node);//从频率为 freq 的map中 清除 当前节点
        // 如果当前链表为空，我们需要在哈希表中删除，且更新minFreq
        if (freqTable.get(freq).size() == 0) {
            freqTable.remove(freq);
            if (minfreq == freq) {// 如果当前被get 的节点是 minfreq 对应的唯一节点 那么minfreq需要++
                minfreq += 1;
            }
        }
        // 插入到 freq + 1 中
        LinkedList<Node> list = freqTable.getOrDefault(freq + 1, new LinkedList<>());
        Node tmpNode = new Node(key, val, freq + 1);
        list.offerFirst(tmpNode);// 头插
        freqTable.put(freq + 1, list);
        keyTable.put(key, tmpNode);// 仍然要更新keyTable 因为原节点的频率变了
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if(keyTable.containsKey(key)){
            // 与 get 操作基本一致，除了需要更新缓存的值
            Node node = keyTable.get(key);
            node.val = value;// 更新值
            keyTable.put(key,node);
            increaseFreq(key);
            return;
        }
        // 缓存里没有  如果缓存已满，需要先进行删除操作  再新建node添加
        if (keyTable.size() == capacity) {
            // 通过 minFreq 拿到 freqTable[minFreq] 链表的末尾节点
            Node node = freqTable.get(minfreq).peekLast();
            keyTable.remove(node.key);
            freqTable.get(minfreq).pollLast();
            if (freqTable.get(minfreq).size() == 0) {
                freqTable.remove(minfreq);
            }// 频率为minfreq的链表没有信息了  就把这个链表删掉
        }
        // 拿到 频率为1的链表  如果没有就新建一个
        LinkedList<Node> list = freqTable.getOrDefault(1, new LinkedList<Node>());
        list.offerFirst(new Node(key, value, 1));// 头插
        freqTable.put(1, list);// 更新频率为1的 频率hashmap
        keyTable.put(key, freqTable.get(1).peekFirst());
        minfreq = 1;
    }
    class Node {
        int key, val, freq;
        Node(int key, int val, int freq) {
            this.key = key;
            this.val = val;
            this.freq = freq;
        }
    }
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/92846.html