Let's discuss the hashcode contract

[Faber Siagian]

Dear ranchers,

K&B says that the hashcode() contract are :

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

2. If two objects are unequal according to the equals(Object) method, there's no requirement
about hashcode().

3. If calling hashcode() on two objects produce different integer result, then both of them
must be unequal according to the equals(Object).

I can't understand point 2 and 3.
I think, if two objects unequal according to the equals(), then calling to the hashcode() must produce different integer result, and viceversa.
Think about this, what happen if 20 equal objects have the same hashcode ? Then HashMap or HashSet or Hashtable will put them in the same bucket. And it will slow down the performance.

Maybe there are reasons that make sense behind the contract no.2 and 3, and i hope there's someone explain it.
[ July 20, 2008: Message edited by: Bear Bibeault ]

[Ralph Jaus]

what happen if 20 equal objects have the same hashcode ? Then HashMap or HashSet or Hashtable will put them in the same bucket. And it will slow down the performance

Assume you've got 100 sorted numbers, each in its own bucket (assume further for simplification they are organized sequentially). Now, if you are looking for 100 you have to look in 100 buckets. That makes about 100 operations.

Now assume the numbers are distributed in 5 buckets with 20 sorted numbers in each bucket. And the buckets are ordered and labeled like 1-20, 21-40,...If you are now looking for 100, you have to look at 5 labels and in the last bucket you have to hurry through 20 numbers. That makes about 25 operations.

Note: This is just a rough explanation of the idea behind a hash code. Of course my example could be optimized with binary searches and so on.
[ July 20, 2008: Message edited by: Ralph Jaus ]

[Cameron Wallace McKenzie]

Remember that hashCode doesn't always generate a unique number. It is a non-unique calculation. For the most part, hashCode gives a unique number, but there is a small chance that calling hashCode on two different objects will generate the same value. That's why you then need to go to the equals method - to see if two objects that create the same hashcode are really equal to each other, as opposed to just curiously generating the same hash.

For the JVM, comparing numbers is much easier than calling equals, so calling hashCode all the time is much faster. Only going to equals when needed, should really speed things up.

I have a bunch of sample mock questions on the hashCode and equals contract on my blog right now. There's about 15-20 sample exam questions on the topic designed to drive home the point. Give them a try!

Sample SCJP 6.0 Mock Exam Questions: Collection Classes and hashCode

Given the following code, what would be the result of running the HashTest class?


public class HashTest{

public static void main (String args[]){
java.util.Hashtable hashtable = new java.util.Hashtable();
hashtable.put(new Entity(1), new Entity(1));
hashtable.put(new Entity(2), new Entity(2));
hashtable.put(new Entity(3), new Entity(3));
System.out.println(hashtable.size());
}
}


/**** Entity Class ****/
class Entity{
public final int CODE = 007;
int id;
Entity(int id) {this.id = id;}
public int hashCode() {return id;}
public boolean equals(Object o) {return true;}
}

a) 0 is printed to the console
b) 1 is printed to the console
c) 2 is printed to the console
d) 3 is printed to the console
e) compile time error
f) runtime error


Option d) is correct.

In this case, the equals method always returns true, but if the hashcode method indicates that two instances are NOT the same, the equals method does not need to be called. As a result, the HashMap treats every Entity key as a unique entity or instance, despite the fact that all three instances would actually generate a true value when compared using the equals method.

Since the key values appear unique to the JVM using the HashMap and the hashcode method of the entities, each key being used by the HashMap is considered unique.

-Cameron McKenzie