java Thread-safe LRUCache implementation

Question

What is best way to implement thread-safe LRUCache in java? Please review this one. Is there any better approach which can be taken here?

package cache;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class LRUCache<K,V> {
 private ConcurrentLinkedQueue<K> concurrentLinkedQueue = new ConcurrentLinkedQueue<K>();
 private ConcurrentHashMap<K,V> concurrentHashMap = new ConcurrentHashMap<K, V>();
 private ReadWriteLock readWriteLock = new ReentrantReadWriteLock();
 private Lock readLock = readWriteLock.readLock();
 private Lock writeLock = readWriteLock.writeLock();
 int maxSize=0;
 public LRUCache(final int MAX_SIZE){
 this.maxSize=MAX_SIZE;
 }
 public V getElement(K key){
 readLock.lock();
 try {
 V v=null;
 if(concurrentHashMap.contains(key)){
 concurrentLinkedQueue.remove(key);
 v= concurrentHashMap.get(key);
 concurrentLinkedQueue.add(key);
 }
 return v;
 }finally{
 readLock.unlock();
 }
 }
 public V removeElement(K key){
 writeLock.lock();
 try {
 V v=null;
 if(concurrentHashMap.contains(key)){
 v=concurrentHashMap.remove(key);
 concurrentLinkedQueue.remove(key);
 }
 return v;
 } finally {
 writeLock.unlock();
 }
 }
 public V addElement(K key,V value){
 writeLock.lock();
 try {
 if(concurrentHashMap.contains(key)){
 concurrentLinkedQueue.remove(key);
 }
 while(concurrentLinkedQueue.size() >=maxSize){
 K queueKey=concurrentLinkedQueue.poll();
 concurrentHashMap.remove(queueKey);
 }
 concurrentLinkedQueue.add(key);
 concurrentHashMap.put(key, value);
 return value;
 } finally{
 writeLock.unlock();
 }
 }
}

Answer 1

Advice 1

This implementation is not thread safe. For example, if two threads invoked getElement(key1) simultaneously, they may runs to concurrentLinkedQueue.add(key) at same times(they both performed delete and get, but delete will fail the second time or just do nothing), then two same keys will be added.

Advice 2

Maybe capacity is more suitable than maxSize.

Advice 3

LinkedHashMap is often used as LRU cache.

• JaDogg: Why does the number 1 happen? Doesn't the key get removed and added? Isn't concurrent containers thread safe.
• lauthu: @422_unprocessable_entity the three operations inside if block is not atomic. If two threads running to concurrentLinkedQueue.add(key); at same times(they both performed delete and get, but delete will fail the second time or just do nothing), two same keys will be added.
• JaDogg: Yes you are correct. Well done on catching it. :) Can you insert the explanation in the answer as well.

Answer 2

Advice 1

public class LRUCache<K,V>

You have two spaces between class and LRUCache.

Advice 2

v=null

In professional Java programming, it is customary to have a single space before and after each binary operator.

Advice 3

public V getElement(K key){
 readLock.lock();
 try { ... } ...

Looks strange to me. Why not have instead the following:

public V getElement(K key){
 readLock.lock();
 try { ... } ...

Advice 4

int maxSize=0;

First of all, I suggest you make it private. Also, there is no need to initialize member ints with zero, that is done by Java by default. Other fundamental types are initialized to zero too.

Advice 5

public LRUCache(final int MAX_SIZE)

It is idiomatic to name only constants with UPPER CASE. Constructor (and method) parameters are advised to be in camelCase.

Advice 6

private ConcurrentHashMap<K,V> concurrentHashMap = new ConcurrentHashMap<K, V>();

You could omit type parameters in new ConcurrentHashMap<K, V> thanks to diamond inference. Also, you could declare all the members instead of maxSize to final:

private final ConcurrentHashMap<K,V> concurrentHashMap = new ConcurrentHashMap<>();

Advice 7

ConcurrentHashMap<K,V>

It is also customary to have a single space after each comma character: <K,_V>.

Advice 8

concurrentLinkedQueue and concurrentHashMap. These are not the best possible names for the two data structures. Instead of naming them according to their type I instead suggest to name them according to what they do.

Answer 3

Advice 1

Rename concurrentHashMap to internalCache

Advice 2

Rename concurrentLinkedQueue to trackingQueue

Advice 3

Declare using Queue Interface:

Queue<K> trackingQueue = new ConcurrentLinkedQueue<>();

Advice 4

Your get API implementation is not thread safe as pointed out in one of the comments above. You can do the getElement implementation as follows to make sure that a simultaneaous remove from queue for same element does not result in adding back duplicate element to queue:

public V getElement(K key){
 readLock.lock();
 try {
 V value = internalCache.get(key);
 if(value != null){
 if (trackingQueue.remove(key)) {
 trackingQueue.add(key);
 }
 }
 return value;
 } finally {
 readLock.unlock();
 }
}