20

I think my question is similar to this one: How to implement a Map with multiple keys? but with an important difference. In that question (if my understanding of it is correct, please let me know if it isn't), the keys were supposed to always be unique. I want to have a Map in the form: MyMap where the keys aren't necessarily unique. If that doesn't make sense, I basically want a 2 dimensional array, but rather than refering to elements by coordinates, I want to refer to them by pairs of objects.

Anyone have any ideas as to either a library where this works or a good way to implement this myself? As far as libraries go, I've looked at Apache Commons and Guava, neither seem to have what I want.

4
  • 4
    Well the whole concept of map is unique Key->value pairs, wanting to break that concept indicates you should be using a different storage object from step one. Can you give an example of "refer to [elements] by pairs of objects"? That might help me out.
    – Grambot
    Commented Jul 20, 2011 at 21:51
  • 1
    Have you looked at MultiMap in Guava library? Commented Jul 20, 2011 at 21:53
  • I have looked at MultiMap, that's not what I want. You make a good point that what I want isn't a map, I'm going to look into the Table structure mentioned in the Answer below, that's something I hadn't seen. But to answer your question, just as you'd refer to an element in a primitive 2D array by: array[0][1], I want to be able to do: array[obj1][obj2] and have that map to a value (obviously with different syntax, that's just the functionality I'm going for).
    – Steve
    Commented Jul 20, 2011 at 22:03
  • Use stackoverflow.com/questions/156275/… pairs in a regular map? Commented Jul 20, 2011 at 22:18

4 Answers 4

22

The Table data structure in Guava seems to meet you requirement of refering to a value by a pair of objects.

1
  • 1
    But adding Guava lib just for Table data structure is not worth, as it has some 15000 methods, all of which are not usefull.
    – shekar
    Commented Jan 31, 2016 at 18:48
14

I hope this answer won't be seen as a rant, but as far as I could understand, you want to use a library for something that you can achieve in a trivial way using a jdk out of the box.

Anyway, you mentioned that you want to access elements using a pair of objects. You could create a class that will hold the keys, such as

public class Pair {
  // string represntation of an object
  private final String x; 
  private final String y;

  // ctor, getters...

  public int hashcode() {...}
  public boolean equals(Object other) {...}
}

The hashcode method will generate the hashcode for all comprising elements (in this case, two, xand y in your case, but can be easily extended to support an arbitrary number of elements), and two keys will be the same if they have the same values for xand y. If your pair elements are not simple strings, it is trivial to derive a string representation of almost any object (provide a decent implementation of the toString method, for instance).

The idea is to have a unique string representation for each element in the pair.

Of course, generating solid hashcodes is not trivial, so an excellent option isto use Strings. To generate a hashcode, you would simply append the string representations of your pair objects:

public int hashcode() {
  return ('x' + x + ":y" + y).hashcode();
}

Be sure to provide some separator. Otherwise, for values such as x=ab, y=b, and x=a, y=bb, you'll get the same hashcode, even if the objects are completely different.

And equality is as trivial as inspecting the value of the elements in the pair:

public boolean equals(Object other) {
  // if other is not null and is an instance of Pair
  final Pair otherPair = (Pair)other;
  return this.x.equals(otherPair.x) && this.y.equals(otherPair.y);
}

So, now you could use your Pairclass in a map, such as in:

final Map<Pair, Whatever> map = new Hashmap<Pair, Whatever>();
// ...

Basicaly, a hashmap works by using the hashcode of the keys to determine in which bucket the value should be allocated. If two keys have the same hashcode, then the equals method will be used to determine if a collision just occurred, or if it's just the same key.

If you want to use your Pair class in a TreeMap, you would have to implement the compareTo method, or provide your own Comparator when instantiating such a map. TreeMap implementations rely on the result of the compareTo method to determine where a value should be allocated.

3
  • 2
    My accepted answer was the suggestion to use the Guava Table class below, since that seems easier than writing/testing/debugging my own custom data structure. However - still upvoted for an equaly excellent solution, thank you.
    – Steve
    Commented Jul 26, 2011 at 14:17
  • the equals and override methods are not working for me. I used the eclipse generated methods and it works perfectly. Source > Generate hashCode() and equals(). Commented Apr 19, 2014 at 22:10
  • Giving +1 because... "I hope this answer won't be seen as a rant"
    – Snoop
    Commented Mar 29, 2016 at 13:11
3

Apache Commons Collections has MultiKey.

import org.apache.commons.collections4.keyvalue.MultiKey;

Map<MultiKey, ValueType> myMap = new HashMap<MultiKey, ValueType>();
myMap.put(new MultiKey(key1, key2), value);

myMap.get(new MultiKey(key1, key2));

It has the benefit of creating N-dimensional arrays from a Map.

2

It sounds to me like you're looking for a nested HashMap. This could work, but my gut says implementing such a monster would be a terrible idea, both performance-wise and sanity-wise.

How you could initialize it:

    HashMap<Key1, HashMap<Key2, Value>> nestedHashMap = new HashMap<Key1, HashMap<Key2, Value>>();

Adding values:

    Key1 first;
    Key2 second;
    Value data;
    HashMap<Key2, Value> tempMap = new HashMap<Key2, Value>();
    tempMap.put(second, data);
    nestedHashMap.put(first, tempMap);

Getting data back out:

    Key1 first;
    Key2 second;
    Value data;
    data = nestedHashMap.get(first).get(second);

Disclaimer: This code hasn't been tested, it just came off the top of my head.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.