Space Efficient Representation of a Graph in Java?

I want to have an undirected graph where the nodes are labelled with a pai开发者_如何学JAVAr (currently using String[] for this) and can be arbitraryly linked to other nodes. I have started with the type Hashtable. It turns out that this is not space efficient enough for me - I intend on having around 60,000 nodes (eventually, well in excess of that number).

How should I implement this kind of graph so as to be more memory efficient? Should I, instead, be considering some kind of Relational Database?

If space efficiency is your priority, then you can sacrifice time efficiency on graph operations and do away with the Hashtable (which I assume you are using for storing a node's labeled links). Simply switch to an array and incur the cost of comparing label values on graph operations:

public class Node {
    private Links[] links;

    // ... the ops ...

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

If you wish to further squeeze the memory usage and your space of labels is finite (i.e. labels are not unique for a given node; e.g. "parent" is a label that occurs again and again) then consider using a custom Label class per flyweight pattern so you do not duplicate instances of String.

Is your main concern the size on disk when serialized, or the size in memory?

If you are concerned about size in memory, and if you do not necessarily need to hold each node in memory at the same time, you may want to look into using some type of lazy loading using something like transparent activation with db4o

If you need ongoing scalability, consider using an existing Graph Database such as Neo4J, which can handle MUCH larger graphs that you describe (millions or billions of relationships). I have used it for graphs of about 25 million nodes with good results.