460. LFU Cache

class LFUCache {

    private final Map<Integer, Integer> map;
    private final Map<Integer, Integer> keyToFreqMap;
    private final Map<Integer, Set<Integer>> freqToKeySetMap;
    private final int capacity;
    private int minFreq;

    public LFUCache(int capacity) {
        this.map = new HashMap<>();
        this.keyToFreqMap = new HashMap<>();
        this.freqToKeySetMap = new HashMap<>();
        this.capacity = capacity;
        this.minFreq = 1;
    }

    public int get(int key) {
        Integer value = map.get(key);
        if (value == null) {
            return -1;
        } else {
            increaseFreq(key);
            return value;
        }
    }

    private void increaseFreq(int key) {
        int previousFreq = keyToFreqMap.remove(key);
        keyToFreqMap.put(key, previousFreq + 1);

        Set<Integer> keySet = freqToKeySetMap.get(previousFreq);
        keySet.remove(key);
        freqToKeySetMap.computeIfAbsent(previousFreq + 1, k -> new LinkedHashSet<>()).add(key);

        // 注意此处更新 minFreq 的条件，如果之前当前 key 是最低频率，且频率增加后最低频率无元素才更新 minFreq
        if (previousFreq == minFreq && keySet.isEmpty()) {
            minFreq += 1;
        }
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }

        Integer previousValue = map.put(key, value);
        if (previousValue == null) {
            // 注意此处，如果是先 put 再淘汰，则需要 map 中元素个数超过 capacity 再淘汰
            if (map.size() > capacity) {
                // 淘汰一个最低频的
                Set<Integer> keySet = freqToKeySetMap.get(minFreq);
                int evictedKey = keySet.iterator().next();

                map.remove(evictedKey);
                keyToFreqMap.remove(evictedKey);
                keySet.remove(evictedKey);
            }

            keyToFreqMap.put(key, 1);
            freqToKeySetMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
            minFreq = 1;
        } else {
            increaseFreq(key);
        }
    }

}

Reference

460. LFU Cache