LRU caching in java with generics and O (1) operations

This is a question in the interview The idea is to define a data structure instead of using Java's built-in LinkedHashMap

The LRU cache deletes the least recently used entry to insert a new entry Therefore, considering the following circumstances:

A - B - C - D - E

Where a is the least used item recently. If we insert F, we need to delete a

If we use (key, value) to save a HashMap with cached entries and a separate list of keys and usage times containing elements, it can be easily implemented However, we need to query the list to find the least recently used items, which has potential o (n) time complexity

How do I implement this structure in Java for generic objects and O (1) operations?

Unlike possible duplication, it focuses on efficiency (O (1) OPS) and implementing the data structure itself, rather than extending Java

Solution

From the problem itself, we can see that the problem of O (n) operation occurs when querying the linked list Therefore, we need an alternative data structure We need to be able to update the last access time of the project from HashMap without searching

We can keep two separate data structures HashMap and bidirectional linked list with (key, pointer) pairs will be used as priority queues for deleting and storing values From HashMap, we can point to an element in the bidirectional linked list and update its retrieval time Because we directly from the HashMap to the items in the list, our time complexity remains at O (1)

For example, our two-way linked list may be as follows:

least_recently_used  -> A <-> B <-> C <-> D <-> E <- most_recently_used

We need to keep pointers to LRU and MRU items The entry value will be stored in the list. When we query the HashMap, we will get a pointer to the list On get (), we need to put the item to the far right of the list On put (key, value), if the cache is full, we need to delete the leftmost item from the list and HashMap

The following is an example implementation in Java:

public class LRUCache<K,V>{

    // Define Node with pointers to the prevIoUs and next items and a key,value pair
    class Node<T,U> {
        Node<T,U> prevIoUs;
        Node<T,U> next;
        T key;
        U value;

        public Node(Node<T,U> prevIoUs,Node<T,U> next,T key,U value){
            this.prevIoUs = prevIoUs;
            this.next = next;
            this.key = key;
            this.value = value;
        }
    }

    private HashMap<K,Node<K,V>> cache;
    private Node<K,V> leastRecentlyUsed;
    private Node<K,V> mostRecentlyUsed;
    private int maxSize;
    private int currentSize;

    public LRUCache(int maxSize){
        this.maxSize = maxSize;
        this.currentSize = 0;
        leastRecentlyUsed = new Node<K,V>(null,null,null);
        mostRecentlyUsed = leastRecentlyUsed;
        cache = new HashMap<K,V>>();
    }

    public V get(K key){
        Node<K,V> tempNode = cache.get(key);
        if (tempNode == null){
            return null;
        }
        // If MRU leave the list as it is
        else if (tempNode.key == mostRecentlyUsed.key){
            return mostRecentlyUsed.value;
        }

        // Get the next and prevIoUs nodes
        Node<K,V> nextNode = tempNode.next;
        Node<K,V> prevIoUsNode = tempNode.prevIoUs;

        // If at the left-most,we update LRU 
        if (tempNode.key == leastRecentlyUsed.key){
            nextNode.prevIoUs = null;
            leastRecentlyUsed = nextNode;
        }

        // If we are in the middle,we need to update the items before and after our item
        else if (tempNode.key != mostRecentlyUsed.key){
            prevIoUsNode.next = nextNode;
            nextNode.prevIoUs = prevIoUsNode;
        }

        // Finally move our item to the MRU
        tempNode.prevIoUs = mostRecentlyUsed;
        mostRecentlyUsed.next = tempNode;
        mostRecentlyUsed = tempNode;
        mostRecentlyUsed.next = null;

        return tempNode.value;

    }

    public void put(K key,V value){
        if (cache.containsKey(key)){
            return;
        }

        // Put the new node at the right-most end of the linked-list
        Node<K,V> myNode = new Node<K,V>(mostRecentlyUsed,key,value);
        mostRecentlyUsed.next = myNode;
        cache.put(key,myNode);
        mostRecentlyUsed = myNode;

        // Delete the left-most entry and update the LRU pointer
        if (currentSize == maxSize){
            cache.remove(leastRecentlyUsed.key);
            leastRecentlyUsed = leastRecentlyUsed.next;
            leastRecentlyUsed.prevIoUs = null;
        }

        // Update cache size,for the first added entry update the LRU pointer
        else if (currentSize < maxSize){
            if (currentSize == 0){
                leastRecentlyUsed = myNode;
            }
            currentSize++;
        }
    }
}