Java concurrent Map of List

Question

I need concurrent HashMap of List as value with following behavior:

• count of read/write ops approximately equals
• support add/remove values in lists
• thread safe iterations over lists

After some research I implemented ConcurrentMapOfList, but I'm not sure in his correctness.

public class ConcurrentMapOfList<Key, ListValue> {
 private final ConcurrentMap<Key, ConcurrentList<ListValue>> values
 = new ConcurrentHashMap<Key, ConcurrentList<ListValue>>();
 public void add(Key key, Value value) {
 List<Value> list = values.get(key);
 if (list == null) {
 final ConcurrentList<Value> newList = new ConcurrentList<Value>();
 final ConcurrentList<Value> oldList = values.putIfAbsent(key, newList);
 if (oldList == null) {
 list = newList;
 } else {
 list = oldList;
 }
 }
 list.add(value);
 }
 public List<ListValue> remove(Key key) {
 return values.remove(key);
 }
 public boolean remove(Key key, ListValue value) {
 final List<ListValue> list = values.get(key);
 if (list == null) {
 return false;
 }
 return list.remove(value);
 }
 public List<ListValue> obtainListCopy(Key key) {
 final ConcurrentList<ListValue> list = values.get(key);
 if (list == null) {
 return Collections.emptyList();
 }
 return list.clone();
 }
 public void removeAll() {
 values.clear();
 }
 private class ConcurrentList<V> extends ArrayList<V> {
 final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
 final Lock readLock = lock.readLock();
 final Lock writeLock = lock.writeLock();
 @Override
 public boolean add(V v) {
 writeLock.lock();
 try {
 return super.add(v);
 }finally {
 writeLock.unlock();
 }
 }
 @Override
 public V remove(int index) {
 writeLock.lock();
 try {
 return super.remove(index);
 }finally {
 writeLock.unlock();
 }
 }
 @Override
 public ConcurrentList<V> clone() {
 readLock.lock();
 try {
 return (ConcurrentList<V>)super.clone();
 }finally {
 readLock.unlock();
 }
 }
 }
}

• tb-: Is there a reason you do not use the wrapper interface synchronizedMap from Collections? It seems to me that this would be the easier and safer solution. From a quick look, your implementation will e.g. fail if you add element and copy it in parallel.
• komelgman: ConcurrentMap better than syncronizedMap and I need additional synchronization on values of map(some Lists). Copy and changes list isn't be failed, because they synchronized with one ReadWriteLock
• komelgman: Map of List it is MultiMap, for example in guava collections
• tb-: For unknown reasons, I did not see this other part. Thanks for the hint. Then just one minor additional comment: I think you mixed up Value and ListValue at some places. At least, this will not compile in the current state (but is trivial to change)
• komelgman: About Value and ListValue you are right. It happened at editing this question.

Answer 1

Ok, after the hint from the comment it makes more sense for me. I felt a bit bad because of the wrong comment, so I have investigated this deeper.

As far as I see it, there is only one problem which I will explain in the next paragraph. But I have to admit, the implementation is rather complex because we have several layers of parallelization and locking with multiple data structures. It would need very carefully analysis to prove the correctness.

The problem I found is the remove method. You have implemented remove(int):

@Override
public V remove(int index) {
 writeLock.lock();
 try {
 return super.remove(index);
 }finally {
 writeLock.unlock();
 }
}

But you are using remove(Object):

public boolean remove(Key key, ListValue value) {
 final List<ListValue> list = values.get(key);
 if (list == null) {
 return false;
 }
 return list.remove(value);
}

Test case to show it:

 final int max = 500;
 final int maxThreads = 200;
 for (int i = 0; i < max; i++) {
 final int currentI = i;
 final List<Thread> threadList = new ArrayList<>();
 for (int j = 0; j < maxThreads; j++) {
 final int currentJ = j;
 threadList.add(new Thread(new Runnable() {
 @Override
 public void run() {
 map.add(currentI, currentJ);
 map.remove(currentI, currentJ);
 }
 }));
 }
 for (final Thread thread : threadList)
 thread.start();
 for (final Thread thread : threadList)
 thread.join();
 }
 if (map.getEntrySet().size() != max)
 System.err.println("entryset size should be: " + maxThreads + " is:" + map.getEntrySet().size());
 for (final Entry<Integer, ConcurrentList<Integer>> entry : map.getEntrySet()) {
 final ConcurrentList<Integer> value = entry.getValue();
 if (value.size() != 0)
 System.err.println("value size should be: " + 0 + " is:" + value.size() + ", value: " + value);
 }

This can easily be solved, if you just implement the remove(Object) method:

@Override
public boolean remove(final Object o) {
 writeLock.lock();
 try {
 return super.remove(o);
 } finally {
 writeLock.unlock();
 }
}

This errors could be avoided if you use one of the following patterns:

• Use a synchronized list here, Vector (not recommended), CopyOnWriteArrayList or Collections.synchronizedList

• Use encapsulation, rather then extension. Do not extend ArrayList, use implements List and use a member field with the backed up data structure. This will be in the end, nearly the same as using Collections.synchronizedList, but you could avoid the mutex and use the ReantrantLocks if you really need it

As already partly mentioned in my comment. To get the code running, I had to change the generic identifier Value to ListValue at some places, it looked like they were mixed up.

• komelgman: My bad, I really wanted implement remove(Object). I found some info on stackoverflow.
• komelgman: My current implementation uses ConcurrentLinkedQueue