Implementing an LRU cache with built in data structures

Question

I want to implement a simple LRU cache in Java using only Java's built in data structures.

The idea is to use a Map and a doubly linked list (DLL).

So for Map I'm using HashMap. The problem I'm facing now is that I want that an item in the HashMap will point to the corresponding item in the DLL, but I don't have an access to the internal nodes of the LinkedList.

What could be a reasonable solution without creating my own new data structure?

score 2 · Accepted Answer · edited May 23 '18 at 14:59

You can use Java LinkedHashMap and override removeEldestEntry to implement LRU cache

public class SimpleLru<K, V> extends LinkedHashMap<K, V>{

    final int cacheSize;

    public SimpleLru(int cacheSize) {
        this.cacheSize = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return this.size() > this.cacheSize;
    }

    public static void main(String[] args) {
        SimpleLru<String, Integer> m = new SimpleLru<>(2); // Max 2
        m.put("k1", 1); // k1:1
        m.put("k2", 2); // k1:1, k2:2
        m.put("k3", 3); // k2:2, k3:3
    }
}

If you want to have a thread-safe version, you can use:

public class ConcurrentLru<K, V> {

    final Object mutex = new Object();
    final Map<K, V> cache;

    public ConcurrentLru(final int cacheSize) {
        this.cache = new LinkedHashMap<K, V>() {

            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return this.size() > cacheSize;
            }
        };
    }

    public void put(K k, V v) {
        synchronized (this.mutex) { this.cache.put(k, v); }
    }

    public boolean contains(K k) {
        synchronized (this.mutex) { return this.cache.containsKey(k); }
    }

    public V remove(K k) {
        synchronized (this.mutex) { return this.cache.remove(k); }
    }

    public V get(K k) {
        synchronized (this.mutex) { return this.cache.get(k); }
    }
}

Out of interest, why are you synchronizing on a mutex rather than using the `synchronized` keyword on the methods themselves? — ᴇʟᴇvᴀтᴇ, May 23 '18 at 15:02
@ᴇʟᴇvᴀтᴇ: You can use synchronized on the methods - similar to synchronized (this). I prefer lighter version of mutex - new Object() — LHA, May 23 '18 at 15:12
Check this: https://stackoverflow.com/questions/574240/is-there-an-advantage-to-use-a-synchronized-method-instead-of-a-synchronized-blo — LHA, May 23 '18 at 15:17

score 1 · Answer 2 · answered May 23 '18 at 14:36

I would try to dissuade you from reinventing a wheel that has plenty of excellent existing implementations. E.g. Google Guava's caches are great. They provide several ways to evict cached elements. Also, Caffeine (written by a developer who worked on Guava's cache), and EhCache that has a long history.

If there's some reason you have to do it yourself, have a look at this question and the answers.

Implementing an LRU cache with built in data structures

2 Answers2