Good hashcode function for 2D coordinates

Question

I would like to use a HashMap to map (x, y) coordinates to values. What is a good hashCode() function definition? In this case, I am only storing integer coordinates of the form (x, y) where y - x = 0, 1, ..., M - 1 for some parameter M.

Answer 1

To calculate a hash code for objects with several properties, often a generic solution is implemented. This implementation uses a constant factor to combine the properties, the value of the factor is a subject of discussions. It seems that a factor of 33 or 397 will often result in a good distribution of hash codes, so they are suited for dictionaries.

This is a small example in C#, though it should be easily adabtable to Java:

public override int GetHashCode()
{
  unchecked // integer overflows are accepted here
  {
    int hashCode = 0;
    hashCode = (hashCode * 397) ^ this.Hue.GetHashCode();
    hashCode = (hashCode * 397) ^ this.Saturation.GetHashCode();
    hashCode = (hashCode * 397) ^ this.Luminance.GetHashCode();
    return hashCode;
  }
}

This scheme should also work for your coordinates, simply replace the properties with the X and Y value. Note that we should prevent integer overflow exceptions, in DotNet this can be achieved by using the unchecked block.

Answer 2

To get unique Value from two numbers, you can use bijective algorithm described in here < x; y >= x + (y + ( (( x +1 ) /2) * (( x +1 ) /2) ) )

This will give you unquie value , which can be used for hashcode

public int hashCode()
{
      int tmp = ( y +  ((x+1)/2));
               return x +  ( tmp * tmp);
}

Answer 3

I generally use Objects.hash(Object... value) for generating hash code for a sequence of items.

The hash code is generated as if all the input values were placed into an array, and that array were hashed by calling Arrays.hashCode(Object[]).

@Override
public int hashCode() {
    return Objects.hash(x, y);
}

Use Objects.hash(x, y, z) for 3D coordinates.

If you wish to handle it manually, you could do compute hashCode using:-

// For 2D coordinates
hashCode = LARGE_PRIME * X + Y;

// For 3D coordinates
hashCode = LARGE_PRIME^2 * X + LARGE_PRIME * Y + Z;

Answer 4

Have you considered simply shifting either x or y by half the available bits?

For "classic" 8bit thats only 16 cells/axis, but with todays "standard" 32bit it grows to over 65k cells/axis.

@override
public int hashCode() {
    return x | (y << 15);
}

For obvious reasons this only works as long as both x and y are in between 0 and 0xFFFF (0-65535, inclusive), but thats plenty of space, more than 4.2bio cells.

Edit: Another option, but that requires you to know the actual size, would be to do x + y * width (where width ofc is in the direction of x)

Answer 5

That depends on what you intend on using the hash code for:

If you plan on using it as a sort of index, E.g. knowing x and y will hash into an index where (x, y) data is stored, it's better to use a vector for such a thing.

Coordinates[][] coordinatesBucket = new Coordinates[maxY][maxX];

But if you absolutely must have a unique hash for every (x, y) combination, then try applying the coordinates to a decimal table (rather than adding or multiplying). For example, x=20 y=40 would give you the simple and unique code xy=2040.