In the previous article, we have discussed internal working about the HashMap and here we will discuss the internal working of LinkedHashMap in Java. As we know that, a lot of interviewers ask internal working of data structures such HashMap, TreeMap, LinkedHashMap, LinkedList etc. That is why I have brought such questions in front of you.
LinkedHashMap extends HashMap class and implements Map interface. That means LinkedHashMap has all functionality same as the HashMap either calculating index using Hashing for bucket finding. The difference between LinkedHashMap and HashMap is the LinkedHashMap has retrieval order same as insertion order.
LinkedHashMap is just an extension of HashMap as the class definition is as below
public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V>
Internally, the node of the LinkedHashMap represents as the below:
Let’s see the working of LinkedHashMap diagrammatically.
LinkedList Algorithms Interview Questions
Find and Break a Loop in a Linked list
How to Detect loop in a linked list
Find the nth node from the end of a singly linked list
Find the middle element in a linked list
How to Reverse linked list in Java
Delete given node from a singly linked list
Remove Duplicates from the Unsorted Singly Linked list
The singly linked list is palindrome without extra space
As we have discussed the Hashing implementation of the LinkedHashMap same as the HashMap hashing implementation, we have already discussed in this article. Let’s see the following class of the Key implementations:
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;
}
}
In the above code, I am taking a class Key and override hashCode() method to show different scenarios. Here, overridden hashCode() method return a calculated hashcode. The hashCode() method is used to get the hash code of an object. The hashCode() method of object class returns the memory reference of the object in integer form. But In LinkedHashMap, hashCode() is used to calculate the bucket and therefore calculate the index.
We have also overridden equals() method in the above code, equals method is used to check that 2 objects are equal or not. LinkedHashMap uses equals() to compare the key whether they are equal or not.
Finding bucket in the LinkedHashMap is same as the HashMap, it uses hash code to find bucket as the following:
Let’s see the following relationship between bucket and capacity is as follows
capacity = number of buckets * load factor
If the hash code of two items is same then both items will be stored into the same bucket.
index = hashCode(key) & (n-1).
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.
Let’s see the how does LinkedHashMap work internally.
Step 1: Create an empty LinkedHashMap as the following
Map map = new LinkedHashMap();
The default size of LinkedHashMap is taken as 16 as the following empty array with size 16.
You can see the above image initially there is no element in the array.
Step 2: Inserting first element Key-Value Pair as the below:
map.put(new Key("Dinesh"), "Dinesh");
This step will be executed as the following:
{
int hash = 4501
Key key = {"Dinesh"}
Integer value = "Dinesh"
Node before = null
Node after = null
}
Let’s see the following diagram of the LinkedHashMap:
Step 3: Adding another element Key-Value Pair as the below:
map.put(new Key("Anamika"), "Anamika");
This step will be executed as the following:
{
int hash = 4498
Key key = {"Anamika"}
Integer value = "Anamika"
Node after = null
Node before = {“Dinesh”}
}
Let’s see the following diagram of the LinkedHashMap:
Step 4: Adding another element Key-Value Pair as the below:
map.put(new Key("Arnav"), "Arnav");
This step will be executed as the following:
Let’s see the following diagram of the LinkedHashMap:
I hope the article helped to understand the working of put() method of LinkedHashMap in java. Let’s see the LinkedHashMap’s get() method internal working as below:
Now we will fetch a value from the LinkedHashMap using the get() method. As the following, we are fetching the data for key {“Arnav”}:
map.get(new Key("Arnav"));
As we know that LinkedHashMap and HashMap have almost the same functionality except maintaining insertion order. So fetching data from LinkedHashMap has the same steps as we have discussed in the previous article of HashMap.
This step will be executed as the following:
Hope this article is able to give much information about the internal working of LinkedHashMap in Java.
Happy Learning with DineshonJava.
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…