Java concurrent Map of List 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&lt;Key, ListValue&gt; {
    private final ConcurrentMap&lt;Key, ConcurrentList&lt;ListValue&gt;&gt; values
            = new ConcurrentHashMap&lt;Key, ConcurrentList&lt;ListValue&gt;&gt;();

    public void add(Key key, Value value) {
        List&lt;Value&gt; list = values.get(key);

        if (list == null) {
            final ConcurrentList&lt;Value&gt; newList = new ConcurrentList&lt;Value&gt;();
            final ConcurrentList&lt;Value&gt; oldList = values.putIfAbsent(key, newList);

            if (oldList == null) {
                list = newList;
            } else {
                list = oldList;
            }
        }

        list.add(value);
    }

    public List&lt;ListValue&gt; remove(Key key) {
        return values.remove(key);
    }

    public boolean remove(Key key, ListValue value) {
        final List&lt;ListValue&gt; list = values.get(key);

        if (list == null) {
            return false;
        }

        return list.remove(value);
    }

    public List&lt;ListValue&gt; obtainListCopy(Key key) {
        final ConcurrentList&lt;ListValue&gt; list = values.get(key);

        if (list == null) {
            return Collections.emptyList();
        }

        return list.clone();
    }

    public void removeAll() {
        values.clear();
    }

    private class ConcurrentList&lt;V&gt; extends ArrayList&lt;V&gt; {
        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&lt;V&gt; clone() {
            readLock.lock();
            try {
                return (ConcurrentList&lt;V&gt;)super.clone();
            }finally {
                readLock.unlock();
            }
        }
    }
}
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&lt;ListValue&gt; 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 &lt; max; i++) {
        final int currentI = i;
        final List&lt;Thread&gt; threadList = new ArrayList&lt;&gt;();
        for (int j = 0; j &lt; 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&lt;Integer, ConcurrentList&lt;Integer&gt;&gt; entry : map.getEntrySet()) {
        final ConcurrentList&lt;Integer&gt; 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.