Let’s ask you a question.
Is there a data structure that has the capability to perform insertion, deletion faster than array or other types of data structure?
Well, if you are a well-versed coder, your literal answer would be; yes!
And, the name of that data structure is hashmap!
Hashmap is defined as the data structure which uses key values to store items in pairs. As the name implies, hashmaps are ideal for the work of mapping.
The implementation of this data structure is being provided in the much-talked about language called Java!
Hence, to make you well-aware of the internal working of hashmap in java, we have prepared this blog post.
So, without any delay, let’s get started with it!
What is a hashmap?
Well, first start with the basics before diving into the internal working of hashmap. A map is touted to contain value pairs and keys.
It is a hashtable implementation with the hashmap java class. This concept offers the constant performance of certain operations like the insertion or the deletion.
Hashmap usually contains the array of certain nodes and all the nodes are represented in the form of classes. They use an array or the linked list to store keys and values. Generally, there exists four fields in the hashmap which are:
Node < K, V>
int hash
K Key
V Value
Node, < K, V> next
Here, two concepts should be known before getting inside of the internal working of hashmaps in java:
equal(): This checks for the equality between the two objects. This is an object class method that compares keys if they are equal or not. Though, it may be overridden. In case of it being overridden, you can override its hashcode()
hashcode(): This method is also an object class method that returns the respective memory of an integer. Any value which gets received from this method is called as its bucket number that is the respective address of elements inside a map.
Buckets: Node arrays are called buckets. Also, each node in the data structure is like the linked list.
Insert key value pairs in the hashmap
Data structure helps to arrange the new elements by replacing it with the old elements.java offers a variety of ways to choose from the linked lists, queues or maps. Each of them works under different scenarios.
To insert the key value pairs in the hashmap, we will be using the put() method for inserting the keys and values in various pairs in a hashmap. Also, the default size of the hashmap would be 16 [ i.e 0 to 15]
Let’s take an example where we have to insert at least three keys or values in the pair of the hashmap
Hashmap <string, integer> map = new hashmap <> ();
f to insert three
map.put [ Sunny, 19];
map.put [ Akash, 29];
map.put [ Rishi, 39];
Let’s see the index at which the keys or value pairs will get saved. While we can use the ideal method called the put() method, it will calculate the hashcode of sunny. Suppose the respective hash code of sunny is 2657860. In this case, to store all the keys in the memory, we need to calculate its index.
Calculation of index
As index is going to minimise your array, formula to calculate the index will be;
Index = hashcode [ key] [ n – 1]
N here represents the given size of your array. Though the index value for sunny in this case will be:
2657860 & [ 16 -1] = 4
At the value of 4, the keys and values will be stored.
Hash Collision
It will be the case, where the value of a calculated index would be exactly the same for more than two keys. Let’s calculate the code for any other key
Akash. Suppose the hashcode for the key akash is 63281940. In order to store the given key in the given value , you can calculate the index using formula;
63281940 [ 16 – 1 ] = 4
This value 4 will be the index value with the key in the hashmap. Here, the equal() method will be checking as if both the keys will be equal or not. If they are the same, you can replace the new value with the given current value.
Else, you need to connect the nodes with the existing nodes through the given linked list. Both of the keys will get stored at the given index 4.
For the last key “Rishi”, you supposedly have the hash code 2349853. Here, the index is 1. The key gets the value of 1.
get() method
This is a method which is used to get the desired value of the key. Though, it may not fetch a key’s value, if we don’t know about the key. Though, it also calculates the hashcode of your key. When the get[ k key] will be used, it can calculate the given hash code of the respective key.
Steps to followed in this method are;
Step 1 first you need to check if the given key is null or not. If the given key is null, it calls for the getformula key() method.
Step 2 : if the respective key is not null, the hash code in case of that key is calculated.
Step 3 : indexfor()method will be used in order to find the index for the key in a table[] array.
Step 4: after you get the index, it gets iterated through the given linked list at any given position to check for the key in an index. If a key is found, the value associated with it gets returned. Otherwise, the null value will get returned.
Additional learning – Deadlock detection in os
Another essential computer fundamental concept that you should know is Deadlock detection in os. It is a situation where one or no member of any group can proceed or can perform any type of operations because of the deadlock or fault. This may put operations on halt.
Wrapping up
This guide has explained to you about the internal working of hashmaps in java. As the hashmaps form a key concept so questions related to it can be asked. Take this guide as your mentor and fill your knowledge bank.
