1

I got a question about why we need equals if we have hashcode.

My first attempt was the answer because collision. But we corrected starting point with the assumption that we have not many objects so there is no collision at all.

My second attempt was the answer because of the speed. But I also got the reply that there is something conceptual difference between hashcode and equals.

So I read a lot of posts, the java doc and can not find the answer. Do I miss something?

  • 3
    Because Equals() can be implemented in ways other than comparing hash codes. See stackoverflow.com/a/16089313 – Robert Harvey Jan 14 '16 at 20:52
  • 5
    To put it another way, equivalency is not always defined by an object's hash. There might be some fields in my object that I don't want to participate in equivalency at all, and a hashcode is not going to work there (unless, of course, I exclude those fields from my hashcode computation). – Robert Harvey Jan 14 '16 at 20:59
  • 1
    I'd say that it's because Equals() provides you with better flexibility. Otherwise, we'd all just use hashcodes. In any case, your teacher/interviewer/whoever clearly believes he knows conceptually the difference between hashcode and equals (though we might not necessarily agree with his reasoning). Why don't you simply ask them? – Robert Harvey Jan 14 '16 at 21:03
  • 1
    There are already some good answers. I would add that Equals transfers a clear message about its meaning. And it is indeed to test for equality. A hash is a technical property that enables efficient access to collections, and it does not necessarily guarantee equality. Consider also that equality may be domain specific and does not necessarily mean identical. Equals compares objects so you may compare objects of different types. It could compare some kind of score, if the objects score the same they may be considered equal. – Martin Maat Jan 14 '16 at 22:57
  • 1
    Because "the assumption that we have not many objects so there is no collision at all" is wrong. – user253751 Jan 10 '17 at 10:40
6

To put it bluntly: they serve different purposes.

  • Equals is for testing equality.
  • Hashcode is in order to produce an int (hopefully well distributed)

if your hashcode is unique, you could as well use it for equality. However, for many kind of objects, producing such a unique hash is plainly impossible.

Imagine an object containing two ints a and b. There is no way to produce a unique int hash for such an object. So you still need equality to compare them.

As for the comparator, it's usually a bad idea to use the output as hash because the result is not well distributed, resulting in lots of collisions when used in hash maps or similar data structures.

  • In addition to the risk of collision or the impossibility to produce a decent hash, there is also the fact that two objects having different hashes may be logically equals, because some objects properties may be not relevant to determine this equality. So even if same hashes (and no collision) should implies equality, different hashes does not implies inequality. – mgoeminne Jan 15 '16 at 10:18
  • @mgoeminne "two objects having different hashes may be logically equals" is actually wrong. Citing the javadoc: "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." ...which makes sense if you know how hashtables work – dagnelies Jan 15 '16 at 10:23
  • Wow, my mistake. I was actually (erroneously) remembering Chapter 3 of Effective Java. So a Rational class must implement hashCode in such a way that two Rational objects representing the same value but having different numerators and denominators (and therefore having potentially a different behavior) have the same hash. OR two Rational objects representing the same value with different numerators and denumerators must not be equal. Right? – mgoeminne Jan 15 '16 at 10:35
  • Well, everything is alright as long as two equal objects have the same hash. – dagnelies Jan 15 '16 at 10:38
5

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.

  • As an aside, an implementation of hash code for a numeric object that has a collision between 0 & -1 is frankly appalling. What were they thinking? – Jules Jan 15 '16 at 9:32
  • @Jules well, there are 2^32 longs that collide with a hash code of 0. Consider a 8 bit hash code (so I don't have to type lots). How do you hash 0xFFFF so that it makes use of all the bits to try to get the best distribution. Remember, you've got to hash it into a space of 0x??. I believe unless you really start doing esoteric things on it that make the hash far less optional for speed, you will get -1 hashing to some other common value. – user40980 Jan 15 '16 at 14:35
2

Let's say you have a 64 bit hash code. There are 2^64 possible hash codes. Now lets say you are hashing strings. There are many, many more than 2^64 strings. There are 2^64 strings of eight 8-bit characters alone. There are 256 times more strings of nine 8-bit characters and even more strings of 10, 11 or more charcters. Obviously there will be many, many 9 character and even more longer strings with the same hash code.

Therefore you can't rely on the hash code alone. Equal hash codes don't guarantee that the objects are identical.

  • Given that this is discussing Java, the hashCode is a 32 bit signed value. Long.hashCode() is enough to cause a problem and it can be trivially shown how two different longs can have the same hashCode(). – user40980 Jan 14 '16 at 21:41

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.