A friend of mine asked me about LRU cache and while explaining the same I could not locate a simple implementation one by just googling it.
The Java util provides a beautiful implementation through LinkedHashMap. Which is a Hash table and linked list implementation of the Map interface, with predictable iteration order. In order to use it as an LRU cache, do the following,
- use constructor LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) and set the accessOrder to true. and,
- override the implementation for removeEldestEntry(Map.Entry eldest)
- please keep in mind that this is NOT an thread safe implementation and to have thread safety for this LinkedHashMap, you can do something like Map m = Collections.synchronizedMap(new LinkedHashMap(…)), if multiple threads may use the map.
You can of-course look at the implementation of LinkedHashMap for reference and it is really awesome how implemented but I thought to write up my own implementation for LRU cache using a HashMap and a linked list with minimal functionality. So this implementation provides a LRU cache implementation in Java using Hashmap and a doubly linked list.
package com.das.yadab.java;
import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V> {
public static final int MAX_SIZE = 100; // Default max size for the cache to grow.
private Entry<K, V> head;
private HashMap<K, Entry> internalCache;
private int maxSize;
public LRUCache() {
this.head = new Entry(null, null);
head.before = head.after = head;
internalCache = new HashMap<K, Entry>();
maxSize = MAX_SIZE;
}
public LRUCache(int maxSize) {
this.head = new Entry(null, null);
head.before = head.after = head;
internalCache = new HashMap<K, Entry>();
this.maxSize = maxSize;
}
/**
* Gets value associated with the specified key from cache.
*
* @param key
* @return value or null if not found
*/
public V get(Object key) {
Entry<K, V> e = internalCache.get(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
/**
* Associates key and value in the cache, null value is not allowed.
* If cache size has grown more than the allowed capacity the eldest member will be evicted.
*
* @param key
* @param value
* @return
*/
public V put(K key, V value) {
if (value == null) {
throw (new IllegalArgumentException("Null Value association is not helpful in caching"));
}
if(internalCache.containsKey(key)){
internalCache.get(key).setValue(value);
internalCache.get(key).recordAccess(this);
return;
}
if (shouldRemoveEldestEntry()) {
Entry eldest = head.after;
removeEntry(eldest);
}
Entry entry = new Entry(key, value);
entry.addBefore(head);
internalCache.put(key, entry);
return value;
}
private void removeEntry(Entry eldest) {
// since we do not allow null value association so this is safe.
if (internalCache.remove(eldest.key) != null) {
eldest.recordRemoval(this);
}
}
/*
Returns true if this map should remove its eldest entry.
if maxSize is not set during initialization the method will always return false.
*/
public boolean shouldRemoveEldestEntry() {
if (internalCache.size() > maxSize) {
return true;
}
return false;
}
static class Entry<K, V> implements Map.Entry<K, V> {
private Entry<K, V> before, after;
private K key;
private V value;
Entry(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
private void addBefore(Entry<K, V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
void recordAccess(LRUCache<K, V> cache) {
remove();
addBefore(cache.head);
}
final void recordRemoval(LRUCache<K, V> m) {
remove();
}
private void remove() {
before.after = after;
after.before = before;
}
@Override
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry) o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
@Override
public int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
@Override
public String toString() {
return "Entry key=" + key +
", value=" + value +
'}';
}
}
@Override
public String toString() {
return "LRUCache{" +
"internalCache=" + internalCache +
", head=" + head +
", maxSize=" + maxSize +
'}';
}
}
An example usage, since it only accesses the key “0”, it should retain the key “0” though it is added at the beginning.
LRUCache cache = new LRUCache(5);
for (int i = 0; i < 10; i++) {
cache.put(Integer.toString(i), i);
cache.get(Integer.toString(0));
}
Sycure 