Cache - Least Recently Used Algorithm

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();

PropertyIgnoreCase

java.util.Properties helps to store and retrieve the key-value pair, where non-null values in key and value. This implementation made on top of java.util.HashTable. We do get all the features and APIs of HashTable additionally, getProperty(...), load() APIs.

In getProperty method, key has to be passed as argument to retrive the value. We can even specify the default value also in it, if no key found in list.

Then, What makes different in this blog posting ?. Here, the key is case-sensitive one. We have to send exact word to get the value. Most of the time, we may need to retrieve value for case-insensitive key. This is where, why don't we extend the functionality to give support to retrieve value with case-insensitive key.

Here, Properties extended to create PropertyIgnoreCase class, and added two APIs - getPropertyIgnoreCase(String key), getPropertyIgnoreCase(String key, String defaultV)

import java.util.Iterator;
import java.util.Properties;
import java.util.Set;
import java.util.Map.Entry;

public class PropertyIgnoreCase extends Properties {

 private static final long serialVersionUID = 7511088737858527084L;

 /**
  * get value from {Properties}
  * 
  * @param props
  * @param key
  * @return
  */
 public String getPropertyIgnoreCase(String key) {
  return getPropertyIgnoreCase(key, null);
 }

 /**
  * get value from {Properties}, if no key exist then return default value.
  * 
  * @param props
  * @param key
  * @param defaultV
  * @return
  */
 public String getPropertyIgnoreCase(String key, String defaultV) {
  String value = getProperty(key);
  if (null != value)
   return value;

  // Not matching with the actual key then
  Set<Entry<Object, Object>> s = entrySet();
  Iterator<Entry<Object, Object>> it = s.iterator();
  while (it.hasNext()) {
   Entry<Object, Object> entry = it.next();
   if (key.equalsIgnoreCase((String) entry.getKey())) {
    return (String) entry.getValue();
   }
  }
  return defaultV;
 }

 public static void main(String[] args) {
  PropertyIgnoreCase props = new PropertyIgnoreCase();
  props.put("Abc", "Value of Abc");
  props.put("xYZ", "Value of xYZ");

  System.out.println("get Key 'XYZ' using API from Properties = "
    + props.getProperty("XYZ"));
  System.out.println("get Key 'XYZ' using new API  = "
    + props.getPropertyIgnoreCase("XYZ"));
 }

}

Output:
get Key 'XYZ' using API from Properties = null
get Key 'XYZ' using new API  = Value of xYZ