Concurrent multimap put and remove

Question

This is a composed concurrent list multimap implementation. A lower-level implementation would be better, but more complex.

Ignoring the O(n) removal in the sublist, is this the correct way to compose a ConcurrentMap and CopyOnWriteArrayList into a functional ConcurrentMultimap? Are there any unresolved data races?

private final ConcurrentMap<K, Collection<V>> map = ...; // inconsequential

public boolean put(K key, V value) {
 Collection<V> list = map.get(key);
 if(list != null) {
   list.add(value);
   return true;
 }

 // put if absent double check to avoid extra list creation
 list = new CopyOnWriteArrayList<V>();
 list.add(value);
 Collection<V> old = map.putIfAbsent(key,value);
 if(old != null) old.add(value);
 return true;
}

public boolean remove(Object key, Object value) {
 Collection<V> list = map.get(key);
 if(list == null) return false;

 // O(n) remove is the least of my worries
 if( ! list.remove(value)) return false;

 if( ! list.isEmpty()) return true;

 // double-check remove
 if( ! map.remove(key,list)) return true; // already removed! (yikes)

 if(list.isEmpty()) return true;

 // another entry was added!
 Collection<V> old = map.putIfAbsent(key,list);

 if(old == null) return true;

 // new list added!
 old.addAll(list);
 return true;
}

Answer 1

I think you have a race. The problem I see is that a thread that is in 'put' CANNOT be sure that the list being inserted into hasn't been removed, and/or replaced with another list.

Observe:

Thread 1 calls put(), and retrieves (or creates) the list associated with the key. Meanwhile, Thread 2 removes that list from the map. Data lost.

I think you'll need to add a retry loop to verify that the right list is in the map after adding to it.