Map of Maps data structure

Question

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.

Which side do you need to be a map? Are you mapping from map to object, object to map, or map to map? — MikeD, Jun 22 '10 at 13:51
Can't you just make Map? Or you want to be able to do something like map.put(key1, key2, value)? — Dave, Jun 22 '10 at 13:53
Not that it's overly relevant, I suppose, but I'm curious: What company/industry (as specifically as you're comfortable telling us) still requires Java 1.4? Even Java 5 has been end-of-lifed. Java 1.4 has been EOLd for almost 2 years already. — Hank Gay, Jun 22 '10 at 13:53
@Dave Java 1.4 doesn't have generics (at least not the standard distro; I understand there was a JSR of some sort that was used to test generics before they became part of the spec in Java 5). — Hank Gay, Jun 22 '10 at 13:54
@Hank Gay I know at least one pharmaceutical company that's still on Java 1.4. — Jack Leow, Jun 22 '10 at 13:58
@Hank - Generics are not required to have a 'Map-of-Maps' datastructure. Just needs more ugly casting... — Andreas Dolk, Jun 22 '10 at 14:00
@Andreas_D I know, but @Dave's comment specifically uses generics syntax. — Hank Gay, Jun 22 '10 at 14:03
@Hank a very large company that makes software for the travel industry — Dónal, Jun 22 '10 at 14:10
It is implicit from your request that the inner map key should be the same as the outer map key, in which case this is redundant. — user44242, Jun 22 '10 at 14:17
@usersmarvin_ I can't say I'm surprised by the pharma company—sad, but not surprised. I *am* surprised by the travel software, though. I wouldn't have expected that. — Hank Gay, Jun 22 '10 at 14:23
In our project I used Guava's [com.google.common.collect.Table](http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Table.html) which perfectly fits, and has lot of helper methods, which saved me tons of lines of code e.g.: iteration over map... *It's pity that you cannot use guava. (**maybe look at the source code for inspiration**)* See: [Guava collection types](https://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained) — To Kra, Nov 25 '15 at 16:12

score 9 · Answer 1 · answered Jun 22 '10 at 14:16

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")

Chris Dutrow · Answer 2 · 2010-06-22T14:41:53.973

4

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);

edited Jun 22 '10 at 14:41

answered Jun 22 '10 at 14:36

Chris Dutrow

48,402
65
188
258

Typically one wants not to have to care about whether a given (first) key already is in `mapOfMaps`, e.g. when doing `mapOfMaps.get("firstKey").put("secondKey",value)`. For example, Python's maps have a [`setdefault` method](http://docs.python.org/2/library/stdtypes.html#dict.setdefault) for this purpose. – Andre Holzner Jul 17 '13 at 12:30

score 0 · Answer 3 · answered Jun 22 '10 at 14:52

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).

Map of Maps data structure

3 Answers3

Linked