LFU Cache

Question:

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item.

For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Requirement: Do both operations in O(1) time complexity!

Analysis:

Since we have to invalidate a key according to the frequency the key was used in the past, we have to use some data structure to record the frequency of each key.

For all the keys that have the same used frequency, we have to apply the LRU cache design mechanism.

Design details:

/*        freqNode1      freqNode2        freqNode3
             ----------      ----------       ----------
    head---->| freq=1 |----> | freq=2  |----->| freq=4 |---->...---->
        <----| kv..   |<---- | kv..    |<-----| kv...  |<----...<----tail
             ----------      -----------      ----------
    */
    /* 1. Use class freqNode to record all the key-value pairs with same used frequency
       2. connect these freqNode as an double-linked-list 
          so that we can find the least frequently used key in O(1) time
       3. Use a HashMap to record the freqNode to which a specified key belongs to
          so that we can find the key's value in O(1) time and also update the frequency of key in O(1) time
       4. Use a LinkedHashMap to record all the key-value pairs that have the same used frequency
          so that when we have to invalidate one key and there is a tie, we can find the least recently used key in O(1) time
      */

Implementation:

public class LFUCache {
    class freqNode{
        int frequency;
        freqNode pre;
        freqNode next;
        LinkedHashMap<Integer,Integer> kv;
        freqNode(int frequency){
            this.frequency=frequency;
            this.kv=new LinkedHashMap<Integer,Integer>();
        }
    }

    freqNode head;
    freqNode tail;
    int capacity;
    Map<Integer,freqNode> key_freqNode;
    public LFUCache(int capacity) {
        this.capacity=capacity;
        this.head=new freqNode(Integer.MIN_VALUE);
        this.tail=new freqNode(Integer.MAX_VALUE);
        this.key_freqNode=new HashMap<Integer,freqNode>();
        head.next=tail;
        tail.pre=head;
    }

    public int get(int key) {
        if(!key_freqNode.containsKey(key)) return -1;
        freqNode tmp=key_freqNode.get(key);
        int value=tmp.kv.get(key);
        tmp.kv.remove(key);
        if(tmp.next!=tail&&tmp.next.frequency-1==tmp.frequency){
            tmp.next.kv.put(key,value);
        }else{
            freqNode nextNode=new freqNode(tmp.frequency+1);
            nextNode.kv.put(key,value);
            tmp.next.pre=nextNode;
            nextNode.next=tmp.next;
            tmp.next=nextNode;
            nextNode.pre=tmp;
        }
        key_freqNode.put(key,tmp.next);
        /*check if tmp is empty, if so remove from double linkedlist*/
        if(tmp.kv.size()==0){
            tmp.next.pre=tmp.pre;
            tmp.pre.next=tmp.next;
        }
        return value;
    }
    /*invalidate the least frequently used kv or least recent used if tied*/
    public void invalidate(){
        freqNode tmp=head.next;
        if(tmp==tail) return;
        int invalidateKey=tmp.kv.keySet().iterator().next();
        tmp.kv.remove(invalidateKey);
        key_freqNode.remove(invalidateKey);
        /*check if tmp is empty, if so remove from double linkedlist*/
        if(tmp.kv.size()==0){
            tmp.next.pre=tmp.pre;
            tmp.pre.next=tmp.next;
        }
    }
    public void put(int key, int value) {
        if(capacity<=0) return;
        if(key_freqNode.size()==capacity&&!key_freqNode.containsKey(key)) invalidate();
        if(key_freqNode.containsKey(key)){
            freqNode tmp=key_freqNode.get(key);
            tmp.kv.remove(key);//remove key-value from this frequency Node
            if(tmp.next!=tail&&tmp.next.frequency-1==tmp.frequency){
                tmp.next.kv.put(key,value);
            }else{
                freqNode nextNode=new freqNode(tmp.frequency+1);
                nextNode.kv.put(key,value);
                tmp.next.pre=nextNode;
                nextNode.next=tmp.next;
                tmp.next=nextNode;
                nextNode.pre=tmp;
            }
            key_freqNode.put(key,tmp.next);
            /*check if tmp is empty, if so remove from double linkedlist*/
            if(tmp.kv.size()==0){
                tmp.next.pre=tmp.pre;
                tmp.pre.next=tmp.next;
            }
        }else{//Add new key-value
            if(head.next==tail||head.next.frequency!=1){
                freqNode frequency1=new freqNode(1);
                frequency1.kv.put(key,value);
                head.next.pre=frequency1;
                frequency1.next=head.next;
                head.next=frequency1;
                frequency1.pre=head;
            }else{
                head.next.kv.put(key,value);
            }
            key_freqNode.put(key,head.next);
        }

    }
}