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<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;
    }
}