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?

Right-click in the your IDE, choose "Generate equals and hashCode", and examine the correct implementation produced by your IDE. Or use `Objects.hash(x, y)`. — JB Nizet, Apr 04 '14 at 11:06
Generally - to produce a meaningful `hashCode()` you have to shift it every time you introduce another property into calculation. — Germann Arlington, Apr 04 '14 at 11:27

score 5 · Answer 1 · answered Apr 04 '14 at 11:06

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

This really isn't the purpose of a hash code, hash codes just need to have fairly uncommon collisions to be useful.
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.
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.

Evgeniy Dorofeev · Answer 2 · 2014-04-04T11:24:33.493

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

edited Apr 04 '14 at 11:24

answered Apr 04 '14 at 11:07

Evgeniy Dorofeev

133,369
30
199
275

Please explain in more detail why you use `31`? It's just because 31 is a prime number? Could I use`23` instead? – ADS Apr 04 '14 at 11:12
Hmm... interesting. It seems that `NetBeans` uses that stratergy as well: `int hash = 5; hash = 41 * hash + (int) (Double.doubleToLongBits(this.x) ^ (Double.doubleToLongBits(this.x) >>> 32)); hash = 41 * hash + (int) (Double.doubleToLongBits(this.y) ^ (Double.doubleToLongBits(this.y) >>> 32)); return hash;` – Hungry Blue Dev Apr 04 '14 at 11:13
4

@ADS: http://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier – JB Nizet Apr 04 '14 at 11:16
1

See Effective Java Item. 9: The value 31 was chosen because it is an odd prime... – Evgeniy Dorofeev Apr 04 '14 at 11:25
Be warned, that whilst this distinguishes between these two points uniquely, it is not guaranteed for all points. (see my post above). It really does depend on what your objectives are for calculating the Hash. – Chris Thomson Apr 04 '14 at 11:47

score 1 · Answer 3 · answered Apr 04 '14 at 11:05

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.

score 1 · Accepted Answer · edited Apr 04 '14 at 11:42

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)

edited Apr 04 '14 at 11:42

Hungry Blue Dev

1,313
16
30

answered Apr 04 '14 at 11:06

Eugene

117,005
15
201
306

1

That would lead to the exact same problem of symmetry. He's better use `Arrays.hashCode(new double[] {x, y})`, or simply `Objects.hash(x, y)`. – JB Nizet Apr 04 '14 at 11:11
1

Please note... I'm accepting this because it's the shortest (and easiest) answer. – Hungry Blue Dev Apr 04 '14 at 11:42

How do I correct my hash function?

4 Answers4