LFU算法实现

     LRU为最近最少使用，LFU为最不经常使用，它们的区别如下

     例如1 ->2 -> 1 -> 2 -> 3 -> 4，缓存的容量为3

     如果按照LRU，则会淘汰1，因为1访问的事件最远

     按照LFU,则3,4访问次数最少，都为1次，4比3访问事件更近，则淘汰3.

class LFUCache {

    Integer capacity;
    Integer minFrequency;
    Map<Integer, Integer> cache = new HashMap<>();
    Map<Integer, Integer> kf = new HashMap<>();
    Map<Integer, LinkedHashSet<Integer>> fk = new HashMap<>();

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFrequency = 0;
    }
    
    public int get(int key) {
        if(!cache.containsKey(key)){
            return -1;
        }
        increaseFreq(key);
        return cache.get(key);
    }
    
    public void put(int key, int value) {
        if(capacity == 0){
            return ;
        }
        if(cache.containsKey(key)){
            cache.put(key, value);
            increaseFreq(key);
        }else{
            if(cache.size() == capacity){
                removeOne();
            }
            cache.put(key, value);
            kf.put(key, 1);
            minFrequency = 1;
            fk.putIfAbsent(1, new LinkedHashSet<Integer>());
            fk.get(1).add(key);
        }
    }

    public void removeOne(){
        LinkedHashSet<Integer> hashSet = fk.get(minFrequency);
        Integer key = hashSet.iterator().next();
        cache.remove(key);
        kf.remove(key);
        hashSet.remove(key);
    }

    public void increaseFreq(int key){
        Integer oldFreq = kf.get(key);
        Integer newFreq = oldFreq + 1;
        kf.put(key, newFreq);
        LinkedHashSet<Integer> set = fk.get(newFreq);
        if(set == null){
            LinkedHashSet<Integer> hashSet = new LinkedHashSet<>();
            hashSet.add(key);
            fk.put(newFreq, hashSet);
        }else{
            set.add(key);
        }
        LinkedHashSet oldSet = fk.get(oldFreq);
        oldSet.remove(key);
        if(oldSet.isEmpty()){
            fk.remove(oldFreq);
            if(oldFreq == minFrequency){
                minFrequency += 1;
            }
        }
    }
}