SCJP 1.5 Objective 6.2, hashCode() and equals()

[John Russell]

Suppose you have a class with three instance variables, call them x, y, and z, all ints. Do the following methods fulfill the equals() and hashCode() contracts? I say no.

public int hashCode() {
return x*y; }
public int equals(Object o)

[John Russell]

Sorry...I submitted the previous post prematurely. The two methods should read:

public int hashCode() { return x * y; }
public boolean equals( Object o ) {
if ((o != null) && (o instanceof ThisClass)) {
ThisClass that = (ThisClass) o;
return ( that.x * that.y * that.z == x * y * z );
} else {
return false;
}
}

I say these don't fulfill the hashCode() and equals() contract because you might have two objects a and b such that a.equals(b) but a.hashCode() =! b.hashCode(), a violation of the contract. Is this reasoning correct?

[Aleksander Zielinski]

Both methods fulfill the contract. Two object are considered equal if hashCode() for both objects returns the same integer and equals() return true. There`s no violation. Even if method equals() returns true the hashCode() must return the same integer in order to consider them equal. If hash codes are different, return value of equals doesn`t matter. If you are comparing two objects the first thing that happens is comparing hash codes, if they are different, that`s all, we stop here.

[John Russell]

I still think that the two methods do not fulfill this part of the contract (from the javadoc for the Object class);

"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."

Suppose object a has x = 1, y = 2 and z = 0, and object b has x = 3, y = 4 and z = 0. Using the methods shown, the two objects are equal according to the equals(Object) method. That is, 1 * 2 * 0 == 3 * 4 * 0. According to the contract, calling the hashCode method on each of the two objects must produce the same integer result. It does not. a.hashCode() returns 2, and b.hashCode() returns 12. It appears the contract is not met.

[Aleksander Zielinski]

John, I wish I spoke better English

"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."

That means: "When equals method returns true then we know for sure that hash codes are the same."

If method equals returns true then it is a must that hashCode methods returns the same integer result, but it is not the way you think it is. Accoring to the equals method implementation you are doing some math on variables to check if the objects are equals, but FIRST you have to check their hash codes and hash codes must be the same to even think that the objects might be equal. If you run the code above and invoke the equals method on the two objects with instance variables you gave us, return will be false. It is because FIRST you check hash codes, then "equality". If hash codes are different the objects can`t be considered equal, even in case if it appears method equals would return true. The thing is, method equals can (not must) return true if hash codes are the same, but it will never return true if hash codes are different.

If it`s still too confusing, please someone with better English explain it.

[John Russell]

Originally posted by Aleksander Zielinski:
[QB]John, I wish I spoke better English

Your English is quite clear!

"When equals method returns true then we know for sure that hash codes are the same."

Right. If the equals() method and the hashCode() method fulfill the contract, then that statement will be true. However, with this implementation of equals() and hashCode we do NOT know for sure that the hash codes are the same. If x * y * z is the same for both objects, we do NOT know for sure that x * y is the same for both objects. Indeed, we have shown a case where this implementation of equals() returns true for two objects whose hash codes are different. So, this implementation of equals() and hashCode() does NOT fulfill the contract.

[Aleksander Zielinski]

I was right, not you.... my English isn`t good I`m sorry John, I misunderstood what you were trying to say, thanks for patience in reading all this stuff, though it seems it was slightly off the point

Yes, although they are implemented legally, they do not fulfill the contract. This implementation would allow for "duplicates" (different hash codes) in Sets while equals method would return true and we were convinced that it this case the object won`t go there.

[Edisandro Bessa]

Hi John/Aleksander,

After read both explanations, I'm confusing about what is evaluated first. (equals() or hashcode() ?). Could you please explain ?

In my first guess, I also said no, because according to preceeding code we'd think two meaningfully objects are in the same "bucket". But actually, they are not.

In addition to this discussion, could you please explain what happens if we don't properly implement hashcode() method when using a HashMap or a HashSet ?

It seems HashMap allows duplicated whereas HashSet don't.

Please see both codes below extracted from K&B book with a little changes.

[B]HashMap implementation[/B]
 
import java.util.*;
class MapEQ {
    public static void main(String[] args) {
        Map<ToDos, String> m = new HashMap<ToDos, String>();
        ToDos t1 = new ToDos("Monday");
        ToDos t2 = new ToDos("Monday");
        ToDos t3 = new ToDos("Tuesday");
        m.put(t1, "doLaundry");
        m.put(t2, "payBills");
        m.put(t3, "cleanAttic");
        System.out.println(m.size());
    } }
 
class ToDos{
    String day;
    ToDos(String d) { day = d; }
 
    public boolean equals(Object o) {
        return ((ToDos)o).day == this.day;
    }
 
    [B]//Missing hashcode() implementation here. Will use default[/B]
}

Output 3.
In this case when using HashMap, duplicates are allowed just because the default inherited hashcode() creates a different hashcode for each object put in HashMap

[B]HashSet implementation[/B]
 
import java.util.*;
class SetEQ {
    public static void main(String[] args){
        HashSet map = new HashSet();
        map.add("one");
        map.add("two");
        map.add("three");
        map.add("four");
        map.add("one");
        System.out.println(map.size());
} }
[B]Output 4.
In this case when using HashSet, duplicates are NOT allowed why ?   :confused:   
 
It seems that hashcode() works different when using HashMap() or HashSet.
[/B]

