LeetCode - 460 LFU 缓存(设计 - 哈希表+双向链表 哈希表+平衡二叉树（TreeSet)）*

哈希表 + 平衡二叉树(TreeSet)

class LFUCache {
    
    class Node{
    
        int key;//key
        int val;//val
        int freq;//使用频率
        int t;//最后一次被使用的时间
        public Node(int key,int val,int freq,int t){
    
            this.key = key;
            this.val = val;
            this.freq = freq;
            this.t = t;
        }
    }

    class NodeComparator implements Comparator<Node>{
    
        //当使用频率不一样时 按使用频率升序排序
        public int compare(Node n1,Node n2){
    
            if(n1.freq != n2.freq)
                return n1.freq - n2.freq;
            else//当使用频率一样的时候 按使用的时间升序排序
                return n1.t - n2.t;
        }
    }
    private Map<Integer,Node> map;
    private TreeSet<Node> set;
    //时间计数器 从0开始
    private int t;
    //LFU缓存的容量
    private int capacity;
    public LFUCache(int capacity) {
    
        this.map = new HashMap<>();
        this.set = new TreeSet<>(new NodeComparator());
        this.t = 0;
        this.capacity = capacity;
    }
    
    public int get(int key) {
    
        //时间计数器加一
        this.t += 1;
        if(map.get(key) == null){
    
            return -1;
        }
        else{
    
            Node node = map.get(key);
            set.remove(node);
            //该key的使用频率加一
            node.freq = node.freq + 1;
            //更新key最后被使用的时间
            node.t = this.t;
            set.add(node);
            map.put(key,node);
            return node.val;
        }
    }
    
    public void put(int key, int value){
    
          if(this.capacity == 0)
            return ;
          this.t += 1;
         //如果key本来就存在于map中
         if(map.get(key)!=null){
    
             Node node = map.get(key);
             set.remove(node);
             //更新val值
             node.val = value;
             //更新最后使用时间
             node.t = this.t;
             //使用频率加一
             node.freq = node.freq + 1;
             set.add(node);
             map.put(key,node);
         }else{
    
             //如果LFU缓存中没有空间 弹出最近最久未使用的
             if(set.size() >=  this.capacity){
    
                 map.remove(set.first().key);
                 set.remove(set.first());
             }
            Node node = new Node(key,value,1,this.t);
            map.put(key,node);
            set.add(node);
         }
    }
}

/** * 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); */

哈希表 + 双向链表

class LFUCache {
    
    class Node{
    
        int key;//key
        int val;//val
        int freq;//key 使用频率
        Node prev;//前驱指针
        Node next;//后驱指针
        public Node(int key,int val,int freq){
    
            this.key = key;
            this.val = val;
            this.freq = freq;
        }
    }
    class DoublyLinkedList{
    
         //双向链表
         Node head;//头指针
         Node tail;//尾指针
         int size;//双向链表中节点个数
         public DoublyLinkedList(){
    
             head = new Node(0,0,0);//头节点
             tail = new Node(0,0,0);//尾节点
             head.next = tail;
             tail.prev = head;
             size = 0;
         }
         public void addFirst(Node node){
    
               Node headNext = head.next;
               head.next = node;
               node.prev = head;
               node.next = headNext;
               headNext.prev = node;
               size += 1;
         }
         public void remove(Node node){
    
             Node nodePrev = node.prev;
             Node nodeNext = node.next;
             nodePrev.next = nodeNext;
             nodeNext.prev = nodePrev;
             size -= 1;
         }
         public Node getHead(){
    
              return head.next;
         }
         public Node getTail(){
    
               return tail.prev;
         }
    }
    // key, Node
    private Map<Integer,Node> keyMap;
    //每个频率 对应的节点放在双向链表中 双向链表按操作时间排序 越久没操作的节点在链表中的位置越靠后
    private Map<Integer,DoublyLinkedList> freqMap;
    //LFU缓存容量
    private int capacity;
    //最小操作频率
    private int minFreq;
    public LFUCache(int capacity) {
    
        keyMap = new HashMap<>();
        freqMap = new HashMap<>();
        this.capacity =  capacity;
        minFreq = 0;
    }
    
    public int get(int key) {
    
        if(this.capacity == 0)
           return -1;
        if(keyMap.get(key) == null){
    
            return -1;
        }
        else{
    
            Node node = keyMap.get(key);
            DoublyLinkedList dl = freqMap.get(node.freq);
            dl.remove(node);
            if(dl.size == 0){
    
                freqMap.remove(node.freq);
                if(node.freq == minFreq)
                   minFreq += 1;
                
            }
            node.freq += 1;
            if(freqMap.get(node.freq) == null)
               freqMap.put(node.freq,new DoublyLinkedList());
            freqMap.get(node.freq).addFirst(node);
            keyMap.put(key,node);
            return node.val;
        }
    }
    
    public void put(int key, int value) {
    
         if(this.capacity == 0)
           return ;
        if(keyMap.containsKey(key)){
    
            Node node = keyMap.get(key);
            DoublyLinkedList dl = freqMap.get(node.freq);
            dl.remove(node);
            if(dl.size == 0){
    
                freqMap.remove(node.freq);
                if(node.freq == minFreq)
                   minFreq += 1;
                
            }
            node.freq += 1;
            node.val = value;
            if(freqMap.get(node.freq) == null)
               freqMap.put(node.freq,new DoublyLinkedList());
            freqMap.get(node.freq).addFirst(node);
            keyMap.put(key,node);
        }
        else{
    
            if(keyMap.size() >= capacity){
    
                Node node = freqMap.get(minFreq).getTail();
                keyMap.remove(node.key);
                freqMap.get(minFreq).remove(node);
                if(freqMap.get(minFreq).size == 0)
                   freqMap.remove(minFreq);
            }
            Node newNode = new Node(key,value,1);
            if(freqMap.get(newNode.freq) == null)
               freqMap.put(newNode.freq,new DoublyLinkedList());
            freqMap.get(newNode.freq).addFirst(newNode);
            minFreq = 1;
            keyMap.put(key,newNode);
        }
    }
}

/** * 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); */