题解 | #LFU缓存结构设计# 详细版

题目介绍

一个缓存结构需要实现如下功能。
set(key, value)：将记录(key, value)插入该结构
get(key)：返回key对应的value值
但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；
如果调用次数最少的key有多个，上次调用发生最早的key被删除
这就是LFU缓存替换算法。

概念描述

简单来说，LFU缓存结构就是把数据按照访问的次数来进行排序，当缓存满的时候，则需要根据策略进行淘汰。

• 正常情况下，直接删除访问次数最少的那个数据；
• 当最少访问次数有多个不同的数据时，则删除最早没被访问的数据。

要想实现LFU缓存，其实并没有那么简单，需要注意的点很多，所以我们要想在面试过程中书写出来一个没有BUG的LFU缓存结构，就需要有一定的实现方向。从整体出发，再到具体实现。
那么现在就来带你一步一步实现LFU缓存结构。

算法实现

定义
先提取出我们需要注意的功能点：
1、容量有限。
2、需要通过key去访问。
3、对key操作时，key的访问次数会增加。
4、需要淘汰访问次数最少的那个key（有多个则淘汰掉最早没被访问的）。
5、题目要求 set和get方法的时间复杂度为O(1)。
所以，我们就可以根据上面的条件来定义出一些用到的属性了。

int capacity; //限制缓存的最大容量
HashMap<Integer,Integer> kv; //能够通过key获取到val
HashMap<Integer,Integer> kt; //能够通过key获取访问的次数times
/* 我们看到上面提出来的功能点4。
我们需要淘汰times做少的key，所以我们需要有times到key的映射
HashMap<Integer,Integer> tk;
但是会有多个key的访问次数相同，并且此时我们需要淘汰那个最先放进去缓存中的key，
这里我们可以利用LinkedHashSet，它会根据我们put进去的数据进行时间的排序。
所以为了兼顾这两者我们定义出下面的属性tk。
我们可以通过访问的次数times拿到所有访问次数为times的key的集合，这些key则会按照放进去的时间先后顺序存储，这就满足了我们的淘汰策略。
*/
HashMap<Integer,LinkedHashSet<Integer>> tk;
// 我们还需要记录最小的访问次数times，方便淘汰此略的使用
int minTimes;

那么，现在我们就可以来写出这个类了。

class LFUCache{
    int capacity; // 容量
    HashMap<Integer,Integer> kv; //能够通过key获取到val
    HashMap<Integer,Integer> kt; //能够通过key获取访问的次数times
    HashMap<Integer,LinkedHashSet<Integer>> tk; //能够通过times获取key
    int minTimes; // 记录访问的最少次数
}

public LFUCache(int capacity){
    this.kv= new HashMap<>();
    this.kt= new HashMap<>();
    this.tk= new HashMap<>();
    this.minTimes= 0; //刚开始的次数为0
    this.capacity= capacity;
}

我们一个简单的LFU结构肯定有两个必不可少的方法，get and set

public int get(int key){
}

public void set(int key,int value){
}

get
根据需求 get方法的流程大概如下图

那么现在我们就来根据流程实现

public int get(int key){
    if(!kv.containsKey(key)){
            return -1;
        }
        // 该key访问次数要加1
        increaseTimes(key);
        return kv.get(key);
}

至于increaseTimes方法的实现，我们先不着急，等总体的框架先形成了，再处理细节。
set
还是一样，我们先把put的流程画出来

那么还是一样根据流程图来实现代码

