Java 有反向查找的 HashMap 吗？

Does Java have a HashMap with reverse lookup?

提问by Kip

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?)

我有以“键-键”格式而不是“键-值”格式组织的数据。它就像一个 HashMap，但我需要在两个方向上进行 O(1) 查找。这种类型的数据结构是否有名称，Java 的标准库中是否包含类似的内容？（或者也许是 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).

我可以编写自己的类，基本上使用两个镜像映射，但我宁愿不重新发明轮子（如果这已经存在，但我只是没有在寻找正确的术语）。

采纳答案by uckelman

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.

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

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

作为数学家，我将这种结构称为双射。

回答by ColinD

In addition to Apache Commons, Guavaalso has a BiMap.

除了 Apache Commons，Guava还有一个BiMap。

回答by rsp

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

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

回答by GETah

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

回答by Fulvius

Here my 2 cents.

这是我的 2 美分。

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.

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

回答by ThatOneGuy

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.

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

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).

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

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.

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

回答by Qw3ry

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

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

• 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)

• 该类正在实现Map<K,V>-Interface
• 通过 a 更改值时注意它确实可以保证双向性put（至少我希望在此保证）

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.

用法就像法线贴图，获取映射调用的反向视图getReverseView()。内容不被复制，只返回一个视图。

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

}