LFU缓存（Leetcode460）

例题：

分析：

这道题可以用两个哈希表来实现，一个hash表（kvMap）用来存储节点，另一个hash表（freqMap）用来存储双向链表，链表的头节点代表最近使用的元素，离头节点越远的节点代表最近最少使用的节点。

注意：freqMap 的 key 为节点的使用频次。

下图是freqMap的结构：

这是kvMap： 它的key没有什么特殊含义，value是储存的节点

题目中调用get方法会增加元素的使用次数（freq），这时在freqMap中需要将该节点转移到对应的位置上（比如该节点使用了两次，那就把该节点转移到key为2的位置上去）

put方法分为两种情况：如果要添加的key不存在，说明是新元素，放到key为1的位置上，如果key存在，此时是修改操作，改变元素的value值，对应的频次+1，同样放到对应的位置上。

淘汰策略：要保证两个hash表中的节点数一致。

代码实现：

package leetcode;
 
import java.util.HashMap;
 
//设计LFU缓存
public class LFUCacheLeetcode460 {
 
    static class LFUCache {
 
        static class Node{
            Node prev;
            Node next;
            int key;
            int value;
            int freq = 1;
            public Node(){
 
            }
            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
 
        static class DoublyLinkedList{
            Node head;
            Node tail;
            int size;
 
            public DoublyLinkedList(){
                head = tail = new Node();
                head.next = tail;
                tail.prev = head;
            }
 
            //头部添加   head<->1<->2<->tail  添加3
            public void addFirst(Node node){
                Node oldFirst = head.next;
                oldFirst.prev = node;
                head.next = node;
                node.prev = head;
                node.next = oldFirst;
                size++;
            }
 
            //指定节点删除   head<->1<->2<->3<->tail  删除2
            public void remove(Node node){
                Node prev = node.prev;
                Node next = node.next;
                prev.next = next;
                next.prev = prev;
                size--;
            }
 
            //删除最后一个节点
            public Node removeLast(){
                Node last = tail.prev;
                remove(last);
                return last;
            }
 
            //判断双向链表是否为空
            public boolean isEmpty(){
                return size == 0;
            }
        }
 
        private HashMap<Integer,Node> kvMap = new HashMap<>();
        private HashMap<Integer,DoublyLinkedList> freqMap = new HashMap<>();
        private int capacity;
        private int minFreq = 1;
        public LFUCache(int capacity) {
            this.capacity = capacity;
        }
 
        /*
        * 获取节点  不存在：返回 -1
        *           存在： 增加节点的使用频次，将其转移到频次+1的链表中
        *           判断旧节点所在的链表是否为空，更新最小频次minFreq
        * */
        public int get(int key) {
            if(!kvMap.containsKey(key)){
                return -1;
            }
            Node node = kvMap.get(key);
            //先删除旧节点
            DoublyLinkedList list = freqMap.get(node.freq);
            list.remove(node);
            //判断当前链表是否为空，为空可能需要更新最小频次
            if(list.isEmpty() && node.freq == minFreq){
                minFreq++;
            }
            node.freq++;
            //将新节点放入新位置，可能该频次对应的链表不存在，不存在需要创建
            freqMap.computeIfAbsent(node.freq, k -> new DoublyLinkedList())
                    .addFirst(node);
            return node.value;
        }
 
        /*
        * 更新
        *     将节点的value更新，增加节点的使用频次，将其转移到频次+1的链表中
        * 新增
        *     检查是否超过容量，若超过，淘汰minFreq链表的最后节点
        *     创建新节点，放入kvMap，并加入频次为 1 的双向链表
        * */
        public void put(int key, int value) {
            if(kvMap.containsKey(key)){ //更新
                Node node = kvMap.get(key);
                DoublyLinkedList list = freqMap.get(node.freq);
                list.remove(node);
                if(list.isEmpty() && node.freq == minFreq){
                    minFreq++;
                }
                node.freq++;
                freqMap.computeIfAbsent(node.freq, k -> new DoublyLinkedList())
                        .addFirst(node);
                node.value = value;
            }else{ //新增
                //先判断容量是否已满
                if(kvMap.size() == capacity){
                    //执行淘汰策略
                    Node node = freqMap.get(minFreq).removeLast();
                    kvMap.remove(node.key);
                }
                Node node = new Node(key, value);
                kvMap.put(key, node);
                //加入频次为1的双向链表
                freqMap.computeIfAbsent(1, k -> new DoublyLinkedList())
                        .addFirst(node);
                minFreq = 1;
            }
        }
    }
 
    public static void main(String[] args) {
        LFUCache cache = new LFUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 1 freq=2
        cache.put(3, 3);
        System.out.println(cache.get(2)); // -1
        System.out.println(cache.get(3)); // 3 freq=2
        cache.put(4, 4);
        System.out.println(cache.get(1)); // -1
        System.out.println(cache.get(3)); // 3  freq=3
        System.out.println(cache.get(4)); // 4  freq=2
 
    }
}