手撕—LFU

与LRU不同，LRU是根据访问顺序来淘汰，LFU是根据访问频率淘汰最少使用的节点

思路

使用一个哈希表作为key到具体Node的映射，快速定位节点

再使用一个哈希表存储同使用频率的Node，同频率的节点按时间顺序存储，方便淘汰最早插入的

再使用一个minFreq变量，记录当前最小的频率

实现

class Node{		// 节点类，记录当前kv和频率
    int key, value, freq;

    public Node(int key, int value){
        this.key = key;
        this.value = value;
        freq = 1;
    }
}

class LFUCache {
    private int capacity, minFreq;
    private Map<Integer, Node> keyMap;	// key对应节点的哈希表
    private Map<Integer, LinkedHashSet<Node>> freqMap;	// 频率对应节点集合的哈希表

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        this.keyMap = new HashMap<>();
        this.freqMap = new HashMap<>();
    }
	
    // 更新节点信息，把当前节点的使用频率+1，如果旧的频率列表空了，就维护minFreq+1
    private void updateNode(Node node){
        LinkedHashSet<Node> nodes = freqMap.get(node.freq);
        nodes.remove(node);
        if(nodes.isEmpty()){
            freqMap.remove(node.freq);
            if(minFreq == node.freq) minFreq ++;
        }
        node.freq ++;
        freqMap.computeIfAbsent(node.freq, k -> new LinkedHashSet<>()).add(node);
    }
    
    public int get(int key) {
        if(!keyMap.containsKey(key)) return -1;
        Node node = keyMap.get(key);
        updateNode(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        if(capacity == 0) return;
		// 与get类似
        if(keyMap.containsKey(key)){
            Node node = keyMap.get(key);
            node.value = value;
            updateNode(node);
        } else {
            // 容量满了，就删一个频率最低，且加入时间最久的节点
            if(keyMap.size() >= capacity){
                LinkedHashSet<Node> nodes = freqMap.get(minFreq);
                Node node = nodes.iterator().next();
                nodes.remove(node);
                if(nodes.isEmpty()) freqMap.remove(minFreq);
                keyMap.remove(node.key);
            }
            minFreq = 1;
            Node cur = new Node(key, value);
            keyMap.put(key, cur);
            freqMap.computeIfAbsent(minFreq, k -> new LinkedHashSet<>()).add(cur);
        }
    }
}