邻接表创建，内存不足错误

Question

我正在尝试创建一个邻接列表来存储图形。该实现在存储 100,000 条记录时工作正常。然而，当我尝试存储大约 100 万条记录时 我遇到了 OutofMemory 错误：

线程“main”中的异常 java.lang.OutOfMemoryError：Java 堆空间 在 java.util.Arrays.copyOfRange(Arrays.java:3209) 在 java.lang.String.(String.java:215) 在 java.io.BufferedReader.readLine(BufferedReader.java:331) 在 java.io.BufferedReader.readLine(BufferedReader.java:362) at liarliar.main(liarliar.java:39)

以下是我的实现

HashMap<String,ArrayList<String>> adj = new HashMap<String,ArrayList<String>>(num);


        while ((str = in.readLine()) != null)
        {

            StringTokenizer Tok = new StringTokenizer(str);
            name = (String) Tok.nextElement();
            cnt = Integer.valueOf(Tok.nextToken());
            ArrayList<String> templist = new ArrayList<String>(cnt);

            while(cnt>0)
             {
                    templist.add(in.readLine());
                    cnt--;
             }
            adj.put(name,templist);

        } //done creating a adjacency list

，我想知道是否有更好的方法来实现邻接列表。另外，我一开始就知道节点的数量，将来我在访问节点时会展平列表。有什么建议吗？

谢谢

Answer 1

我在这里似乎有一个不公平的优势，因为我认识到问题的名称（liarliar ）以及输入的确切性质。

我可以告诉你，这个 OutOfMemoryError 是设计使然。您需要找到一种更好的算法，该算法不会将图的整个邻接信息存储在内存中。

我不会给出太多的算法见解，但我可以告诉你，在这个阶段，你需要坐下来思考比编程所需的更多的东西。也许读一本关于算法和数据结构的好书。

---

您现在所做的实际上是将输入文件中的字符串不必要地存储到HashMap>中。考虑到问题的性质，这是非常浪费空间的。

如果您使用 <改为代码>java.util.Scanner。 new Scanner(new File(inputFilename)) 和 next() 以及 nextInt() 就是您所需要的。

为每个名称分配一个唯一的int（提示：Map），并存储更小的int。

Answer 2

感谢您回答我的问题。是的，你猜对了，代码是关于什么的。

我认为是的，使用字符串到整数的映射将为我节省一些邻接列表的空间需求。从这个意义上说，上述错误可以被消除。

但是，我使用了java -jar -Xmx1024M。这提供了一种使用更多堆内存运行程序的方法，并且由于它允许在给定的问题中使用它，所以这不应成为我提交失败的原因。

尽管我不确定，但性能可能是机器人失败的原因之一。

关于您的解决方案，

如果我创建一个 Map ，然后将数字存储在邻接列表中，它将节省一些空间，但每次我需要在 bfs/dfs 遍历期间访问节点时，它也会添加额外的查找。这让我很烦恼。您是说我根本不应该创建邻接列表吗？我是否正确理解了您想说的内容？

谢谢。