How to create a HashMap with two keys (Key-Pair, Value)?

Question

There are several options:

2 dimensions

Map of maps

Map<Integer, Map<Integer, V>> map = //...
//...

map.get(2).get(5);

Wrapper key object

public class Key {

    private final int x;
    private final int y;

    public Key(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Key)) return false;
        Key key = (Key) o;
        return x == key.x && y == key.y;
    }

    @Override
    public int hashCode() {
        int result = x;
        result = 31 * result + y;
        return result;
    }

}

Implementing equals() and hashCode() is crucial here. Then you simply use:

Map<Key, V> map = //...

and:

map.get(new Key(2, 5));

Table from Guava

Table<Integer, Integer, V> table = HashBasedTable.create();
//...

table.get(2, 5);

Table uses map of maps underneath.

N dimensions

Notice that special Key class is the only approach that scales to n-dimensions. You might also consider:

Map<List<Integer>, V> map = //...

but that's terrible from performance perspective, as well as readability and correctness (no easy way to enforce list size).

Maybe take a look at Scala where you have tuples and case classes (replacing whole Key class with one-liner).

When you create your own key pair object, you should face a few thing.

First, you should be aware of implementing hashCode() and equals(). You will need to do this.

Second, when implementing hashCode(), make sure you understand how it works. The given user example

public int hashCode() {
    return this.x ^ this.y;
}

is actually one of the worst implementations you can do. The reason is simple: you have a lot of equal hashes! And the hashCode() should return int values that tend to be rare, unique at it's best. Use something like this:

public int hashCode() {
  return (X << 16) + Y;
}

This is fast and returns unique hashes for keys between -2^16 and 2^16-1 (-65536 to 65535). This fits in almost any case. Very rarely you are out of this bounds.

Third, when implementing equals() also know what it is used for and be aware of how you create your keys, since they are objects. Often you do unnecessary if statements cause you will always have the same result.

If you create keys like this: map.put(new Key(x,y),V); you will never compare the references of your keys. Cause everytime you want to acces the map, you will do something like map.get(new Key(x,y));. Therefore your equals() does not need a statement like if (this == obj). It will never occure.

Instead of if (getClass() != obj.getClass()) in your equals() better use if (!(obj instanceof this)). It will be valid even for subclasses.

So the only thing you need to compare is actually X and Y. So the best equals() implementation in this case would be:

public boolean equals (final Object O) {
  if (!(O instanceof Key)) return false;
  if (((Key) O).X != X) return false;
  if (((Key) O).Y != Y) return false;
  return true;
}

So in the end your key class is like this:

public class Key {

  public final int X;
  public final int Y;

  public Key(final int X, final int Y) {
    this.X = X;
    this.Y = Y;
  }

  public boolean equals (final Object O) {
    if (!(O instanceof Key)) return false;
    if (((Key) O).X != X) return false;
    if (((Key) O).Y != Y) return false;
    return true;
  }

  public int hashCode() {
    return (X << 16) + Y;
  }

}

You can give your dimension indices X and Y a public access level, due to the fact they are final and do not contain sensitive information. I'm not a 100% sure whether private access level works correctly in any case when casting the Object to a Key.

If you wonder about the finals, I declare anything as final which value is set on instancing and never changes - and therefore is an object constant.

You can't have an hash map with multiple keys, but you can have an object that takes multiple parameters as the key.

Create an object called Index that takes an x and y value.

public class Index {

    private int x;
    private int y;

    public Index(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int hashCode() {
        return this.x ^ this.y;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Index other = (Index) obj;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        return true;
    }
}

Then have your HashMap<Index, Value> to get your result. :)

Implemented in common-collections MultiKeyMap