题解 | #设计LFU缓存结构#

设计LFU缓存结构

http://www.nowcoder.com/practice/93aacb4a887b46d897b00823f30bfea1

题意整理

设计一个缓存结构，实现set、get功能。
set(key, value)：将记录(key, value)插入该结构。get(key)：返回key对应的value值。
缓存结构中最多存放k条记录，如果超过k条记录，则根据策略删掉一条记录。
删除策略为：删掉调用次数最少的记录，如果调用次数最少的记录有多条，则删掉上次调用发生最早的key。

方法一（双哈希表）

1.解题思路

首先定义两个Map，分别记为cache和freqMap。cache用于存储缓存，键为缓存的键，值为key、value组成的Node，freqMap用于存储频次，键为某个Node调用次数，值为对应频次的双向链表。然后定义一个变量min记录最小调用次数。
对于get方法，如果cache不包含对应的key，直接返回-1。如果包含，则找到对应的node，更新其调用的频次。并返回node对应的value。
对于set方法，如果cache不包含对应的key，并且容量达到上限容量，这时候要考虑删除一条记录。首先根据最小调用次数找到对应的双向链表，然后删掉双向链表的第一个node，同时从cache中移除掉对应的key。如果cache包含对应的key，则新建一个node，将其放入cache缓存，并在频次为1的双向链表添加该node。

图解展示： alt

2.代码实现

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) {
        //记录get调用的次数
        int cnt=0;
        for(int[] opera:operators){
            if(opera[0]==2){
                cnt++;
            }
        }
        //根据cnt新建结果数组
        int[] res=new int[cnt];
        int id=0;
        //新建缓存结构
        LFUCache lfu=new LFUCache(k);
        for(int[] opera:operators){
            //执行set操作
            if(opera[0]==1){
                lfu.set(opera[1],opera[2]);
            }
            //执行get操作
            else{
                int value=lfu.get(opera[1]);
                res[id++]=value;
            }
        }
        return res;
    }
    
    
}

class LFUCache{
    //定义Node结构，包含一个key和一个value，并初始化调用次数freq为1
    class Node{
        int key;
        int value;
        int freq=1;
        
        Node(int key,int value){
            this.key=key;
            this.value=value;
        }
    }
    
    //用于存储缓存，键为缓存的键，值为key、value组成的Node
    Map<Integer,Node> cache;
    //用于存储频次，键为某个Node调用次数，值为对应频次的双向链表
    Map<Integer,LinkedHashSet<Node>> freqMap;
    //缓存的容量
    int capacity;
    //记录最小调用次数
    int min;
    
    //初始化
    public LFUCache(int capacity){
        this.capacity=capacity;
        cache=new HashMap<>(capacity);
        freqMap=new HashMap<>();
    }
    
    //返回key对应的value值
    public int get(int key){
        //如果缓存中不存在key，直接返回-1
        if(!cache.containsKey(key)){
            return -1;
        }
        //找到对应的node
        Node node=cache.get(key);
        //更新调用频次
        freqInc(node);
        return node.value;
    }
    
    //将记录(key,value)插入缓存结构
    public void set(int key,int value){
        //如果缓存中已经存在这个key
        if(cache.containsKey(key)){
            //找到对应的node，设置值为value，更新频次
            Node node=cache.get(key);
            node.value=value;
            freqInc(node);
        }
        //如果缓存中不存在这个key
        else{
            //如果缓存的大小达到了容量capacity
            if(cache.size()==capacity){
                //根据策略从双向链表删掉对应的节点
                Node deadNode=removeNode();
                //从缓存中移除对应的key
                cache.remove(deadNode.key);
            }
            //新建一个Node，将其放入缓存，并在双向链表添加该Node
            Node newNode=new Node(key,value);
            cache.put(key,newNode);
            addNode(newNode);
        }
        
    }
    
    //更新频次
    public void freqInc(Node node){
        //找到对应的双向链表，移除掉node
        int freq=node.freq;
        LinkedHashSet<Node> set=freqMap.get(freq);
        set.remove(node);
        //如果删掉的刚好是最小频次，并且只存在一个这样的node，需要更新min
        if(freq==min&&set.size()==0){
            min=freq+1;
        }
        //node对应的频次加1
        node.freq++;
        //找到node新的频次对应的双向链表
        LinkedHashSet<Node> newSet=freqMap.get(node.freq);
        if(newSet==null){
            //如果为空，新建一个，并放到缓存
            newSet=new LinkedHashSet<>();
            freqMap.put(node.freq,newSet);
        }
        //在新的频次对应的双向链表中添加node
        newSet.add(node);
    }
    
    //根据策略从双向链表删掉对应的节点
    public Node removeNode(){
        //找到最小频次对应的双向链表
        LinkedHashSet<Node> set=freqMap.get(min);
        //找到该链表中最早进来的node
        Node deadNode=set.iterator().next();
        //移除掉这个node
        set.remove(deadNode);
        return deadNode;
    }
    
    //在频次为1的链表中添加新的node
    public void addNode(Node node){
        //找到频次为1的链表
        LinkedHashSet<Node> set=freqMap.get(1);
        if(set==null){
            //如果为空，新建一个并放入频次map
            set=new LinkedHashSet<>();
            freqMap.put(1,set);
        }
        //添加node，并设置min为1
        set.add(node);
        min=1;
    }
}

