数据结构等同于大型数据集的map(在java中)

Question

是否有一个已经实现的数据结构,我可以使用它来分配给一个对象(在我的情况下是一个Edge),一个整数？我正在从一个文件,10密耳顶点,60密耳边缘读取图形,并使用地图(cost.put(e,cost))为每个边缘分配成本.

我以这种方式创建成本图:

costs = new HashMap<Edge,Integer>();

它给出的例外是:

java.lang.OutOfMemoryError: Java heap space
    at java.util.HashMap.resize(Unknown Source)
    at java.util.HashMap.addEntry(Unknown Source)
    at java.util.HashMap.put(Unknown Source) 

Answer 1

HashMap是基本的正确数据结构Map.您遇到的问题是没有指示JVM保留足够的空间来将文件内容保存在内存中.使用-Xmx标志启动JVM .例如,-Xmx1G参数将允许它使用1千兆字节的内存.

Answer 2

你有6e7的边缘.普通对象占用24个字节(64位HotSpot),因此那里的1.44e9字节(1.5 GB).现在,您将介绍可以想象的最有效的地图,仅添加6e7个引用和6e7个Integer对象.这是ref的另一个2.4e8字节和Integers的1.44e9字节:另一个1.5 GB,总数现在是3 GB - 这是你的问题的理论下限(模缓存,见下文).

基于此,我建议你Edge用另一个int领域扩展你的课程.这将大大减少您的内存占用.

但是,如果这不是一个选项,并且:

• 你的整数很少超过两位数,
• 你小心永远不要使用new Integer,但是Integer.valueOf,自动装箱等,
• 你使用Java 7,

您将自动受益于内置的小整数缓存.如果整数假设范围更广,但仍有大量重复,则强烈建议使用自定义缓存.