Implement LRU cache using LinkedHashMap

By default LinkedHashMap stores elements in the order they inserted. LinkedHaspMap provides one special constructor, that is used to get the elements of LinkedHashMap in their access order, that is from least-recently accessed to most-recently access-order.

public LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder)

Above constructor is used to define a access-order linked hash map. If the argument 'accessOrder' is true, then it constructs linked hash map using access order of the keys, else insertion order of the keys.

Example

Map<Integer, String> map = new LinkedHashMap<>(10, 0.75f, true);

By overridding the method ‘removeEldestEntry’ of LinkedHashMap class, you can use LinkedHashMap as LRU cache.

private static final int MAX_ENTRIES = 5;

@Override

protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {

         return size() > MAX_ENTRIES;

}

Above override allow the map to grow up to 5 entries and then delete the eldest entry each time a new entry is added, maintaining a steady state of 100 entries. If the map is an access-ordered map, eldest entry is the least recently accessed entry. If map is not an access-ordered map, eldest entry is the least recently inserted entry.

Find the complete working application.

Test.java

import java.util.LinkedHashMap;
import java.util.Map;

public class Test {

 private static Map<Integer, String> getLRUMap() {
  return new LinkedHashMap<Integer, String>(2, (float) 0.75, true) {
   private static final long serialVersionUID = 1L;
   private static final int MAX_ENTRIES = 5;

   @Override
   protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
    return size() > MAX_ENTRIES;
   }
  };
 }

 private static void printMap(Map<Integer, String> map) {

  System.out.println("\n***************************************");
  for (Map.Entry<Integer, String> entry : map.entrySet()) {
   System.out.println(entry.getKey() + " : " + entry.getValue());
  }
  System.out.println("***************************************");

 }

 public static void main(String args[]) {
  Map<Integer, String> map = getLRUMap();

  map.put(1, "Krishna");
  map.put(2, "Hari");
  map.put(3, "Ram");
  map.put(4, "Joel");
  map.put(5, "Kiran");

  printMap(map);

  System.out.println("Accessing the keys 1, 2, 5");

  map.get(1);
  map.get(5);
  map.get(2);

  System.out.println("Inserting the key 6");

  map.put(6, "Naveen");
  printMap(map);

 }
}

Output

***************************************
1 : Krishna
2 : Hari
3 : Ram
4 : Joel
5 : Kiran
***************************************
Accessing the keys 1, 2, 5
Inserting the key 6

***************************************
4 : Joel
1 : Krishna
5 : Kiran
2 : Hari
6 : Naveen
***************************************

As you observe above output, initially map has 1, 2, 3, 4, 5 keys.  After that I accessed 1, 2, 5 keys. When I tried to insert the key 6, it removes the key 3 (Since 3 is the least recently used key) and add the key 6.

You may like

Why to implement Comparable?

Is operations on primitive types are atomic?

What is null in Java?

Can I pass null to append method of StringBuilder?

Why and how to set JAVA_HOME

Interview Questions