Java unique value map

Question

I need a map with unique keys and also storing duplicate values only once. The interface will be the Map but I don't want that the same value use memory multiple times. For example:

In a normal Map implementation like HashMap suposing value.equals(value') and value.equals(value'') but value!=value' and value!=value' and value!=value'' if we:

put(key1, value);
put(key2, value');
put(key3, value'');

Then the value will be stored three times.

I tried to make my own implementation which looks like:

class MyMap2<K, V> extends HashMap<K, V> {
    private Map<V, V> values;

    public MyMap2() {
        values = new HashMap<V, V>();
    }

    @Override
    public V put(final K key, final V value) {
        V v = values.get(value);
        if (v == null) {
            v = value;
            values.put(v, v);
        }
        return super.put(key, v);
    }
}

This implementation stores the value just one time (Please, note that I'm using the same value). But is there any Map which already implements this kind of data structure with get/put O(1)?

Please, note that BiMap is not useful because it will cause an error in case of duplicated values.

Answer 1

This implementation already promises constant time get/put operations. The worst case is when inserting a new value that has never been seen yet. In this case you will:

1. Attempt to find the value in the values map - O(1), since it's a HashMap.
2. Not find it, and put the value in the values map - O(1), since it's a HashMap.
3. Put the key-value pair in super - O(1), since it's a HashMap.

You find a better way of implementing this logic, but not by an order of magnitude.

EDIT:
Note that the implementation may put in super twice, which is just redundant. It can be tweaked to be slightly cleaner:

@Override
public V put(final K key, final V value) {
    V v = values.get(value);
    if (v == null) {
        v = value
        values.put(v, v);
    } 
    return super.put(key, v);
}