LFU算法

最不经常使用算法（LFU）：这个缓存算法使用一个计数器来记录条目被访问的频率。通过使用LFU缓存算法，最低访问数的条目首先被移除。

LFU 算法的难度大于 LRU 算法，因为 LRU 算法相当于把数据按照时间排序，这个需求借助链表很自然就能实现，你一直从链表头部加入元素的话，越靠近头部的元素就是新的数据，越靠近尾部的元素就是旧的数据，我们进行缓存淘汰的时候只要简单地将尾部的元素淘汰掉就行了。

而 LFU 算法相当于是淘汰访问频次最低的数据，如果访问频次最低的数据有多条，需要淘汰最旧的数据。把数据按照访问频次进行排序，而且频次还会不断变化。

01 LFU 缓存

请你为 最不经常使用（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) 的平均时间复杂度运行。

  1. 示例：
  3. 输入：
  4. ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
  5. [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
  6. 输出：
  7. [null, null, null, 1, null, -1, 3, null, -1, 3, 4]
  9. 解释：
  10. // cnt(x) = 键 x 的使用计数
  11. // cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
  12. LFUCache lfu = new LFUCache(2);
  13. lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
  14. lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
  15. lfu.get(1);      // 返回 1
  16.                  // cache=[1,2], cnt(2)=1, cnt(1)=2
  17. lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
  18.                  // cache=[3,1], cnt(3)=1, cnt(1)=2
  19. lfu.get(2);      // 返回 -1（未找到）
  20. lfu.get(3);      // 返回 3
  21.                  // cache=[3,1], cnt(3)=2, cnt(1)=2
  22. lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
  23.                  // cache=[4,3], cnt(4)=1, cnt(3)=2
  24. lfu.get(1);      // 返回 -1（未找到）
  25. lfu.get(3);      // 返回 3
  26.                  // cache=[3,4], cnt(4)=1, cnt(3)=3
  27. lfu.get(4);      // 返回 4
  28.                  // cache=[3,4], cnt(4)=2, cnt(3)=3
  31. 提示：
  33. 0 <= capacity <= 104
  34. 0 <= key <= 105
  35. 0 <= value <= 109
  36. 最多调用 2 * 105 次 get 和 put 方法
  38. 来源：力扣（LeetCode）
  39. 链接：https://leetcode-cn.com/problems/lfu-cache
  40. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我们定义两个哈希表，第一个 freq_table以频率 freq为索引，每个索引存放一个双向链表，这个链表里存放所有使用频率为 freq的缓存，缓存里存放三个信息，分别为键 key，值 value，以及使用频率 freq。第二个 key_table以键值 key为索引，每个索引存放对应缓存在 freq_table 中链表里的内存地址，这样我们就能利用两个哈希表来使得两个操作的时间复杂度均为 O(1)。同时需要记录一个当前缓存最少使用的频率 minFreq，这是为了删除操作服务的。

对于 get(key) 操作，我们能通过索引 key在 key_table中找到缓存在 freq_table中的链表的内存地址，如果不存在直接返回 -1，否则我们能获取到对应缓存的相关信息，这样我们就能知道缓存的键值还有使用频率，直接返回 key 对应的值即可。

但是我们注意到 get 操作后这个缓存的使用频率加一了，所以我们需要更新缓存在哈希表 freq_table 中的位置。已知这个缓存的键 key，值 value，以及使用频率 freq，那么该缓存应该存放到 freq_table 中 freq + 1 索引下的链表中。所以我们在当前链表中 O(1) 删除该缓存对应的节点，根据情况更新 minFreq 值，然后将其O(1) 插入到 freq + 1 索引下的链表头完成更新。这其中的操作复杂度均为 O(1)。你可能会疑惑更新的时候为什么是插入到链表头，这其实是为了保证缓存在当前链表中从链表头到链表尾的插入时间是有序的，为下面的删除操作服务。

对于 put(key, value) 操作，我们先通过索引 key 在 key_table中查看是否有对应的缓存，如果有的话，其实操作等价于 get(key) 操作，唯一的区别就是我们需要将当前的缓存里的值更新为 value。如果没有的话，相当于是新加入的缓存，如果缓存已经到达容量，需要先删除最近最少使用的缓存，再进行插入。

先考虑插入，由于是新插入的，所以缓存的使用频率一定是 1，所以我们将缓存的信息插入到 freq_table中 1 索引下的列表头即可，同时更新 key_table[key] 的信息，以及更新 minFreq = 1。

那么剩下的就是删除操作了，由于我们实时维护了 minFreq，所以我们能够知道 freq_table 里目前最少使用频率的索引，同时因为我们保证了链表中从链表头到链表尾的插入时间是有序的，所以 freq_table[minFreq] 的链表中链表尾的节点即为使用频率最小且插入时间最早的节点，我们删除它同时根据情况更新 minFreq，整个时间复杂度均为 O(1)。

class LFUCache {
private:
    struct Node {
        int key, val, freq;
        Node(int _key, int _val, int _freq) : key(_key), val(_val), freq(_freq) {}
    };
    int minfreq, capacity;
    // 通过 key 快速找到 node 地址
    unordered_map<int, list<Node>::iterator> key_table;
    unordered_map<int, list<Node>> freq_table;
public:
    LFUCache(int capacity) {
        minfreq = 0;
        this->capacity = capacity;
        key_table.clear();
        freq_table.clear();
    }

    int get(int key) {
        if (capacity == 0)
            return -1;
        // 寻找是否有这个 key
        auto it = key_table.find(key);
        // 没有找到这个 key
        if (it == key_table.end())
            return -1;
        // 找到了这个 key，获得存储该缓存结构体的迭代器
        list<Node>::iterator node = it->second;
        // 通过结构体，获得 key 对应的 val，该缓存使用的频次
        int val = node->val, freq = node->freq;
        // 找到该缓存，该缓存的频次需要加 1，所以先删除，再将该缓存放置在索引为 频次 + 1 处 
        // 1. 先删除 key 和 迭代器之间的映射
        freq_table[freq].erase(node);
        // 如果删除了之后，该链表没有节点
        if(freq_table[freq].empty()) {
            // 2. 将该条链表删除
            freq_table.erase(freq);
            // 3. 如果在 get 之前，该缓存是使用频次最小的，那么最小的频次就要 + 1
            if (minfreq == freq)
                minfreq += 1;
        }
        // 将该缓存插入到 freq + 1 中
        freq_table[freq + 1].push_front(Node(key, val, freq + 1));
        // 创建相应的映射关系
        key_table[key] = freq_table[freq + 1].begin();
        return val;
    }

    void put(int key, int value) {
        if (capacity == 0)
            return;
        auto it = key_table.find(key);
        if (it == key_table.end()) {
            // 缓存已满，需要进行删除
            if (key_table.size() == capacity) {
                // 通过 minFreq 拿到 freq_table[minFreq] 链表的末尾节点
                auto it2 = freq_table[minfreq].back();
                // 删除
                key_table.erase(it2.key);
                // 弹出末尾节点
                freq_table[minfreq].pop_back();
                if (freq_table[minfreq].empty()) {
                    // 如果改条链表没有节点，将该条链表删除
                    freq_table.erase(minfreq);
                }
            }
            freq_table[1].push_front(Node(key, value, 1));
            key_table[key] = freq_table[1].begin();
            minfreq = 1;
        } else {
            list<Node>::iterator node = it->second;
            int freq = node->freq;
            // 先删除该节点
            freq_table[freq].erase(node);
            if (freq_table[freq].empty()) {
                freq_table.erase(freq);
                if (minfreq == freq)
                    minfreq += 1;
            }
            freq_table[freq + 1].push_front(Node(key, value, freq + 1));
            key_table[key] = freq_table[freq + 1].begin();
        }
    }
};