How to use two numbers as a Map key

Question

I have two numbers and I want to use them together as a key in a Map. Currently, I'm concatenating their string representations. For example, suppose the key numbers are 4 and 12. I use:

String key = 4 + "," + 12;

The map is declared as Map<String, Object>.

I think this is so bad! I like to use something other than a String as the key! I want the fastest way to create these keys.

Who has a good idea?

Shiest

I think the comma-delimited String is a good idea. I use this approach all the time. – Loreanloredana

Answer 1

Create an object that holds the two numbers 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 prefer a mathematical approach, see this StackOverflow answer.

Handel

Thanks, Your very good method, but I do not want to use "class" to solve the problem. How to use the ordinary mathematical methods to get a key? I am only asking, "the fastest" – Shiest

OK. I have added a link to the answer you want :-) – Handel

ok - so this is now pretty clearly a homework problem. The correct solution here is to use a class. The implementation of the hashcode() method of that class is where performance comes into play. – Distinction

Do you really want x and y to be mutable if you're using this as a HashMap key? – Fluor

Also, if you need to lookup stuff from your Map, and not just iterate over it, you should override the methods hashCode() and equals(). This will allow you to: A create Coordinates objects at a future time and retrieve stuff from your already populated Map. Otherwise, even if you create a Coordinates with the same x and y as a Coordinates used as a key in the Map, you won't be returned the value. B It will improve lookup time in from your Map – Mufti

But, I guess the question is still how to implement the hashCode() method then? – Social

Does this solution have theta(1) complexity? I guess Map in Java is just like Map in C++ whose complexity of search an element is theta(logn). – Jordonjorey

Answer 2

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

Dimension key = new Dimension(4, 12);

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

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

Here's a table showing the hashCode for different values of width and 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 from 0 to 14, you'll see the pattern.

Here's the code that produces this hashCode:

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

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

For speed, you should calculate the hashCode in the constructor. So 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 course, if you'll probably need an equals method, but you limit yourself to positive integers that won't overflow, you can add 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 values because negative values will produce some duplicated hash codes. But with this restriction in place, these are the fastest hashCode() and equals() methods that can be written. (Of course, you can write hashCodes just as fast in any immutable class by calculating the hashCode in the constructor.)

If you can't live with those restrictions, you 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 the kicker. You don't need this class at all. Since the formula gives you a unique integer for each pair of numbers, you can just use that Integer as your map key. The Integer class has its own fast equals() and hashCode methods that will work fine. This method will generate the hash key from two short values. The restriction is that your inputs need to be positive short values. This is guaranteed not to overflow, and by casting the intermediate sum to a long, it has a wider range than the previous method: It 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;
}

Kingofarms

For the curious, the function used in this answer is called the Cantor pairing function. – Nomo

Answer 3

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

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

For instance, using java.awt.Point -- which looks, on paper, like 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

Fluor

Answer 4

You can store two integers in a long like 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();
    }
} 

Maccarone

I would upvote this for the nifty int -> long solution, but I would also downvote it for making the Pair mutable. – Fluor

You can't use primitives as generic parameters. – Midrash

Nice trick, but I'm having trouble extracting those two integers from that one long once they're stored there. What bit operations can you use to pull those two integers (r and l) out? – Incuse

The hashCode with be the same for (1,2) and (2,1) – Social

Answer 5

A practical answer to this questions is:

hashCode = a + b * 17;

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

Sciential

Answer 6

Another approach would be to use nested maps:

Map<Integer,Map<Integer,Object>>

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

Asseverate

Answer 7

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

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

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

Habitue

Answer 8

You need write the right eqauls and hashcode methods , or produce some bugs.

Heddle