Designing a Least recently used cache is an important piece in the software development where an element is removed from the cache if the size of the cache is reaches to the capacity.
Caching is always helpful in the faster retrieval and gives O(1) or constant time retrieval complexity.
Map data structure are helpful in achieving the O(1) time complexity and other data structures like Queue or Stack could be a solution where pop or remove method are useful in adding new element in the data structure in a constant time or using doubly linked list could also be one solution for this caching.
To provide a solution , I have used an implementation using the LinkedHashMap which has the property of giving the least recently used element with the iterator . First element is always an LRU element in the map.
I will demonstrate the same using the following code snippet :
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
/**
* @author sachin.srivastava
* tek9g.blogspot.com
*
*/
public class LRUCaching<T> {
private int capacity;
private LinkedHashMap<String, T> map;
public LRUCaching(int capacity) {
this.capacity = capacity;
map = new LinkedHashMap<>();
}
public T get(String key){
T t = this.map.get(key);
if(t == null){
return null;
} else {
this.set(key, t);
return t;
}
}
public void set(String key,T value){
if(this.map.containsKey(key)){
this.map.remove(key);
} else if(this.map.size() == this.capacity){
Iterator<String> it = this.map.keySet().iterator();
it.next();
it.remove();
}
this.map.put(key, value);
}
public static <T> void printMap(Map<String, T> map){
System.out.println("\n--printing the map elements--\n");
for (Entry<String, T> entry : map.entrySet()) {
System.out.println("key=" + entry.getKey() + " and value=" + entry.getValue());
}
}
public static void main(String[] args) {
LRUCaching<Integer> lru = new LRUCaching<>(5);//capacity of 5 elements.
lru.set("a", 1);
lru.set("b", 2);
lru.set("c", 3);
lru.set("d", 4);
lru.set("e", 5);
printMap(lru.map);
System.out.println("\nget key=a and value=" + lru.get("a"));// it will move key a to front and b would be at the rear.
printMap(lru.map);
//setting the element beyond the capacity
lru.set("f", 6);//it will remove the least used key b
printMap(lru.map);
}
}
Output :
--printing the map elements--
key=a and value=1
key=b and value=2
key=c and value=3
key=d and value=4
key=e and value=5
get key=a and value=1
--printing the map elements--
key=b and value=2
key=c and value=3
key=d and value=4
key=e and value=5
key=a and value=1
--printing the map elements--
key=c and value=3
key=d and value=4
key=e and value=5
key=a and value=1
key=f and value=6
--------------------------------------
In the above example the Map always contains the number of elements as per the capacity and as it reaches the limit , it removes the Least Recently Used element from the map. As soon as an element is get from the map , it ranks higher in the map so is the case when key 'a' is get , it moves the key in the above to key 'b' which becomes the LRU element so when adding a new key 'f' it shows the capacity is reached and hence the LRU element which is removed from the map and allows a new key to inserted in the map.
Enjoy the coding!!!!
