题解 | #设计LFU缓存结构#

基本思路

题目要求在缓存满时移除调用次数最少的key，并且在调用次数相同时移除最早进入的key，那么移除调用次数最少的key可以用一个最小频率minFreq来记录，移除最早进入的key就需要一个双向链表维护，每次进行查询或插入操作时都将该节点更新到链表头部，这样链表尾部存放的就是最早进入的key了。

所以设计一个哈希表存放频率和该频率下的双向链表节点，还有一个哈希表存放key和该key对应的频率链表的头结点的映射，minFreq在key首次加入缓存时设置为1，并且会在更新节点频率时同时更新minFreq，更新节点频率就是将该key对应的节点从之前的频率节点链表中移除，然后放到原来频率加一的频率链表中，如果频率链表不存在就需要新建。

在缓存满时，首先根据最小频率找到对应的key，从该key对应的频率链表中移除该key对应的节点，并在缓存中移除该key，频率链表移除操作时要判断是否移除后链表为空，如果链表为空就移除该频率链表。

查询和更新缓存时，都需要更新频率链表，注意map的put操作在key不存在时是插入该键值对，如果key存在的情况下会更新键值对。

参考

参考题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    class Node {
        private int key;
        private int val;
        private int freq;  // 记录当前节点的使用频率

        public Node(int key, int val, int freq) {
            this.key = key;
            this.val = val;
            this.freq = freq;
        }
    } 
    private Map<Integer, LinkedList<Node>> freqMp = new HashMap<>();  // 记录频率和该频率下的所有节点链表
    private Map<Integer, Node> mp = new HashMap<>();  // 记录key和该key的节点对应的频率链表的头结点
    private int size = 0;  // 记录缓存中已使用的容量
    private int capacity = 0;  // 记录缓存中的最大容量
    private int minFreq = 0;  // 记录缓存中最小的频率
    public int[] LFU (int[][] operators, int k) {
        // write code here
        this.capacity = k;
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < operators.length; ++i) {
            if (operators[i][0] == 1) {
                set(operators[i][1], operators[i][2]);
            }
            else if (operators[i][0] == 2) {
                list.add(get(operators[i][1]));
            }
        }

        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    private void set(int key, int val) {
        if (mp.containsKey(key)) {
            updateFreq(key, val, mp.get(key));  // 将该key放入新的频率链表中
            return;
        }

        if (size == capacity) {
            int minFreqKey = freqMp.get(minFreq).getLast().key;  // 取得最近使用频率最少的key
            freqMp.get(minFreq).removeLast();  // 移除链表尾部最不经常使用的元素
            if(freqMp.get(minFreq).isEmpty()) {  // 如果当前频率下的双向链表为空，则在哈希表中移除该链表
                freqMp.remove(minFreq);
            }
            mp.remove(minFreqKey);  // 缓存中移除使用频率最小的key
            size--;
        }

        Node node = new Node(key, val, 1);
        minFreq = 1;  // 第一次加入元素，最小频率设置为1
        if (!freqMp.containsKey(1)) {
            freqMp.put(1, new LinkedList<>());  // 如果该频率没有对应的链表，则创建一个链表
        }
        freqMp.get(1).addFirst(node);  // 将该key的节点加入到该key对应的频率链表中
        mp.put(key, freqMp.get(1).getFirst());  // 缓存中加入该key对应的频率链表的首节点
        size++;
    }

    private int get(int key) {
        int res = -1;

        if (mp.containsKey(key)) {
            Node node = mp.get(key);
            res = node.val;
            updateFreq(key, res, node);
        }

        return res;
    }

    // 将当前node从原来的频率链表中移除，然后加入新的频率链表中
    private void updateFreq(int key, int val, Node node) {
        int freq = node.freq;
        freqMp.get(freq).remove(node);  // 从该key对应的频率链表中移除当前key
        if (freqMp.get(freq).isEmpty()) { // 如果移除节点后该频率链表为空，则移除当前频率
            freqMp.remove(freq);
            if (minFreq == freq) {  // 因为要移除该频率，所以要更新最低频率链表
                minFreq++;
            }
        }

        // 将该key加入新的频率链表中
        if (!freqMp.containsKey(freq+1)) {  // 如果没有该频率链表，则新建一个
            freqMp.put(freq+1, new LinkedList<>());
        }
        // 将该节点加入频率链表的头部
        freqMp.get(freq+1).addFirst(new Node(key, val, freq+1));
        mp.put(key, freqMp.get(freq+1).getFirst());  // put如果key存在的情况下会更新键值对
    }
}