Monday, 2 January 2017

How HashMap works Internally In Java ?


Know Also : Map / HashMap / LinkedList

HashMap Internal Working :

HashMap works on the principle of Hashing. Hashing is the technique through which keys are getting converted into Hashcode. Hashcode are nothing but some integer values (e.g. 1632136162).
HashMap internally uses table to store elements. And each block of table is known as bucket. And each bucket uses LinkedList to store elements. The default size of HashMap is 16.

0
1
2
3
4
:
:
15

How put(k,v) works internally :

When we put any key value pair in HashMap, put(k,v) method first check for null if key is null the value is stored at index[0] because hashcode for null is  always 0.

If key is not null then, Hashcode is calculated by hashCode() method of Object class. (We can get Hashcode of any Object or Variable/data member through hashCode() method because this method belongs to Object class.)As Hashcode is calculated it calculates the index (position on which it store the element in table) by dividing the Hashcode by default size of HashMap.

Here the index is calculated because we cannot create the memory of Hashcode size. It may be possible for one or two Hashcode, but it is not possible for many Hashcodes or keys.

Example:                                                        
HashMap<String, Integer> map = new HashMap<>();
map.put("pushkar",100);
map.put("Nitesh",101);
map.put("sanjay",102);

1 ) put() first calculate the Hashcode of key pushkar i.e 219783038 and now it calculates the index by dividing hashcode i.e 219783038 by default size of Map i.e 16 and get remainder as 14. Now this key value pair will stored at index 14 in form of node.


2 ) put() now calculate the Hashcode of key Nitesh  i.e 909651390 and now it calculates the index by dividing hashcode i.e 909651390  by default size of Map i.e 16 and get remainder as 14. Now this key value pair will stored at index 14 in form of node.

If any element already exists at calculated index or two keys have same index positions. Then each block of table or each bucket maintain LinkedList internally. We add element at same index as next node. And null will removed from the node and it will contain reference/memory address of next node.


3 ) put() now calculate the Hashcode of key sanjay i.e 1961367327 and now it calculates the index by dividing hashcode i.e 1961367327 by default size of Map i.e 16 and get remainder as 15. Now this key value pair will stored at index 15 in form of node. And this process will continue of all the keys.


How get(k) works internally :

get(k) method do all the operations as put(k,v) method does, get(k) also first calculates the hashcode of key, then it calculates the index by dividing the hashcode by default size of map. Then it look at particular index and match the hashcode , if hashcode matches , then it match the key with equals method and if key matches it return the value. Otherwise if the key not matches it return null.

Example:
map.get("pushkar");
map.get("Nitesh");
map.get("sanjay");
map.get("sanjay1");

Output :
100
101
102

   
Blog Author - Pushkar Khosla,
Software Developer by Profession with 3.0 Yrs of Experience , through this blog i'am sharing my industrial Java Knowledge to entire world. For any question or query any one can comment below or mail me at pushkar.itsitm52@gmail.com.

This blog is all about to learn Core Java ,Interview Programs and Coding tricks to polish your Java Knowledge. If you like the content of this blog please share this with your friends.



Share this Blog with yours Friends !!

No comments:

Post a Comment