<p>In this article, we will discuss the Internal Working of <strong><a href="https://dineshonjava.com/hashmap-class-in-collection-framework/">HashMap</a></strong> in <strong><a href="https://dineshonjava.com/core-java-baby-step-to-be-best-java-ian/">Java</a> </strong>and how hashmap&#8217;s get and put method works internally. As we know that HashMap is a key and value collection in java. The HashMap stores the data in key and value format. It provides the basic implementation of the Map interface of Java. We can put a value with using a key and also we can access this value using that key.</p>
<p>HashMap uses a technique called Hashing. Hashing is a technique to convert an object into an integer. The hashing is done by using the method <em>hashCode()</em>. This method is very important to maintain the performance of the HashMap.</p>
<h2>Internal Structure of HashMap</h2>
<p>A HashMap is an array of the node and these nodes are like a linked list&#8217;s node as the following:</p>
<ul>
<li>int hash</li>
<li>K key</li>
<li>V value</li>
<li>Node next</li>
</ul>
<blockquote><p><strong><a href="https://dineshonjava.com/find-and-break-a-loop-in-a-linked-list/">Find and Break a Loop in a Linked list</a></strong><br />
<strong><a href="https://dineshonjava.com/how-to-detect-loop-in-a-linked-list/">How to Detect loop in a linked list</a></strong><br />
<strong><a href="https://dineshonjava.com/nth-node-from-the-end-of-a-singly-linked-list/">Find the nth node from the end of a singly linked list</a></strong><br />
<strong><a href="https://dineshonjava.com/find-the-middle-element-in-a-linked-list/">Find the middle element in a linked list</a></strong><br />
<strong><a href="https://dineshonjava.com/reverse-linked-list/">How to Reverse linked list in Java</a></strong><br />
<strong><a href="https://dineshonjava.com/delete-given-node-from-singly-linked-list/">Delete given node from a singly linked list</a></strong><br />
<strong><a href="https://dineshonjava.com/remove-duplicates-from-the-unsorted-singly-linked-list/">Remove Duplicates from the Unsorted Singly Linked list</a></strong><br />
<strong><a href="https://dineshonjava.com/singly-linked-list-is-palindrome/">The singly linked list is palindrome without extra space</a></strong></p></blockquote>
<h3>Hashing Implementation</h3>
<p>As we have discussed that Hashing is processed to convert a long string into a small string to represent the same string. In other words, the Hashing is a technique to convert an object into an integer number and this number is known as the hashcode of the object and you can generate this hashcode by using hashcode() method. Let&#8217;s see the following implementation of the hashcode() method for the class Key:</p>
<pre>package com.dineshonjava.algo.map; 
 
/** 
 * @author Dinesh.Rajput 
 * 
 */ 
public class Key { 
	 
	final int data = 112; 
	private String key; 
	 
	public Key(String key) { 
		super(); 
		this.key = key; 
	} 
	 
	//index = hashCode(key) &; (n-1). 
	 
	@Override 
	public int hashCode() { 
		final int prime = 31; 
		int result = 1; 
		result = prime * result + data; 
		result = prime * result + ((key == null) ? 0 : (key.charAt(0)+"").hashCode()); 
		System.out.println("hashCode for key: "+ key + " = " + result); 
		System.out.println("Index "+ (result &; 15)); 
		return result; 
	} 
 
