设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
一个项目的使用次数就是该项目被插入后对其调用 get 和 put 函数的次数之和。使用次数会在对应项目被移除后置为 0。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lfu-cache
put时，1.若map中存在该key，则更新key值，在优先队列中找到key对应的node，先删除在增加，达到重新排序的效果。
2.若map中不存在key，则在map中新建并存储node。在将node存入优先队列之前要先判断优先队列的大小。若大小等于capacity，则限制性queue.poll()。
注意node节点重写compareTo方法时，在次数相同的情况下，要比较存入的先后顺序。所以引入idx变量。
代码如下。时间复杂度为O(logN)
1 package Leetcode; 2 3 import java.util.HashMap; 4 import java.util.Map; 5 import java.util.PriorityQueue; 6 import java.util.Queue; 7 8 class LFUCache1 { 9 10 class Node implements Comparable<Node> { 11 int key; 12 int value; 13 int freq; 14 int idx; 15 16 public Node() {} 17 18 public Node(int key, int value, int idx) { 19 this.key = key; 20 this.value = value; 21 freq = 1; 22 this.idx = idx; 23 } 24 25 @Override 26 public int compareTo(Node node) { 27 int diff = freq - node.freq; 28 return diff != 0? diff: idx - node.idx; 29 } 30 } 31 32 Map<Integer, Node> cache; 33 Queue<Node> queue; 34 int capacity; 35 int size; 36 int idx = 0; 37 38 public LFUCache1(int capacity) { 39 cache = new HashMap<>(capacity); 40 if (capacity > 0) { 41 queue = new PriorityQueue<>(capacity); 42 } 43 this.capacity = capacity; 44 } 45 46 public int get(int key) { 47 Node node = cache.get(key); 48 if (node == null) { 49 return -1; 50 } 51 node.freq++; 52 node.idx = idx++; 53 queue.remove(node); 54 queue.offer(node); 55 return node.value; 56 57 } 58 59 public void put(int key, int value) { 60 if (capacity == 0) { 61 return; 62 } 63 Node node = cache.get(key); 64 if (node != null) { 65 node.value = value; 66 node.freq++; 67 node.idx = idx++; 68 queue.remove(node); 69 queue.offer(node); 70 } else { 71 if (size == capacity) { 72 cache.remove(queue.peek().key); 73 queue.poll(); 74 size--; 75 } 76 Node newNode = new Node(key, value, idx++); 77 cache.put(key, newNode); 78 queue.offer(newNode); 79 size++; 80 } 81 } 82 83 public static void main(String[] args) { 84 LFUCache1 lfu = new LFUCache1(3); 85 lfu.put(1,1); 86 lfu.put(2,2); 87 lfu.put(3,3); 88 lfu.put(4,4); 89 } 90 }
代码中91到94行含义为方法一种的queue.poll，思路类似，时间复杂度为O(1)
代码如下
1 package Leetcode; 2 3 import java.util.HashMap; 4 import java.util.LinkedHashSet; 5 import java.util.Map; 6 import java.util.Queue; 7 8 class LFUCache { 9 class Node { 10 int key; 11 int value; 12 int freq = 1; 13 14 public Node() {} 15 16 public Node(int key, int value) { 17 this.key = key; 18 this.value = value; 19 } 20 } 21 Map<Integer, Node> cache; // 存储缓存的内容 22 Map<Integer, LinkedHashSet<Node>> freqMap; // 存储每个频次对应的双向链表 23 int size; 24 int capacity; 25 int min; // 存储当前最小频次 26 27 public LFUCache(int capacity) { 28 cache = new HashMap<> (capacity); 29 freqMap = new HashMap<>(); 30 this.capacity = capacity; 31 } 32 33 public int get(int key) { 34 Node node = cache.get(key); 35 if (node == null) { 36 return -1; 37 } 38 freqInc(node); 39 return node.value; 40 } 41 42 public void put(int key, int value) { 43 if (capacity == 0) { 44 return; 45 } 46 Node node = cache.get(key); 47 if (node != null) { 48 node.value = value; 49 freqInc(node); 50 } else { 51 if (size == capacity) { 52 Node deadNode = removeNode(); 53 cache.remove(deadNode.key); 54 size--; 55 } 56 Node newNode = new Node(key, value); 57 cache.put(key, newNode); 58 addNode(newNode); 59 size++; 60 } 61 } 62 63 void freqInc(Node node) { 64 // 从原freq对应的链表里移除, 并更新min 65 int freq = node.freq; 66 LinkedHashSet<Node> set = freqMap.get(freq); 67 set.remove(node); 68 if (freq == min && set.size() == 0) { 69 min = freq + 1; 70 } 71 // 加入新freq对应的链表 72 node.freq++; 73 LinkedHashSet<Node> newSet = freqMap.get(freq + 1); 74 if (newSet == null) { 75 newSet = new LinkedHashSet<>(); 76 freqMap.put(freq + 1, newSet); 77 } 78 newSet.add(node); 79 } 80 81 void addNode(Node node) { 82 LinkedHashSet<Node> set = freqMap.get(1); 83 if (set == null) { 84 set = new LinkedHashSet<>(); 85 freqMap.put(1, set); 86 } 87 set.add(node); 88 min = 1; 89 } 90 91 Node removeNode() { 92 LinkedHashSet<Node> set = freqMap.get(min); 93 Node deadNode = set.iterator().next(); 94 set.remove(deadNode); 95 return deadNode; 96 } 97 }
原文：https://www.cnblogs.com/zhangbochao/p/12639022.html