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.

• yploo: Thanks a lot for your comments! Appreciated it.Some followup to your comment: 1. The DDLNode class is actually gonna be used if other classes ( I actually have another cache algo class MRU), how can the HashMap.Node design be applied in that case? 2.if DDLNode is used by mutlipled classes, you think i can still keep the fields public? (I do know it's an anti-pattern but also think using setter and getter function everywhere is quite messy :p, need a second opinion) Thanks.
• Flame239: @yploo First of all, what this DDLNode? Abbreviations, especially not widely known, are confusing. My guess is that its DoublyLinkedListNode (which is DLLNode - even more confusing name). Anyways, if you are going to implement Most recently used cache - you can just use this class for both - the only difference will be in removeLeast/MostRecentEntry() method. In this case keeping Node class as private static makes total sense. My example about HashMap.Node was to show that if you want to expose those nodes, you should be careful what getters/setters you expose