地图<对象，集合<Object>>有什么问题？

我想在Java中构建一个数据结构，我将插入大约200,000个键的字符串，每个字符串的平均值为1000个整数Map<String, Arraylist<Integer>>。地图最终将有大约2亿个值。地图<对象，集合<Object>>有什么问题？

问题是，在插入时，我必须首先检查密钥是否存在于地图中，如果为true，则获取存储在临时集合中的所有值，然后将新整数添加到集合并将它们放回地图，或者用一个新的整数实例化一个新的集合。

当我到达一个集合包含大约50000个整数的点时，这非常缓慢。我通常从堆空间错误中得到一个Java。

有没有办法摆脱获得过程？在那里我只检查关键存在，然后立即将值添加到已存在的集合中，像posh到堆栈，特别是映射位于内存中，还是它在Java和C++之间产生了区别，在C++中我可以从使用指针中受益？

保持这样一个事实，即我不喜欢使用像multimaps这样的东西来增加地图的大小，因为结构看起来几乎是直截了当的。

非常感谢提前。

来源

2013-04-05 EurikaIam

'Multimap'实现不会消耗比'Map >更多的内存“。 – 2013-04-05 15:23:40

你为什么不给我们展示一些代码？ – NPE 2013-04-05 15:23:47

如果在地图中找不到密钥，您实际上只需要进行放置。添加相关的SSCCE。 – Perception 2013-04-05 15:25:46

如果你的代码实际上在做你的问题建议，那么你工作得太辛苦了。一旦你的Key与ArrayList关联了。只需将ArrayList从地图中取出并将新的整数添加到该列表中即可。你不需要“放回去”。对列表的引用是您需要更改列表的全部内容。

Map<String, ArrayList<Integer>> m = new HashMap<String, ArrayList<Integer>>(); 
    for (int i = 0; i < 5; i++) { 
     String key = (i % 2 == 0) ? "Bob" : "Robert"; 
     ArrayList<Integer> l = m.get(key); 
     if (l == null) { 
      l = new ArrayList<Integer>(); 
      m.put(key, l); 
     } 
     l.add(i); 
    } 
    System.out.println("m is " + m);

在我看来，虽然，番石榴Multimap之是一个更好的解决了这个问题：http://guava-libraries.googlecode.com/svn/tags/release03/javadoc/com/google/common/collect/Multimap.html

来源

2013-04-05 15:36:48

在一个捏，你可以使用['Multimaps.newListMultimap']（http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/com/google/common/collect/Multimaps.html #newListMultimap（java.util.Map，％20com.google.common.base.Supplier））和fastutil的['IntList']（http://fastutil.di.unimi.it/docs/it/unimi/dsi/fastutil /ints/IntList.html）来避免盒装的整数。 – 2013-04-05 21:23:00

你知道，200,000,000个整数将迫使你去做一些关于Java堆空间的事情，而不管实现如何。我的microbenchmarked与Guava的MultiMap和上面的中间纯Java在大致相同的点上ch咽; 51250000。如果我的数学是正确的，那么你将需要大约3GB的内存来处理200,000,000个整数（他们每个最终都是16字节，我认为）。我认为你需要根据你的预期大小做一些数学计算，以找出如何调整JVM以适应这种情况。 – 2013-04-06 03:51:38

有相关的HashMap调整大小一个巨大的性能开销。当您使用无参数构造函数创建新的HashMap时，其大小默认为16。您将越来越多的元素放入其中，所以无论何时超出可用空间，它都需要调整大小。调整大小涉及计算每个密钥的哈希代码并在哈希表之间移动密钥。这个很贵。

如果你知道你的HashMap会存储很多密钥，你可以创建它的大小，例如200,000。

ArrayList的默认容量为10。如果你放更多的元素，它需要调整大小。这涉及到创建新数组（ArrayList内部存储元素）并将旧数组中的元素复制到新数组中。对于大型ArrayList，这也是非常昂贵的。

我建议使用LinkedList来代替。添加新元素非常便宜，因为元素被存储为独立节点。但是，有一些缺点。详情请参阅this question。

您必须能够为200,000,000个对象预留足够的内存。正如Tom Hawtin所建议的，增加JVM使用的最大堆空间可能是必要的。 Java不是C++，你不能只使用越来越多的内存。

来源

2013-04-05 17:08:29

地图<对象，集合<Object>>有什么问题？

回答

相关问题