LRU Cache is a caching strategy where we use Least Recently Used (LRU) eviction policy when the cache is full and we want to add more new data to the cache. LRU cache is used in many caching applications. For example memcached uses LRU cache.
I have implemented a simple LRU Cache. The code is far from production use. First of all it is not thread safe and I have not used template programming to make it generic. The code is just to illustrate one of the possible ways of implementing an LRU Cache.
The implementation is inspired from Sun Java LinkedHashMap implementation. For serious production use one should use the LinkedHashMap implementation. The code here is just to illustrate the data structure used.
I have used a doubly-linked list and a hashmap. All the key-value pairs are saved in a node of doubly-linked list and these nodes are hashed on the key in the hashmap. This allows for O(1) time access. The node corresponding to the most recently used key-value pair is always at the head of the linked list and the node corresponding to the least recently used key-value pair is always at the tail of the linked list. Time complexity for ‘get’ and ‘put’ operation is O(1) and the space complexity is O(n), where n is the maximum capacity of cache.
Here goes the code -
public class Node {
public Node prev;
public Node next;
public String key;
public String data;
public Node()
{
}
public Node(String key, String data)
{
this.key = key;
this.data = data;
}
}
import java.util.*;
public class LRUCache {
private Node head;
private Node tail;
private int maxSize;
private HashMap<String, Node> m = new HashMap<String, Node>();
// Constructor - maxSize is the maximum capacity of the cache
public LRUCache(int maxSize)
{
this.maxSize = maxSize;
head = new Node(null, null);
tail = new Node(null, null);
head.next = tail;
tail.prev = head;
}
private void addElementToListAtHead(Node node)
{
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
private void removeElementFromList(Node node)
{
node.prev.next = node.next;
node.next.prev = node.prev;
}
// Function to access data from the cache
public String get(String key)
{
Node node = m.get(key);
if(node == null)
return null;
if(m.size() == 1)
return node.data;
removeElementFromList(node);
addElementToListAtHead(node);
return node.data;
}
// Function to add new data or modify existing data in the cache
public void put (String key, String data)
{
if(maxSize <= 0)
return;
Node node = m.get(key);
if (node != null)
{
removeElementFromList(node);
addElementToListAtHead(node);
node.data = data;
} else {
node = new Node(key, data);
m.put(key, node);
addElementToListAtHead(node);
if(m.size() > maxSize)
{
m.remove(tail.prev.key);
removeElementFromList(tail.prev);
}
}
return;
}
}
Please point out the obvious/non-obvious bugs in the code. And also provide suggestions for better implementation.