LeetCode_数据结构设计_困难_460.LFU 缓存

约定不等于承诺〃 2023-10-06 22:39 41阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）
 *   *  3.1.思路1
     *  3.2.思路2

## 1.题目 ##

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

**示例：**

输入：
    ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
    [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
    输出：
    [null, null, null, 1, null, -1, 3, null, -1, 3, 4]
    
    解释：
    // cnt(x) = 键 x 的使用计数
    // cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
    LFUCache lfu = new LFUCache(2);
    lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
    lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
    lfu.get(1);      // 返回 1
                     // cache=[1,2], cnt(2)=1, cnt(1)=2
    lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
                     // cache=[3,1], cnt(3)=1, cnt(1)=2
    lfu.get(2);      // 返回 -1（未找到）
    lfu.get(3);      // 返回 3
                     // cache=[3,1], cnt(3)=2, cnt(1)=2
    lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
                     // cache=[4,3], cnt(4)=1, cnt(3)=2
    lfu.get(1);      // 返回 -1（未找到）
    lfu.get(3);      // 返回 3
                     // cache=[3,4], cnt(4)=1, cnt(3)=3
    lfu.get(4);      // 返回 4
                     // cache=[3,4], cnt(4)=2, cnt(3)=3

**提示：**  
0 <= capacity <= 104  
0 <= key <= 105  
0 <= value <= 109  
最多调用 2 \* 105 次 get 和 put 方法

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/lfu-cache

## 2.思路 ##

（1）三哈希表  
思路参考[算法题就像搭乐高：手把手带你拆解 LFU 算法][LFU]。

（2）双哈希表  
思路参考[本题官方题解][Link 1]。

（1）我们定义两个哈希表 `freqMap` 和 `keyMap`：

*  第一个 freqMap 以频率 `freq` 为索引，每个索引存放一个双向链表 `DoublyLinkedList`，这个链表里存放所有使用频率为 freq 的缓存，缓存里存放三个信息，分别为键 key，值 value，以及使用频率 freq，这三个信息使用 `Node` 类进行封装。

Map<Integer, DoublyLinkedList> freqMap;
    
    class Node {
        
        int key, val, freq;
        Node prev, next;
        
        Node() {
        
            this(-1, -1, 0);
        }
        
        Node(int key, int val, int freq) {
        
            this.key = key;
            this.val = val;
            this.freq = freq;
        }
    }

*  第二个 keyMap 以键值 `key` 为索引，每个索引存放对应缓存在 freqMap 中链表里的内存地址，即 `Node 对象`，这样我们就能利用两个哈希表来使得两个操作的时间复杂度均为 O(1)。同时需要记录一个当前缓存最少使用的频率 `minFreq`，这是为了删除操作服务的。

Map<Integer, Node> keyMap;

（2）对于 `get(key)` 操作，我们能通过索引 key 在 `keyMap` 中找到缓存在 `freqMap` 中的链表的内存地址，即对应的 `Node 对象`：

*  如果不存在直接返回 -1；
 *  如果存在，我们能获取到对应缓存的相关信息，这样我们就能知道缓存的键值还有使用频率，直接返回 key 对应的值即可。除此之外，get 操作后这个缓存的使用频率加 1 了，所以我们需要**更新缓存在哈希表 freqMap 中的位置**。已知这个缓存的键 key，值 value，以及使用频率 freq，那么**该缓存应该存放到 freqMap 中 freq + 1 索引下的链表中**。所以我们在当前链表中 O(1) 删除该缓存对应的节点，根据情况更新 minFreq 值，然后将其 O(1) 插入到 freq + 1 索引下的链表头完成更新。这其中的操作复杂度均为 O(1)。

> 思考：**为什么是插入到链表头？**  
> 答：这其实是为了保证缓存在当前链表中从链表头到链表尾的插入时间是有序的，为下面的删除操作服务。

（3）对于 `put(key, value)` 操作，我们先通过索引 key 在 keyMap 中查看是否有对应的缓存：

*  如果有的话，其实操作等价于 `get(key)` 操作，唯一的区别就是我们**需要将当前的缓存里的值更新为 value**；
 *  如果没有的话，相当于是新加入的缓存，如果缓存已经到达容量，需要先删除最近最少使用的缓存，再进行插入：
    
     *  先考虑**插入操作**，由于是新插入的，所以缓存的使用频率一定是 1，所以我们将缓存的信息插入到 freqMap 中 1 索引下的列表头即可，同时更新 keyMap\[key\] 的信息，以及更新 minFreq = 1。
     *  那么剩下的就是**删除操作**了，由于我们实时维护了 minFreq，所以我们能够知道 freqMap 里目前最少使用频率的索引，同时因为我们保证了链表中从链表头到链表尾的插入时间是有序的，所以 **freqMap\[minFreq\] 的链表中链表尾的节点即为使用频率最小且插入时间最早的节点**，我们删除它同时根据情况更新 minFreq ，整个时间复杂度均为 O(1)。

如下图展示了样例的部分操作过程：

![在这里插入图片描述][1f561d2e2ff743ae8f25b6faaea7608a.png]

![在这里插入图片描述][f5aeea6babc74b188ab71691d82a9a1d.png]

![在这里插入图片描述][a194bcdac405471fb7ada2c45baf617e.png]  
![在这里插入图片描述][205d458f65a74932bc203e539ef54a6d.png]

相关题目：  
[LeetCode\_数据结构设计\_中等\_146.LRU 缓存][LeetCode_146.LRU]

## 3.代码实现（Java） ##

### 3.1.思路1 ###

//思路1————三哈希表
    class LFUCache {
        
        
        // LFU 缓存的最大容量
        int capacity;
        // LFU 缓存最小的频次
        int minFreq;
        // key 到 value 的映射
        HashMap<Integer, Integer> keyToValue;
        // key 到 freq 的映射
        HashMap<Integer, Integer> keyToFreq;
        // freq 到 key 列表的映射，此处的 key 可能有多个
        HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
        
        public LFUCache(int capacity) {
        
            this.capacity = capacity;
            this.minFreq = 0;
            this.keyToValue = new HashMap<>();
            this.keyToFreq = new HashMap<>();
            this.freqToKeys = new HashMap<>();
        }
        
        public int get(int key) {
        
            if (!keyToValue.containsKey(key)) {
        
                //未找到该 key
                return -1;
            } else {
        
                //找到该 key，则其频率加一
                increaseFreq(key);
                return keyToValue.get(key);
            }
        }
        
        public void put(int key, int value) {
        
            if (this.capacity <= 0) {
        
                return;
            }
            if (keyToValue.containsKey(key)) {
        
                //若 key 已存在，修改其对应的 value 即可
                keyToValue.put(key, value);
                //key 的频率加一
                increaseFreq(key);
                return;
            }
            //若 key 不存在，则需要将其插入
            if (this.capacity <= keyToValue.size()) {
        
                //LFU 缓存容量已满，则需要淘汰一个 freq 最小的 key
                removeMinFreqKey();
            }
            //将 (key, value) 加入到 keyToValue 中
            keyToValue.put(key, value);
            //将 (key, 1) 加入到 keyToFreq 中
            keyToFreq.put(key, 1);
            //更新 freqToKeys
            freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
            freqToKeys.get(1).add(key);
            //插入新 key 后 minFreq 肯定是 1
            this.minFreq = 1;
        }
        
        // key 的频率加一
        public void increaseFreq(int key) {
        
            //1.更新 keyToFreq
            int freq = keyToFreq.get(key);
            keyToFreq.put(key, freq + 1);
            
            //2.更新 freqToKeys
            //将 key 从 freq 对应的列表中删除
            freqToKeys.get(freq).remove(key);
            //将 key 加入 freq + 1 对应的列表中
            freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
            freqToKeys.get(freq + 1).add(key);
            //如果 freq 对应的列表为空，则移除这个 freq
            if (freqToKeys.get(freq).isEmpty()) {
        
                freqToKeys.remove(freq);
                //如果这个 freq 恰好是 minFreq，则更新 minFreq
                if (freq == this.minFreq) {
        
                    this.minFreq++;
                }
            }
        }
        
        //淘汰一个 freq 最小的 key
        public void removeMinFreqKey() {
        
            //从 freqToKeys 中找到 freq = minFreq 的列表
            LinkedHashSet<Integer> keysList = freqToKeys.get(this.minFreq);
            // keysList 中最先加入的 key 就是应该被淘汰的 key
            int removedKey = keysList.iterator().next();
            keysList.remove(removedKey);
            if (keysList.isEmpty()) {
        
                //删除 removedKey 后，keysList 为空
                freqToKeys.remove(this.minFreq);
                /*
                    此处不需要更新 minFreq，具体原因如下：
                    removeMinFreqKey() 在 put() 中插入新 key 时可能会调用，而 put() 的代码中，
                    插入新 key 时一定会把 minFreq 更新成 1，所以此处无需更新 minFreq
                */
            }
            //删除 keyToValue 中的 removedKey
            keyToValue.remove(removedKey);
            //删除 keyToFreq 中的 removedKey
            keyToFreq.remove(removedKey);
        }
    }
    /**
     * 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);
     */

### 3.2.思路2 ###

//思路2————双哈希表
    class LFUCache {
        
        //总容量
        int capacity;
        //最小频率
        int minFreq;
    
        Map<Integer, Node> keyMap;
        Map<Integer, DLinkedList> freqMap;
    
        public LFUCache(int capacity) {
        
            this.capacity = capacity;
            this.minFreq = 0;
            this.keyMap = new HashMap<>();
            this.freqMap = new HashMap<>();
        }
        
        public int get(int key) {
        
            Node node = keyMap.get(key);
            if (node == null) {
        
                return -1;
            }
            int value = node.value;
            int freq = node.freq;
            /*
                当前节点 node 已经被访问过了，因此其频率应该应该变为 freq + 1，
                所以需要从原本频率为 freq 所对应的双向链表中删除该节点 node
            */
            freqMap.get(freq).removeNode(node);
            //如果频率为 freq 所对应的双向链表为空，我们需要在哈希表中删除，且更新 minFreq
            if (freqMap.get(freq).size == 0) {
        
                //删除频率为 freq 所对应的双向链表
                freqMap.remove(freq);
                //如果 freq 恰好等于 minFreq，则更新 minFreq
                if (minFreq == freq) {
        
                    minFreq++;
                }
            }
            //从 freqMap 中获取频率为 freq + 1 所对应的双向链表 list，如果没有则创建
            DLinkedList list = freqMap.getOrDefault(freq + 1, new DLinkedList());
            Node newNode = new Node(key, value, freq + 1);
            //将 newNode 插入到 list 的头部
            list.addToHead(newNode);
            freqMap.put(freq + 1, list);
            keyMap.put(key, newNode);
            return value;
        }
        
        public void put(int key, int value) {
        
            if (keyMap.containsKey(key)) {
        
                //与 get 操作基本一致，除了需要更新缓存的值
                Node node = keyMap.get(key);
                int freq = node.freq;
                freqMap.get(freq).removeNode(node);
                if (freqMap.get(freq).size == 0) {
        
                    freqMap.remove(freq);
                    if (minFreq == freq) {
        
                        minFreq++;
                    }
                }
                DLinkedList list = freqMap.getOrDefault(freq + 1, new DLinkedList());
                Node newNode = new Node(key, value, freq + 1);
                list.addToHead(newNode);
                freqMap.put(freq + 1, list);
                keyMap.put(key, newNode);
            } else {
        
                //缓存已满，需要删除频率为 minFreq 所对应的双向链表中的尾节点
                if (keyMap.size() == capacity) {
        
                    //通过 minFreq 拿到 freqTable[minFreq] 链表的末尾节点
                    Node node = freqMap.get(minFreq).getTail();
                    keyMap.remove(node.key);
                    freqMap.get(minFreq).removeNode(node);
                    if (freqMap.get(minFreq).size == 0) {
        
                        freqMap.remove(minFreq);
                    }
                }
                DLinkedList list = freqMap.getOrDefault(1, new DLinkedList());
                Node newNode = new Node(key, value, 1);
                list.addToHead(newNode);
                freqMap.put(1, list);
                keyMap.put(key, newNode);
                minFreq = 1;
            }
        }
    }
    
    class Node {
        
        int key;
        int value;
        int freq;
        Node prev, next;
    
        public Node() {
        
            this(-1, -1, 0);
        }
    
        public Node(int key, int value, int freq) {
        
            this.key = key;
            this.value = value;
            this.freq = freq;
        }
    }
    
    class DLinkedList {
        
        int size;
        Node dummyHead, dummyTail;
    
        public DLinkedList() {
        
            size = 0;
            dummyHead = new Node();
            dummyTail = new Node();
            dummyHead.next = dummyTail;
            dummyHead.prev = dummyHead;
        }
    
        //将节点 node 添加到双向链表头部
        public void addToHead(Node node) {
        
            node.prev = dummyHead;
            node.next = dummyHead.next;
            dummyHead.next.prev = node;
            dummyHead.next = node;
            size++;
        }
    
        //从双向链表中移除节点 node
        public void removeNode(Node node) {
        
            node.next.prev = node.prev;
            node.prev.next = node.next;
            size--;
        }
    
        //获取尾节点
        public Node getTail() {
        
            return dummyTail.prev;
        }
    }
    
    /**
     * 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]: https://mp.weixin.qq.com/s/oXv03m1J8TwtHwMJEZ1ApQ
[Link 1]: https://leetcode.cn/problems/lfu-cache/solution/lfuhuan-cun-by-leetcode-solution/
[1f561d2e2ff743ae8f25b6faaea7608a.png]: https://img-blog.csdnimg.cn/1f561d2e2ff743ae8f25b6faaea7608a.png
[f5aeea6babc74b188ab71691d82a9a1d.png]: https://img-blog.csdnimg.cn/f5aeea6babc74b188ab71691d82a9a1d.png
[a194bcdac405471fb7ada2c45baf617e.png]: https://img-blog.csdnimg.cn/a194bcdac405471fb7ada2c45baf617e.png
[205d458f65a74932bc203e539ef54a6d.png]: https://img-blog.csdnimg.cn/205d458f65a74932bc203e539ef54a6d.png
[LeetCode_146.LRU]: https://blog.csdn.net/weixin_43004044/article/details/124601850