Java Concurrent Multimap

Question

I've implemented a concurrent multimap that support concurrent put and remove but I'm unsure of its correctness. I would appreciate your feedback.

public class ConcurrentMultiMap<K, V> {
 private static ConcurrentHashMap emptySet = new ConcurrentHashMap();
 private ConcurrentHashMap<K, ConcurrentHashMap<V, Object>> map = new ConcurrentHashMap<>();
 // return true if the method increased the size of the multimap or false if the multimap already contained the key-value pair
 public boolean put(K k, V v) {
 Preconditions.checkNotNull(k);
 Preconditions.checkNotNull(v);
 boolean tryAgain;
 boolean success = true;
 do {
 ConcurrentHashMap<V, Object> oldSet = map.get(k);
 if (oldSet == null) {
 tryAgain = map.putIfAbsent(k, new ConcurrentHashMap<>(Collections.singeltonMap(v, 1))) != null;
 } else {
 success = oldSet.putIfAbsent(v, 1) == null; //I do not allow multiple equal values for the same key
 if (success) {
 // if the put was a success we check that the key was not removed from the map by a concurrent remove operation.
 ConcurrentHashMap<V, Object> currentSet = map.get(k);
 tryAgain = currentSet == null || !currentSet.contains(v);
 } else {
 return false;
 }
 } while(tryAgain);
 return success;
 }
 // returns true if the multimap changed
 public boolean remove(K k, V v) {
 Preconditions.checkNotNull(k);
 Preconditions.checkNotNull(v);
 ConcurrentHashMap<V, Object> oldSet = map.get(k);
 if (oldSet == null) {
 return false;
 }
 if (oldSet.remove(v) != null) {
 if (oldSet.size() == 0) {
 map.remove(k, emptySet);
 }
 return true;
 }
 return false;
 }
}

• BenC: You're not extending from any other collection classes/interfaces; do you provide functionality for getting things from the multimap?
• Eth0: I'm implementing guava multimap. I didn't include the full implementation of the class in the code above to keep the focus on the put/remove methods.
• Solomon Ucko: What do you mean by "concurrent"?
• Eth0: @SolomonUcko concurrent means that the methods will be called from multiple threads of execution. In the implementation above I'm using concurrent hash map, which is a class from the java.util package which guarantees a form of consistency when used from several threads, moreover it does so without locking the entire map and thus it is considered efficient. You can read more about it here docs.oracle.com/javase/tutorial/essential/concurrency and here docs.oracle.com/javase/8/docs/api/java/util/concurrent/…
• Solomon Ucko: That's what I thought, but can you take a look at my answer and explain why it's wrong if it's wrong?

Answer 1

You should have HashMap<K, Set<V>>, not ConcurrentHashMap<K, ConcurrentHashMap<V, Object>>.

• Solomon Ucko: Why did someone down vote? Is the answer too short? Is it incorrect? If it is incorrect, please explain why.
• slowy: I think it's because you didn't explain, why he should use HashMap. And you ask what he means by 'concurrent', which is imo necessary to understand beforehand, to be able to give a proper answer.
• Solomon Ucko: @slowy, I added a comment to the question, I'll edit later.
• Eth0: My implementation relies heavily on the concurrency guarantees given by ConcurrentHashMap. By replacing it with HashMap not only that my code will not support concurrent put and remove it will not even support modifications from different threads done in a sequential manner due to lack of memory barriers.
• Solomon Ucko: @EladTolochinsky Oh, oops. It looked like you were defining ConcurrentHashMap, not ConcurrentMultiMap. Should I delete this answer?