For reasons of practicality, hashCode()
returns a signed int
. 232 possible values. One could trivially have this be a long
instead of an int
and it would only slightly have me change the remainder of this answer.
The essence of all of this is the pigeonhole principle. If you have m
items and try to put them in n
boxes and m > n
, then you will have two items that go in the same box.
Lets look at the hashCode for Long
- which can have 264 values. Since 264 > 232 you will have two values that has to the same value.
public int hashCode() {
return (int)(value ^ (value >>> 32));
}
So, lets write some quick code.
System.out.println(Long.valueOf(0).hashCode());
System.out.println(Long.valueOf(-1).hashCode());
System.out.println(Long.valueOf(0).equals(Long.valueOf(-1)));
System.out.println(Long.valueOf(0).hashCode() == Long.valueOf(-1).hashCode());
This prints out:
0
0
false
true
And there we have it. Two numbers. One of them is 0
and the other is -1
that have the same hash code, but not the same number.
The hex value of -1
is 0xffffffffffffffff
which when you do an 0xffffffff ^ 0xffffffff
you get 0
But wait! What if we used long
for the hashCode instead!
As I said, its only a slightly different problem. I would have to start digging into another class that has the possibility of having more values than hashCodes, like BigInteger or String or Inet6Address (2128 possible values). All it does is make the calculation of the hashCode a bit harder to do right here (those are more than a line long with two bit operations). It doesn't change that the hashCode, being a fixed size value, is subject to the pigeonhole principle.