Java Concurrent Multimap 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&lt;K, V&gt; {
    private static ConcurrentHashMap emptySet = new ConcurrentHashMap();
    private ConcurrentHashMap&lt;K, ConcurrentHashMap&lt;V, Object&gt;&gt; map = new ConcurrentHashMap&lt;&gt;();

    // 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&lt;V, Object&gt; oldSet = map.get(k);
            if (oldSet == null) {
                tryAgain = map.putIfAbsent(k, new ConcurrentHashMap&lt;&gt;(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&lt;V, Object&gt; 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&lt;V, Object&gt; 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;
    }
}
You should have HashMap&lt;K, Set&lt;V&gt;&gt;, not ConcurrentHashMap&lt;K, ConcurrentHashMap&lt;V, Object&gt;&gt;.