460. LFU 缓存（数据结构系列）

刺骨的言语ヽ痛彻心扉 2023-10-05 20:17 18阅读 0赞

#### 460. LFU 缓存 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

实现 LFUCache 类：

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

注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

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

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

## 解题思路 ##

## 代码 ##

class LFUCache {
        
        //key到val的映射，称之为KV表
        HashMap<Integer,Integer> keyToVal;
        //key到Freq的映射，称之为KF表
        HashMap<Integer,Integer> keyToFreq;
        //freq到key列表的映射，称之为FK表
        HashMap<Integer,LinkedHashSet<Integer>> freqToKeys;
    
        int minFreq;//记录最小的频次
        int cap;//记录LFU缓存的最大容量
        
        
        public LFUCache(int capacity) {
        
            keyToVal=new HashMap<>();
            keyToFreq=new HashMap<>();
            freqToKeys=new HashMap<>();
            this.cap=capacity;
            this.minFreq=0;//默认为0
        }
        
        public int get(int key) {
        
            if (!keyToVal.containsKey(key)) {
        
                return -1;
            }
            //增加key对应的freq
            increaseFreq(key);
    
            return keyToVal.get(key);
        }
    
        public void put(int key, int value) {
        
            if (this.cap <= 0) {
        
                return;
            }
            //key已存在
            if (keyToVal.containsKey(key)) {
        
                keyToVal.put(key, value);
                increaseFreq(key);
                return;
            }
            if (this.cap <= keyToVal.size()) {
        
                removeMinFreq();
            }
            keyToVal.put(key, value);
            keyToFreq.put(key, 1);
            freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
            freqToKeys.get(1).add(key);
            //新插入后最小的频次，就是刚插入的这个元素的频次：1
            this.minFreq = 1;
        }
    
        public void removeMinFreq() {
        
            //freq 最小的key列表
            LinkedHashSet<Integer> keyList = freqToKeys.get(this.minFreq);
            //如果有很多freq相同小的，就淘汰最早插入的
            int deleteKey = keyList.iterator().next();
            //更新FK表
            keyList.remove(deleteKey);
            if (keyList.isEmpty()) {
        
                freqToKeys.remove(this.minFreq);
            }
            //更新KV、KF表
            keyToVal.remove(deleteKey);
            keyToFreq.remove(deleteKey);
        }
    
        public void increaseFreq(int key) {
        
            int freq = keyToFreq.get(key);
            //更新KF表
            keyToFreq.put(key, freq + 1);
            //更新FK表
            //将key从freq对应的列表删除
            freqToKeys.get(freq).remove(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,因为最小的freq没有对应元素了，已经被删除了，所以minFreq要加1
                if (freq == this.minFreq) {
        
                    this.minFreq++;
                }
            }
    
        }
    }
    
    /**
     * 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);
     */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210224113618424.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70