public void set(int key,int value){
        // 容量不合法
        if(this.capacity <= 0)
            return;

        /* key存在 */
        // 1.覆盖value
        if(kv.containsKey(key)){
            kv.put(key,value);
            //2.访问次数+1
            increaseTimes(key);
            return;
        }

        /* key不存在 */
        // 1、cache满了
        if(this.capacity <= kv.size()){
            // 淘汰Times最小的
            removeMinTimes();
        }

        // 2、cache没满
        // 先插入kv表
        kv.put(key,value);
        // kt表 首次插入，访问次数为1
        kt.put(key,1);

        // 下面步骤为淘汰策略做准备
        // 插入tk表 
        // 当times为1的所有的key的集合不存在时，就新建一个
        tk.putIfAbsent(1,new LinkedHashSet<Integer>());
        // 否则，则直接插入
        tk.get(1).add(key);
        // 插入后此时最小的times肯定就是1了
        this.minTimes = 1;
    }

好了，现在我们整个LFU缓存结构的雏形已经形成了，基本的get和set方法都已经有了，那么我们就来实现具体的方法了。
increaseTimes(int key)
这个方法是LFU中的核心方法，是将key的访问次数+1。
我们将所需要涉及到的集合先列出来:

1. kt表。需要将原来的key,times的映射改为key,times+1 。
2. tk表。需要将key从原来的times,set中去除，加入到times+1,set中去。（这里的set表示，访问次数为times的所有的key的集合）。

所以有了这波分析，还是一样，我们先来画流程图

private void increaseTimes(int key){
        // 拿到原来的times
        int times = kt.get(key);
        // 更新kt表
        kt.put(key,times+1);

        // 更新tk表
        // 将key从原来的times,set中去除
        tk.get(times).remove(key);
        // 将key加入到times+1,set中去
        // 但是还需要考虑times+1对应的set集合是否存在
        tk.putIfAbsent(times+1,new LinkedHashSet<Integer>());
        tk.get(times+1).add(key);
        // 此时基本已经完成了，但是我们还需要做一些细节处理
        // 当我们从原来的set集合中移除的时候，我们得考虑一下这个key是否为其最后一个
        if(tk.get(times).isEmpty()){
            // 如果是的话，则我们需要销毁对应的set集合
            tk.remove(times);
            // 如果times刚好为最小的，则需要更新minTimes
            if(times == this.minTimes){
                this.minTimes++;
            }
        }

    }

写到这里，是不是觉得离我们的目标越来越近，而且整个过程也很清晰？那么下面我们就来实现最后一个核心方法！
removeMinTimes()
在一开始我们就有说到淘汰的策略，主要分为两种情况：
1、当最小的times中，只有一个key时，则直接淘汰
2、否则，则需要淘汰最早没被访问的key

这个方法其实实现起来不难，难点是在原来设计用什么数据结构来解决我们的难点。
所以我们直接实现代码：

private void removeMinTimes(){
        // 获取最小的times的set集合
        LinkedHashSet<Integer> set = tk.get(this.minTimes);

        // 这里是直接将两个步骤结合起来，利用了LinkedHashSet这个数据结构底层的设计
        // LinkedHashSet底层是按照key放进去的时间先后进行排序的
        // 所以此时set集合中的第一个即为需要删除的key
        int delKey = set.iterator().next();

        // 移除掉
        set.remove(delKey);
        if(set.isEmpty()){
            tk.remove(this.minTimes);
        }
        // 更新kv表
        kv.remove(delKey);
        // 更新tk表
        tk.remove(delKey);

    }

代码很简单，就是将这个key从对应的set中移除掉，然后再在kv和tk表中移除掉即可。

但是，细心的人应该会发现，我们将minTimes对应的key移除掉，如果这个key刚好只有一个，没有多个，我们的minTimes不是需要更新了吗？(tips: minTimes为最小的访问次数)
如果发现了这一点的同学，确实考虑得很细节，正常情况来说，肯定是需要更新这个值的，
但是，我们来看一下 removeMinTimes() 这个方法是在什么时候调用的？在put进去新的 k,v 键值对的之后，cache满了我们才需要去进行removeMinTimes。注意，put进去的是新的，所以我们在put方法里面，已经将这个minTimes更新为1了，是不是很细节哈哈哈。

到这里，我们整个LFU缓存结构的设计就已经结束了，我们只需要将上面的方法拼在一起，则可以得到一个完成的LFU了。

