How Java Hashtable Works ?
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. It is obvious that 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. By the end of this article you will find out the reason behind this condition.
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.
and
Initial capacity is number of buckets created at the time of Hashtable instantiation. Bucket is a logical space of storage for Hashtable.
If you are going to write a custom hashCode(), then follow the following contract:
hashCode() guarantees distinct integers by using the internal address of the object.
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. By the end of this article you will find out the reason behind this condition.
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.
and
Initial capacity is number of buckets created at the time of Hashtable instantiation. Bucket is a logical space of storage for Hashtable.
Hashing and Hashtable
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 hasing function h(k) should return a number within that allocated spectrum (logical address space).
Hashing in Java
Java’s 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.
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:
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.
- The general contract of
hashCodeis: 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.
- If two objects are equal according to the equals(Object)method, then calling the
hashCodemethod on each of the two objects must produce the same integer result
hashCode() guarantees distinct integers by using the internal address of the object.
