Does Java have a HashMap with reverse lookup?

问题:

I have data that is organized in kind of a "key-key" format, rather than "key-value". It's like a HashMap, but I will need O(1) lookup in both directions. Is there a name for this type of data structure, and is anything like this included in Java's standard libraries? (or maybe Apache Commons?)

I could write my own class that basically uses two mirrored Maps, but I'd rather not reinvent the wheel (if this already exists but I'm just not searching for the right term).

回答1:

There is no such class in the Java API. The Apache Commons class you want is going to be one of the implementations of BidiMap.

As a mathematician, I would call this kind of structure a bijection.

回答2:

In addition to Apache Commons, Guava also has a BiMap.

回答3:

Here is a simple class I used to get this done (I did not want to have yet another third party dependency). It does not offer all features available in Maps but it is a good start.

    public class BidirectionalMap<KeyType, ValueType>{
        private Map<KeyType, ValueType> keyToValueMap = new ConcurrentHashMap<KeyType, ValueType>();
        private Map<ValueType, KeyType> valueToKeyMap = new ConcurrentHashMap<ValueType, KeyType>();

        synchronized public void put(KeyType key, ValueType value){
            keyToValueMap.put(key, value);
            valueToKeyMap.put(value, key);
        }

        synchronized public ValueType removeByKey(KeyType key){
            ValueType removedValue = keyToValueMap.remove(key);
            valueToKeyMap.remove(removedValue);
            return removedValue;
        }

        synchronized public KeyType removeByValue(ValueType value){
            KeyType removedKey = valueToKeyMap.remove(value);
            keyToValueMap.remove(removedKey);
            return removedKey;
        }

        public boolean containsKey(KeyType key){
            return keyToValueMap.containsKey(key);
        }

        public boolean containsValue(ValueType value){
            return keyToValueMap.containsValue(value);
        }

        public KeyType getKey(ValueType value){
            return valueToKeyMap.get(value);
        }

        public ValueType get(KeyType key){
            return keyToValueMap.get(key);
        }
    }

回答4:

If no collisions occur, you can always add both directions to the same HashMap :-)

回答5:

Here my 2 cents.

Or you can use a simple method with generics. Piece of cake.

public static <K,V> Map<V, K> invertMap(Map<K, V> toInvert) {
    Map<V, K> result = new HashMap<V, K>();
    for(K k: toInvert.keySet()){
        result.put(toInvert.get(k), k);
    }
    return result;
}

Of course you must have a map with unique values. Otherwise, one of them will be replaced.

回答6:

Quite an old question here, but if someone else has brain block like I just did and stumbles on this, hopefully this will help.

I too was looking for a bi-directional HashMap, sometimes it is the simplest of answers that are the most useful.

If you do not wish to re-invent the wheel and prefer not to add other libraries or projects to your project, how about a simple implementation of parallel arrays (or ArrayLists if your design demands it).

SomeType[] keys1 = new SomeType[NUM_PAIRS];
OtherType[] keys2 = new OtherType[NUM_PAIRS];

As soon as you know the index of 1 of the two keys you can easily request the other. So your lookup methods could looks something like:

SomeType getKey1(OtherType ot);
SomeType getKey1ByIndex(int key2Idx);
OtherType getKey2(SomeType st); 
OtherType getKey2ByIndex(int key2Idx);

This is assuming you are using proper object oriented structures, where only methods are modifying these arrays/ArrayLists, it would be very simple to keep them parallel. Even easier for an ArrayList since you would not have to rebuild if the size of the arrays change, so long as you add/remove in tandem.

回答7:

Inspired by GETah's answer I decided to write something similar by myself with some improvements:

• The class is implementing the Map<K,V>-Interface
• The bidirectionality is really guaranteed by taking care of it when changing a value by a put (at least I hope to guarantee it hereby)

Usage is just like a normal map, to get a reverse view on the mapping call getReverseView(). The content is not copied, only a view is returned.

I'm not sure this is totally fool-proof (actually, it's probably not), so feel free to comment if you notice any flaws and I'll update the answer.

public class BidirectionalMap<Key, Value> implements Map<Key, Value> {

    private final Map<Key, Value> map;
    private final Map<Value, Key> revMap;

    public BidirectionalMap() {
        this(16, 0.75f);
    }

    public BidirectionalMap(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    public BidirectionalMap(int initialCapacity, float loadFactor) {
        this.map = new HashMap<>(initialCapacity, loadFactor);
        this.revMap = new HashMap<>(initialCapacity, loadFactor);
    }

    private BidirectionalMap(Map<Key, Value> map, Map<Value, Key> reverseMap) {
        this.map = map;
        this.revMap = reverseMap;
    }

    @Override
    public void clear() {
        map.clear();
        revMap.clear();
    }

    @Override
    public boolean containsKey(Object key) {
        return map.containsKey(key);
    }

    @Override
    public boolean containsValue(Object value) {
        return revMap.containsKey(value);
    }

    @Override
    public Set<java.util.Map.Entry<Key, Value>> entrySet() {
        return Collections.unmodifiableSet(map.entrySet());
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public Set<Key> keySet() {
        return Collections.unmodifiableSet(map.keySet());
    }

    @Override
    public void putAll(Map<? extends Key, ? extends Value> m) {
        m.entrySet().forEach(e -> put(e.getKey(), e.getValue()));
    }

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public Collection<Value> values() {
        return Collections.unmodifiableCollection(map.values());
    }

    @Override
    public Value get(Object key) {
        return map.get(key);
    }

    @Override
    public Value put(Key key, Value value) {
        Value v = remove(key);
        getReverseView().remove(value);
        map.put(key, value);
        revMap.put(value, key);
        return v;
    }

    public Map<Value, Key> getReverseView() {
        return new BidirectionalMap<>(revMap, map);
    }

    @Override
    public Value remove(Object key) {
        if (containsKey(key)) {
            Value v = map.remove(key);
            revMap.remove(v);
            return v;
        } else {
            return null;
        }
    }

}