Java是否有反向查找的HashMap？

Question

我的数据是以"密钥"格式组织的,而不是"键值".它就像一个HashMap,但我需要在两个方向上进行O(1)查找.这种类型的数据结构是否有名称,Java标准库中是否包含这样的名称？(或者可能是Apache Commons？)

我可以编写自己的类,基本上使用两个镜像映射,但我宁愿不重新发明轮子(如果这已经存在但我只是没有找到合适的术语).

Answer 1

Java API中没有这样的类.您想要的Apache Commons类将成为BidiMap的一个实现.

作为一名数学家,我将这种结构称为双射.

Answer 2

除了Apache Commons之外,Guava还有一个BiMap.

Answer 3

这是一个我用来完成这个的简单类(我不想再有另一个第三方依赖).它不提供地图中提供的所有功能,但它是一个良好的开端.

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

Answer 4

如果没有发生冲突,您可以随时将两个方向添加到同一个HashMap :-)

Answer 5

这是我的 2 美分。

或者您可以使用带有泛型的简单方法。小菜一碟。

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

当然，您必须拥有具有唯一值的地图。否则，其中之一将被替换。