LRU algorithm is heavily used in most of the cache implementation. In general, most of the time we depend on heavy weighted caching implementation and end up paying huge for that softwares.
java.util.LinkedHashMap provides simplest way to do this by overriding a method removeEldestEntry().
Here, I would like to present as an utilit class which will be reused our needs. New class LRUHashMap created from LinkedHashMap and cacheSize limit has to be passed as argument.
LRUHashMap Implementation
LRUHashMap.java
import java.util.LinkedHashMap;
import java.util.Map;
/**
* LRUHashMap implements Least Recently Used algorithm to store and retrive the
* values from {Map}.
*/
public class LRUHashMap<K, V> extends LinkedHashMap<K, V> {
private static final long serialVersionUID = -6805360112277349979L;
private final static int DEFAULT_INITIALCAPACITY = 10;
private final static float LOADFACTOR = 0.75f;
/**
* Number of entries possible to keep maximum in given time in this {Map}
*/
private final int cacheSize;
public LRUHashMap() {
super(DEFAULT_INITIALCAPACITY, LOADFACTOR, true);
cacheSize = -1;
}
public LRUHashMap(int cacheSize) {
super(DEFAULT_INITIALCAPACITY, LOADFACTOR, true);
this.cacheSize = cacheSize;
}
/**
* @param initialCapacity
*/
public LRUHashMap(int initialCapacity, int cacheSize) {
super(initialCapacity, LOADFACTOR, true);
this.cacheSize = cacheSize;
}
/**
* @param m
*/
public LRUHashMap(Map<K, V> m, int cacheSize) {
super(DEFAULT_INITIALCAPACITY, LOADFACTOR, true);
putAll(m);
this.cacheSize = cacheSize;
}
/**
* @param initialCapacity
* @param loadFactor
*/
public LRUHashMap(int initialCapacity, float loadFactor, int cacheSize) {
super(initialCapacity, loadFactor, true);
this.cacheSize = cacheSize;
}
/** To achieve Thread Safe
* @return
*/
public Map<K, V> getsynchronizedMap()
{
return Collections.synchronizedMap(this);
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > cacheSize;
}
}
Test
LRUHashMapTest.java
public class LRUHashMapTest {
public static void main(String[] args) {
Map<Integer, String> map = new LRUHashMap<Integer, String>(10);
//Enables Thread Safe
//map = ((LRUHashMap<Integer, String>)map).getsynchronizedMap();
for (int i = 0; i < 100; i++) {
map.put(i, "valueof :" + i);
for (int j = i - 5; j >= 0; j--)
map.get(j);
}
System.out.println(map);
}
}
Here, Cache Size set to 10, hence at any given time only 10 entries will be stored in Map. Additionally, whenever read access happens that object will be removed from actual location and added to rear of Map.
Output:
{95=valueof :95, 96=valueof :96, 97=valueof :97, 98=valueof :98, 99=valueof :99,
4=valueof :4, 3=valueof :3, 2=valueof :2, 1=valueof :1, 0=valueof :0}
Thread Safe
The above mentioned implementation alone will not achieve thread safe. If our application is multi-threaded then we may need to fall-back to Collections.SynchronizedMap. We can achieve this by calling getsynchronizedMap(); in LRUHashMap.Map<Integer, String> map = ((LRUHashMap<Integer, String>)map).getsynchronizedMap();