Map of Maps data structure

Question

Hi,

The MultiValueMap class (Apache commons collections) makes it easy to work with a Map whose values are Collections. I'm looking for a a class that makes it easy to work with a Map whose keys are objects and values are Maps.

I'm using Java 1.4, so can't use Google Collections or generics.

Thanks, Don

Answer 1

Map of maps is actually a tree-type structure without single root node (as well as map of maps of maps...).

You can look at Composite pattern which is widely used for implementing tree structures (if their components has the same type which is not the case as I feel).

Another solution is to implement a simple domain model. It'll be much clearer to read and easy to maintain something like:

school.getPupil ("John Doe").getMark ("Math")

than

school.get ("John Doe").get ("Math")

Answer 2

The regular Map collection works for this:

    Map<Object,Map<Object,Object>> mapOfMaps = new LinkedHashMap<Object,Map<Object,Object>>();
    Object newObject = new String("object as string");
    mapOfMaps.put(newObject, new LinkedHashMap<Object,Object>());
    Map<Object,Object> objectMap = mapOfMaps.get(newObject);

In fact, if you're not worried about type safety, you can put whatever you want into the value section:

    Map<Object,Object> mapOfWhatever = new LinkedHashMap<Object,Object>();
    Object newObject = new String("object as string");
    mapOfWhatever.put(newObject, new LinkedHashMap<Object,Object>());
    Map<Object,Object> objectMap = (Map<Object, Object>) mapOfWhatever.get(newObject);

Answer 3

If you've got a map:{string,map:{string,thing}} (deliberately not using Java syntax to avoid the whole Java1.4/Java5 business) then you should also consider whether you should instead model that as map:{tuple:{string,string},thing}. If multi-level lookups dominate, then that's a good change to make (provided you implement a good tuple that does equals() correctly and hashCode() intelligently) but if you are doing a lot of inserts and deletes then it's less good.

Intelligence in hashCode probably means just coming up with a reasonable way to mix the bits from the hashCodes of the contents together. If the member values are expected to be from disjoint sets (e.g., names and occupations) then you can just XOR them together – imperfect, but cheap and fast – but if you've less control/certainty then you need to do something else as well (e.g., rotate the bits of one of the values prior to the XOR).