算法

import java.util.*;

public class LFUCache<K, V> {
    private final int capacity;
    private Map<K, V> cache;
    private Map<K, Integer> freqMap;
    private Map<Integer, LinkedHashSet<K>> freqKeysMap;
    private int minFreq;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        freqMap = new HashMap<>();
        freqKeysMap = new HashMap<>();
        minFreq = 0;
    }

    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null;
        }
        int freq = freqMap.get(key);
        freqMap.put(key, freq + 1);
        freqKeysMap.get(freq).remove(key);
        if (freq == minFreq && freqKeysMap.get(freq).size() == 0) {
            minFreq++;
        }
        if (!freqKeysMap.containsKey(freq + 1)) {
            freqKeysMap.put(freq + 1, new LinkedHashSet<>());
        }
        freqKeysMap.get(freq + 1).add(key);
        return cache.get(key);
    }

    public void put(K key, V value) {
        if (capacity <= 0) {
            return;
        }
        if (cache.containsKey(key)) {
            cache.put(key, value);
            get(key);
            return;
        }
        if (cache.size() >= capacity) {
            K evictKey = freqKeysMap.get(minFreq).iterator().next();
            freqKeysMap.get(minFreq).remove(evictKey);
            cache.remove(evictKey);
            freqMap.remove(evictKey);
        }
        cache.put(key, value);
        freqMap.put(key, 1);
        minFreq = 1;
        if (!freqKeysMap.containsKey(1)) {
            freqKeysMap.put(1, new LinkedHashSet<>());
        }
        freqKeysMap.get(1).add(key);
    }
}