Easy Solution based on Paper (193ms) - An O(1) algorithm for implementing the LFU cache eviction scheme


  • 0
    R

    Implementation is based on this paper http://dhruvbird.com/lfu.pdf . All credits to the algorithm goes to the paper writers.

    Data structures used :
    HashMap
    LinkedHashSet
    Doubly Linked List

    HashMap stores the mapping from Key to Cache Item
    Doubly linked list - Chain of frequency nodes where each frequency node stores
    a LinkedHashSet of Keys that have the same frequency .

    When ever an access is made on an existing key, the cache entry is shifted to the next frequency node's linked hash set and removed from the previous frequency node's linked hash set.

    public class LFUCache {
    
        public int size;
        public int capacity;
        public Map<Integer, LFUCacheItem> lookup;
        public FreqNode freqHead;
        
        public LFUCache(){
            
        }
        
        public class FreqNode{ // freqency node part of a double linked list 
            public LinkedHashSet<LFUCacheItem> set; //all cache entries that have same frequency ordered by time
            public int freqNo;
            public FreqNode prev; //points to lower frequency node
            public FreqNode next; //points to higher frequency node
            
            public FreqNode(int freq, FreqNode prev, FreqNode next){
                set = new LinkedHashSet<>();
                freqNo = freq;
                this.prev = prev;
                this.next = next;
                if(prev != null)
                    prev.next = this;
                if(next != null)
                    next.prev = this;
            }
        }
        
        public class LFUCacheItem{ //cache entry that stores pointer to FreqNode that it belongs to
            public FreqNode parent;
            public int key;
            public int value;
            
            public LFUCacheItem(FreqNode parent, int key, int value){
                this.parent = parent;
                this.key = key;
                this.value = value;
            }
        }
        
        public LFUCache(int capacity) { 
            size =0;
            //fixed size
            this.capacity = capacity; 
            // a lookup table to get the cache entry
            lookup = new HashMap<>(); 
            freqHead = new FreqNode(0, null, null); // initialize the head of frequency node doubly linked list.
        }
        
        public int get(int key) {
            if(lookup.containsKey(key)){
                LFUCacheItem item = lookup.get(key);
                FreqNode freqNode = item.parent;
                FreqNode nextFreqNode = freqNode.next;
                
                if(nextFreqNode == null || nextFreqNode.freqNo != freqNode.freqNo+1){
                    nextFreqNode = new FreqNode(freqNode.freqNo+1, freqNode, nextFreqNode);
                }
                item.parent = nextFreqNode;
                nextFreqNode.set.add(item);
                
                freqNode.set.remove(item);
                
                if(freqNode.set.size() == 0){
                    removeFreqNode(freqNode);
                }
                    
                return item.value;
                
            }
            else{
                return -1; //not found
            }
        }
        
        private void removeFreqNode(FreqNode node){
            if(node.next != null)
                node.next.prev = node.prev;
            node.prev.next= node.next;
        }
        
        public void put(int key, int value) {
            if(capacity <=0) return ;
            
            if(!lookup.containsKey(key) ){
                FreqNode obj = freqHead.next; //get lowest frequency
                
                if(size == capacity){//eviction case
                    //get first cache item
                    LFUCacheItem toBeEvicted = obj.set.iterator().next();
                    //remove from set
                    obj.set.remove(toBeEvicted); 
                    // remove from lookup
                    lookup.remove(toBeEvicted.key); 
                    size--;
                }
                
                if(obj == null || obj.freqNo != 1){
                    obj = freqHead.next = new FreqNode(1, freqHead, obj);
                }
                LFUCacheItem entry = new LFUCacheItem(obj, key, value);
                entry.parent = obj;
                obj.set.add( entry );
                lookup.put(key , entry);
                
                size++;
            }
            else{
                LFUCacheItem item = lookup.get(key);
                item.value = value;
                //reorganize cache
                get(key);
            }
        }
    }
    
    

Log in to reply
 

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