How to use two numbers as a Map key

问题:

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?

回答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.

回答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;
}

回答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

回答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();
    }
} 

回答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.

回答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.

回答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.

回答8:

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