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

当然，你必须有一张具有独特价值的地图。否则，将更换其中一名。

Answer 6

受到 GETah 的回答的启发，我决定自己写一些类似的东西，并进行一些改进：

• 该类正在实现 Map< K,V>-Interface
• 通过在通过 put 更改值时处理它，双向性确实得到了保证（至少我希望在此保证）

使用方式就像正常情况一样地图，要获取映射上的反向视图，请调用 getReverseView()。不复制内容，仅返回视图。

我不确定这是否完全万无一失（实际上，可能不是），所以如果您发现任何缺陷，请随时发表评论，我会更新答案。

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

}

Answer 7

这是一个相当老的问题，但是如果其他人像我一样有脑块，并且偶然发现了这个问题，希望这会有所帮助。

我也在寻找双向 HashMap，有时它是最有用的最简单的答案。

如果您不想重新发明轮子并且不想向您的项目添加其他库或项目，那么可以简单地实现并行数组（或 ArrayList，如果您的设计需要）。

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

一旦您知道两个键中 1 个的索引，您就可以轻松请求另一个键。因此，您的查找方法可能类似于：

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

假设您正在使用正确的面向对象结构，其中只有方法正在修改这些数组/ArrayList，保持它们并行将非常简单。对于 ArrayList 来说甚至更容易，因为如果数组的大小发生变化，只要同时添加/删除，就不必重建。