<p>In the previous article, we have discussed <strong><a href="https://dineshonjava.com/internal-working-of-hashmap-in-java/">internal working about the <em>HashMap</em></a></strong> and here we will discuss the internal working of <em>LinkedHashMap</em> in <a href="https://dineshonjava.com/core-java-baby-step-to-be-best-java-ian/"><strong>Java</strong></a>. As we know that, a lot of interviewers ask internal working of data structures such <strong><a href="https://dineshonjava.com/hashmap-class-in-collection-framework/"><em>HashMap</em></a></strong>, <strong><a href="https://dineshonjava.com/treemap-class-in-collection-framework/"><em>TreeMap</em></a></strong>, <strong><a href="https://dineshonjava.com/linkedhashmap-class-in-collection/"><em>LinkedHashMap</em></a></strong>, <strong><a href="https://dineshonjava.com/linkedlist-class-in-collection/"><em>LinkedList</em> </a></strong>etc. That is why I have brought such questions in front of you.</p>
<p><em>LinkedHashMap</em> extends <em>HashMap</em> class and implements <em>Map</em> interface. That means <em>LinkedHashMap</em> has all functionality same as the <em>HashMap</em> either calculating index using Hashing for bucket finding. The difference between <em>LinkedHashMap</em> and <em>HashMap</em> is the <em>LinkedHashMap</em> has retrieval order same as insertion order.</p>
<h2>LinkedHashMap in Java</h2>
<p><em>LinkedHashMap</em> is just an extension of HashMap as the class definition is as below</p>
<pre>public class LinkedHashMap<;K, V>; 
extends HashMap<;K, V>; 
implements Map<;K, V>; 
</pre>
<h2>Structure of Each Node</h2>
<p>Internally, the node of the <em>LinkedHashMap</em> represents as the below:</p>
<ul>
<li>int hash</li>
<li>K key</li>
<li>V value</li>
<li>Node next</li>
<li>Node previous</li>
</ul>
<p>Let&#8217;s see the working of <em>LinkedHashMap</em> diagrammatically.</p>
<p><img class="aligncenter size-full wp-image-4295" src="https://dineshonjava.com/wp-content/uploads/2018/10/LinkedHashMap-Node.png" alt="Internal Working of LinkedHashMap" width="381" height="99" /></p>
<blockquote><p><strong>LinkedList Algorithms Interview Questions</strong></p>
<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>
<h2>Hashing Implementation</h2>
<p>As we have discussed the Hashing implementation of the <em>LinkedHashMap</em> same as the <em>HashMap</em> hashing implementation, we have already discussed in <strong><a href="https://dineshonjava.com/internal-working-of-hashmap-in-java/">this article</a></strong>. Let&#8217;s see the following class of the Key implementations:</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 hash code of an object. The <em>hashCode()</em> method of object class returns the memory reference of the object in integer form. But In <em>LinkedHashMap</em>, <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. <em>LinkedHashMap</em> uses <em>equals()</em> to compare the key whether they are equal or not.</p>
<h2>Bucketing and Indexing</h2>
<p>Finding bucket in the <em>LinkedHashMap</em> is same as the <em>HashMap</em>, it uses hash code to find bucket as the following:</p>
<p>Let’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.</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’s see the how does <em>LinkedHashMap</em> work internally.</p>
<h2>Internal Working of LinkedHashMap in Java</h2>
<p><strong>Step 1:</strong> Create an empty <em>LinkedHashMap</em> as the following</p>
<pre>Map map = new LinkedHashMap(); 
</pre>
<p>The default size of <em>LinkedHashMap</em> 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 LinkedHashMap" 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 {“Dinesh”}. As we have implemented <em>hashCode()</em> 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 before = null 
 Node after = 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>
<li>As <em>LinkedHashMap</em> will provide us with the retrieval order as insertion order of elements, it needs to keep track of last inserted object. It has two references head and tail which will keep track of the latest object inserted and the first object inserted. Because it is very first node i.e. {&#8220;Dinesh&#8221;} is added then head and tail will both point to the same object.</li>
</ol>
<p>Let’s see the following diagram of the <em>LinkedHashMap</em>:</p>
<p><img class="aligncenter size-full wp-image-4296" src="https://dineshonjava.com/wp-content/uploads/2018/10/LinkedHashMap-Node-1.png" alt="LinkedHashMap first insert" width="578" height="290" /></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 {“Anamika”}. 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>But, as we are inserting {“Anamika”} after {“Dinesh”}, this information must be present in form of some links.<br />
So {“Dinesh”}.after will refer to {“Anamika”}, {“Anamika”}.before will refer to {“Dinesh”}. The head refers to {“Dinesh”} and tail refers to {“Anamika”}. Now it creates a node object as the following:</p>
<pre>{ 
 int hash = 4498 
 Key key = {"Anamika"} 
 Integer value = "Anamika" 
 Node after = null 
 Node before = {“Dinesh”} 
} 
</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’s see the following diagram of the <em>LinkedHashMap</em>:</p>
<p><img class="aligncenter size-full wp-image-4297" src="https://dineshonjava.com/wp-content/uploads/2018/10/LinkedHashMap-Node-2.png" alt="LinkedHashMap-Node-2" width="569" height="414" /></p>
<p><strong>Step 4:</strong> 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 {“Arnav”}. As we have implemented <em>hashCode()</em> 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>{&#8220;Anamika&#8221;} will have next object as {“Arnav”}</li>
<li>{“Arnav”} will have the previous object as {&#8220;Anamika&#8221;}</li>
<li>The head will remain unchanged and will refer to {“Dinesh”}</li>
<li>The tail will refer to latest added {“Arnav”}</li>
</ol>
<p>Let’s see the following diagram of the LinkedHashMap:</p>
<p><img class="aligncenter size-full wp-image-4298" src="https://dineshonjava.com/wp-content/uploads/2018/10/LinkedHashMap-Node-3.png" alt="LinkedHashMap-Node-3" width="570" height="559" /></p>
<p>I hope the article helped to understand the working of <em>put()</em> method of LinkedHashMap in java. Let&#8217;s see the <em>LinkedHashMap&#8217;s get()</em> method internal working as below:</p>
<h2>LinkedHashMap’s get() method work internally</h2>
<p>Now we will fetch a value from the <em>LinkedHashMap</em> using the <em>get()</em> method. As the following, we are fetching the data for key {“Arnav”}:</p>
<pre>map.get(new Key("Arnav")); 
</pre>
<p>As we know that <em>LinkedHashMap</em> and <em>HashMap</em> have almost the same functionality except maintaining insertion order. So fetching data from <em>LinkedHashMap</em> has the same steps as we have discussed in the <strong><a href="https://dineshonjava.com/internal-working-of-hashmap-in-java/">previous article of <em>HashMap</em></a></strong>.</p>
<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 <em>hashCode()</em> 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 <em>LinkedHashMap</em> 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/internal-working-of-hashmap-in-java/">Previous</a> 
									 </div> 
									 <div class="wp-post-navigation-next"> 
									 <a href="https://dineshonjava.com/internal-working-of-treemap-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: '4294'});
});
</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…