# [ACCEPTED]-How to use two numbers as a Map key-key

Score: 17

Create an object that holds the two numbers 2 and use it as the key. For example:

``````class Coordinates {

private int x;
private int y;

public Coordinates(int x, int y) {
...
}

// getters

// equals and hashcode using x and y
}

Map<Coordinates, Location> locations = new HashMap<Coordinates, Location>();
``````

If you 1 prefer a mathematical approach, see this StackOverflow answer.

Score: 15

You should use java.awt.Dimension as your 45 key.

Dimension key = new Dimension(4, 12);

Dimension 44 has a very nice hashCode() method that produces 43 a different hashCode for each pair of positive 42 integers, so that the hashCodes for (4, 12) and 41 (12, 4) are different. So these are fast 40 to instantiate and make very good hashCodes.

I 39 do wish they had made the class immutable, but 38 you can make your own immutable class modeled 37 on Dimension.

Here's a table showing the 36 hashCode for different values of width and 35 height:

``````     0   1   2   3   4  <-- width
+--------------------
0 |  0   2   5   9  14
1 |  1   4   8  13
2 |  3   7  12
3 |  6  11
4 | 10

^
|
height
``````

If you follow the hashCodes in order 34 from 0 to 14, you'll see the pattern.

Here's 33 the code that produces this hashCode:

``````public int hashCode() {
int sum = width + height;
return sum * (sum + 1)/2 + width;
}
``````

You 32 may recognize the formula for triangular 31 number inside the last line. That's why 30 the first column of the table contains all 29 triangular numbers.

For speed, you should 28 calculate the hashCode in the constructor. So 27 your whole class could look like this:

``````public class PairHash {
private final int hash;
public PairHash(int a, int b) {
int sum = a+b;
hash = sum * (sum+1)/2 + a;
}
public int hashCode() { return hash; }
}
``````

Of 26 course, if you'll probably need an equals 25 method, but you limit yourself to positive 24 integers that won't overflow, you can add 23 a very fast one:

``````public class PairHash {
// PAIR_LIMIT is 23170
// Keeping the inputs below this level prevents overflow, and guarantees
// the hash will be unique for each pair of positive integers. This
// lets you use the hashCode in the equals method.
public static final int PAIR_LIMIT = (int) (Math.sqrt(Integer.MAX_VALUE))/2;
private final int hash;

public PairHash(int a, int b) {
assert a >= 0;
assert b >= 0;
assert a < PAIR_LIMIT;
assert b < PAIR_LIMIT;
int sum = a + b;
hash = sum * (sum + 1) / 2 + a;
}

public int hashCode() { return hash; }

public boolean equals(Object other) {
if (other instanceof PairHash){
return hash == ((PairHash) other).hash;
}
return false;
}
}
``````

We restrict this to positive 22 values because negative values will produce 21 some duplicated hash codes. But with this 20 restriction in place, these are the fastest 19 hashCode() and equals() methods that can 18 be written. (Of course, you can write hashCodes 17 just as fast in any immutable class by calculating 16 the hashCode in the constructor.)

If you 15 can't live with those restrictions, you 14 just need to save the parameters.

``````public class PairHash {
private final int a, b, hash;
public PairHash(int a, int b) {
this.a = a;
this.b = b;
int sum = a+b;
hash = sum * (sum+1)/2 + a;
}
public int hashCode() { return hash; }
public boolean equals(Object other) {
if (other instanceof PairHash) {
PairHash otherPair = (PairHash)other;
return a == otherPair.a && b == otherPair.b;
}
return false;
}
``````

But here's 13 the kicker. You don't need this class at 12 all. Since the formula gives you a unique 11 integer for each pair of numbers, you can 10 just use that Integer as your map key. The 9 Integer class has its own fast equals() and 8 hashCode methods that will work fine. This 7 method will generate the hash key from two 6 short values. The restriction is that your 5 inputs need to be positive short values. This 4 is guaranteed not to overflow, and by casting 3 the intermediate sum to a long, it has a 2 wider range than the previous method: It 1 works with all positive short values.

``````static int hashKeyFromPair(short a, short b) {
assert a >= 0;
assert b >= 0;
long sum = (long) a + (long) b;
return (int) (sum * (sum + 1) / 2) + a;
}
``````
Score: 10

If you go with the object solution, make sure your key object is immutable.

Otherwise, if 7 somebody mutates the value, not only will 6 it no longer be equal to other apparently-identical 5 values, but the hashcode stored in the map 4 will no longer match the one returned by 3 the `hashCode()` method. At that point you're basically 2 SOL.

For instance, using `java.awt.Point` -- which looks, on paper, like 1 exactly what you want -- the following:

``````  public static void main(String[] args) {
Map<Point, Object> map = new HashMap<Point, Object>();

Point key = new Point(1, 3);
Object val = new Object();

map.put(key, val);

System.out.println(map.containsKey(key));
System.out.println(map.containsKey(new Point(1, 3)));

// equivalent to setLeft() / setRight() in ZZCoder's solution,
// or setX() / setY() in SingleShot's
key.setLocation(2, 4);

System.out.println(map.containsKey(key));
System.out.println(map.containsKey(new Point(2, 4)));
System.out.println(map.containsKey(new Point(1, 3)));
}
``````

prints:

``````true
true
false
false
false
``````
Score: 6

You can store two integers in a long like 1 this,

``````   long n = (l << 32) | (r & 0XFFFFFFFFL);
``````

Or you can use following `Pair<Integer, Integer>` class,

``````public class Pair<L, R> {

private L l;
private R r;

public Pair() {
}

public Pair(L l, R r) {
this.l = l;
this.r = r;
}

public L getLeft() {
return l;
}

public R getRight() {
return r;
}

@Override
public boolean equals(Object o) {
if (!(o instanceof Pair)) {
return false;
}
Pair obj = (Pair) o;
return l.equals(obj.l) && r.equals(obj.r);
}

@Override
public int hashCode() {
return l.hashCode() ^ r.hashCode();
}
}
``````
Score: 1

A practical answer to this questions is:

``````hashCode = a + b * 17;
``````

... where 5 a, b and hashCode are all ints. 17 is just 4 an arbitrary prime number. Your hash will 3 not be unique, but that's OK. That sort 2 of thing is used all over the Java standard 1 library.

Score: 0

Another approach would be to use nested 5 maps:

``````Map<Integer,Map<Integer,Object>>
``````

Here you have no overhead to create 4 keys. However you have more overhead to 3 create and retrieve entries correctly and 2 you need always to map-accesses to find 1 the object you are looking for.

Score: 0

Why should writing all that extra code to 14 make a full blown class that you don't need 13 for anything else be better than using a 12 simple String? Will computing the hash code 11 for instances of that class be much faster 10 than for the String? I don't think so.

Unless 9 you are running in an extremely limited 8 computing power environment, the overhead 7 of making and hashing Strings should not 6 be noticeably larger than that of instantiating 5 your custom class.

I guess the fastest way 4 would be to simply pack the ints into a 3 single Long as ZZ Coder suggested, but in 2 any case, I don't expect the speed gains 1 to be substantial.

More Related questions