LruCache in Java

Java collections has LinkedHashMap which is a combination of a HashMap and a linked list which allows for predictable iteration order. There are two options for iteration - Based on insertion order, or based on Access order.

Now to create a Least Recently Used cache, the implementation need to use the access order for iteration and override the hook method removeEldestEntry() which should check the required size of the map to remove entries. I've posted the code in the example below.

Also present in the example is how you should *not* use the map in an multithreaded fashion. The class is not thread-safe and you end up with non deterministic behavior and the size invariant and probably other things go wrong.

	import java.util.LinkedHashMap;
	import java.util.Map;
	import java.util.concurrent.ExecutorService;
	import java.util.concurrent.Executors;
	import java.util.concurrent.ThreadLocalRandom;
	/**
	* A LRU Cache implementation based of LinkedHashMap
	* This implementation is NOT thread safe
	*/
	public class LruCache<K, V> extends LinkedHashMap<K, V> {
	private static final long serialVersionUID = 1L;
	private final int maxNumberOfEntries;
	public LruCache(final int maxNumberOfEntries) {
	super(maxNumberOfEntries + 1, 0.75f, true);
	this.maxNumberOfEntries = maxNumberOfEntries;
	}
	@Override
	public boolean removeEldestEntry(final Map.Entry<K, V> eldest) {
	return size() > maxNumberOfEntries;
	}
	private static final int PUT_COUNT = 1_000_000;
	private static final int MAX_ENTRIES = 7;
	private static final int THREAD_COUNT = 50;
	/**
	* Accessing the cache across multiple threads does cause indeterministic behaviour
	*/
	public static void main(String[] args) {
	final LruCache<String, Integer> cache = new LruCache<String, Integer>(MAX_ENTRIES);
	ExecutorService e = Executors.newFixedThreadPool(THREAD_COUNT);
	for (int i = 0; i < PUT_COUNT; i++) {
	e.submit(new Runnable() {
	@Override
	public void run() {
	int r = ThreadLocalRandom.current().nextInt();
	cache.put(Thread.currentThread().getName() + r, r);
	}
	});
	}
	e.shutdown();
	System.out.println("Size of cache is " + cache.size());
	}
	}

view raw LruCache hosted with ❤ by GitHub