Embedding LRU Cache in Java

Question

I saw the following code, and I think there is a useless while loop in the implementation of the addElement method. There should never be more items except for size + 1, as a write lock already exists. So why does the addElement method remove elements until it receives this condition true

while(concurrentLinkedQueue.size() >=maxSize) 

Any pointers around this would be great.

Here is the implementation:

 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

dot here, I think you need to check if the LRU matches the maximum size. the check here is NOT (map.size ()> maxSize), it is "> =". now you will probably replace this with "if (map.size () == maxSize) {...}" - which under ideal conditions should do the same.

but in non-ideal conditions, if for some reason someone puts an EXTRA record on a card without checking, then with this code the card will NEVER decrease in size again, because the if condition will never be true.

therefore - why not "while" and "> =" instead of "if" and "=="? the same amount of code, as well as more reliable against "unexpected" conditions.

Answer 2

A simple LRU cache implementation does the following: a while loop is needed only when the maximum size is configured, but not for primitive operations:

• During put, remove the superflous element.
• While receiving, move the item up.

Primitive operations will be done in one shot. You can then use a regular, synchronized or read write lock around this data structure.

When using read-write locks, justice to who comes first is more likely a problem of the read-read locks used than the LRU cache itself.

Here is an example implementation.