When building applications, there’s often a need to retrieve data repeatedly. Fetching this data, especially from external sources like databases, can be time-consuming and expensive. To optimize this, developers use caching mechanisms, one of which is the LRU Cache.

What is LRU Cache?

LRU stands for “Least Recently Used”. An LRU Cache is a mechanism that keeps recently used items around, but when the cache reaches its limit, the least recently used item is discarded to make space for a new item. This approach ensures that the cache always contains the most recently accessed items, which are more likely to be accessed again.

Why use LRU Cache?

Performance: Fetching data from a cache is faster than recomputing it or retrieving it from a slower data source (e.g., a database).
Reduces Load: By avoiding frequent access to slower back-end sources, we reduce the load on them, leading to overall faster application performance.

How does it work?

Imagine a room of fixed size. People come into the room based on how frequently they’re called. If the room is full and a new person needs to come in, the person who has been in the room the longest without being called is asked to leave.

How to implement LRU Cache?

Implementing an LRU Cache without any built-in language constructs requires us to build our own data structures. We can achieve this by combining a Doubly Linked List (to maintain the order of elements) with a HashMap (for O(1) access time).

Here’s how we can approach it:

Doubly Linked List: This will allow us to maintain the order of elements based on their usage. When an element is accessed or added, it will be moved to the front (indicating it’s the most recently used). When we need to remove an element due to the cache being full, we’ll remove from the end (indicating it’s the least recently used).
HashMap: This will store references to nodes in the doubly linked list, giving us constant time access.

Custom Implementation

import java.util.HashMap;

public class LRUCache<K, V> {
    private final int capacity;
    private final HashMap<K, Node<K, V>> map;
    private final DoublyLinkedList<K, V> list;

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

    public V get(K key) {
        if (!map.containsKey(key)) return null;

        Node<K, V> node = map.get(key);
        list.moveToFront(node);
        return node.value;
    }

    public void put(K key, V value) {
        if (map.containsKey(key)) {
            Node<K, V> node = map.get(key);
            node.value = value;
            list.moveToFront(node);
            return;
        }

        if (map.size() == capacity) {
            Node<K, V> tail = list.removeTail();
            map.remove(tail.key);
        }

        Node<K, V> newNode = new Node<>(key, value);
        list.addToFront(newNode);
        map.put(key, newNode);
    }

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

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

        public void moveToFront(Node<K, V> node) {
            if (head == node) return;

            removeNode(node);
            addToFront(node);
        }

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

            Node<K, V> node = tail;
            removeNode(tail);
            return node;
        }

        private void removeNode(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;
            }
        }
    }

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

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

Explanation

Node represents an element in the doubly linked list. It contains pointers to the previous and next nodes, as well as the key and value.
DoublyLinkedList contains methods to handle the movement, addition, and removal of nodes.
The main LRUCache class leverages both the Node and DoublyLinkedList classes in conjunction with a HashMap to ensure O(1) access and update time for cache elements.

Using Java in-built constructs to implement LRU Cache

To implement an LRU cache in Java, we can make use of Java’s built-in LinkedHashMap.

Key Components

Capacity: The maximum number of items the cache can hold.
LinkedHashMap: A hash table and linked list implementation of the Map interface. It allows for constant-time performance for the basic operations (get and put), and entries are maintained in a doubly-linked list, which provides order.

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

public class LRUCache<K, V> {
    private final int capacity;
    private final LinkedHashMap<K, V> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > LRUCache.this.capacity;
            }
        };
    }

    public synchronized V get(K key) {
        return cache.get(key);
    }

    public synchronized void put(K key, V value) {
        cache.put(key, value);
    }
}

Key Points

We set the accessOrder flag to true when creating the LinkedHashMap. This makes it an access-order rather than an insertion-order linked hash map.
The overridden removeEldestEntry() function ensures that when the number of entries exceeds the capacity, the oldest (least recently accessed) entry is removed.
The methods are synchronized to make our cache thread-safe.

If you found this guide useful, please share with your friends and spread the knowledge!

What is LRU Cache and How to implement it yourself?