June 21, 2002
When I use an object as a key in a Hashtable, what in the Object class must I override and why?
![]()
When you create your own key object for use in a Hashtable, you must override the Object.equals() and Object.hashCode() methods since Hashtable uses a combination of the key's hashCode() and equals() methods to store and retrieve its entries quickly. It's also a general rule that when you override equals(), you always override hashCode().
A slightly more in-depth explanation will help you understand Hashtable's mechanism for storage and retrieval. A Hashtable internally contains buckets in which it stores the key/value pairs. The Hashtable uses the key's hashcode to determine to which bucket the key/value pair should map.

Figure 1. A Hashtable and its buckets
Figure 1 shows a Hashtable and its buckets. When you pass a key/value to the Hashtable, it queries the key's hashcode. The Hashtable uses that code to determine the bucket in which to place the key/value. So, for example, if the hashcode equals zero, the
Hashtable places the value into Bucket 0. Likewise, if the hashcode is two, the Hashtable places the value into Bucket 2. (This is a simplistic example; the Hashtable will massage the hashcode first so the Hashtable doesn't try to insert the value outside the bucket.)
By using the hashcode this way, the Hashtable can also quickly determine in which bucket it has placed the value when you try to retrieve it.
Hashcodes, however, represent only half the picture. The hashcode only tells the Hashtable into which bucket to drop the key/value. Sometimes, however, multiple objects may map to the same bucket, an event known
as a collision. In Java, the Hashtable responds to a collision by placing multiple values into the same bucket (other implementations may handle collisions differently).
Figure 2 shows what a Hashtable might look like after a few collisions.

Figure 2. A Hashtable after a few collisions
Now imagine that you call get() with a key that maps to Bucket 0. The Hashtable will now need to peform a sequential search through the key/value pairs in Bucket 0 to find your requested value. To perform
this lookup, the Hashtable executes the following steps:
get() is found
A long answer to a short question I know, but it gets worse. Properly overriding equals() and hashCode() is a nontrivial exercise. You must take extreme care to guarantee both methods' contracts.
According to the equals() Javadoc, the method must conform to the following rules:
"Theequals()method implements an equivalence relation:
- It is reflexive: For any reference value x,
x.equals(x)should return true- It is symmetric: For any reference values x and y,
x.equals(y)should return true if and only ify.equals(x)returns true- It is transitive: For any reference values x, y, and z, if
x.equals(y)returns true andy.equals(z)returns true, thenx.equals(z)should return true- It is consistent: For any reference values x and y, multiple invocations of
x.equals(y)consistently return true or consistently return false, provided no information used in equals comparisons on the object is modified- For any non-null reference value x,
x.equals(null)should return false"
In Effective Java, Joshua Bloch offers a five-step recipe for writing an effective equals() method. Here's the recipe in code form:
Ground shaking content i getBy jack skellington on October 17, 2009, 3:23 amGround shaking content i get form your blog. Very nice post about good article. Thanks for your beneficial information about 70-647 exam, 70-270 exam and 640-553...
Reply | Read entire comment
Good explanation indeed. Thanks.By Anonymous on September 18, 2009, 7:11 amGood explanation indeed. Thanks.
Reply | Read entire comment
Good Article.By Anonymous on August 21, 2009, 4:11 amGood Article...Thanks,
Reply | Read entire comment
View all comments