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;}}}}
如果觉得《LFU算法实现》对你有帮助，请点赞、收藏，并留下你的观点哦！
