When I use an object as a key in a Hashtable, Which methods must I override and why ?

When you create object to use as the key 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.

A general rule : when you override equals() , you always override hashCode()

Why ?

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.

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. 

Example 1. If the hashcode equals zero, the Hashtable places the value into Bucket 0

Example 2. If the hashcode is two, the Hashtable places the value into Bucket 2.

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.

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 in form of Linked list.

Now imagine that you call get() with a key that maps to Bucket 0 determined by hashcode().

The Hashtable will now need to perform a sequential search through the key/value pairs in Bucket 0 to find your requested value on the basis of equals().

Steps for lookup

  1. Query the key' s hashcode

  2. Retrieve the list of key/values residing in the bucket given by the hashcode

  3. Scan through each entry sequentially until a key that equals the key passed into get() is found.