一个允许通过值快速查找键的Java多重映射表

Question

我有一个多重映射（类似于Guava提供的那种）：

Multimap<K, V>

这在逻辑上可以被理解为：

Map<K, Set<V>>

我的 multimap 中的数据有唯一的键和唯一的值。即，一个值永远不会被分配给多个键。

除了维护两个 Map 结构之外，是否有人知道现有的类/ API 可以让我通过键或值进行快速查找。

例如：

Collection<V> get(K)

...and...

K getKeyByValue(V)

顺便提一下，这个地图必须是可变的，也就是说我的数据一直在改变。（对于不可变的Map，Guava提供了一个ImmutableMultimap.inverse()方法，如果我的Map可以是不可变的话，可以解决这个问题。）

非常感谢任何帮助。

- Ben

---

你看过Guava的BiMap了吗？我认为那就是你想要的...虽然它是通过两个映射实现的（这似乎是你想避免的）。 - Chthonic Project

Guava没有公开BiMultimap类型，因为对这种结构的需求并不是非常高，并且其许多用户可以使用不可变版本。 - Louis Wasserman

这个问题（基于多对多关系的映射）被23人标记为星标，如果您希望在Guava中看到BiMultimap，请点赞/评论。然而，正如Louis所说，不可变的反向Multimap对于许多用例已经足够了。 - Grzegorz Rożniecki

这很可能取决于您的地图通常的使用方式。如果V到K的查找速度很关键，并且每个K的V数量足够少，那么显而易见的解决方案是让每个V都有一个对其K的引用，在每次将（K，V）添加到地图或从地图中删除时更新（显然，这应该以OOP方式干净地完成）。这使得V到K的查找为O(1)，但添加和删除（K，V）需要O(|V|)更长的时间。根据用例，它可能是好的或可怕的。 - Zoyd

如果我是您，我会创建自己的Multimap类，并使用内部映射进行相反查找。我要避免的难点是通过返回的视图（keys()，keyset()，asMap()等）允许间接修改。 - aalku

Answer 1

尝试这个。

import java.util.Collection;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;

import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Maps;
import com.google.common.collect.Multimap;
import com.google.common.collect.Multiset;

public class MyMap<K, V> implements Multimap<K, V> {

    private Multimap<K, V> key2Value = ArrayListMultimap.create();
    private Map<V, K> value2key = Maps.newHashMap();

    public K getKeyByValue(V value) {
        return value2key.get(value);
    }

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

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

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

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

    @Override
    public boolean containsEntry(Object key, Object value) {
        return key2Value.containsEntry(key, value);
    }

    @Override
    public boolean put(K key, V value) {
        value2key.put(value, key);
        return key2Value.put(key, value);
    }

    @Override
    public boolean remove(Object key, Object value) {
        value2key.remove(value);
        return key2Value.remove(key, value);
    }

    @Override
    public boolean putAll(K key, Iterable<? extends V> values) {
        for (V value : values) {
            value2key.put(value, key);
        }
        return key2Value.putAll(key, values);
    }

    @Override
    public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
        for (Entry<? extends K, ? extends V> e : multimap.entries()) {
            value2key.put(e.getValue(), e.getKey());
        }
        return key2Value.putAll(multimap);
    }

    @Override
    public Collection<V> replaceValues(K key, Iterable<? extends V> values) {
        Collection<V> replaced = key2Value.replaceValues(key, values);
        for (V value : replaced) {
            value2key.remove(value);
        }
        for (V value : values) {
            value2key.put(value, key);
        }
        return replaced;
    }

    @Override
    public Collection<V> removeAll(Object key) {
        Collection<V> removed = key2Value.removeAll(key);
        for (V value : removed) {
            value2key.remove(value);
        }
        return removed;
    }

    @Override
    public void clear() {
        value2key.clear();
        key2Value.clear();
    }

    @Override
    public Collection<V> get(K key) {
        return key2Value.get(key);
    }

    @Override
    public Set<K> keySet() {
        return key2Value.keySet();
    }

    @Override
    public Multiset<K> keys() {
        return key2Value.keys();
    }

    @Override
    public Collection<V> values() {
        return key2Value.values();
    }

    @Override
    public Collection<Entry<K, V>> entries() {
        return key2Value.entries();
    }

    @Override
    public Map<K, Collection<V>> asMap() {
        return key2Value.asMap();
    }

    public static void main(String[] args) {

        MyMap<String, String> map = new MyMap<>();

        map.put("key1", "value1");
        map.put("key1", "value2");
        map.put("key1", "value3");
        map.put("key1", "value4");
        map.put("key2", "value5");

        System.out.println(map.getKeyByValue("value1"));
        System.out.println(map.getKeyByValue("value5"));

    }

}

输出：

key1
key2

- slavik

Answer 2

我认为你可能需要这个类：org.apache.commons.collections.map.MultiValueMap 它是ASF commons-collections.jar中的一个类，文档链接：http://commons.apache.org/proper/commons-collections/javadocs/api-3.2.1/org/apache/commons/collections/map/MultiValueMap.html。

- SongLing Dong

---

你的回答并没有解决我的原始问题。我需要一个可以通过值快速查找键的多重映射表。Apache的MultiValueMap并不能提供通过值查找键的功能。 - Ben

很抱歉没有帮到你，但是存在一个问题：一个值可能被多个键引用，这将非常复杂，更像是多对多的关系。 - SongLing Dong