【LFU算法】的实现——Java

什么是LFU算法？

1. LFU算法淘汰的是使用频率最小的
2. 它的名字是：Least Frequently Used algorithm
3. 既然是跟频率有关的，那么就需要用数据结构来存放key-频率。

怎么写？

1. 首先，列举基本的需求

   1. 在调用get(key)时，返回对应的value
   2. get 或 put 之后，这个key的频率 +1；
   3. 如果在容量满的时候进行put操作，那么就要删除频率最低的（通过频率找到key），如果有多个频率相同，删除最老的那个
   4. 以上操作希望是**O(1)**时间复杂度

2. 根据要求，选择数据结构解决以上问题

   1. 用HashMap来存放key - value
   2. 用HashMap 来存放key-frequency，这样就可以通过key来快速找到它的频率
   3. 这一点是LFU算法的核心
      1. 需要一个frequency 到key的映射
      2. 需要一个变量minFreq来存放最小的频率
      3. 需要一个链表来存放一个freq对应的多个key
      4. freq对应的key列表是有时序的
      5. 希望能快速插入删除key列表中的元素
      6. 综上：frequency到key的映射使用HashMap<Integer, LinkedHashSet< Integer>>

3. 编码：就是按照数据结构来填空几个函数

   1. 在increaseFreq函数中，怎么修改freqToKey表呢？

      分三步

      1. 删除key项
      2. 如果freq+1不存在，创建
      3. 在freq+1的列表中，添加key
      4. 如果原来的freq列表因为本次操作，空了，那就删掉它
      5. 如果freq 是等于最小freq的，那么删除了freq列表后，最小freq需要++（因为freq+1 肯定存在）

   2. deleteMinFreq函数要做什么？

      1. 处理fk表

         1. 获取到minFreq对应的列表

         2. 获取列表第一个元素key

         3. 在列表中把key删除

         4. 如果列表空了，删除这个列表（minFreq怎么更新？）

            minFreq不用更新，因为删除这个minFreq之后肯定要插入一个新元素，到时候会处理minFreq

      2. 处理kf表

         1. 删除minFreq对应得元素

      3. 处理kv表

         1. 删除这个key

   class LFUCache {
       
       int minFreq = 0;
       int cap; //容量
       HashMap<Integer, Integer> keyToValue; 
       HashMap<Integer, Integer> keyToFreq; 
       HashMap<Integer, LinkedHashSet< Integer>> freqToKey; 
   
       // 构造容量为 capacity 的LFU缓存
       public LFUCache(int capacity) {
           this.cap = capacity;
           keyToValue = new HashMap<>();
           keyToFreq = new HashMap<>();
           freqToKey = new HashMap<>(); 
       }
       
       // 在缓存中查询 key
       public int get(int key) {
           
           if(keyToValue.containsKey(key)){
               increaseFreq(key);//增加这个key的频率
               return keyToValue.get(key);
           }
           return -1;
       }
       
       // (重点)将 key 和 val 存入缓存
       public void put(int key, int val) {
       
           //如果已经存在这个key,直接插入
          	if(keyToValue.containsKey(key){
          		keyToValue.put(key,value);
          		increaseFreq(key);//增加这个key的频率
          		return;
          	}
           
           if(keyToValue.size() == cap){
           		//缓存空间已满
           		removeMinFreq();
           }
           
           
           //更改kv，直接插入
           keyToValue.put(key,value);
           //更改kf，直接插入
           keyToFreq.put(key, 1);
           
           //更改fk
           freqToKey.putIfAbsent(1, new LinkedHashSet<>());
           //把key添加到这个队列
           freqToKey.get(1).add(key);
           //更改minFreq
           minFreq = 1;
       }
       
       public void increaseFreq(int key){
   
    		int freq = keyToFreq.get(key); //获取到对应的freq 
    		
       	//修改kf表
       	keyToFreq.put(key, freq + 1); 
   
       	//修改fk表
       		//删除原来的key
       	LinkedHashSet<>() Keys = freqToKey.get(freq);
       	Keys.remove(key);
       	if(Keys.isEmpty()){
       		freqToKey.remove(freq);
       		if(freq == this.minFreq){
       			this.minFreq++;
       		}
       	}
   
       	//把key插入到另一个freq中
     		freqToKey.putIfAbsent(freq + 1, new LinkedHashSet<>() );
     		freqToKey.get(freq + 1).add(key);
     	}
     	
     	private void removeMinFreqKey() {
            // freq 最小的 key 列表
            LinkedHashSet<Integer> keyList = freqToKeys.get(this.minFreq);
            // 其中最先被插入的那个 key 就是该被淘汰的 key
            int deletedKey = keyList.iterator().next();
            /* 更新 FK 表 */
            keyList.remove(deletedKey);
            if (keyList.isEmpty()) {
                freqToKeys.remove(this.minFreq);
                // 问：这里需要更新 minFreq 的值吗？
            }
            /* 更新 KV 表 */
            keyToVal.remove(deletedKey);
            /* 更新 KF 表 */
            keyToFreq.remove(deletedKey);
    	}	
   }
   

   参考资料

   Labuladong大神的解析