How to build a simple LRU cache

Short answer

An LRU cache keeps a limited number of entries and, when full, removes the one that has not been used for the longest time. A LinkedHashMap in access order does this for you:

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
 
    LruCache(int capacity) {
        super(16, 0.75f, true);
        this.capacity = capacity;
    }
 
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}
 
void main() {
    var cache = new LruCache<String, Integer>(2);
    cache.put("a", 1);
    cache.put("b", 2);
    cache.get("a");
    cache.put("c", 3);
 
    IO.println(cache);
}

Output:

{a=1, c=3}

The third constructor argument true turns on access order: get("a") moves a to the end, so b is evicted.

A cache of computations

Together with computeIfAbsent() the cache remembers the results of expensive calculations:

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
 
    LruCache(int capacity) {
        super(16, 0.75f, true);
        this.capacity = capacity;
    }
 
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}
 
int slowSquare(int n) {
    IO.println("computing " + n);
    return n * n;
}
 
void main() {
    var cache = new LruCache<Integer, Integer>(100);
 
    IO.println(cache.computeIfAbsent(4, this::slowSquare));
    IO.println(cache.computeIfAbsent(4, this::slowSquare));
}

Output:

computing 4
16
16

Common mistake

Forgetting the third constructor argument. Without it a LinkedHashMap keeps insertion order, and the oldest entry is evicted even if it was just read:

void main() {
    var cache = new LinkedHashMap<String, Integer>() {
        @Override
        protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
            return size() > 2;
        }
    };
    cache.put("a", 1);
    cache.put("b", 2);
    cache.get("a");
    cache.put("c", 3);
 
    IO.println(cache);
}

Output:

{b=2, c=3}

This cache is not thread-safe. If several threads use it, wrap it in Collections.synchronizedMap() or use a ready-made library such as Caffeine.

Thanks for reading!

Short answer

A cache of computations

Common mistake

Functions used in this recipe

Thanks for reading!