LFU 缓存【LC460】

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

• LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
• int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。
• void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。

为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

• 错误答案

  class LFUCache {// 注意：PriorityQueue要插入(删除)数据，顺序会发生改变，如果仅仅是修改已经稳定队列的值或内容，而不进行插入或者删除，那么，这个顺序是不会变的。// 使用Node存储每个key对应的value，以及该key的操作次数、最近操作时间// 小顶堆存储每个元素， 以使用次数及最近使用时间降序排序int capacity;PriorityQueue<Node> pq;Map<Integer, Node> map;int time;public LFUCache(int capacity) {this.capacity = capacity;this.pq = new PriorityQueue<>((o1, o2) -> o1.freq == o2.freq ? o1.time - o2.time : o1.freq - o2.freq);this.map = new HashMap<>();this.time = 0;}public int get(int key) {if (!map.containsKey(key)) return -1;Node node = map.get(key);node.freq += 1;node.time = time++;return node.val;}public void put(int key, int value) {if (map.containsKey(key)){Node node = map.get(key);node.val = value;node.freq += 1;node.time = time++;}else{Node node = new Node(key, value, time++, 1);if (pq.size() == capacity){Node node1 = pq.poll();map.remove(node1.key);}pq.add(node);map.put(key, node);}}
  }
  class Node{int key;int val;int time;int freq;public Node(){this.freq = 0;}public Node(int key, int val, int time, int freq){this.key = key;this.val = val;this.time = time;this.freq = freq;}
  }/*** Your LFUCache object will be instantiated and called as such:* LFUCache obj = new LFUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/
  

• 思路

  • LFU和LRU不同之处
    • LRU移除元素时移除最近最久未使用的元素
    • LFU移除元素时移除使用频率最少的最近最久未使用的元素
  • 因此LFU实现可以仿照LRU，使用哈希表记录每个频率下的节点，相同频率下的各个节点以双向链表的形式组织
    • 每次移除元素时移除频率最小的最久未使用的元素
    • 每操作一次元素需要修改节点频率至相应链表
    • 链表的首部存放最新操作的元素
    • 为了快速找到某个节点在链表中的位置，可以使用哈希表存储每个key对应的节点
    • 为了快速找到最小频率，维护一个int变量记录最小频率

• 实现

  class LFUCache {private static class Node {int key, value, freq = 1; // 新书只读了一次Node prev, next;Node(int key, int value) {this.key = key;this.value = value;}}private final int capacity;private final Map<Integer, Node> keyToNode = new HashMap<>();private final Map<Integer, Node> freqToDummy = new HashMap<>();private int minFreq;public LFUCache(int capacity) {this.capacity = capacity;}public int get(int key) {Node node = getNode(key);return node != null ? node.value : -1;}public void put(int key, int value) {Node node = getNode(key);if (node != null) { // 有这本书node.value = value; // 更新 valuereturn;}if (keyToNode.size() == capacity) { // 书太多了Node dummy = freqToDummy.get(minFreq);Node backNode = dummy.prev; // 最左边那摞书的最下面的书keyToNode.remove(backNode.key);remove(backNode); // 移除if (dummy.prev == dummy) { // 这摞书是空的freqToDummy.remove(minFreq); // 移除空链表}}node = new Node(key, value); // 新书keyToNode.put(key, node);pushFront(1, node); // 放在「看过 1 次」的最上面minFreq = 1;}private Node getNode(int key) {if (!keyToNode.containsKey(key)) { // 没有这本书return null;}Node node = keyToNode.get(key); // 有这本书remove(node); // 把这本书抽出来Node dummy = freqToDummy.get(node.freq);if (dummy.prev == dummy) { // 抽出来后，这摞书是空的freqToDummy.remove(node.freq); // 移除空链表if (minFreq == node.freq) { // 这摞书是最左边的minFreq++;}}pushFront(++node.freq, node); // 放在右边这摞书的最上面return node;}// 创建一个新的双向链表private Node newList() {Node dummy = new Node(0, 0); // 哨兵节点dummy.prev = dummy;dummy.next = dummy;return dummy;}// 在链表头添加一个节点（把一本书放在最上面）private void pushFront(int freq, Node x) {Node dummy = freqToDummy.computeIfAbsent(freq, k -> newList());x.prev = dummy;x.next = dummy.next;x.prev.next = x;x.next.prev = x;}// 删除一个节点（抽出一本书）private void remove(Node x) {x.prev.next = x.next;x.next.prev = x.prev;}
  }