java Thread-safe LRUCache implementation

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();
}
}
}


2 Answers

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.

• Why does the number 1 happen? Doesn't the key get removed and added? Isn't concurrent containers thread safe. – bhathiya-perera Mar 11 '19 at 9:02
• @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. – lauthu Mar 11 '19 at 9:33
• Yes you are correct. Well done on catching it. :) Can you insert the explanation in the answer as well. – bhathiya-perera Mar 11 '19 at 9:50

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.