Java concurrent Map of List
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.