This sample shows how to create a LRU cache, which is a map where the least recently used element is available in constant time.
How Does it Work?
Making an LRU cache can seem difficult, but there is a relatively simple trick to it. The key is in combining two data structures, a map and a linked list. Basically, we store a map and and an integer to represent its maximum capacity. Whenever we add an item to the map, we also add it to the front of the linked list. When the map is at its maximum capacity and we add another item, the last item in the linked list represents the least-recently used item in the map. So, we remove that least recently used item from the cache and the map and add the new item, returning the old item to the caller. We also need to make sure to update the map and the list when items are accessed with get() or when they are removed. An item accessed with get() becomes the most recently used item and has to be promoted to the front of the list.
Also note that we are really tracking the most recently used item and the least recently used item at the same time. One is the front of the linked list and the other is the back of the linked list.
Sample Implementation
The following code is heavily commented and fully functional. You may double click it to and copy it so that you can run it in your IDE of choice to help understand it better.
import java.util.LinkedList;
import java.util.Map;
import java.util.TreeMap;
//This data structure is designed to hold a limited-size cache
//in the form of a map, and to track the most and least recently
//used elements in the cache so that they can be retrieved in
//constant time.
public class LRUCache {
//Private members for the capacity, the map itself, and the
//list used to age elements.
private final int capacity;
private Map<String, String> cache;
private LinkedList<String> ageList;
//Constructor for initializing the cache.
public LRUCache(final int capacity) {
this.capacity = capacity;
cache = new TreeMap<>();
ageList = new LinkedList<>();
}
//Put a new element into the cache.
public String put(final String key, final String value) {
//If the cache is full, remove the oldest element and
//save it as the result. The oldest element is the
//last element in the age list.
String result = null;
if (cache.size() >= capacity) {
final String removed = ageList.removeLast();
cache.remove(removed);
result = removed;
}
//Add the new element to the cache and the front of the
//age list.
cache.put(key, value);
ageList.add(0, key);
//Return the removed element, or null if the cache was
//not yet full.
return result;
}
//Retrieve an existing element from the cache.
public String get(final String key) {
//Try and retrieve the value from the cache.
final String value = cache.get(key);
//If we found the value, re-add it to the front of the
//age list to record that it has been recently used.
if (value != null) {
ageList.remove(key);
ageList.addFirst(key);
}
//Return the value or null if it was not fund.
return value;
}
//Remove a value from the cache. If the given value is
//really found in the cache, make sure to remove it from
//the age list as well.
public String remove(final String key) {
final String value = cache.remove(key);
if (value != null) {
ageList.remove(key);
}
return value;
}
//Get the most recently used element in the cache.
public String getNewestElement() {
return ageList.getFirst();
}
//Get the least recently used element in the cache.
public String getOldestElement() {
return ageList.getLast();
}
//Return the cache contents.
@Override
public String toString() {
return cache.toString();
}
public static void main(String[] args) {
final LRUCache cache = new LRUCache(10);
cache.put("A", "Armadillo");
cache.put("B", "Bronco");
cache.put("C", "Camel");
cache.put("D", "Dingo");
cache.put("E", "Elephant");
cache.put("F", "Frog");
cache.put("G", "Giraffe");
cache.put("H", "Hawk");
cache.put("I", "Iguana");
cache.put("J", "Jaguar");
System.out.println(cache);
cache.put("K", "Koala");
System.out.println(cache);
System.out.println("Looking up B = " + cache.get("B"));
cache.put("L", "Lion");
System.out.println(cache);
System.out.println("Removing D = " + cache.remove("D"));
System.out.println(cache);
System.out.println("Adding M.");
cache.put("M", "Monkey");
System.out.println(cache);
System.out.println("Adding N.");
cache.put("N", "Newt");
System.out.println(cache);
}
}
Output From Example
{A=Armadillo, B=Bronco, C=Camel, D=Dingo, E=Elephant, F=Frog, G=Giraffe, H=Hawk, I=Iguana, J=Jaguar}
{B=Bronco, C=Camel, D=Dingo, E=Elephant, F=Frog, G=Giraffe, H=Hawk, I=Iguana, J=Jaguar, K=Koala}
Looking up B = Bronco
{B=Bronco, D=Dingo, E=Elephant, F=Frog, G=Giraffe, H=Hawk, I=Iguana, J=Jaguar, K=Koala, L=Lion}
Removing D = Dingo
{B=Bronco, E=Elephant, F=Frog, G=Giraffe, H=Hawk, I=Iguana, J=Jaguar, K=Koala, L=Lion}
Adding M.
{B=Bronco, E=Elephant, F=Frog, G=Giraffe, H=Hawk, I=Iguana, J=Jaguar, K=Koala, L=Lion, M=Monkey}
Adding N.
{B=Bronco, F=Frog, G=Giraffe, H=Hawk, I=Iguana, J=Jaguar, K=Koala, L=Lion, M=Monkey, N=Newt}
Coding Stream of Consciousness 