Internal working of java Hashmap

   The java.util package provides lot of built in data structures. Popular data structures are like lists, sets and maps. lets focus on Map interface in this post.
Maps:
Map is an Interface. It is an associative array data structure which stores keys against values.
i.e. "key1"-->"value",
     "key2"-->"value",
     "key3"-->"value" and so on.

 Map collection framework

Clearly from the above snapshot, we could depict that Hashmap is one of the implementation of Map interface.

Features of HashMap:
-> Java HashMap class contains values based on the key.
-> Java HashMap class contains only unique keys.
-> Java HashMap class may have one null key and multiple null values.
-> Java HashMap class is non synchronized. Thus it gives faster search results.
-> Java HashMap class maintains no order.
-> The initial default capacity of Java HashMap class is 16 with a load factor of 0.75.
Note:
We could imagine hashmap as a dictionary. Means we could lookup for the values against search key, provided it should be loaded with data first.


HashMap class definition:

HashMap<k, v> internally extends class: AbstractMap<k, v> and implements interface: Map<k, v>.

a. Below is the declaration for java.util.HashMap class:
     public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
     Here K and V are the key value parameters.
     K: type of keys maintained by this map. Ex: String, int, Object,..
     V: type of mapped values. Ex: String, int,..

b. Below is the usage of HashMap:
     HashMap<String, Object> hm = new HashMap<>();
hm.put("key1", "value");
hm.put("key2", "value");
hm.get("key1");
hm.size();
hm.clone();
hm.clear();.....

Now lets try to understand the working of Hashmap:
     Internal implementation of the same hashmap is by a technique called 'Hashing'.
What is Hashing?
   It is a technique of transforming the characters string(Text) to a shorted fixed-length value that represents original string. Here a short value(i.e. hashcode) helps in indexing and faster searches.
Now how to transform the characters string to shorted-fixed length value?
   In java, every Object(super class of all classes) has a method 'hash(K k)' that will returns a hash value of short fixed-length for given object.
   i.e. put(K "key1", V "value"){
           long hashcode = hash(key1);
           int index = hashcode & (n-1)
}
n: is the index of hash table. Default index size is 16.
hashcode: it is the computation of hash(key1) which gives long(say 27345643).
index: computation of hashcode with bitwise & operator gives the index ranging from 1 to 15. index[0.....15]

Find the below steps for internal mechanism of hashing:

Step1: Hash table, bucket, Node<K, V> discussion:

For every hashmap, there will be a creation of corresponding hashing table of default bucket size 16. In the  hashing table, each bucket contains the Node which is the linked list of nodes.
What is a Node<K, V>?
  Node is the actual key value holder at the bucket arraylist index with hashcode.
Node consists of: Key,
                            Value,
                            Hash,
                            Linkedlist Node.

Step2: Illustration of 'put' mechanism:

Consider scores is the HashMap<String, Integer> in above snapshot. For each statement execution, put(K k, V v) AbstractMap method will be triggered. In this method, first hashcode will be generated for k and next index is computed with hash using bitwise & operator. Index value lies between 0....15 range. Now in the hashing table, this(key, hash, value, Node) will fit/store in the corresponding indexed bucket(say index 4)
For next 'put' operation, same process is computed for hash index and fits in corresponding indexed bucket. It goes further same way.
Now what if the same index(again 4) is generated and where will it fit?
 i.e. hashing collisions will arise. In this case, same indexed bucket has already been stored with node.
What are Hash collisions?
  In the indexed bucket, it will check if already node exists then linked list of that node will be created and in that created linked list node latest node is fitted in. Same mechanism will be continued if same index will be generated for non unique keys further.

Step3: After 'put' mechanism:

Above snapshot illustrates the after 'put' mechanism how the hash data will be stored in corresponding hashing table.
Note:
HashMap table stores 'null' key. hash(null) is 0 and thus indexed at 0 bucket. 

Step4: 'get' mechanism:
    Step3's snapshot shows the get methods to retrive the hash data value stored in hashing table by keys. First for the 'key', hash will be generated and then corresponding index value for the 'key'. Now in the corresponding indexed bucket, it will try to compare the hashcode of key with the nodes hashcode stored. If the hashcode is found to be same, then corresponding value will be returned back else linked list of next immediate node's hashcode will be compared. This kind of traversing will be continued till the hashcode matches else returns null value.