3.复杂度分析

时间复杂度：get方法和set方法中均是 $O (1)$ 复杂度级别的操作，所以时间复杂度是 $O (1)$ 。
空间复杂度：假设缓存结构的容量为n，需要额外大小为n的cache哈希表以及最多大小为n的freqMap哈希表，所以空间复杂度为 $O (n)$ 。

方法二（自定义双向链表）

1.解题思路

思路和方法一大致相同，不过使用了自定义的双向链表。需要注意的地方有：1.如何从双向链表中添加节点？2.如何从双向链表中移除指定节点？3.如何确定双向链表中最早调用的key？4.如何判断双向链表是否为空？

对于如何从双向链表中添加节点，可以通过将新node添加到head节点之后，head.next节点之前。对于如何从双向链表中移除指定节点，只需改变它的前驱的next指针和后继的pre指针即可。对于如何确定双向链表中最早调用的key，因为是从头节点后面加入的，所以最早调用的node一定是tail指针的前一个。对于如何判断双向链表是否为空，只需看head节点的next指针是否指向tail节点。

2.代码实现

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) {
        //记录get调用的次数
        int cnt=0;
        for(int[] opera:operators){
            if(opera[0]==2){
                cnt++;
            }
        }
        //根据cnt新建结果数组
        int[] res=new int[cnt];
        int id=0;
        //新建缓存结构
        LFUCache lfu=new LFUCache(k);
        for(int[] opera:operators){
            //执行set操作
            if(opera[0]==1){
                lfu.set(opera[1],opera[2]);
            }
            //执行get操作
            else{
                int value=lfu.get(opera[1]);
                res[id++]=value;
            }
        }
        return res;
    }
    
    
}

class LFUCache {
    //定义Node结构，包括一个key、value对，以及freq和两个指针
    class Node{
        int key;
        int value;
        int freq=1;
        Node pre;
        Node next;
        Node(){}
        Node(int key,int value){
            this.key=key;
            this.value=value;
        }
    } 
    
    //定义双向链表结构
    class DoubleLinkedList{
        //头节点和尾节点
        Node head;
        Node tail;

        //构造函数
        DoubleLinkedList(){
            head=new Node();
            tail=new Node();
            head.next=tail;
            tail.pre=head;
        }

        //从头节点后面添加节点
        public void addNode(Node node){
            node.next=head.next;
            head.next.pre=node;
            node.pre=head;
            head.next=node;
        }

        //移除掉指定节点
        public void removeNode(Node node){
            node.pre.next=node.next;
            node.next.pre=node.pre;
        }
    }
    
    //缓存Map
    Map<Integer,Node> cache;
    //频次Map
    Map<Integer,DoubleLinkedList> freqMap;
    //最小频次
    int min;
    //缓存上限容量
    int capacity;

    //初始化
    public LFUCache(int capacity) {
        cache=new HashMap<>(capacity);
        freqMap=new HashMap<>();
        this.capacity=capacity;
    }
    
    //返回key对应的value值
    public int get(int key) {
        //如果不存在key，直接返回-1
        if(!cache.containsKey(key)){
            return -1;
        }
        //找到对应node
        Node node=cache.get(key);
        //更新频次
        freqInc(node);
        return node.value;
    }
    
    //插入(key,value)记录
    public void set(int key, int value) {
        if(!cache.containsKey(key)){
            //如果达到容量上限
            if(cache.size()==capacity){
                //找到min频次对应的链表
                DoubleLinkedList doubleList=freqMap.get(min);
                //缓存中移除频次最小的最早进来的node
                cache.remove(doubleList.tail.pre.key);
                //链表中移除最早进来的node
                doubleList.removeNode(doubleList.tail.pre);
            }
            //新建一个node
            Node newNode=new Node(key,value);
            //放入缓存
            cache.put(key,newNode);
            //找到频次为1的链表
            DoubleLinkedList newDoubleList=freqMap.get(1);
            if(newDoubleList==null){
                //如果为空，则新建一个，并放入频次Map
                newDoubleList=new DoubleLinkedList();
                freqMap.put(1,newDoubleList);
            }
            //链表中添加新node
            newDoubleList.addNode(newNode);
            //更新最小频次
            min=1;
        }
        else{
            //如果存在node，直接找到node，更新value和频次freq
            Node node=cache.get(key);
            node.value=value;
            freqInc(node);
        }
    }

    //更新频次
    private void freqInc(Node node){
        int freq=node.freq;
        //找到node.freq对应的双向链表
        DoubleLinkedList doubleList=freqMap.get(freq);
        //从链表中移除node
        doubleList.removeNode(node);
        //如果node被移除后，链表为空，并且移除node的频次刚好等于min
        if(freq==min&&doubleList.head.next==doubleList.tail){
            //更新min
            min=freq+1;
        }
        //node频次加1
        node.freq++;
        //找到新频次对应的双向链表
        DoubleLinkedList newDoubleList=freqMap.get(node.freq);
        if(newDoubleList==null){
            //如果为空，则新建一个，并放入频次Map
            newDoubleList=new DoubleLinkedList();
            freqMap.put(node.freq,newDoubleList);
        }
        //在新的链表中添加这个node
        newDoubleList.addNode(node);
    }

}