Java hashCode for a Point class

Question

I have a simple custom Point class as follows and I would like to know if my hashCode implemention could be improved or if this is the best it's going to get.

public class Point 
{
    private final int x, y;

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

    public int getX() 
    {
        return x;
    }

    public int getY()
    {
        return y;
    }

    @Override
    public boolean equals(Object other) 
    {
        if (this == other)
          return true;

        if (!(other instanceof Point))
          return false;

        Point otherPoint = (Point) other;
        return otherPoint.x == x && otherPoint.y == y;
    }


    @Override
    public int hashCode()
    {
        return (Integer.toString(x) + "," + Integer.toString(y)).hashCode();
    }

}

Solution 1

Please do not use Strings. There's a lot of theory behind this and several implementations (division method, multiplication one, etc...). If you have about a hour you can watch this MIT-Class

This being said, here is what Netbeans 7.1 suggests:

@Override
public int hashCode() {
    int hash = 7;
    hash = 71 * hash + this.x;
    hash = 71 * hash + this.y;
    return hash;
}

October 2015 Edit

I started using IntelliJ a while back, I live happier now. This is what its automatic hashCode generation produces. It's a little less verbose. Note the use of prime numbers as well.

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

Solution 2

The manual multiplication of values of all significant member fields as suggested by Gevorg is probably the most efficient and has a good value distribution. However, if you favour readability, there are nice alternatives available either in Java 7...

import java.util.Objects;

...

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

... or in the Guava library:

import com.google.common.base.Objects;

....

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

Both of these varags methods simply delegate to Arrays.hashCode(Object[] a), so there is a slight impact on performance because of the autoboxing of ints and creating an array of object references, but it should be far less significant than using reflection.

And the readability is just great, since you simply see, which fields are used for the hashcode computation and all the multiply and add syntax is just hidden under the hood of Arrays.hashCode(Object[] a):

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}

Solution 3

I would recommend using a simpler and more performant method without strings, perhaps Josh Bloch's method from this answer, in your case just:

return 37 * x + y;

EDIT: nybbler is correct. What is actually recommended is:

int result = 373; // Constant can vary, but should be prime
result = 37 * result + x;
result = 37 * result + y;

Solution 4

A really nice way to hash a 2D point into a single integer is to use a number spiral!

http://ulamspiral.com/images/IntegerSpiral.gif

@Override
public int hashCode() {
    int ax = Math.abs(x);
    int ay = Math.abs(y);
    if (ax>ay && x>0) return 4*x*x-3*x+y+1;
    if (ax>ay && x<=0) return 4*x*x-x-y+1;
    if (ax<=ay && y>0) return 4*y*y-y-x+1;
    return 4*y*y-3*y+x+1;
}

While this method requires a few more calculations, there will be no unpredictable collisions. It also has the nice property that points closer to the origin in general will have smaller hash value. (Still can overflow with x or y > sqrt(MAX_VALUE) however)

View more solutions

Comments

[Matthew Flaschen]

Since there are only two fields, you could also use this library, but explicitly list the fields.

[user949300]

If this class is used significantly in a Collection, a reflective hashCode will be a big performance hit.

[nybbler]

That's not quite what's recommended in your linked answer. You missed that this should be done for every field individually, not at the same time. This algorithm generates the same result for [0,37] and [1,0]

[nybbler]

+1 Interesting that Netbeans suggests something different than eclipse, but the basis for the implementation is similar and solid.

[Matthew Flaschen]

Perhaps you miswrote "Java" instead of "Eclipse". By default, hashCode "is typically implemented by converting the internal address of the object into an integer."

[Matthew Flaschen]

I'd recommend using the HashCodeBuilder.append method instead.

[nybbler]

@MatthewFlaschen Indeed I did. Updated now; thanks for catching that.

[Christopher Shroba]

I'm confused, how is the second implementation a good implementation? You get collisions even with very small numbers, like (0,31),(1,0). That seems very detrimental, no?

[Marsellus Wallace]

@ChristopherShroba yours is a very interesting comment and I'll look into that once I'm back from vacation! The main issue is that result is initialized with 0 given your sample input. Still, that's what IntelliJ 2016 does...

[Christopher Shroba]

Right, and there'd be a collision for any points of the form (a, 31b),(b,31a). Thanks for the response! I'd love to hear your take on this when you get the chance!

[Marsellus Wallace]

@ChristopherShroba My assumption that the problem was due to result being initialized with 0 is also wrong... However, the Netbeans implementation is also not immune to the (a, 71b), (b,71a) attack... Thoughts?

[Marsellus Wallace]

Note that the new implementation will still generate a collision for any pair of Points in the form (x, 37y), (y, 37x)...

[Marsellus Wallace]

Still vulnerable to any pairs in the form (x, 31y), (y, 31x) e.g. (0, 31), (1, 0) or (3, 217), (7, 93). I'm trying to spark a question wide discussion here. Is there a way to have a more robust implementation or with just 2 integers with have to deal with this kind of issue (that depends on the prime number used in the hashcode generation)?

[Christopher Shroba]

Very true. I guess it comes down to the pigeonhole principle - if the algorithm is using such small numbers, there are going to be collisions with small numbers. Personally, I think the algorithm is sound but the constants are too low. The chances of a hashset containing both (0,31) and (1,0) are higher than containing (0,4095) and (1,0) for example. One alternate implementation I can think of would use half the bits for x and half for y: return (x%(1<<16))<<16+y%(1<<16). An even better implementation would mod by the largest prime less than 2^16 instead of 2^16 itself. What do you think?

[Marsellus Wallace]

I might need some time to think about it. Have you looked at Michael's answer below about the Point Java class implementation? Thought: The simple fact that we cannot spot a pattern does not mean that such a pattern does not exist...

[MaxZoom]

@ChristopherShroba As stated in Java documentation the general contract for the hashcode is 1. If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result. 2. It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results.

[vincent]

Word of warning to all those using this for identification. Hash collisions are a reality... E.g. pastebin.com/6wM3W3Wv