How do I correct my hash function?

Question

This question is a result of the responses submitted to my post at CodeReview.

---

I have a class called Point, which is basically "intended to encapsulate a point represented in 2D space." I have overrided the hashcode() function which is as follows:

...
@Override
public int hashCode() {
    int hash = 0;
    hash += (int) (Double.doubleToLongBits(this.getX())
            ^ (Double.doubleToLongBits(this.getX()) >>> 32));
    hash += (int) (Double.doubleToLongBits(this.getY())
            ^ (Double.doubleToLongBits(this.getY()) >>> 32));
    return hash;
}
...

Let me clarify (for those who didn't check the above link) that my Point uses the two doubles: x and y to represent its coordinates.

Problem:
My Problem is evident when I run this method:

public static void main(String[] args) {
    Point p1 = Point.getCartesianPoint(12, 0);
    Point p2 = Point.getCartesianPoint(0, 12);
    System.out.println(p1.hashCode());
    System.out.println(p2.hashCode());
}

I get the Output:

1076363264
1076363264

This is clearly a problem. Basically I intend my hashcode() to return equal hashcodes for equal Points. If I reverse the order in one of the parameter declarations (i.e. swap 12 with 1 in one of them to get equal Points), I get the correct (same) result. How can I correct my approach while maintaining the quality or uniqueness of the hash?

Answer 1

Can't you use the code that is present in Arrays.hashCode already?

  Arrays.hashCode(new double[]{x,y});

This is what guava for example is using in Objects.hashCode.

If you have Java 7, simply:

 Objects.hash(x,y)

Answer 2

You cannot get an integer hash code for two doubles that is unique, without some further information about the numbers being made available about the nature of the numbers in the doubles.

Why?

int is stored as a 32bit representation, double as a 64 bit representation (see the Java tutorial).

So you are trying to store 128 bits of information in a 32 bit space, so it can never give an unique hash.

However

1. This really isn't the purpose of a hash code, hash codes just need to have fairly uncommon collisions to be useful.
2. If you know something about the double numbers, that reduces their entropy/information content then you could use this to compress the number of bits they use. This will be dependant on the application of this class that you have not discussed yet.
3. This is why equals normally does not make use of the hashcode to check for equality, use getX and getY of each Point to do the comparison instead.

Answer 3

Try this

public int hashCode() {
    long bits = Double.doubleToLongBits(x);
    int hash = 31 + (int) (bits ^ (bits >>> 32));
    bits = Double.doubleToLongBits(y);
    hash = 31 * hash + (int) (bits ^ (bits >>> 32));
    return hash;
}

this implementation follows Arrays.hashCode(double a[]) pattern. It produces these hash codes:

-992476223
1076364225

You can find suggestions how to write good hashCode in Effective Java Item. 9

Answer 4

It might be a silly idea, bt you are using + which is a symetric operation and you are getting symetric problems. What if you ue a non-symmetric operation such as division (check for denominator == 0 though) or minus? Or any other that you cna find in literature or invent yourself.