Hash Algorithm in Java

Java collections like Hashtable, HashSet and HashMap uses Hashing Algorithm. The objective of this article is to help you to visualize how hashing algorithm works.

Each entry in Hashtable is stored as "Entry" object. The "Entry" object contains members like,
hash index, key object, value object, next entry object.

Let's say Hashtable contains group of employee objects - e1, e2, e3, ...e9. The Employee class must override equals & hashcode method. Each employee object contains members like id, name and department.

Populate the Hashtable,
hashtable.put(new Integer(e1.id), e1);
.......................................................
.......................................................
hashtable.put(new Integer(e9.id), e9);

The hash algorithm works like whenever you put any entry into hastable, the bucket index will be calculated
based on return value of hashcode() from Key object. The hastable contains array of Entry objects. Each entry is inserted into array in the corresponding bucket index.

In this case, the hashtable has got 9 keys and,
bucket index of e1/e5/e6  is 23
bucket index of e7/e2/e3 is 125
bucket index of e4/e8/e9 is 225

Each bucket is represented as vertical bar in the below diagram. In each bucket, the elements are stored in singly linked list format as shown in the picture. The next value (refer diagram - next) is maintained in each element inside hashtable.

The new element always be added into the bottom of the bucket and an element can be removed from any position.

For example, if object e2 is removed, then bucket 125 will look like,
next -> e7.next->e3.next->null

if object e10 is to be added into bucket 23, then it will look like,
next ->e1.next->e5.next->e6.next->e10.next->null

To get any value based on key, the bucket index will be calculated using hashcode() of Key object.
1. Identify the bucket based on bucket index
2. Iterate over each element in the bucket and compare element's key with the given key object.
3. Return the value object from element.
Note: Element is nothing but Entry object which has hash, key, value and next entry.

Also note down that if two objects are equals, the hashcode should be equal. At the same time, if two objects are not equl then hashcode should be different.

Hope this article can help programmers to visualize how the hashing algorithm works in Hashtable, HashSet & HashMap.

Note: one more important info is the HashSet internally uses HashMap. All the elements are represented as keys and dummy object as values for all those keys.