题目地址：

https://leetcode.com/problems/lfu-cache/

实现一个Least Frequently Used (LFU) cache。它是一个类似HashMap的数据结构，存的是key-value pair，key唯一，并可以做三种操作：
1、初始化，它有一个最大容量；
2、int get(int key)，得到key对应的value，如果key不存在则返回$-1$；
3、void put(int key, int value)，如果key不存在，则添加该key-value pair，并且如果当前已经存了最大容量个元素了，就需要将cache里使用次数最少的元素删掉，如果有多个，则把最近使用时间最久的元素删掉，这里的“使用”的含义是这个元素被get过或put过，都算；如果key存在，则更新其value。

思路是HashMap + 双链表。开两个HashMap，一个存key和Node的对应关系，其中Node里存key对应的value以及该key被使用的次数，另一个存使用次数和该使用次数对应的所有Node所组成的链表，之所以要用链表来存，是因为要在使用次数相同的情况下删除最近使用时间最久的那个Node，可以借助链表来实现，链表头存最新的Node，链表尾存最旧的Node。并且，由于我们要找使用次数最小的那个链表，所以我们再维护一个变量minFreq专门存当前使用次数最少是多少次。

我们先考虑某个node被使用过一次之后，应该怎样处理它。我们开个函数叫update(Node node)专门做这件事。其实现如下：
因为其freq会增加，所以我们先找到其freq对应的链表，然后将其在链表中删除，接着看一下minFreq是否要被更新，其被更新当且仅当当前使用次数为minFreq的节点都不存在了，即这个链表空了，并且它刚好就是对应的minFreq。如果是这样，就将minFreq增加$1$（因为被update的节点的使用次数会等于minFreq加$1$），再接着将node的使用次数加$1$，再加入这个使用次数对应的链表的头部。当然如果该使用次数的链表不存在，则还需要将其建出来。

三个操作分别如下实现：
1、初始化两个HashMap，并存一下最大容量值。最好先在frequency map里先存一个使用次数$1$对应的链表，因为添加新值的时候这个链表是一定会被用到的；
2、get的时候，先从key找到对应的node（找不到则直接返回$-1$），然后将其更新（执行update操作），最后返回该node里存的value值即可；
3、put的时候，如果最大容量是$0$那就什么也不用做了，直接返回；接着先看一下key是否存在，如果存在，则将其对应的Node找出来，更新其value，并执行update；如果不存在，说明需要增加新Node了，此时要看一下是否达到了容量上限，如果达到了，则要执行删除Least Frequently Used元素的操作（该操作这样执行，先找到minFreq对应的链表，然后删掉其表尾node，并且将该node在key-Node的HashMap里也删掉。如果该链表空了，则说明minFreq的元素不存在了，但是这里事实上不需要更新minFreq，因为执行了删除Least Frequently Used元素的操作一定是因为有新元素进来，它的freq是$1$，所以minFreq一定会变成$1$，这可以在后面的逻辑里写上），删除完之后，将新节点new出来，加入key-Node的HashMap中，并将其加入使用次数为$1$的链表表头，并且重置minFreq为$1$。

代码如下：

class LFUCache {
  struct Node {
    int key, val, freq;
    Node *prev, *next;
    Node(int key, int val)
        : key(key), val(val), prev(nullptr), next(nullptr), freq(1) {}
  };
  struct LinkedList {
    Node *head, *tail;
    LinkedList() {
      head = new Node(0, 0);
      tail = new Node(0, 0);
      head->next = tail;
      tail->prev = head;
    }

    void addFirst(Node *node) {
      node->prev = head;
      node->next = head->next;
      head->next = node;
      node->next->prev = node;
    }

    void remove(Node *node) {
      node->prev->next = node->next;
      node->next->prev = node->prev;
    }

    Node *removeLast() {
      auto *res = tail->prev;
      remove(res);
      return res;
    }

    bool empty() { return head->next == tail; }
  };

  unordered_map<int, Node *> nodemp;
  unordered_map<int, LinkedList *> freq;
  int cap, minFreq;

  void update(Node *node) {
    auto *list = freq[node->freq];
    list->remove(node);
    // 如果该node是minFreq对应的唯一节点，则需要更新minFreq
    if (node->freq == minFreq && list.empty()) minFreq++;
    node->freq++;
    if (!freq.count(node->freq)) freq[node->freq] = new LinkedList();
    freq[node->freq]->addFirst(node);
  }
  
  // 这个是为了删除链表尾，即最近使用时间最久的元素
  void removeOldest() {
    auto *list = freq[minFreq];
    auto *node = list->removeLast();
    nodemp.erase(node->key);
  }

