java - Java中图的空间高效表示？

Question

我想要一个无向图，其中节点用一对标记（目前使用 String[] ）并且可以任意链接到其他节点。我从 Hashtable 类型开始。事实证明，这对我来说空间效率不够——我打算拥有大约 60,000 个节点（最终，远远超过这个数字）。

我应该如何实现这种图以提高内存效率？相反，我应该考虑某种关系数据库吗？

Answer 1

如果空间效率是您的首要任务，那么您可以牺牲图形操作的时间效率并取消哈希表（我假设您正在使用它来存储节点的标记链接）。只需切换到一个数组并产生比较图形操作上的标签值的成本：

public class Node {
    private Links[] links;

    // ... the ops ...

    public static final class Link {
        String label;
        Node   target;
    }
}

如果您希望进一步压缩内存使用并且您的标签空间是有限的（即标签对于给定节点不是唯一的；例如，“父”是一个反复出现的标签）然后考虑使用每个享元模式Label的自定义类，所以您不会重复.String

Answer 2

您主要关心的是序列化时磁盘上的大小，还是内存中的大小？

如果您关心内存中的大小，并且如果您不一定需要同时将每个节点保存在内存中，您可能需要考虑使用某种类型的延迟加载，例如使用db4o进行透明激活

Answer 3

如果您需要持续的可扩展性，请考虑使用现有的图形数据库，例如Neo4J，它可以处理您描述的更大的图形（数百万或数十亿个关系）。我已经将它用于大约 2500 万个节点的图表，效果很好。