460. LFU Cache

HashMap + LinkedHashSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class LFUCache {

    private final Map<Integer, Integer> cacheMap;
    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.cacheMap = new HashMap<>();
        this.keyToFreqMap = new HashMap<>();
        this.freqToKeySetMap = new HashMap<>();
        this.capacity = capacity;
        this.minFreq = 1;
    }

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

        increaseFreq(key);
        return value;
    }

    private void increaseFreq(int key) {
        int freq = keyToFreqMap.get(key);
        keyToFreqMap.put(key, freq + 1);
        Set<Integer> keySet = freqToKeySetMap.get(freq);
        keySet.remove(key);
        if (keySet.isEmpty()) { // 注意当频次为 0 时需要将空集合移除，以便后续淘汰元素时能获取到正确的元素，否则将触发 NoSuchElementException
            freqToKeySetMap.remove(freq);
            if (freq == minFreq) {
                minFreq++;
            }
        }
        freqToKeySetMap.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);
    }

    public void put(int key, int value) {
        Integer cachedValue = cacheMap.get(key);
        if (cachedValue != null) {
            cacheMap.put(key, value);
            increaseFreq(key);
            return;
        }

        if (cacheMap.size() == capacity) {
            // 当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项
            int evictedKey = freqToKeySetMap.get(minFreq).iterator().next();
            int evictedFreq = keyToFreqMap.remove(evictedKey);
            freqToKeySetMap.get(evictedFreq).remove(evictedKey);
            cacheMap.remove(evictedKey);
        }

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

}

注意题目中的要求：当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。

References

460. LFU Cache