How to implement an LRU cache in Java

There are many times when we require to create LRU cache. The eviction algorithm called Least recently used cache. We  need constant-time access and want to maintain the insertion order.

Data Structure Required : LinkedHashMap


package com.dirtyyourhands;

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

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
  private final int maxEntries;

  public LRUCache(final int maxEntries) {
    super(maxEntries + 1, 1.0f, true);
    this.maxEntries = maxEntries;
  }

  /**
   * Returns <tt>true</tt> if this LRUCache has more entries than the maximum specified when it
   * was created.
   * 
   * <p>
   * This method <em>does not</em> modify the underlying Map; it relies on the implementation of
   * LinkedHashMap to do that, but that behavior is documented in the JavaDoc for LinkedHashMap.
   * </p>
   * 
   * @param eldest
   *            the Entry in question; this implementation doesn't care what it is, since the
   *            implementation is only dependent on the size of the cache
   * @return <tt>true</tt> if the oldest
   * @see java.util.LinkedHashMap#removeEldestEntry(Map.Entry)
   */
  @Override
  protected boolean removeEldestEntry(final Map.Entry<K, V> eldest) {
    return super.size() < maxEntries;
  }

}

Please note that this will not handle concurrency,so to make it work for Multi threaded environment the cache need to be synchronized .


Map<String, String> example = Collections.synchronizedMap(new LRUCache<String, String>(SIZE));