【每日一题Day337】LC460LFU 缓存 | 双链表+哈希表

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);
   */
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62

• 思路

  • 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; // 更新 value
              return;
          }
          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;
      }
  }
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87