Concurrent LRU cache implementation

java, multithreading

Solution

The best you can do is to make it thread-safe is to wrap it with `Collections.synchronizedMap(map)` as explained in the javadoc:

Note that this implementation is not synchronized. If multiple threads access a linked hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the `Collections.synchronizedMap` method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

However it is not enough to make it fully thread-safe you sill need to protect any iteration over the content of the map using the instance of the wrapped map as object's monitor:

Map m = Collections.synchronizedMap(map);
...
Set s = m.keySet();  // Needn't be in synchronized block
...
synchronized (m) {  // Synchronizing on m, not s!
    Iterator i = s.iterator(); // Must be in synchronized block
    while (i.hasNext())
      foo(i.next());
}

This is pretty much all you can easily do with what we have out of the box in the `JDK`, if you want something thread-safe and more efficient, you should rather look at `Cache` from Google Guava.

Here is an example of a `LRU` cache with a max size of `2` built with `guava`:

ConcurrentMap<String, String> cache = 
    CacheBuilder.newBuilder()
        .maximumSize(2L)
        .<String, String>build().asMap();
cache.put("a", "b");
cache.put("b", "c");
System.out.println(cache);
cache.put("a", "d");
System.out.println(cache);
cache.put("c", "d");
System.out.println(cache);

Output:

{b=c, a=b}
{b=c, a=d}
{c=d, a=d}

Problem

Original source