2
\$\begingroup\$

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;
    }
}
\$\endgroup\$
12
  • \$\begingroup\$ You're not extending from any other collection classes/interfaces; do you provide functionality for getting things from the multimap? \$\endgroup\$
    – BenC
    Commented Aug 23, 2017 at 0:40
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 23, 2017 at 5:56
  • \$\begingroup\$ What do you mean by "concurrent"? \$\endgroup\$ Commented Aug 24, 2017 at 14:30
  • \$\begingroup\$ @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/… \$\endgroup\$ Commented Aug 26, 2017 at 15:45
  • \$\begingroup\$ That's what I thought, but can you take a look at my answer and explain why it's wrong if it's wrong? \$\endgroup\$ Commented Aug 26, 2017 at 21:06

1 Answer 1

-2
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ Why did someone down vote? Is the answer too short? Is it incorrect? If it is incorrect, please explain why. \$\endgroup\$ Commented Aug 23, 2017 at 23:37
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – slowy
    Commented Aug 24, 2017 at 10:47
  • \$\begingroup\$ @slowy, I added a comment to the question, I'll edit later. \$\endgroup\$ Commented Aug 24, 2017 at 14:30
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 28, 2017 at 8:52
  • \$\begingroup\$ @EladTolochinsky Oh, oops. It looked like you were defining ConcurrentHashMap, not ConcurrentMultiMap. Should I delete this answer? \$\endgroup\$ Commented Aug 28, 2017 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.