LRU cache in Java with Generics and O(1) operations

Question

This is a question that comes up a lot in job interviews. The idea is to define a data structure instead of using Java's built in LinkedHashMap.

An LRU cache deletes the least recently used entry to insert a new one. So, given the following scenario:

 A - B - C - D - E

Where A is the least recently used item, if we were to insert F, we need to remove A.

This can be easily implemented if we keep a HashMap with the cache entries by (key,value) and a separate list that contains the elements' key and time of use. However, we would need to query the list to find the least recently used item, with a potential O(n) time complexity.

How can this structure be implemented in Java for Generic objects and O(1) operations?

This is different from the possible duplicate in that it focuses on efficiency (O(1) ops) and implementing the data structure itself, not extending Java's.

Answer 1

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

We can keep two separate data structures. A HashMap with (Key,Pointer) pairs and a doubly linked list which will work as the priority queue for deletion and store the Values. From the HashMap, we can point to an element in the doubly linked list and update its' retrieval time. Because we go directly from the HashMap to the item in the list, our time complexity remains at O(1)

For example, our doubly linked list can look like:

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

We need to keep a pointer to the LRU and MRU items. The entries' values will be stored in the list and when we query the HashMap, we will get a pointer to the list. On get(), we need to put the item at the right-most side of the list. On put(key,value), if the cache is full, we need to remove the item at the left-most side of the list from both, the list and the 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, null);
        mostRecentlyUsed = leastRecentlyUsed;
        cache = new HashMap<K, Node<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, null, 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++;
        }
    }
}

Answer 2

Implementation that passes the tests of the leetcode question with simple unit tests

I have made a pull request with this at: https://github.com/haoel/leetcode/pull/90/files The code was later improved here in the answer with accessOrder = true and I didn't bother to make another pull request though, so the code here is slightly better for now.

LRUCache.java

import java.util.Iterator;
import java.util.LinkedHashMap;

public class LRUCache {

    private int capacity;
    private LinkedHashMap<Integer,Integer> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new LinkedHashMap<>(16, 0.75f, true);
    }

    public int get(int key) {
        Integer value = this.map.get(key);
        if (value == null) {
            value = -1;
        }
        return value;
    }

    public void put(int key, int value) {
        if (
            !this.map.containsKey(key) &&
            this.map.size() == this.capacity
        ) {
            Iterator<Integer> it = this.map.keySet().iterator();
            it.next();
            it.remove();
        }
        this.map.put(key, value);
    }
}

LRUCacheTest.java

public class LRUCacheTest {
    public static void main(String[] args) {
        LRUCache c;

        // Starts empty.
        c = new LRUCache(2);
        assert c.get(1) == -1;

        // Below capcity.
        c = new LRUCache(2);
        c.put(1, 1);
        assert c.get(1) == 1;
        assert c.get(2) == -1;
        c.put(2, 4);
        assert c.get(1) == 1;
        assert c.get(2) == 4;

        // Above capacity, oldest is removed.
        c = new LRUCache(2);
        c.put(1, 1);
        c.put(2, 4);
        c.put(3, 9);
        assert c.get(1) == -1;
        assert c.get(2) == 4;
        assert c.get(3) == 9;

        // get renews entry
        c = new LRUCache(2);
        c.put(1, 1);
        c.put(2, 4);
        assert c.get(1) == 1;
        c.put(3, 9);
        assert c.get(1) == 1;
        assert c.get(2) == -1;
        assert c.get(3) == 9;

        // Double put does not remove due to capacity.
        c = new LRUCache(2);
        assert c.get(2) == -1;
        c.put(2, 6);
        assert c.get(1) == -1;
        c.put(1, 5);
        c.put(1, 2);
        assert c.get(1) == 2;
        assert c.get(2) == 6;
    }
}

removeEldestEntry() alternative implementation

Not sure it is worth it as it takes the same number of lines, but here goes for completeness:

import java.util.LinkedHashMap;
import java.util.Iterator;
import java.util.Map;

import java.io.*;

class LinkedhashMapWithCapacity<K,V> extends LinkedHashMap<K,V> {
    private int capacity;

    public LinkedhashMapWithCapacity(int capacity) {
        super(16, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return this.size() > this.capacity;
    }
}

public class LRUCache {

    private LinkedhashMapWithCapacity<Integer,Integer> map;

    public LRUCache(int capacity) {
        this.map = new LinkedhashMapWithCapacity<>(capacity);
    }

    public int get(int key) {
        Integer value = this.map.get(key);
        if (value == null) {
            value = -1;
        }
        return value;
    }

    public void put(int key, int value) {
        this.map.put(key, value);
    }
}

Tested on Ubuntu 20.10, OpenJDK 11.0.10.