Leetcode - 460 LFU cache (Design - hash table + bidirectional linked hash table + balanced binary tree (TreeSet))*

Hashtable + Balanced binary trees (TreeSet)

class LFUCache {
    
    class Node{
    
        int key;//key
        int val;//val
        int freq;// Frequency of use 
        int t;// The last time it was used 
        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>{
    
        // When the frequency of use is different   Sort by usage frequency in ascending order 
        public int compare(Node n1,Node n2){
    
            if(n1.freq != n2.freq)
                return n1.freq - n2.freq;
            else// When the frequency of use is the same   Sort in ascending order of time used 
                return n1.t - n2.t;
        }
    }
    private Map<Integer,Node> map;
    private TreeSet<Node> set;
    // Time counter   from 0 Start 
    private int t;
    //LFU The capacity of the cache 
    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) {
    
        // Add one to the time counter 
        this.t += 1;
        if(map.get(key) == null){
    
            return -1;
        }
        else{
    
            Node node = map.get(key);
            set.remove(node);
            // The key Frequency of use plus one 
            node.freq = node.freq + 1;
            // to update key The last time used 
            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;
         // If key Already exists in map in 
         if(map.get(key)!=null){
    
             Node node = map.get(key);
             set.remove(node);
             // to update val value 
             node.val = value;
             // Update last used time 
             node.t = this.t;
             // Use frequency plus one 
             node.freq = node.freq + 1;
             set.add(node);
             map.put(key,node);
         }else{
    
             // If LFU There is no space in the cache   Pop up the most recently unused 
             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); */

Hashtable + Double linked list

class LFUCache {
    
    class Node{
    
        int key;//key
        int val;//val
        int freq;//key  Frequency of use 
        Node prev;// Precursor pointer 
        Node next;// After drive pointer 
        public Node(int key,int val,int freq){
    
            this.key = key;
            this.val = val;
            this.freq = freq;
        }
    }
    class DoublyLinkedList{
    
         // Double linked list 
         Node head;// The head pointer 
         Node tail;// Tail pointer 
         int size;// Number of nodes in the bidirectional linked list 
         public DoublyLinkedList(){
    
             head = new Node(0,0,0);// Head node 
             tail = new Node(0,0,0);// Tail node 
             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;
    // Every frequency   The corresponding nodes are placed in the bidirectional linked list   The two-way linked list is sorted by operation time   The longer the node has not been operated, the more backward it is in the linked list 
    private Map<Integer,DoublyLinkedList> freqMap;
    //LFU Cache capacity 
    private int capacity;
    // Minimum operating frequency 
    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); */