	@Override 
	public boolean equals(Object obj) { 
		if (this == obj) 
			return true; 
		if (obj == null) 
			return false; 
		if (getClass() != obj.getClass()) 
			return false; 
		Key other = (Key) obj; 
		if (data != other.data) 
			return false; 
		if (key == null) { 
			if (other.key != null) 
				return false; 
		} else if (!key.equals(other.key)) 
			return false; 
		return true; 
	} 
} 
</pre>
<p>In the above code, I am taking a class Key and override <em>hashCode()</em> method to show different scenarios. Here, overridden <em>hashCode()</em> method return a calculated hashcode. The <em>hashCode()</em> method is used to get the hashCode of an object. The <em>hashCode()</em> method of object class returns the memory reference of the object in integer form. But In HashMap, <em>hashCode()</em> is used to calculate the bucket and therefore calculate the index.</p>
<p>We have also overridden <em>equals()</em> method in the above code, equals method is used to check that 2 objects are equal or not. HashMap uses <em>equals()</em> to compare the key whether they are equal or not.</p>
<h3>Buckets</h3>
<p>As we have said, HashMap stores elements in the array. Internally it uses array data structure. A bucket is an item of that array. This whole array considers as the buckets. This bucket is used to store nodes. It can store one or more than two nodes. Each node has a link to the next nodes if they store into the same bucket. In that case, a link list structure is used to connect the nodes.</p>
<p>Let&#8217;s see the following relationship between bucket and capacity is as follows:</p>
<pre>capacity = number of buckets * load factor 
</pre>
<p>If the hash code of two items is same then both items will be stored into the same bucket. That means node storage in the bucket depends on the hashCode<em>()</em> method. The better your <em>hashCode()</em> method is, the better your buckets will be utilized.</p>
<h3>Index Calculation in Hashmap</h3>
<p>HashCode is used to decide the bucket in the HashMap array, so using the HashCode we create an index. What happens, if Hashcode of the key may be very large or may be in the range of integer and if we create arrays for such a range. That may be a reason of the <em>OutOfMemoryException</em>. That is why it uses an index to minimize the size of an array. An index is created by using the following calculation.</p>
<pre>index = hashCode(key) &; (n-1). 
</pre>
<p>In the above formula, n is a number of buckets or the size of an array. In our example, I will consider n as default size that is 16.</p>
<p>Let&#8217;s see the how does HashMap work internally.</p>
<h2>Internal Working of HashMap in Java</h2>
<p><strong>Step 1:</strong> Create an empty HashMap as the following</p>
<pre>Map map = new HashMap(); 
</pre>
<p>The default size of HashMap is taken as 16 as the following empty array with size 16.</p>
<p><img class="aligncenter size-full wp-image-4286" src="https://dineshonjava.com/wp-content/uploads/2018/10/buckets.png" alt="Empty HashMap" width="596" height="94" /></p>
<p>You can see the above image initially there is no element in the array.</p>
<p><strong>Step 2:</strong> Inserting first element Key-Value Pair as the below:</p>
<pre>map.put(new Key("Dinesh"), "Dinesh"); 
</pre>
<p>This step will be executed as the following:</p>
<ol>
<li>First, it will calculate the hash code of Key {&#8220;Dinesh&#8221;}. As we have implemented hashCode() method for the Key class, hash code will be generated as 4501.</li>
<li>Calculate index by using a generated hash code, according to the index calculation formula, it will be 5.</li>
<li>Now it creates a node object as the following:
<pre>{ 
 int hash = 4501 
 Key key = {"Dinesh"} 
 Integer value = "Dinesh" 
 Node next = null 
} 
</pre>
</li>
<li>This node will be placed at index 5. As of now, we are supposing there is no node present at this index because it is a very first element.</li>
</ol>
<p>Let&#8217;s see the following diagram of the HashMap:<br />
<img class="aligncenter size-full wp-image-4287" src="https://dineshonjava.com/wp-content/uploads/2018/10/buckets-insert-1.png" alt="HashMap first insert" width="596" height="218" /></p>
<p><strong>Step 3:</strong> Adding another element Key-Value Pair as the below:</p>
<pre>map.put(new Key("Anamika"), "Anamika"); 
</pre>
<p>This step will be executed as the following:</p>
<ol>
<li>First, it will calculate the hash code of Key {&#8220;Anamika&#8221;}. As we have implemented hashCode() method for the Key class, hash code will be generated as 4498.</li>
<li>Calculate index by using a generated hash code, according to the index calculation formula, it will be 2.</li>
<li>Now it creates a node object as the following:
<pre>{ 
 int hash = 4498 
 Key key = {"Anamika"} 
 Integer value = "Anamika" 
 Node next = null 
} 
</pre>
</li>
<li>This node will be placed at index 2. As of now, we are supposing there is no node present at this index because it is a very first element.</li>
</ol>
<p>Let&#8217;s see the following diagram of the HashMap:</p>
<p><img class="aligncenter size-full wp-image-4288" src="https://dineshonjava.com/wp-content/uploads/2018/10/buckets-insert-2.png" alt="HashMap put method internal working" width="596" height="218" /></p>
<p><strong>Step 4:</strong> (Case of Collision) Adding another element Key-Value Pair as the below:</p>
<pre>map.put(new Key("Arnav"), "Arnav"); 
</pre>
<p>This step will be executed as the following:</p>
<ol>
<li>First, it will calculate the hash code of Key {&#8220;Arnav&#8221;}. As we have implemented hashCode() method for the Key class, hash code will be generated as 4498.</li>
<li>Calculate index by using a generated hash code, according to the index calculation formula, it will be 2.</li>
<li>Now it creates a node object as the following:
<pre>{ 
int hash = 4498 
Key key = {"Arnav"} 
Integer value = "Arnav" 
Node next = null 
} 
</pre>
</li>
<li>This node will be placed at index 2 if no other object is presented there.</li>
<li>But at this index 2, one node is already presented, so this is the case of a collision.</li>
<li>Now, it will check hashCode() and equals() method if both keys are same then it will replace the old value with current value.</li>
<li>If both keys are not the same then it will connect this node to the previous node object via the linked list and both are stored at index 2.</li>
</ol>
<p>Let&#8217;s see the following diagram of the HashMap:</p>
<p><img class="aligncenter size-full wp-image-4289" src="https://dineshonjava.com/wp-content/uploads/2018/10/buckets-insert-3.png" alt="HashMap internal working" width="630" height="289" /></p>
<p><strong>Step 5:</strong> Adding another element Key-Value Pair as the below:</p>
<pre>map.put(new Key("Rushika"), "Rushika"); 
</pre>
<p>This step will be executed as the following:</p>
<ol>
<li>First, it will calculate the hash code of Key {&#8220;Rushika&#8221;}. As we have implemented hashCode() method for the Key class, hash code will be generated as 4515.</li>
<li>Calculate index by using a generated hash code, according to the index calculation formula, it will be 3.</li>
<li>Now it creates a node object as the following:
<pre>{ 
int hash = 4515 
Key key = {"Rushika"} 
Integer value = "Rushika" 
Node next = null 
}</pre>
</li>
<li>This node will be placed at index 3. As of now, we are supposing there is no node present at this index because it is a very first element.</li>
</ol>
<p>Let&#8217;s see the following diagram of the HashMap:</p>
<p><img class="aligncenter size-full wp-image-4290" src="https://dineshonjava.com/wp-content/uploads/2018/10/buckets-insert-4.png" alt="Internal Working of HashMap" width="630" height="324" /></p>
<p>As we have seen how does HashMap&#8217;s put() method work internally? Let&#8217;s move to the next section and see how does HashMap&#8217;s get() method work internally.</p>
<h2>HashMap&#8217;s get() method work internally</h2>
<p>Now we will fetch a value from the HashMap using the get() method. As the following, we are fetching the data for key {&#8220;Arnav&#8221;}:</p>
<pre>map.get(new Key("Arnav")); 
</pre>
<p>This step will be executed as the following:</p>
<ol>
<li>First, it will calculate the hash code of Key {&#8220;Arnav&#8221;}. As we have implemented hashCode() method for the Key class, hash code will be generated as 4498.</li>
<li>Calculate index by using a generated hash code, according to the index calculation formula, it will be 2.</li>
<li>Go to index 2 of an array and compare the first element’s key with given key. If both are equals then return the value, otherwise, check for next element if it exists.</li>
<li>In our case, it is not found as the first element and next of node object is not null.</li>
<li>If next of node is null then return null.</li>
<li>If next of node is not null traverse to the second element and repeat the process 3 until a key is not found or next is not null.</li>
</ol>
<p>Hope this article is able to give much information about the internal working of HashMap in Java.</p>
<p>Happy Learning with DineshonJava.</p>
<div align="center"><iframe style="width: 120px; height: 240px;" src="//ws-in.amazon-adsystem.com/widgets/q?ServiceVersion=20070822&;OneJS=1&;Operation=GetAdHtml&;MarketPlace=IN&;source=ac&;ref=tf_til&;ad_type=product_link&;tracking_id=dineshonjav06-21&;marketplace=amazon&;region=IN&;placement=1787127567&;asins=1787127567&;linkId=a1e64f621b5e6128d8cb10e876eb1c48&;show_border=true&;link_opens_in_new_window=true&;price_color=333333&;title_color=0066c0&;bg_color=ffffff" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" align="center"><span data-mce-type="bookmark" style="display: inline-block; width: 0px; overflow: hidden; line-height: 0;" class="mce_SELRES_start"></span><br />
</iframe></div>
<div class="wp-post-navigation"> 
									 <div class="wp-post-navigation-pre"> 
									 <a href="https://dineshonjava.com/find-and-break-a-loop-in-a-linked-list/">Previous</a> 
									 </div> 
									 <div class="wp-post-navigation-next"> 
									 <a href="https://dineshonjava.com/internal-working-of-linkedhashmap-in-java/">Next</a> 
									 </div> 
									</div>
<script type="text/javascript">
jQuery(document).ready(function($) {
 $.post('https://dineshonjava.com/wp-admin/admin-ajax.php', {action: 'mts_view_count', id: '4285'});
});
</script>
Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…
Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…
Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…
Technology has emerged a lot in the last decade, and now we have artificial intelligence;…
Managing a database is becoming increasingly complex now due to the vast amount of data…
Overview In this article, we will explore Spring Scheduler how we could use it by…