我正在为具有 32678 个顶点的完整图生成随机边。所以，5亿+的价值。
我正在使用 HashMap 将边缘用作键，将随机边缘权重用作值。我不断遇到：
线程“main”中的异常 java.lang.OutOfMemoryError：java.lang.StringBuilder.toString(StringBuilder.java:430) at pa1.Graph.(Graph.java:60) at pa1.Main.main(Main) 处的 Java 堆空间.java:19)
然后，该图将用于构建最小生成树。
关于更好的数据结构或方法的任何想法？
我知道有分配更多内存的覆盖，但我更喜欢按原样工作的解决方案。
AHashMap将非常大，因为它将包含Doubles（大写字母 D）显着大于 8 个字节。（更不用说Entry）取决于实现和CPU芯片，但我认为每个至少16个字节，可能更多？
我认为您应该考虑将主要数据保存在一个巨大的double[]（或者，如果您可以保留一些准确性，a float[]）。这将内存使用量减少了 2 倍或 4 倍。（500M 浮点数是“仅仅”2GB）然后在这个数组中使用整数索引来实现你的边和顶点。例如，一条边可以是一个 int[2]。这与 OO 相去甚远，这里有一些严肃的挥手。（而且我不明白你正在尝试做的所有细微差别）
风格非常“老式”，但需要的内存要少得多。
更正-我认为边缘可能是int [4]，顶点可能是int [2]。但你明白了。实际上，对于边和顶点，您将拥有较少数量的对象，并且您可能可以使用“真实”对象、地图等...
由于它是一个完整的图，因此毫无疑问边是什么。如何将这些边的标签存储在一个以某种方式排序的简单列表中？因此，例如，如果您有 5 个节点，则边缘的权重将按如下顺序排列{1,2}, {1,3} {1,4} {1,5} {2,3} {2,4} {2,5} {3,4} {3,5} {4,5}：
但是，正如@BillyO'Neal 所指出的，这可能仍会占用 8 GB 的空间。您可能希望将此列表拆分为多个文件，并同时维护这些文件的索引，指示一组权重在一个文件中的结束位置以及下一组权重的开始位置。
此外，鉴于您正在查找图表的 MST，您可能还想查看以下论文：http ://cvit.iiit.ac.in/papers/Vibhav09Fast.pdf 。该论文似乎基于 Boruvka 算法 ( http://en.wikipedia.org/wiki/Bor%C5%AFvka 's_algorithm; http://iss.ices.utexas.edu/?p=projects/galois/benchmarks /mst )。