1

我正在尝试在 Java 中构建一个数据结构，我将在其中插入大约 200,000 个字符串键，每个“平均”为 1000 Integers Map<String, Arraylist<Integer>>。该地图最终将具有大约 2 亿个值。

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

当我到达一个集合包含大约 50000 个整数的地步时，这太慢了。我通常会遇到 Java 堆空间不足的错误。

有没有办法摆脱获取过程？我只检查键是否存在，然后立即将值添加到现有集合中，例如将 posh 添加到堆栈中，尤其是映射在内存中，或者它是导致 Java 和 C++ 之间差异的原因，在 C++ 中我可以从使用指针中受益吗？

保持这样一个事实，即我不喜欢通过使用多图之类的东西来增加地图的大小，因为结构看起来几乎很简单。

提前谢谢了。

4

2 回答 2

5

如果您的代码实际上正在按照您的问题所建议的那样做，那么您工作太努力了。一旦你的 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 );

不过，在我看来，Guava Multimap 是一个更好的解决方案：http: //guava-libraries.googlecode.com/svn/tags/release03/javadoc/com/google/common/collect/Multimap.html

于 2013-04-05T15:36:48.390 回答
2
  1. 与 HashMap 调整大小相关的性能开销很大。当您使用无参数构造函数创建新的 HashMap 时，其大小默认为 16。您将越来越多的元素放入其中，因此任何时候超出可用空间时，它都需要调整大小。调整大小涉及计算每个键的哈希码以及在哈希表之间移动键。这个很贵。

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

  1. ArrayList 的默认容量为 10。如果放置更多元素，则需要调整大小。这涉及创建新数组（其中 ArrayList 内部存储元素）并将元素从旧数组复制到新数组。这在大型 ArrayList 上也可能非常昂贵。

我建议改用 LinkedList。向其中添加新元素非常便宜，因为元素作为独立节点存储。但是，也有一些缺点。有关详细信息，请参阅此问题。

  1. 您必须能够为 200,000,000 个对象保留足够的内存。正如 Tom Hawtin 建议的那样，增加 JVM 使用的最大堆空间可能是必要的。Java 不是 C++，你不能只是使用越来越多的内存。
于 2013-04-05T17:08:29.580 回答