How HashMap Internally Works ?

Hashing : How hash map works in java or How get() method works internally

HashMap works on the principle of Hashing.  To understand Hashing, we should understand the three terms first   i.e Hash Function, Hash Value and Bucket.

What is Hash Function , Hash Value  and Bucket ?

HashCode () function which returns an integer value is the Hash function. The important point to note that, this method is present in Object class ( Mother of all class ) .

This is the code for the hash function(also known as hashCode method) in Object Class :

    public native int hashCode();

The most important point to note from the above line :  hashCode method return  int value .

So the Hash value is the int value returned by the hash function .

    So summarize the terms in the diagram below :

               

What is bucket ? 

A bucket is used to store key value pairs . A bucket can have multiple key-value pairs . In hash map, bucket used simple linked list to store objects .

After understanding the terms we are ready to move next step

 How hash map works in java or How get() works internally in java .

Code inside Java Api (HashMap class internal implementation) for HashMap get(Obejct key) method 

1.  Public  V get(Object key)

   {

2.     if (key ==null)

3.     //Some code

4.     int hash = hash(key.hashCode());

5.     // if key found in hash table then  return value

6.     //    else return null

   }

Hash map works on the principle of hashing 

HashMap get(Key k) method calls hashCode method on the key object and applies returned hashValue to its own static hash function to find a bucket location(backing array) where keys and values are stored in form of anested class called Entry (Map.Entry) . So you have concluded that from the previous line that Both key and value is stored in the bucket as a form of  Entry object . So thinking that Only value is stored  in the bucket is not correct and will not give a good impression on the interviewer .

* Whenever we call get (Key k) method on the HashMap object. First it checks that whether key is null or not.  Note that there can only be one null key in HashMap.  

If key is null , then Null keys always map to hash 0, thus index 0.

If key is not null then , it will call hash function on the key object , see line 4 in above method i.e. key.hashCode()  ,so after key.hashCode() returns hashValue , line 4 looks like

4.     int hash = hash(hashValue)

 , and now, it applies returned hashValue into its own hashing function.

We might wonder why we are calculating the hashvalue again using hash(hashValue). Answer is ,It defends against poor quality hash functions.

Now step 4 final  hashvalue is used to find the bucket location at which the Entry object is stored . Entry object stores in the bucket like this (hash,key,value,bucketindex)  

What if  when two different keys have the same hashcode ?

Solution, equals() method comes to rescue. Here candidate gets puzzled. Since bucket is one and we have two objects with the same hashCode .Candidate usually forgets that bucket is a simple linked list.

The bucket is the linked list effectively. Its not a LinkedList as in a java.util.LinkedList - It's a separate (simpler) implementation just for the map .

So we traverse through linked list , comparing keys in each entries using keys.equals() until it return true.  Then the corresponding entry object Value is returned.

How TreeMap works in java : 

Treemap class is like HashMap which stores key- value pairs . The major difference is that Treemap  sorts

the key in ascending order.

According to Java doc  :

Treemap is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

Conclusion:

TreeMap is a Red-Black tree based NavigableMap implementation.In other words , it sorts the TreeMap object keys using Red-Black tree algorithm.

so we learned that TreeMap uses Red Black tree algorithm internally to sort the elements.  

Red Black algorithm is a complex algorithm . We should read the pseudo code of Red Black algorithm in order to understand the internal implementation .

Red Black tree has the following properties :

1. As the name of the algorithm suggests ,color of every node in the tree is either red or black.

2. Root node must be Black in color.

3. Red node cannot have a red color neighbor node.

4. All paths from root node to the null should consist the same number of black nodes.

Rotation in Red Black Tree:

Rotations maintains the in order to ordering of the keys(x,y,z).

A rotation can be maintained in O(1) time.