Java中哪种数据结构最适合进行双向多值映射？

Question

我相对于Java比较新，关于什么类型的数据结构最适合我的情况，我有一个问题。我有一组数据，它们本质上是键-值对，但每个值可能对应多个键，每个键可能对应多个值。一个简化的例子是：

红色-苹果 绿色-苹果 红色-草莓 绿色-葡萄 紫色-葡萄

考虑上面的例子，我需要能够返回我有哪些颜色的苹果和/或哪些红色水果。实际数据将根据输入文件动态生成，每个集合将从100到100,000个值不等，每个值可能对应于另一个集合中的数百个值。

存储和解析这些数据的最有效方法是什么？我希望使用尽可能原生于Java的解决方案，而不是像外部数据库那样的东西。

此问题与此问题相关，但考虑到我需要在两个方向上为每个键分配多个值，因此不确定如何应用该解决方案。

- user4588937

---

地图怎么样？http://docs.oracle.com/javase/7/docs/api/java/util/Map.html - Koogle

@Josh - 谢谢，我在搜索中没有找到那个问题。我会浏览这些解决方案，看看是否能够成功地将它们应用于我的数据。 - user4588937

如果您可以使用外部库（jar），我建议您使用Guava的Table http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Table.html，特别是HashBasedTable。Guava是来自Google的一组实用程序类（不是数据库）。 - fps

@Magnamag - 看起来Guava表格很适合。据我所知，我不需要使用表格的值元素。使用表格与两个MultiMaps相比是否存在性能成本？显然，使用两个MultiMaps存在同步问题，而表格可以解决这个问题。 - user4588937

https://dev59.com/FXNA5IYBdhLWcg3wUMHn#1011072 - Steve Kuo

Answer 1

由于在Map中不能有重复的键，因此您可以创建一个Map<Key，List<Value>>，或者如果可以的话，使用Guava的Multimap。

Multimap<String, String> multimap = ArrayListMultimap.create();
multimap.put("Red", "Apple");
multimap.put("Red", "Strawberry");

System.out.println(multimap.get("Red"));  // Prints - [Apple, Strawberry]

但问题是您不能请求给定对象的键，如果我找到其他内容，我会继续寻找并进行编辑，希望它有所帮助。

不过，您可以通过迭代映射并找到对象的键自行创建反向映射。

- Luke SpringWalker

---

“但问题是你无法请求给定对象的键。”听起来这个问题可以通过使用BiMultiMap解决。不确定是否存在，但它应该被称为这个名字。或者使用节点名称索引的有向图。 - David Ehrmann

你能否将其中两个封装在自定义对象中以实现此目的？ - Richard Tingle

Answer 2

我建议您使用Guava's Table结构。将颜色作为行键，水果作为列键或反之亦可。具体而言，HashBasedTable非常适合您的情况。

根据您的用例，您不需要为值存储任何内容。但是，这些Table不允许null值。您可以使用虚拟的Boolean或任何其他有用的统计值，例如插入的日期和时间、用户、颜色/水果对的数量等。 Table具有您需要的方法，例如column()和row()。请记住，文档中说这些结构针对行访问进行了优化。如果您计划通过一个键而不是另一个键进行访问，则这可能对您没有问题。

- fps

Answer 3

您可以创建自己的自定义数据结构

public class MultiValueHashMap<K, V> {
     private HashMap<K, ArrayList<V>> multivalueHashMap = new HashMap<K, ArrayList<V>>();

    public static void main(String[] args) {
        MultiValueHashMap<String, String> multivaluemap = new MultiValueHashMap<String, String>();
        multivaluemap.put("Red", "Apple");
        multivaluemap.put("Green", "Apple");
        multivaluemap.put("Red", "Strawberry");
        multivaluemap.put("Green", "Grapes");
        multivaluemap.put("Purple", "Grapes");

        for(String k : multivaluemap.keySet()){
            System.out.println(k + " : " + multivaluemap.get(k).toString());
        }
    }

    public void put(K key, V value){
        if (multivalueHashMap.containsKey(key)){
            ArrayList<V> values = multivalueHashMap.get(key);
            values.add(value);
        }else{
            ArrayList<V> values  = new ArrayList<V>();
            values.add(value);
            multivalueHashMap.put(key, values);
        }
    }

    public Set<K> keySet(){
        return multivalueHashMap.keySet();
    }

    public ArrayList<V> get(K key){
        return multivalueHashMap.get(key);
    }
}

输出应为：

红色：[苹果，草莓]

紫色：[葡萄]

绿色：[苹果，葡萄]

- Anwuna