Java Map of Map

Question

I need to do a look-up table based on two keys. I am building a mileage look-up chart similar to what is seen in the back of road maps. A sample of a chart can be found here. If you know the starting city is x and the ending city is y you look to find the intersection to find out the total miles.

When I first started attacking this problem I though of doing Two maps. City being an ENUM of my city of interest.

Map<City, Map<City, Integer>> map;

But, as I researched I am seeing warnings about Map's that have values of type Map. Is there an easier solution to my problem that I might be overlooking? With this being 66x66 col*row I want to make sure I do it right the first time and dont have to redo the data entry.

As a note I will be saving all my values into a database for easy update and retrieval so the solution would need to be easy to map with JPA or Hibernate etc.

Thanks in advanced.

Answer 1

If you're using Eclipse Collections, you can use MutableObjectIntMap and Pair.

MutableObjectIntMap<Pair<City, City>> map = ObjectIntHashMap.newMap();
map.put(Tuples.pair(newYorkCity, newark), 10);
map.put(Tuples.pair(newYorkCity, orlando), 1075);
Assert.assertEquals(10, map.get(Tuples.pair(newYorkCity, newark)));
Assert.assertEquals(1075, map.get(Tuples.pair(newYorkCity, orlando)));

Pair is built into the framework so you don't have to write your own. MutableObjectIntMap is similar to a Map<Object, Integer> but optimized for memory. It's backed by an Object array and an int array and thus avoids storing Integer wrapper objects.

Note: I am a committer for Eclipse collections.

Answer 2

It'd be easier if you do this:

Map<Pair<City, City>, Integer> map;

That is: create a new generic class, let's call it Pair that represents a pair of cities, and use it as key to your Map. Of course, don't forget to override hashCode() and equals() in Pair. And take a look at @increment1's answer, he's right: if the distance from city A to B is the same as the distance from B to A, then there's no need to store two pairs of cities, a single pair will do, no matter the order used to add the cities to the Map.

Notice that this is the strategy used by ORMs (for instance, JPA) when mapping composite keys in a database: create a new class (Pair in the example) that encapsulates all the objects used as keys, it'll be much easier to manage this way: conceptually, there's only one key - even if internally that key is composed of several elements.

Answer 3

Similar to other answers, I suggest creating a city pair class to be your map key (thus avoid a map of maps). One difference I would make, however, would be to make the city pair class order agnostic in regards to the cities in its hashCode and equals methods.

I.e. Make CityPair(Seattle,LA) equal to CityPair(LA,Seattle).

The advantage of this is that you would then not duplicate any unnecessary entries in your map automatically.

I would achieve this by having hashCode and equals always consider city1 to be the city with the lower ordinal value (via Enum.ordinal()) in your enum.

Alternatively, try this simple unordered pair implementation given in another question and answer.

Answer 4

There is another way to do this, that may work for you. Basically, you want to create a class called something like CityPair. It would take 2 arguments to its constructor, the start and end cities, and would override the hashcode function to generate a unique hash based on the two inputs. These two inputs could then be used in a HashMap<CityPair,Integer> type.

if there are only 66 cities, then your hashing function could look something like this:

//first assign each city an id, 0-65 and call it city.getID()
@Override public int hashCode()
{
  return ((city1.getID() << 16) | (city2.getID()))
}

of course as noted in the comments, and in other answers, you will want to override the function prototyped by:

public boolean equals(Object)

from object so that the map can recover from a hash collision

Answer 5

To do the same as the graphic, i would use a 2d- array.

// index is the city code:
int[][] distances;

store the city code in a

 Map<String, Integer> cityNameToCodeMap

Use it as follows;

Integer posA = cityNameTCodeMap.get("New York");
// TODO check posA and posB for null, if city does not exits
Integer posB = cityNameTCodeMap.get("Los Angeles");

int distance = distances[posA][posB];

reason for this design:
The matrix is in the graphic is not a sparse matrix, it is full. For that case an 2d-array uses least memory.

Answer 6

You should create a simple class that contains two City references, from and to, and which overrides equals and hashCode appropriately. Then use that as your key.

Answer 7

Make a map of Path's, where Path is a custom class that holds two cities. Remember to override equals and hashcode.

Edit: Why is there 66x66 paths? Is the mileage different regarding which way you go (probably is a bit difference, but do you have that data)? If not, you can discard more than half that number of entries (the half is obvious, the 'more' part is from New York to New York entry no longer needs to be saved with 0).