Caching is an important technique used in software applications to improve performance and reduce unnecessary database calls.
Instead of fetching the same information repeatedly from a database or an external service, applications can temporarily store frequently accessed information in memory.
However, memory is limited. We cannot keep every piece of information in the cache indefinitely. When the cache reaches its configured capacity, we need a strategy to decide which entry should be removed.
One popular caching strategy is LRU (Least Recently Used) Cache.
LRU Cache removes the entry that has not been accessed for the longest period of time.
In this article, we will implement a simple LRU Cache in Java using two data structures:
· HashMap
· Doubly Linked List
We will also understand how these two data structures work together to achieve O(1) average-time cache operations.
1. Understanding LRU Cache
Let's assume we have an LRU Cache with a maximum capacity of 3. Initially, the cache is empty.
Now, let's insert three entries:
cache.get("A");
cache.get("B");
cache.get("C");
The get() method first checks whether the requested element exists in the cache. If found, it returns the cached value. Otherwise, it fetches the data from an external source, such as a database, updates the cache with the retrieved value, and returns it.
Since C was accessed most recently, the cache maintains the following order:
MRU LRU C <-> B <-> A
Here:
· MRU (Most Recently Used): The entry accessed most recently.
· LRU (Least Recently Used): The entry accessed least recently.
Now, suppose we access A.
cache.get("A");
Since A is accessed again, it becomes the most recently used entry. The cache order changes:
MRU LRU A <-> C <-> B
Next, let's insert or access another entry D.
cache.get("D");
The cache has already reached its maximum capacity of 3. Therefore, we must remove the least recently used entry, which is B.
The final cache order becomes:
MRU LRU D <-> A <-> C
This is the fundamental working principle of an LRU Cache.
2. Why HashMap and Doubly Linked List?
We need two data structures to implement an efficient LRU Cache.
2.1 HashMap
A HashMap stores cache keys and their corresponding linked-list nodes.
private final Map<Object, Node> cacheMap = new HashMap<>();
For example:
|
Key |
Value |
|
A |
Node(A, ValueA) |
|
B |
Node(B, ValueB) |
|
C |
Node(C, ValueC) |
The main advantage of HashMap is that it provides O(1) average-time lookup. When a user requests a cache entry, we can directly locate its corresponding node without traversing the linked list.
3.2 Doubly Linked List
A doubly linked list maintains the access order of cache entries. Each node contains four fields:
private static class Node {
private Object key;
private Object val;
private Node prev;
private Node next;
public Node(Object key, Object val) {
this.key = key;
this.val = val;
}
}
Here:
· key: Stores the cache key.
· val: Stores the cached value.
· prev: References the previous node.
· next: References the next node.
The cache maintains two references first and last.
private Node first = null, last = null;
· first: Points to the Most Recently Used (MRU) node.
· last: Points to the Least Recently Used (LRU) node.
The doubly linked list looks like this:
A doubly linked list allows us to remove or reposition any node in O(1) time when we already have its reference. Combining HashMap and Doubly Linked List gives us efficient cache operations.
3. Implementing LRU Cache in Java
Let's implement the LRU Cache step by step.
3.1 Cache Initialization
First, we define the cache capacity and initialize the HashMap.
private Node first = null, last = null;
private final int capacity;
private final Map<Object, Node> cacheMap = new HashMap<>();
public LRUCache(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException(
"Cache capacity must be positive");
}
this.capacity = capacity;
}
The constructor accepts the maximum number of entries the cache can hold. We also validate the capacity to ensure that it is always positive.
3.2 Node Structure
Each cache entry is represented by a node in the doubly linked list.
private static class Node {
private Object key;
private Object val;
private Node prev;
private Node next;
public Node(Object key, Object val) {
this.key = key;
this.val = val;
}
}
We store both the key and value in the node. Storing the key is important because when we remove the least recently used node, we also need to remove its corresponding entry from the HashMap.
3.3 Adding a Node at the Beginning
Whenever we insert a new cache entry or access an existing entry, it should become the most recently used entry. We achieve this by inserting the node at the beginning of the doubly linked list.
private void addNodeAtFirst(Node node) {
node.prev = null;
node.next = first;
if (first != null) {
first.prev = node;
}
first = node;
if (last == null) {
last = node;
}
}
3.4 Moving an Existing Node to the Beginning
Suppose a cache entry is accessed. We need to mark it as the most recently used entry. Instead of creating a new node, we move the existing node to the beginning of the linked list.
private void moveNodeToFirst(Node node) {
if (node == first) {
return;
}
if (node == last) {
last = node.prev;
}
Node next = node.next;
Node prev = node.prev;
if (next != null) {
next.prev = prev;
}
if (prev != null) {
prev.next = next;
}
node.prev = null;
node.next = null;
addNodeAtFirst(node);
}
For example, consider the following cache:
A <-> B <-> C <-> D
Now, suppose we access C.
We disconnect C from its current position and insert it at the beginning.
C <-> A <-> B <-> D
C is now the most recently used entry. The operation takes O(1) time because we already have a reference to the node from HashMap.
3.5 Removing the Last Node
When the cache reaches its maximum capacity, we need to remove the least recently used entry. Since the last reference points to the least recently used node, we can remove it directly.
private void removeLast() {
if (last == null) {
return;
}
cacheMap.remove(last.key);
if (first == last) {
first = last = null;
return;
}
last = last.prev;
last.next = null;
}
3.6 Fetching Data from Database
For demonstration purposes, let's simulate database retrieval.
private Node getFromDB(Object key) {
return new Node(key, UUID.randomUUID().toString());
}
In a real-world application, this method would be replaced with an actual database or external service call. We generate a random UUID to simulate the retrieved value.
3.7 Implementing the Get Operation
Now comes the main part of the implementation. The get method performs the following operations:
· Check whether the requested key exists in the cache.
· If it exists, move the node to the beginning and return its value.
· If it does not exist, fetch the value from the database. If the cache is full, remove the least recently used entry. Insert the new node at the beginning.
· Add the node to the HashMap.
public Object get(Object key) {
System.out.println("Accessing the key : " + key + "\n");
// Step 1: Check cache
Node node = cacheMap.get(key);
if (node != null) {
moveNodeToFirst(node);
return node.val;
}
// Step 2: Cache miss - fetch from DB
Node newNode = getFromDB(key);
// Step 3: Evict least recently used entry if cache is full
if (cacheMap.size() >= capacity) {
removeLast();
}
// Step 4: Insert new entry at the beginning
addNodeAtFirst(newNode);
cacheMap.put(key, newNode);
return newNode.val;
}
Notice that we perform both HashMap lookup and linked-list manipulation without traversing the entire list. Therefore, the get operation takes O(1) average time, excluding the actual database retrieval.
The flow looks like below:
5. Time Complexity Analysis
This implementation achieves the following time complexity:
|
Operation |
Time Complexity |
|
Cache lookup |
O(1) average |
|
Insert node at beginning |
O(1) |
|
Move existing node |
O(1) |
|
Remove last node |
O(1) |
|
Cache eviction |
O(1) |
The HashMap provides fast lookup, while the doubly linked list allows us to reposition and remove nodes efficiently. The overall cache space complexity is O(capacity).
6. Limitations and Possible Improvements
This implementation is intentionally kept simple to explain the internal working of an LRU Cache. Some improvements are required before using it in a production environment:
· Thread Safety: Add synchronization or an appropriate concurrency strategy if multiple threads access the cache.
· Expiration: Introduce TTL (Time To Live) to automatically expire old entries.
· Database Integration: Replace the simulated database retrieval with an actual data-loading mechanism.
· Null Handling: Define how null keys and null values should be handled.
· Cache Statistics: Track cache hits, misses, and eviction counts.
Find the below working Application.
LRUCache.java
package com.sample.app.cache;
import java.util.HashMap;
import java.util.Map;
import java.util.UUID;
/**
* A simple implementation of a Least Recently Used (LRU) Cache using a HashMap
* and a Doubly Linked List.
*
* <p>
* This implementation is primarily intended for learning purposes to
* demonstrate how an LRU cache works internally and how a HashMap and Doubly
* Linked List can be combined to achieve efficient cache operations.
*
* <p>
* The cache maintains entries in the following order:
* <ul>
* <li>Head (first): Most Recently Used (MRU) entry.</li>
* <li>Tail (last): Least Recently Used (LRU) entry.</li>
* </ul>
*
* <p>
* When an existing entry is accessed, it is moved to the head of the list. When
* a new entry is added and the cache reaches its configured capacity, the least
* recently used entry is evicted.
*
* <p>
* <b>Implementation details:</b>
* <ul>
* <li>HashMap provides O(1) average-time lookup.</li>
* <li>Doubly Linked List provides O(1) node insertion, removal, and
* repositioning.</li>
* <li>Cache lookup, insertion, and eviction take O(1) average time.</li>
* <li>Printing cache entries takes O(n) time.</li>
* </ul>
*
* <p>
* <b>Limitations:</b>
* <ul>
* <li>This is a simplified implementation intended for educational purposes,
* not production use.</li>
* <li>Thread safety and synchronization are not handled.</li>
* <li>Database retrieval is simulated and should be replaced with an actual
* data-loading mechanism.</li>
* <li>Additional production concerns such as expiration policies, cache
* statistics, and failure handling are not implemented.</li>
* </ul>
*
* @see java.util.HashMap
*/
public class LRUCache<K, V> {
private Node<K, V> first = null, last = null;
private final int capacity;
private final Map<K, Node<K, V>> cacheMap = new HashMap<>();
private static class Node<K, V> {
private K key;
private V val;
private Node<K, V> prev;
private Node<K, V> next;
public Node(K key, V val) {
this.key = key;
this.val = val;
}
}
public LRUCache(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("Cache capacity must be positive");
}
this.capacity = capacity;
}
private void removeLast() {
if (last == null) {
return;
}
cacheMap.remove(last.key);
if (first == last) {
first = last = null;
return;
}
last = last.prev;
last.next = null;
}
private Node<K, V> getFromDB(K key) {
V value = fetchValueFromDB(key);
return new Node<>(key, value);
}
private V fetchValueFromDB(K key) {
// Simulate database retrieval.
return (V) UUID.randomUUID().toString();
}
public V get(K key) {
System.out.println("Accessing the key : " + key + "\n");
// Step 1: Check cache
Node<K, V> node = cacheMap.get(key);
if (node != null) {
moveNodeToFirst(node);
return node.val;
}
// Step 2: Cache miss - fetch from DB
Node<K, V> newNode = getFromDB(key);
// Step 3: Evict least recently used entry if cache is full
if (cacheMap.size() >= capacity) {
removeLast();
}
// Step 4: Insert new entry at the beginning
addNodeAtFirst(newNode);
cacheMap.put(key, newNode);
return newNode.val;
}
/**
* Inserts the given node at the beginning (head) of the doubly linked list,
* making it the Most Recently Used (MRU) entry.
*
* <p>
* The operation involves the following steps:
* <ol>
* <li>Set the node's previous reference to null because it will become the
* first node in the list.</li>
* <li>Set the node's next reference to the current first node.</li>
* <li>If the list is not empty, update the current first node's previous
* reference to point to the new node.</li>
* <li>Update the first reference to point to the newly inserted node.</li>
* <li>If the list was empty, also update the last reference to point to the new
* node, since it is both the first and last node.</li>
* </ol>
*
* <p>
* This operation reuses the given node and adjusts the links without creating a
* new node. It takes O(1) time.
*
* @param node the node to insert at the beginning of the list
*/
private void addNodeAtFirst(Node<K, V> node) {
node.prev = null;
node.next = first;
if (first != null) {
first.prev = node;
}
first = node;
if (last == null) {
last = node;
}
}
/**
* Moves the given node to the beginning (head) of the doubly linked list,
* making it the Most Recently Used (MRU) entry.
*
* <p>
* The operation involves the following steps:
* <ol>
* <li>If the node is already at the beginning, no operation is required.</li>
* <li>If the node is the last node (LRU), update the tail reference.</li>
* <li>Disconnect the node from its current position by updating the previous
* and next nodes' references.</li>
* <li>Reset the node's previous and next references to detach it from its
* existing position.</li>
* <li>Insert the detached node at the beginning of the list using
* {@link #addNodeAtFirst(Node)}.</li>
* </ol>
*
* <p>
* This operation does not create a new node. It reuses the existing node and
* adjusts the links, maintaining the integrity of the doubly linked list.
*
* @param node the existing node to move to the beginning of the list
*/
private void moveNodeToFirst(Node<K, V> node) {
if (node == first) {
return;
}
if (node == last) {
last = node.prev;
}
Node<K, V> next = node.next;
Node<K, V> prev = node.prev;
if (next != null) {
next.prev = prev;
}
if (prev != null) {
prev.next = next;
}
node.prev = null;
node.next = null;
addNodeAtFirst(node);
}
public void printCache() {
System.out.println(" MRU LRU");
if (first == null) {
System.out.println(" | |");
System.out.println(" v v");
System.out.println("first --> [Empty Cache] <-- last");
return;
}
System.out.println(" | |");
System.out.println(" v v");
Node<K, V> current = first;
StringBuilder top = new StringBuilder();
StringBuilder middle = new StringBuilder();
StringBuilder bottom = new StringBuilder();
while (current != null) {
String key = String.valueOf(current.key);
String display = String.format("%-4s", key.length() > 4 ? key.substring(0, 4) : key);
top.append("+------+");
middle.append("| ").append(display).append("|");
bottom.append("+------+");
if (current.next != null) {
top.append(" ");
middle.append(" <-> ");
bottom.append(" ");
}
current = current.next;
}
System.out.println("first --> " + top + " <-- last");
System.out.println(" " + middle);
System.out.println(" " + bottom);
}
}
LRUCacheDemo.java
package com.sample.app.cache;
public class LRUCacheDemo {
public static void main(String[] args) {
LRUCache<String, Object> cache = new LRUCache<>(3);
cache.get("A");
cache.get("B");
cache.get("C");
cache.printCache();
// Access A: makes A the most recently used
cache.get("A");
// Insert D: evicts D
cache.get("D");
cache.printCache();
// Access C: makes C the most recently used
cache.get("C");
// Insert E: evicts A
cache.get("E");
cache.printCache();
}
}
Output
Accessing the key : A
Accessing the key : B
Accessing the key : C
MRU LRU
| |
v v
first --> +------+ +------+ +------+ <-- last
| C | <-> | B | <-> | A |
+------+ +------+ +------+
Accessing the key : A
Accessing the key : D
MRU LRU
| |
v v
first --> +------+ +------+ +------+ <-- last
| D | <-> | A | <-> | C |
+------+ +------+ +------+
Accessing the key : C
Accessing the key : E
MRU LRU
| |
v v
first --> +------+ +------+ +------+ <-- last
| E | <-> | C | <-> | D |
+------+ +------+ +------+
Conclusion
LRU Cache is a useful caching strategy for applications that need to manage limited memory while retaining frequently accessed data.
By combining a HashMap and a Doubly Linked List, we can implement an LRU Cache with O(1) average-time lookup, insertion, repositioning, and eviction.
The HashMap helps us locate nodes quickly, while the doubly linked list maintains the access order.
Understanding this implementation provides a good foundation for learning more advanced caching strategies and designing efficient caching systems in Java.
You may like
Creating Case-Insensitive Maps in Java: Simplifying Lookups with Lowercase Keys
Utility class to get primitive type from wrapper type and vice versa
FNV hash algorithm implementation in Java
Controlling Randomness in Java: Exploring the Role of Seeds in java.util.Random
Calculating initial capacity from expected size and load factor
No comments:
Post a Comment