 public:
  LFUCache(int capacity) {
	// 使用次数为1的链表一开始就添进去，因为这个链表是一定会被用到的（除非cap = 0）
    freq[1] = new LinkedList();
    cap = capacity;
    minFreq = 0;
  }

  int get(int key) {
    if (!nodemp.count(key)) return -1;
    auto *node = nodemp[key];
    update(node);
    return node->val;
  }

  void put(int key, int value) {
    // 尤其要注意特判这个，否则nodeMap为空的时候会触发removeOldest操作，
    // 会导致NullPointerException
    if (!cap) return;
    if (nodemp.count(key)) {
      auto *node = nodemp[key];
      node->val = value;
      update(node);
      return;
    }

    if (nodemp.size() == cap) removeOldest();
    auto *node = new Node(key, value);
    nodemp[key] = node;
    freq[1]->addFirst(node);
    minFreq = 1;
  }
};

所有操作时间复杂度$O(1)$，空间$O(n)$，$n$是最大容量。

可以用对象池来优化。代码如下：

class LFUCache {
  struct Node {
    int key, val, freq;
    Node *prev, *next;
    Node(int key, int val)
        : key(key), val(val), prev(nullptr), next(nullptr), freq(1) {}
  };

  struct Allocator {
    Node *freehead;
    int chunksize = 16;
    vector<void *> pools;
    Allocator() {
      pools.emplace_back(::operator new(chunksize * sizeof(Node)));
      freehead = static_cast<Node *>(pools[0]);
      for (int i = 0; i < chunksize; i++)
        freehead[i].next = i + 1 < chunksize ? &freehead[i + 1] : nullptr;    
    }

    ~Allocator() {
      static_assert(is_trivially_destructible<Node>::value,
                    "Node is not trivially destructible.");
      for (void *pool : pools)
        ::operator delete(pool);
    }

    Node *allocate(int key, int val) {
      if (!freehead) {
        pools.emplace_back(::operator new(chunksize * sizeof(Node)));
        Node *node = static_cast<Node *>(pools.back());
        for (int i = 0; i < chunksize; i++)
          node[i].next = i + 1 < chunksize ? &node[i + 1] : nullptr;
        freehead = node;
        chunksize *= 2;
      }
      Node *next = freehead->next;
      Node *node = new (freehead) Node(key, val);
      freehead = next;
      return node;
    }

    void deallocate(Node *p) {
      p->next = freehead;
      freehead = p;
    }
  } allocator;
  struct LinkedList {
    Node *head, *tail;
    void init(Node *head, Node *tail) {
      this->head = head;
      this->tail = tail;
      this->head->next = this->tail;
      this->tail->prev = this->head;
    }

    void addFirst(Node *node) {
      node->prev = head;
      node->next = head->next;
      head->next = node;
      node->next->prev = node;
    }

    void remove(Node *node) {
      node->prev->next = node->next;
      node->next->prev = node->prev;
    }

    Node *removeLast() {
      auto *res = tail->prev;
      remove(res);
      return res;
    }

    bool empty() { return head->next == tail; }
  };

  unordered_map<int, Node *> nodemp;
  unordered_map<int, LinkedList> freq;
  int cap, minFreq;

  void update(Node *node) {
    auto &list = freq[node->freq];
    list.remove(node);
    if (node->freq == minFreq && list.empty()) minFreq++;
    node->freq++;
    auto [it, ins] = freq.try_emplace(node->freq);
    if (ins)
      it->second.init(allocator.allocate(0, 0), allocator.allocate(0, 0));
    it->second.addFirst(node);
  }

  void removeOldest() {
    auto &list = freq[minFreq];
    auto *node = list.removeLast();
    nodemp.erase(node->key);
    allocator.deallocate(node);
  }

public:
  LFUCache(int capacity) : cap(capacity), minFreq(0) {
    freq[1].init(allocator.allocate(0, 0), allocator.allocate(0, 0));
  }

  int get(int key) {
    Node *node;
    if (auto it = nodemp.find(key); it == nodemp.end()) return -1;
    else node = it->second;
    update(node);
    return node->val;
  }

  void put(int key, int value) {
    if (!cap) return;
    auto &node = nodemp[key];
    if (node) {
      node->val = value;
      update(node);
      return;
    }

    if (nodemp.size() > cap) removeOldest();
    node = allocator.allocate(key, value);
    freq[1].addFirst(node);
    minFreq = 1;
  }
};

/**
 * 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);
 */

时空复杂度一样。