Cache Design with LRU Eviction

Let's design a cache that supports put(key, value) and get(key) operations with an LRU (Least Recently Used) eviction policy, thread safety, and generics.

Data Structures

We'll use the following data structures:

HashMap<K, Node<K, V>> cache: Stores key-value pairs for O(1) average-case access.
DoubleLinkedList<K, V> lruList: Maintains the order of elements based on their usage. The most recently used element is at the head, and the least recently used is at the tail.
int capacity: Specifies the maximum number of key-value pairs the cache can hold.

Implementation Details

Node (Inner Class)

private static class Node<K, V> {
    K key;
    V value;
    Node<K, V> prev;
    Node<K, V> next;

    Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

A simple node structure to hold the key, value, and pointers to the previous and next nodes in the doubly linked list.

DoubleLinkedList (Inner Class)

private static class DoubleLinkedList<K, V> {
    Node<K, V> head;
    Node<K, V> tail;

    public DoubleLinkedList() {
        head = null;
        tail = null;
    }

    public void addFirst(Node<K, V> node) {
        if (head == null) {
            head = node;
            tail = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

    public void remove(Node<K, V> node) {
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }

        if (node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;
        }
    }

    public Node<K, V> removeLast() {
        if (tail == null) {
            return null;
        }

        Node<K, V> last = tail;
        remove(last);
        return last;
    }
}

A standard doubly linked list implementation to track the order of node accesses. addFirst adds a node to the head, remove removes a node from the list, and removeLast removes the tail node (LRU).

Cache Class

import java.util.HashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class Cache<K, V> {
    private final int capacity;
    private final HashMap<K, Node<K, V>> cache;
    private final DoubleLinkedList<K, V> lruList;
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    private final Lock readLock = lock.readLock();
    private final Lock writeLock = lock.writeLock();

    public Cache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>(capacity);
        this.lruList = new DoubleLinkedList<>();
    }

    public V get(K key) {
        readLock.lock();
        try {
            Node<K, V> node = cache.get(key);
            if (node == null) {
                return null;
            }
            lruList.remove(node);
            lruList.addFirst(node);
            return node.value;
        } finally {
            readLock.unlock();
        }
    }

    public void put(K key, V value) {
        writeLock.lock();
        try {
            Node<K, V> node = cache.get(key);
            if (node != null) {
                // Key already exists, update value and move to front
                node.value = value;
                lruList.remove(node);
                lruList.addFirst(node);
            } else {
                // Key doesn't exist
                if (cache.size() == capacity) {
                    // Evict LRU node
                    Node<K, V> lruNode = lruList.removeLast();
                    cache.remove(lruNode.key);
                }

                // Add new node
                Node<K, V> newNode = new Node<>(key, value);
                cache.put(key, newNode);
                lruList.addFirst(newNode);
            }
        } finally {
            writeLock.unlock();
        }
    }

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private static class DoubleLinkedList<K, V> {
        Node<K, V> head;
        Node<K, V> tail;

        public DoubleLinkedList() {
            head = null;
            tail = null;
        }

        public void addFirst(Node<K, V> node) {
            if (head == null) {
                head = node;
                tail = node;
            } else {
                node.next = head;
                head.prev = node;
                head = node;
            }
        }

        public void remove(Node<K, V> node) {
            if (node.prev != null) {
                node.prev.next = node.next;
            } else {
                head = node.next;
            }

            if (node.next != null) {
                node.next.prev = node.prev;
            } else {
                tail = node.prev;
            }
        }

        public Node<K, V> removeLast() {
            if (tail == null) {
                return null;
            }

            Node<K, V> last = tail;
            remove(last);
            return last;
        }
    }
}

`get(K key)`

Acquire a read lock to allow concurrent reads.
Check if the key exists in the cache (HashMap). If not, return null.
If the key exists, retrieve the corresponding Node.
Remove the node from its current position in the lruList.
Add the node to the head of the lruList (most recently used).
Return the value of the node.
Release the read lock.

`put(K key, V value)`

Acquire a write lock for exclusive access.
Check if the key already exists in the cache.
- If it exists, update the value of the node, remove it from the lruList, and add it to the head.
- If it doesn't exist:
  - Check if the cache is full (size equals capacity).
    - If it's full, remove the least recently used node (tail of lruList) and remove its corresponding entry from the cache.
  - Create a new Node with the given key and value.
  - Add the new node to the cache.
  - Add the new node to the head of the lruList.
Release the write lock.

Thread Safety

Thread safety is achieved using a ReadWriteLock. This allows multiple threads to read from the cache concurrently, but only one thread can write to it at a time. This prevents race conditions and ensures data consistency.

ReadLock: Used for the get operation. Multiple readers can access the cache simultaneously.
WriteLock: Used for the put operation. Only one writer can modify the cache at a time, blocking other readers and writers.

Generics

The cache uses generics (<K, V>) to allow it to store any type of key and value. This provides flexibility and type safety.

Time Complexity

get(K key): O(1) on average, due to the HashMap lookup. Removing and adding to the doubly linked list are also O(1).
put(K key, V value): O(1) on average. HashMap put/get, and doubly linked list add/remove operations are O(1).

Space Complexity

O(capacity), where capacity is the maximum number of key-value pairs the cache can hold. This is because the HashMap and doubly linked list store at most capacity elements.

Example Usage

public static void main(String[] args) {
    Cache<Integer, String> cache = new Cache<>(5);
    cache.put(1, "one");
    cache.put(2, "two");
    cache.get(1); // Access key 1, moves it to the most recently used
    cache.put(3, "three");
    cache.put(4, "four");
    cache.put(5, "five");
    cache.put(6, "six"); // This will evict key 2 (LRU)
    System.out.println(cache.get(2)); // Output: null (because it was evicted)
}

How would you design a thread-safe LRU cache with O(1) get and put operations?