什么是LFU算法

LFU，全称Least Frequently Used，即最不经常使用

常被用于缓存淘汰策略，核心思想就是依据缓存的访问次数来降序排序。 缓存访问次数多的排前面，当需要删除缓存时，优先删除排在末尾的缓存

对LFU列表的操作主要有两类：

• 写入缓存
• 读取缓存

假设现在有一个容量大小为4的LFU列表，我们来看看对LFU列表的读写操作

写入缓存

当写入的缓存不存在时

当写入的缓存不存在时，新写入的缓存访问次数为1，添加到访问次数为1的缓存头节点位置。当列表长度超过限制时，删除列表的尾节点

列表中存在缓存A，访问次数为4，依次添加B、C、D四个缓存，结果如下图：

添加缓存E，此时列表长度超过4，需要删除尾节点B，结果如下图：

当写入的缓存已存在时

当写入的缓存已存在时，更新对应缓存的值，对应缓存的访问次数+1，把对应的节点移到访问次数相同的缓存头节点即可。因为缓存已存在，列表的大小不会改变，所以不需要进行删除的操作

写入已存在的缓存B列表前后变化，如下图：

读取缓存

当读取的缓存不存在时，直接返回null(或其他默认值)即可

当读取的缓存存在时，除了返回对应的缓存，还需要把对应缓存的访问次数+1，把对应的节点移到访问次数相同的缓存头节点。读取不涉及列表大小的改变，所以也不需要考虑删除操作

读取已存在的缓存B列表前后变化，如下图：

实现一个LFU算法

设计思路

LFU的主要操作：

• 写入缓存
• 读取缓存

两种操作都会频繁涉及到节点的新增和删除(节点的移动，其实也可以通过先删除，后新增来实现)，因此使用链表比数组更加适合

写入/读取已存在的缓存时，对访问次数+1后，需要把对应节点移动到对应访问次数的头节点

如何快速定位对应访问次数的头节点？我们可以拆分成两个问题来解决：

1. 依据访问次数获取对应的节点列表
2. 获取节点列表的头节点

依据访问次数获取对应的节点列表 - 可以通过哈希表来实现，key就是对应的访问次数，value就是对应的缓存节点链表

获取节点列表的头节点 - 可以通过添加虚拟头节点来解决，通过head.next快速定位

超过LFU最大长度限制时，还需要在链表尾部删除节点？对问题进行拆分：

1. 获取最小访问次数对应的链表
2. 定位链表尾节点

获取最小访问次数对应的链表 - 通过一个minFreq变量记录即可

如何快速定位尾节点？通过添加虚拟尾节点 + 双向链表来解决，通过tail.prev来快速定位

另外我们还需要读取缓存，为了降低读取的时间复杂度，可以再使用一个哈希表来进一步优化，key是对应缓存的key，value就是对应的缓存节点

代码

核心思想：双哈希表

LeetCode 460. LFU 缓存

class LFUCache {
    // 链表节点数
    private int size;
    // 最大容量
    private int cap;
    // 最小的访问次数
    private int minFreq;
    // 链表节点哈希表
    private Map<Integer, MLinkedNode> keyMap;
    // 访问次数哈希表
    private Map<Integer, MLinkedList> freqMap;

    public LFUCache(int capacity) {
        keyMap = new HashMap<Integer, MLinkedNode>();
        freqMap = new HashMap<Integer, MLinkedList>();
        cap = capacity;
        size = 0;
        minFreq = 0;
    }
    
    public int get(int key) {
        MLinkedNode node = keyMap.get(key);
        if (node == null) {
            return -1;
        }

        // 依据访问次数获取对应的节点链表
        MLinkedList nodeList = freqMap.get(node.freq);
        // 删除对应的节点
        nodeList.removeNode(node);
        // 如果当前访问次数对应的链表为空，则在freqMap哈希表中删除对应的key
        if (nodeList.size == 0) {
            freqMap.remove(node.freq);
            if (minFreq == node.freq) {
                minFreq++;
            }
        }
        // 对应的key的访问次数+1，并添加到freqMap哈希表中
        MLinkedList nodeList2 = freqMap.get(node.freq + 1);
        if (nodeList2 == null) {
            nodeList2 = new MLinkedList();
        }
        nodeList2.addNodeToHead(new MLinkedNode(node.key, node.value, node.freq + 1));
        freqMap.put(node.freq + 1, nodeList2);
        keyMap.put(key, nodeList2.getHead());
        return node.value;
    }
    
    public void put(int key, int value) {
        MLinkedNode node = keyMap.get(key);
        if (node == null) {
            // 判断缓存是否已满
            if (size == cap) {
                MLinkedList minNodeList = freqMap.get(minFreq);
                MLinkedNode tailNode = minNodeList.getTail();
                keyMap.remove(tailNode.key);
                minNodeList.removeNode(tailNode);
                size--;
                if (minNodeList.size == 0) {
                    freqMap.remove(minFreq);
                }
            }

            // 插入之前不存在的缓存
            MLinkedList nodeList = freqMap.get(1);
            if (nodeList == null) {
                nodeList = new MLinkedList();
            }
            nodeList.addNodeToHead(new MLinkedNode(key, value, 1));
            freqMap.put(1, nodeList);
            keyMap.put(key, nodeList.getHead());
            minFreq = 1;
            size++;
        } else {
            // 更新已存在的缓存
            // 依据访问次数获取对应的节点链表
            MLinkedList nodeList = freqMap.get(node.freq);
            // 删除对应的节点
            nodeList.removeNode(node);
            // 如果当前访问次数对应的链表为空，则在freqMap哈希表中删除对应的key
            if (nodeList.size == 0) {
                freqMap.remove(node.freq);
                    if (minFreq == node.freq) {
                    minFreq++;
                }
            }
            // 对应的key的访问次数+1，并添加到freqMap哈希表中
            MLinkedList nodeList2 = freqMap.get(node.freq + 1);
            if (nodeList2 == null) {
                nodeList2 = new MLinkedList();
            }
            nodeList2.addNodeToHead(new MLinkedNode(node.key, value, node.freq + 1));
            freqMap.put(node.freq + 1, nodeList2);
            keyMap.put(key, nodeList2.getHead());
        }
    }
}

// 定义链表节点
class MLinkedNode {
    int key;
    int value;
    int freq;
    MLinkedNode prev;
    MLinkedNode next; 

    public MLinkedNode() {}
    public MLinkedNode(int k, int v, int f) {
        key = k;
        value = v;
        freq = f;
    }
}

// 定义双链表
class MLinkedList {
    // 虚拟头尾节点
    MLinkedNode head;
    MLinkedNode tail;
    // 双链表节点数
    int size;

    MLinkedList() {
        head = new MLinkedNode();
        tail = new MLinkedNode();
        // 形成双向链表
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    public void addNodeToHead(MLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        size++;
    }

    public void removeNode(MLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
    }

    public MLinkedNode getHead() {
        return head.next;
    }

    public MLinkedNode getTail() {
        return tail.prev;
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */