Thread-safe LRU Cache Implementation in Java

Question

I am trying to implement a thread-safe LRU cache algorithm, please review my code and would really appreciate some criticism or suggestion.

Some assumptions:

1. capacity will be larger than 0

Some questions I have:

1. I know it is better to encapsulate variables in a class and declare them private, but since DDLNode is simply a data class, is it acceptable to make the variables public ?

2. I am considering to extract the following block of code (inside put) into a function (something like addEntry(key, value)

   DDLNode<K, V> node = new DDLNode<>(key, value); addNode(node); entries.put(key, node); 

   do you think it's neccesary? or the original code is self-explanatory enough?

Here is the code, Thanks in advance!!

import java.util.HashMap; import java.util.Map; import java.util.concurrent.locks.ReentrantLock; interface CacheAlgorithm<K, V> { public V get(K key); public void put(K key, V value); } class DDLNode<K, V> { public V value; public K key; public DDLNode<K, V> prev; public DDLNode<K, V> next; public DDLNode() {} public DDLNode(K key, V value) { this.key = key; this.value = value; } } public class LRU<K, V> implements CacheAlgorithm<K, V> { private final ReentrantLock lock; private final int capacity; private final Map<K, DDLNode<K, V>> entries; private final DDLNode<K, V> head; private final DDLNode<K, V> tail; public LRU(int capacity) { this.capacity = capacity; lock = new ReentrantLock(); head = new DDLNode<>(); tail = new DDLNode<>(); entries = new HashMap<>(capacity); head.next = tail; tail.prev = head; } @Override public V get(K key) { lock.lock(); try { if (!entries.containsKey(key)) { return null; } DDLNode<K, V> node = entries.get(key); moveToMostRecent(node); return node.value; } finally { lock.unlock(); } } @Override public void put(K key, V value) { lock.lock(); try { if (entries.containsKey(key)) { DDLNode<K, V> node = entries.get(key); node.value = value; moveToMostRecent(node); } else { if (entries.size() == capacity) { removeLeastRecentEntry(); } DDLNode<K, V> node = new DDLNode<>(key, value); addNode(node); entries.put(key, node); } } finally { lock.unlock(); } } private void removeLeastRecentEntry() { entries.remove(tail.prev.key); removeNode(tail.prev); } private void moveToMostRecent(DDLNode<K, V> node) { removeNode(node); addNode(node); } private void removeNode(DDLNode<K, V> node) { DDLNode<K, V> prev = node.prev; DDLNode<K, V> next = node.next; prev.next = next; next.prev = prev; } private void addNode(DDLNode<K, V> node) { DDLNode<K, V> headNext = head.next; head.next = node; node.prev = head; headNext.prev = node; node.next = headNext; } } ```

Answer 1

I like the codestyle!

Code organization tips:

• Its better to move DDLNode into LRU and make it static, because sole purpose of this class is to be used by LRU class.

• If you are not going to expose DDLNode to outside world, then it make sense to make it also private. Keeping its fields as public is fine here.

• If you want to expose DDLNode to outside world (for example, in iterator), you should think more thoroughly about field access. You can get inspiration from HashMap.Node class, for example: fields here have default access, so HashMap itself can manipulate them without using getter or setters. Also note, that there is no setKey() method for outside world, because if we change the key on the node it will break the map.

• Maybe you just put all the classes into 1 file to make it easies for us to read , but if not - its bad practice to have more than 1 class/interface in 1 file.

Optimization tips:

• In get() you are doing unnecessary .containsKey() call, because just .get(key) is enough: if key if present, it will find it; if not, then it will return null and you can then just return from method.

• Unnecessary containsKey() call in put() as well: you can just check .get(key) == null instead.

• head and tail will always occupy memory, event if map is empty. They could be removed, although then you should be more careful will null checks.