160ms O(1) solution using 1 HashMap


  • 1
    I
    public class LFUCache {
        //head and tail of double linked list
        //the closer to the tail, the less count and the less recently used
        private final Element head, tail;
        
        private final int capacity;
        
        //keyed hash array
        private final Element[] elementArray;
        
        //for every count as map key, the value is the most recent element 
        //e.g.
        //["LFUCache","set","set"]
        //[[2],[1,1],[2,2]]
        //after first "set", recentMap.get(0).val = 1
        //after second "set", recentMap.get(0).val = 2
        private final Map<Integer, Element> recentMap;
        
        //num elements added so far
        private int total = 0;
    
        public LFUCache(int capacity) {
            this.capacity = capacity;
            
            //1.5 times the hash array size to alleviate hash collision
            //also tested that the code works if we do not enlarge the hash array
            elementArray = new Element[capacity + (capacity>>1)];
            
            recentMap = new HashMap<>();
            
            head = new Element(0, 0);
            tail = new Element(0, 0);
            head.next = tail;
            tail.prev = head;
        }
        
        public int get(int key) {
            if(capacity == 0) {
                return -1;
            }
            
            final int hash = hash(key);
    
            final Element element = findInLink(key, hash);
            
            if(element == null) {
                return -1;
            }
            
            //maintain recentMap before increase the access count
            maintainMapThenIncreaseCount(element);
    
            //swap to be the first in double linked list that has same count
            swap(element);
            
            return element.val;
        }
        
        public void set(int key, int value) {
            if(capacity == 0) {
                return;
            }
            
            final int hash = hash(key);
            
            Element element = findInLink(key, hash);
            
            if (element == null) {
                assureCapacity();
                    
                final Element newElement = new Element(key, value);
                    
                //set as first of hash link
                newElement.linkNext = elementArray[hash];
                elementArray[hash] = newElement;
    
                //append to the end of double linked list or swap to be the first in double linked list that has 0 count
                appendOrSwap(newElement);
                return;
            }
            
            element.val = value;
            
            maintainMapThenIncreaseCount(element);
    
            //swap to be the first in double linked list that has same count
            swap(element);
        }
        
        private void maintainMapThenIncreaseCount(final Element element) {
            //if element is the most recent, set most recent to its next or remove the count from map
            if(recentMap.get(element.count) == element) {
                if(element.next.count == element.count) {
                    recentMap.put(element.count, element.next);
                }else {
                    recentMap.remove(element.count);
                }
            }  
            
            element.count++;
        }
        
        //method for newly created element
        //in such case, the input element is NOT in the double linked list
        private void appendOrSwap(final Element element) {
            if(!recentMap.containsKey(element.count)) {
                //add to end of double linked list
                element.prev = tail.prev;
                tail.prev.next = element;
                tail.prev = element;
                element.next = tail;
            }else{
                reorder(recentMap.get(element.count), element);
            }
            
            recentMap.put(element.count, element);
        }
        
        //method for element already in the double linked list
        private void swap(final Element element) {
            final Element temp;
            if(recentMap.containsKey(element.count)) {
                //same count already exists
                temp = recentMap.get(element.count);
            }else if(element.prev != head && element.prev.count < element.count) {
                //same count non-exist, element will be put before recentMap.get(element.prev.count)
                temp = recentMap.get(element.prev.count);
            }else {
                //same count non-exit, and either element.prev.count > element.count or element.prev == head
                temp = null;
            }
            
            if(temp != null){
                //take element out of double linked list
                element.prev.next = element.next;
                element.next.prev = element.prev;
    
                reorder(temp, element);
            }
            
            recentMap.put(element.count, element);
        }
        
        private void reorder(final Element first, final Element element) {
            final Element begin = first.prev;
            
            //begin <-> element <-> first;
            begin.next = element;
            element.next = first;
            first.prev = element;
            element.prev = begin;
        }
        
        private void assureCapacity() {
            if(++total > capacity) {
                removeLast();
            }
        }
        
        //the last element has smallest count and is least recently used
        private void removeLast() {
            final Element element = tail.prev;
            
            if(recentMap.get(element.count) == element) {
                recentMap.remove(element.count);
            }
            
            //take element out of double linked list
            tail.prev = tail.prev.prev;
            tail.prev.next = tail;
            
            //take element out of hash link
            final int hash = hash(element.key);
            if(elementArray[hash] == element) {
                elementArray[hash] = element.linkNext;
            }else{
                Element current = elementArray[hash];
                while(current.linkNext != element) {
                    current = current.linkNext;
                }
                current.linkNext = element.linkNext;
            }
            
            total--;
        }
        
        //find key in the hash link
        private Element findInLink(final int key, final int hash) {
            Element element = elementArray[hash];
            
            while(element != null && element.key != key) {
                element = element.linkNext;
            }
            
            return element;        
        }
        
        private int hash(final int key) {
            final int res = key % elementArray.length;
            return res >= 0 ? res : (elementArray.length + res);
        }
        
        private class Element {
            //next element in double linked list
            Element next;
            
            //previous element in double linked list
            Element prev;
            
            //next element in hash link, so as to tackle hash collision
            Element linkNext;
            
            int key;
            int val;
            
            //used count of this element
            int count;
            
            Element(final int key, final int val) {
                this.key = key;
                this.val = val;
            }
        }
    }
    
    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.set(key,value);
     */
    

  • 0

    @infini Do you really have to write your own hash and what essentially HashMap!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.