Can anyone explain ?

[Edited to fix formatting = Jim]
[ March 02, 2006: Message edited by: Jim Yingst ]

[Jon Egan]

Edisandro,

You are getting different results because you are giving the two Hash implementations different object types...

in your first case, you give the HashMap instances of ToDos objects, for which the hashCode() contract is violated.... it doesn't agree with the equals() method notion of equality, as discussed above. HashMap is giving "incorrect" results because it is given "incorrect" objects to hash.

in your second case, you gave HashSet instances of String, for which hashCode() and equals() are perfectly well defined, and abide by the contract. HashSet is giving the "correct" result because it is given "correct" objects to hash.

Your example doesn't demonstrate an inconsistency between the hashing implementations of HashMap and HashSet (in fact, they are the same - a HashSet is backed by a HashMap - it just has null values). What you have demonstrated is the importance of adhering to the hashCode() contract if you want predictable results from HashMap, HashSet, etc.


Try using the flawed object as the hashed item in your HashSet, and check the results:

import java.util.*;
class SetEQ {
    public static void main(String[] args){
        HashSet map = new HashSet<ToDos>();
        map.add(new ToDos("one"));
        map.add(new ToDos("two"));
        map.add(new ToDos("three"));
        map.add(new ToDos("four"));
        map.add(new ToDos("one"));
        System.out.println(map.size());
    }
}
 
class ToDos{
    String day;
    ToDos(String d) { day = d; }
 
    public boolean equals(Object o) {
        return ((ToDos)o).day == this.day;
    }
 
    //[B]Missing hashcode() implementation here. Will use default[/B]
}

Hope this helps,
-- Jon

[sreedhar lak]

Hi John ,
Please can you tell me soething clear about hashCode() and equals() ,i read the javadoc and searched in google also,but till i didn't get clear idea abt these two.
Please tell me in simple words and with a simple example,which will help me to go in depth like your post.
I know only one thing that, suppose if we are comapring two String objects ,
the equals() method will return true otherwise false.
Thanks a lot,

[Manish Hatwalne]

Do have a look at and see if this article and see if it is of some help.

HTH,
- Manish

[Edisandro Bessa]

Oh yeah I see Jon.

Thank U so much.

[John Russell]

Sreedar,

I'll try to give a simple way of thinking about equals() and hashCode().

When you store a key in a hashed collection, you want to store it in such a way that you will be able to find it later.

A hashed collection, like a HashSet, stores keys in numbered buckets. Each bucket may hold many keys. Each bucket is identified by a number.

When you put yourKey into the collection, the system calls yourKey.hashCode() which returns the number of a bucket. Then the system stores yourKey in that bucket.

When you ask the system to search for wantedKey in the collection, the system calls wantedKey.hashCode() which returns the number of a bucket. Then the system searches through the keys in that bucket, and ONLY that bucket, to see if there is some key-in-the-bucket such that wantedKey.equals( key-in-the-bucket ).

What can go wrong if hashCode() and equals() are written in a way that violates the contract? That is, what happens if wantedKey and yourKey are equal according to equals(), but wantedKey.hashCode() != yourKey.hashCode().

You'll end up looking in the wrong bucket, and you won't find your key. You'll be able to put keys into the collection, but not always find them.

The contract is: When equals() says that two objects are equal, then hashCode() must say that the two objects have the same hash code.

Consider these situations with respect to the contract:

equals() says: the objects are equal
hashCode() says:

[John Russell]

(continuing...)

Scenario 1:
equals() says two objects are equal.
hashCode() says their hash codes are equal.
The contract says that's okay.

Scenario 2:
equals() says two objects are not equal.
hashCode() says their hash codes are equal.
The contract says that's okay.

Scenario 3:
equals() says two objects are not equal.
hashCode() says that their hash codes are not equal.
The contract says that's okay.

Scenario 4: (This is the one we must prevent.)
equals() says two objects are equal.
hashCode() says their hash codes are not equal.
The contract says NOT OKAY.

[ak pillai]

You can use

HashCodeBuilder class & EqualsBuilder class

from apache's common package. some points to consider if you want to write your own:

�If a class overrides equals(), it must override hashCode().
�If 2 objects are equal, then their hashCode values must be equal as well.
�If a field is not used in equals(), then it must not be used in hashCode().
�If it is accessed often, hashCode() is a candidate for caching to enhance performance.

[sreedhar lak]

Hi John,
Thank you very much.The explanation which you have given is helped me a lot.
Please, can you tell me what are the actual usages of these two.In which situations actually we will use these.

Thank you ak pillai .

Thanks a lot

[John Russell]

Originally posted by sreedhar lak:
Please, can you tell me what are the actual usages of these two.In which situations actually we will use these.

Usually, we use them _indirectly_. I have never had the need (except for testing) to write code that calls hashCode() _directly_. However, every time I use a HashMap, LinkedHashMap, HashSet, LinkedHashSet, or Hashtable, the system is calling hashCode() and equals() on my behalf.

For example, suppose we are making a collection of objects and we want to make sure that the collection is a "set". That is, we want to make sure that the collection never contains two references to the same object, and that the collection never contains references to two objects that are "equal". In other words, we want to guarantee that the objects in our collection are unique. Using a HashSet collection will guarantee this...provided that we guarantee that equals() and hashCode() obey the contract.