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?
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); }
}
}
synchronized keyword on the methods themselves?
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.
