42

In Java, I have a class that represents a point with int coordinates

public class Point {
    int x = -1;
    int y = -1;

    public Point (int xNew, int yNew) {
        x = xNew; y = yNew;
    }

    public boolean equals (Object o) {
        // no need for (o instanceof Point) by design
        return x == ((Point)o).x && y == ((Point)o).y;
    }
}

I'm using objects of class Point as keys in a HashMap and as elements in a HashSet.

What would be the best candidate for the hashCode function? I would make it double so that the left part is x and the right part is y, for example: x = 4, y = 12, then the hashCode returns 4.12. But by the implementation, it cannot be double, only int.

This is not an option:

public int hashCode() {
    // no need to check for exception parseInt since x and y are valid by design
    return Integer.parseInt(Integer.toString(x) + Integer.toString(y));
}

because values x and y can be too long, so that together they will not be converted.

2
  • int hashCode says return for hashcode method is int only, so double is ruled out.
    – kosa
    Jul 31, 2012 at 14:38
  • Yes, that's why I got stuck for a while. Jul 31, 2012 at 14:38

8 Answers 8

61

You can't change the type of hashCode, nor should you want to.

I'd just go with something like:

public int hashCode() {
    return x * 31 + y;
}

Note that this means that (a, b) is different to (b, a) for most cases (unlike e.g. adding or XOR-ing). This can be useful if you often end up with keys for the "switched" values in real life.

It isn't unique - but hash codes don't have to be. They just have to be the same for equal values (for correctness), and (for efficiency) "usually" different for non-equal values, with a reasonable distribution.

In general, I usually follow the same kind of pattern as Josh Bloch suggests in Effective Java:

public int hashCode() {
    int hash = 17;
    hash = hash * 31 + field1Hash;
    hash = hash * 31 + field2Hash;
    hash = hash * 31 + field3Hash;
    hash = hash * 31 + field4Hash;
    ...
    return hash;
}

Where field1Hash would be the hash code for reference type fields (or 0 for a null reference), the int itself for int values, some sort of hash from 64 bits to 32 for long etc.

EDIT: I can't remember the details of why 31 and 17 work well together. The fact that they're both prime may be useful - but from what I remember, the maths behind why hashes like this are generally reasonable (though not as good as hashes where the distribution of likely values is known in advance) is either difficult or not well understood. I know that multiplying by 31 is cheap (shift left 5 and subtract the original value)...

7
  • Could you edit to remind me (or respond via comment) why 31 is often the magic number chosen for hash codes? Jul 31, 2012 at 14:40
  • @JonSkeet Thanks! It is always helpful to glean the details behind your answers. Jul 31, 2012 at 15:02
  • 2
    @Matt: Please don't edit answers like that - the code you edited in would have been perfectly fine for a separate answer.
    – Jon Skeet
    Jul 31, 2012 at 16:24
  • 2
    @Matt: You edited my answer to edit in some extra code. It's a perfectly reasonable bit of code to include in an answer, but I don't think it makes sense to make it part of my answer.
    – Jon Skeet
    Jul 31, 2012 at 21:10
  • 5
    I just saw someone using hash *= 31 + field1Hash instead of hash = hash * 31 + field1Hash . DON'T do that. It changes the order of the operators as the part after the *= is evaluated at first and then multiplicated with the current hash. Just my 5 cents warning for people "optimizing" code too quickly.
    – Ray
    Sep 14, 2014 at 15:58
12

I know that it is ok for non-equal objects to have the same hashcodes. However, the more collisions, the worse the performance will be (for example, in a hash table).

As far as I know, the best mapping from Z² → Z is the "elegant pairing function" (google it). Here is the implementation

// x,y must be non-negative
int elegant(int x, int y) {
    return x < y ? y * y + x : x * x + x + y;
}


// returns a unique number for every x,y pair
int elegantSigned(int x, int y) {
    if (x < 0) {
        if (y < 0)
            return 3 + 4 * elegant(-x - 1, -y - 1);
        return 2 + 4 * elegant(-x - 1, y);
    }
    if (y < 0)
        return 1 + 4 * elegant(x, -y - 1);
    return 4 * elegant(x, y);
}

This will begin to overlap as soon as you get multiplication overflow. If the absolute value of x and y is less than about 46000, then this will have zero hash collisions.

11

Just use java.util.Objects.hash(Object... values).

public int hashCode() {
    return Objects.hash(field1,field2);
}

Objects.hash actually calls 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;
}
1
5

This question is quite old, but I think the very idea will be actual as long as java exist. Let us analyze approaches above:

  1. Objects.hash(...) is fluent and clear what needs to be done, BUT it uses varargs (implicitly creating an array) and moreover, it implicitly boxes every single primitive, being passed into the method.
  2. x * 31 + y is performance-efficient: there is no boxing, no explicit or implicit array creation operations being used. BUT, it is unclear what needs to be done. Why 31, not 42? For the ones familiar with how hashing works there's no difficulties to understand such code, but what for the others? The second pitfall is that it is difficult to extend: you easily can forget to add new values into the hashing code if you, for example, wanted to go 3D and added z coordinate, because it forces you to copy-paste almost identical code many times.

I can introduce the third approach, not being mentioned in answers above:

@Override
public final int hashCode()
{
    final int[] numbers = {x, y};
    return Arrays.hashCode(numbers);
}

It uses a temporary array to hold integers being hashed, and calling Arrays.hashCode(), which is available since Java 1.5, there's also versions for other primitive types.

Pros: It is DRY, fluent and completely clear what needs to be done. It does not suffer from implicit boxing and does not uses implicit vararg. It is relatively fast and cheap. It can be easily extended by adding extra numbers into array initializer.

Cons: It is not as fast as copy-paste method. Please consider it if hash code is being called frequently.

Best regards.

3

It's often worth considering Apache Commons HashCodeBuilder

This class enables a good hashCode method to be built for any class. It follows the rules laid out in the book Effective Java by Joshua Bloch. Writing a good hashCode method is actually quite difficult. This class aims to simplify the process

and I would definitely recommend looking at the referenced book Effective Java.

2

There is a common strategy of generating a hashcode operation. In your case this would be :

public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + x;
    result = prime * result + y;
    return result;

}

1
  • 1
    So just return 31 * (31 + x) + y; Jul 31, 2012 at 15:12
1

You may want to take a look at Google Guava's Objects.hashCode(Object...) method.

public int hashCode() {
  return Objects.hashCode(x, y);
}
-1

try adding their hashcodes. ?

return new Integer(x).hashCode()+new Integer(y).hashCode();

6
  • 1
    Primitive types do not have hashCode. Jul 31, 2012 at 14:41
  • @MarkusMikkolainen Which simply returns the int it's wrapping. It would be simpler to just use x + y.
    – Jeffrey
    Jul 31, 2012 at 15:02
  • ah. I was not aware of the implementation of Integer.hashCode. Usually hashcodes try to avoid returning sequential hashcodes for sequential values.. Jul 31, 2012 at 16:55
  • Please consider not to use new Integer(int) explicitly, use Integer.valueOf(int) instead. There's one little optimization called integer caching helping you to increase performance sometimes. There's also a method Objects.hashCode(Object), you may easily pass your int, and it will be boxed into Integer automatically! Cheers.
    – Netherwire
    Aug 15, 2018 at 14:14
  • 1
    That would make Point(x, y) have the same hash code as Point(y, x)
    – Dimezis
    Aug 8, 2020 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.