END
给出这道题目的代码

import java.util.*;


public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        // write code here
        LRUCache lru = new LRUCache(k);
        int len = 0;
        for(int i = 0; i < operators.length; i++){
            if(operators[i][0] == 2)
                len++;
        }
        // 返回数组
        int[] res = new int[len];
        len = 0;
        for(int i = 0; i < operators.length; i++){
            if(operators[i][0] == 1){
                lru.set(operators[i][1],operators[i][2]);
            }else{
                res[len++] = lru.get(operators[i][1]);
            }
        }
        return res;
    }
}
class LRUCache{
    int capacity;
    HashMap<Integer,Integer> kv;
    HashMap<Integer,Integer> kt;
    HashMap<Integer,LinkedHashSet<Integer>> tk;
    int minTimes;

    public LRUCache(int capacity){
        this.kv= new HashMap<>();
        this.kt= new HashMap<>();
        this.tk= new HashMap<>();
        this.minTimes= 0; //刚开始的次数为0
        this.capacity= capacity;
    }

    public int get(int key){
        if(!kv.containsKey(key)){
            return -1;
        }
        // 该key访问次数要加1
        increaseTimes(key);
        return kv.get(key);
    }


    public void set(int key,int value){
        // 容量不合法
        if(this.capacity <= 0)
            return;

        /* key存在 */
        // 1.覆盖value
        if(kv.containsKey(key)){
            kv.put(key,value);
            //2.访问次数+1
            increaseTimes(key);
            return;
        }

        /* key不存在 */
        // 1、cache满了
        if(this.capacity <= kv.size()){
            // 淘汰Times最小的
            removeMinTimes();
        }

        // 2、cache没满
        // 先插入kv表
        kv.put(key,value);
        // kt表 首次插入，访问次数为1
        kt.put(key,1);
        // 插入tk表 
        // 当times为1的所有的key的集合不存在时，就新建一个
        tk.putIfAbsent(1,new LinkedHashSet<Integer>());
        // 否则，则直接插入
        tk.get(1).add(key);
        // 插入后此时最小的times肯定就是1了
        this.minTimes = 1;
    }


    private void increaseTimes(int key){
        // 拿到原来的times
        int times = kt.get(key);
        // 更新kt表
        kt.put(key,times+1);

        // 更新tk表
        // 将key从原来的times,set中去除
        tk.get(times).remove(key);
        // 将key加入到times+1,set中去
        // 但是还需要考虑times+1对应的set集合是否存在
        tk.putIfAbsent(times+1,new LinkedHashSet<Integer>());
        tk.get(times+1).add(key);
        // 此时基本已经完成了，但是我们还需要做一些细节处理
        // 当我们从原来的set集合中移除的时候，我们得考虑一下这个key是否为其最后一个
        if(tk.get(times).isEmpty()){
            // 如果是的话，则我们需要销毁对应的set集合
            tk.remove(times);
            // 如果times刚好为最小的，则需要更新minTimes
            if(times == this.minTimes){
                this.minTimes++;
            }
        }

    }

    private void removeMinTimes(){
        // 获取最小的times的set集合
        LinkedHashSet<Integer> set = tk.get(this.minTimes);

        // 这里是直接将两个步骤结合起来，利用了LinkedHashSet这个数据结构底层的设计
        // LinkedHashSet底层是按照key放进去的时间先后进行排序的
        // 所以此时set集合中的第一个即为需要删除的key
        int delKey = set.iterator().next();

        // 移除掉
        set.remove(delKey);
        if(set.isEmpty()){
            tk.remove(this.minTimes);
        }
        // 更新kv表
        kv.remove(delKey);
        // 更新tk表
        tk.remove(delKey);

    }
}

复杂度分析：
LFU缓存结构的set和get都满足
时间复杂度：。for循环的次数
空间复杂度：。返回数组的空间大小。