26

I want a map indexed by two keys (a map in which you put AND retrieve values using two keys) in Java. Just to be clear, I'm looking for the following behavior: 

map.put(key1, key2, value); 
map.get(key1, key2); // returns value
map.get(key2, key1); // returns null
map.get(key1, key1); // returns null

What's the best way to to it? More specifically, should I use:

  • Map<K1,Map<K2,V>>

  • Map<Pair<K1,K2>, V>

  • Other?

(where K1,K2,V are the types of first key, second key and value respectively)

EclipseQuestion
  • 1,045
  • 2
  • 9
  • 6

7 Answers7

40

You should use Map<Pair<K1,K2>, V>

  1. It will only contain one map, instead of N+1 maps

  2. Key construction will be obvious (creation of the Pair)

  3. Nobody will get confused as to the meaning of the Map as its programmer facing API won't have changed.

  4. Dwell time in the data structure would be shorter, which is good if you find you need to synchronize it later.

Edwin Buck
  • 69,361
  • 7
  • 100
  • 138
  • I'm using 'apache commons' lib. Does anyone know if the 'Pair' class will work? (I mean, if it implements hashCode and equals correctly FOR THIS CASE?) – EclipseQuestion Jun 16 '11 at 14:36
  • Hashes need not be perfect, a good way is to implement your own pair. The `hashcode()` method can just return a.hashCode() xor b.hashCode(). – Edwin Buck Jun 16 '11 at 14:38
  • But doesn't that just alloc memory for a pair object EVERY time we search for something in the doubleMap? I mean, it's cleaner and all, but what if we're talking a big map with static data, isn't this solution badly engineered memory wise? – Pedro Borges Dec 11 '13 at 18:05
  • If you are worried about allocating each time you search, it doesn't really matter what kind of Map you use because the Map isn't really the core issue. You would probably want a Factory to generate the Key backed to a store of unique keys, such that two requests to generate two keys return the same object twice. It's independent of the Map of pair issue, and a Map of Maps is likely to take more storage anyway, considering the hash array (1 vs 1*M, in a M*N example) and bucket lists they both will have to maintain. – Edwin Buck Dec 11 '13 at 22:00
16

If you're willing to bring in a new library (which I recommend), take a look at Table in Guava. This essentially does exactly what you're looking for, also possibly adding some functionality where you may want all of the entries that match one of your two keys.

interface Table<R,C,V>

A collection that associates an ordered pair of keys, called a row key and a column key, with a single value. A table may be sparse, with only a small fraction of row key / column key pairs possessing a corresponding value.

Dave
  • 5,133
  • 21
  • 27
2

I'd recommend going for the second option 

Map<Pair<K1,K2>,V>

The first one will generate more overload when retrieving data, and even more when inserting/removing data from the Map. Every time that you put a new Value V, you'll need to check if the Map for K1 exists, if not create it and put it inside the main Map, and then put the value with K2.

If you want to have an interface as you're exposing initially wrap your Map<Pair<K1,K2>,V> with your own "DoubleKeyMap".

(And don't forget to properly implement the methods hash and equals in the Pair class!!)

Jaime
  • 36
  • 4
2

While I also am on board with what you proposed (a pair of values to use as the key), you could also consider making a wrapper which can hold/match both keys. This might get somewhat confusing since you would need to override the equals and hashCode methods and make that work, but it could be a straightforward way of indicating to the next person using your code that the key must be of a special type.

Searching a little bit, I found this post which may be of use to you. In particular, out of the Apache Commons Collection, MultiKeyMap. I've never used this before, but it looks like a decent solution and may be worth exploring.

Community
  • 1
  • 1
pseudoramble
  • 2,541
  • 22
  • 28
1

I would opt for the Map<Pair<K1,K2>, V> solution, because:

  • it directly expresses what you want to do
  • is potentially faster because it uses fewer indirections
  • simplifies the client code (the code that uses the Map afterwards
Waldheinz
  • 10,399
  • 3
  • 31
  • 61
1

Logically, you Pair (key1, key2) corresponds to something since it is the key of your map. Therefore you may consider writing your own class having K1 and K2 as parameters and overriding the hashCode() method (plus maybe other methods for more convenience). This clearly appears to be a "clean" way to solve your problem.

Jean Logeart
  • 52,687
  • 11
  • 83
  • 118
-1

I have used array for the key: like this

Map<Array[K1,K2], V>

Mauricio Gracia Gutierrez
  • 10,288
  • 6
  • 68
  • 99
sre
  • 1