java-collection: How hashtable works in java?

Hashtable is an implementation of a key-value pair data structure in java. You can store and retrieve a ´value´ using a ´key´ and it is an identifier of the value stored. The ´key´ should be unique.

java.util.Hashtable extends Dictionary and implements Map. Objects with non-null value can be used as a key or value. Key of the Hashtable must implement hashcode() and equals() methods.

Generally a Hashtable in java is created using the empty constructor Hashtable(). Which is a poor decision and an often repeated mistake. Hashtable has two other constructors

1. Hashtable(int initialCapacity)
2. Hashtable(int initialCapacity, float loadFactor)

Initial capacity is number of buckets created at the time of Hashtable instantiation. Bucket is a logical space of storage for Hashtable.


Hashing:
------------------------------
Before seeing java´s Hashtable in detail you should understand hashing in general. Assume that, v is a value to be stored and k is the key used for storage / retrieval, then h is a hash function where v is stored at h(k) of table. To retrieve a value compute h(k) so that you can directly get the position of v. So in a key-value pair table, you need not sequentially scan through the keys to identify a value. h(k) is the hashing function and it is used to find the location to store the corresponding value v. h(k) cannot compute to a indefinite space. Storage allocated for a Hashtable is limited within a program. So, the hashing function h(k) should return a number within that allocated spectrum (logical address space).

Javas hashing uses uses hashCode() method from the key and value objects to compute. Following is the core code from Hashtable where the hashCode ´h´ is computed. You can see that both key´s and value´s hashCode() method is called.

h += e.key.hashCode() ^ e.value.hashCode();

It is better to have your hashCode() method in your custom objects. String has its own hashCode methode and it computes the hashcode value as below:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

If you don´t have a hashCode() method, then it is derived from Object class. Following is javadoc comment of hashCode() method from Object class:

"Returns a hash code value for the object. This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable."

If you are going to write a custom hashCode(), then follow the following contract:

"The general contract of hashCode is: Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified."

The following is to improve performance of the Hashtable.

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

hashCode() guarantees distinct integers by using the internal address of the object.