HashMap Internal Working in Java: Hashing, Collision & Java 8

[00:00:00]hey what's up everyone and welcome to daily code buffer we just crossed 50 000 subscribers and all thanks to you thank you so much everyone for subscribing to this channel and supporting me along this journey so with your help only we were able to cross this milestone and now let's cross the 100k milestone as well so we are going to have a really good videos coming soon about the different topics so stay tuned for that so if you have not subscribed subscribe to this channel so you won't miss any new videos so in this video we are going to learn about each and everything about hashmap how hashmap works what are the improvements in the hashmap from java 8 and how you can store the data in the hashmap and this is the most common interview questions when you are going for the interview so all the interviewers love this question how you should answer this question that also we are going to see in this video so without wasting any time let's get started [Music] so when the interviewer is asking you a question how hash map works they are particularly looking for these particular things like the first one is how hashing works how hashing is responsible and how hashing is done within the hashmap the other thing is how the collision works so when there is a collision in the hashing how how hash map will handle that particular collision the other thing is how hashcode and equals method play a role in this hash map so these are the basic things interviewer is looking for and the most important thing you can explain with the example is how the put operation works and how the get operation works so once you are able to explain these two operations with all the concepts that i mentioned earlier like hashing collision and how the hash code and equals contract works within the hashmap you will be easily able to explain the answer like how hashmap works in java so let's see that how it works first let me just walk you through the hashmap itself so hashmap is a class in java that implements map interface so in the map interface there are a bunch of methods available and it's a part of collection framework where each and every methods are defined and hashmap is one of the implementation of the map interface there are other classes also available but let's see how hashmap works and what are the different methods and how we can and how internally it stores the data so if you are creating a hash map you can directly create by the class but let's create by the map interface because map is the interface that been implemented by the hashmap so you can see that this map interface takes two generic values that is the k and v that is key and value so whenever you are storing the data in hashmap that will be in the key n value so here let me take the key a string and the value as also string and let me create the map objects employees equals to new hash map you can see that as map is the interface we need to use the class that is the hashmap so here we are using the hashmap okay so this is how you will be creating the hashmap and to put any data to add in data to hashmap what you can do is you can do employees dot put method and here you can see that this put method takes key and value so whatever the key that you need that is suppose i'm taking the key as a subway and value as the employee id suppose one two three four five okay so this is one key and value pair that you are storing in the hash map suppose you want to store any other value employees dot put nickel and the value i'm giving is three four five six seven okay you can see that i am storing two values over here so this is how you will be able to store the values in the hash map now let's understand the concept how hash map internally stores all this value so what we will do is we will directly go to the hashmap class itself and see what are the different things available and accordingly we will see what this particularly or how the particular data has been stored okay so let's go to the hashmap class itself if we scroll up here you can see that this hash map class is implementing map interface okay and you can see that it is also taking key and value that is knv now if you scroll down here here you can see that it has all the default capacity and maximum capacity and everything that's all fine for now but the only thing that i want to show you is here you can see that here it creates the table okay and here you can see that this table is nothing but the array of nodes okay so this is something that internally it creates a structure so as it is creating the table let me just show you the representation like this way it will create the table you can call it as a as it is as you can see that it's an array so it just creates the array where the type of the error is node and node is of type taking key and value whatever you are passing in the hashmap okay this node you can see that it's a class and let's go to this particular class so currently if you see each and every index here that is 0 1 2 right 0 1 2 and by default it will be size of 50 16 so 0 to 15 elements it will be there in the node okay so that's the size of the table that's going to create now within this particular you can see that it's going to store the node okay now let's see what is node so here you can see that node is nothing but a class that implements map dot entry okay as we already know that map stores the data in the entry object where it will be having the key and value pair so this is what it's doing that it is implementing the map dot entry and the name of the class is node which is in fact a linked list okay here you can see that within the class we have properties called hash the key the value and the next node itself so whenever you are creating a node and the other nodes are there the other nodes will be referred by this particular next node itself okay so it's just a linked list that we are going to store in each and every indexes over here so that is just a data structure that is going to store but let's see how it is implementing so let me just uh take the example here here we can see that the key that we have mentioned wash up there right and the value was one two three four five so we are working with this thing right in the particular test class you can see that we were storing shabir as a key and the value was one two three four five now this is something that we want to store so what hash map will do is it will take the key okay and with the help of this key it will try to generate the hash code so so from here from subway it will try to generate the hash code so it will call the hashcode method on shabir okay so the hash code method on shabiri has been called so it will return a unique hash code value that will be integer value okay so you got the integer value of the key itself now with that particular integer value whatever you got from the hash code hashmap will do the hashing on it so hashing is one of the function okay so it will do hashing and what hashing will do is hashing will give you the index where you want to store the data in the entire bucket itself so this is your so this is your key pass shabir from that the hash code is generated from that hash code whatever the integer value is from that integer value hashing is performed and what hashing will return the index where you are storing the data so we have 0 to 15 so hashing function will be doing the module operator with the total size of the bucket itself and it will give the particular value this value will be from 0 to 15 whatever the value it gives it will try to store the data so suppose we got the value 2 okay when we did the hashing on the key shabir so at that particular time what we will do is we will go to this second index and at that particular second index we will store the node object you can see that we are going to create the node object over here right so this is the node object is going to be created where it will be having the hash key value and the next object so the object is created of the node and that particular node value is been stored over here cool right so you can see that the whatever the value that we passed up there and the value that has been stored over here now suppose we are entering the another value okay at that particular time that particular key is different where you got the hash code from that particular key and from that hash code you got the hashing as well and suppose your index is four so at that particular time you you went and created the object of the node and stored in the fourth particular index itself so now you got the third object so third object is let me just create one more thing and suppose the third object is again uh nikhil right as you mentioned nikhil and suppose three four five six seven is the key okay now what happens is suppose for this particular for this particular key and value pair for nikhil we generated the hash code from that hash code we generated the hashing as well and the hashing value we got is two okay so at this second position we had already stored this shabir and one two three four five a node is already available right so that's the collision because at the same particular bucket location that is the index two the the node is already there so we got the another key value pair also which we want to store at that particular location so that's the collision because one node is already available so that's the collision and how the collision has been handled is it will always so when when it tries to store the value at that particular index at that particular index that is index 2 it will check that what is the value of a node is the value of the node is null if null that means there is nothing stored already that means you can directly go ahead and store the node but if it's not null that means any node object is already been there okay so at that time collision happens the equals methods comes into picture to do the equality check so at that particular time it will check the key of the particular object that we are going to store that nickel is this key equals to the key stored in the node or not okay if so okay if that's the case then what it will do is it will replace the value of it okay otherwise it will go until you find the null object so suppose you have two objects available over here at this particular value okay so it will go until the next nodes until you find the null object and once you find the null this particular object this particular object will be attached at the end of the linked list okay so currently you have only one node object and at this particular time it will check okay is nickel equal to shabbir no then go to the next node okay the next node is null right so we found the null and at that particular point this particular object is attached at that point and the short bear will be referring to the next object that is nickel so at that particular time you can see that we will be having two objects first shabir and then the next will be nikhil after that okay so yeah there are two object here there is one object available and this way it will try to store all the objects and whenever and whenever there is a collision it will try to do the quality check based on the key and whenever the key is same it will update the value so suppose if i'm again trying to store the sub with new value okay six seven eight nine zero at that particular time this shabeer key will also return the same hash code value right because that's the contract with the hash code if two values are same two objects are same the code will be also same so for this sharp bear and this shabby the hash code would be same and when the hash code would be same the hashing operate operation will also return into the same index so it will go to two at that particular point we will check the quality with equals method that this key is equal to the key that is stored in this bucket or not and whenever we found the equals key what we will do is we will update the values for that key okay so that's how whenever we try to add multiple data with the same key it will always override and whenever we are trying to add the new keys it will append the keys at the end of the node or when there is a new index available it will try to add into new index okay that's how generally it will work now what if you pass null as a key suppose instead of shabir you're passing null as a key and a value also suppose null okay at that time what will happen you won't be able to get the hash code of a null right and you won't be able to get the hashing also for the null value so for that scenarios what happens is by default there's a special scenario where whenever there is a null key available the index of that null key would be zero so whenever you are going to store the null value it will go to the zeroth index itself okay so that's a special scenario you can mention in the interview so that's how it will try to store all the objects now suppose you are inserting a lot of data in the hash map right and at that particular time whatever the hash code that you are generating and from that hash code whatever the hashing that you are generating it is ending up in the same bucket itself okay suppose if you are using 10 or 20 records and all those records are ending up in the second index so what will happen is for each and every entry that you are going to store it will end up in the collision and whenever there is a collision what it has to do is it has to traverse to the entire linked list okay so whenever it has to traverse to the entire linked list so whatever the nodes available within the linked list suppose there are eight or ten nodes already available so i thought eight or ten entries you have already inserted in the linked list and you are inserting again so a particular node has to traverse all those elements and need to add the new node at the end of the linked list so you can see that the time complexity to insert the data is getting increasing in the amount the data is also increasing okay so if your thousand records or a few thousand nodes available what will happen is uh you need to traverse thousand nodes to insert a new node if it's in the same bucket itself okay so that's how generally it will work so that's not the optimal solution right so the time complexity for that would be o of n so whatever the number of nodes you have to traverse each and everything so for that reason from java 8 there was the improvement done in the hashmap where whenever the amount of nodes in the one particular index is at the threshold of 8 so suppose whenever you are inserting nodes one by one whenever there's a collision and the amount of nodes reach eight value so you're going to add the nodes one by one and the moment it reaches the eighth node internally it will create that linked list into the balance tree okay so rather than having the entire linked list what it will do is it will have the balance tree where the values will be stored in the tree so let me just add all this value so it will create a tree so just understand these are just objects where it will create the tree okay one object then it will have childs then this also will be having another another child's this object will also having another child accordingly so it will create the balance tree and that balance tree will help to search insert and delete the records effectively so once the balance tree has been done the time complexity of the algorithm will change from big o of n to big o of log n okay which is very less than the big o of n so that's that's how the internal working will be from converting the linked list to the balanced tree and now once the balance is done you are inserting the elements and everything and at particular time you are removing the elements also so whenever there is a balanced tree created and when and from that balance tree you are removing the elements and at that particular point if your if your node count is at the threshold of 6 so the 8 was the count when it will convert to the tree but when your count reaches back to 6 it will again convert from 3 to the linked list so you have almost 10 10 or 20 elements over here in the tree and you are removing the data and and at that particular moment if your count reaches six nodes then it will convert your tree into the linked list back again so that's how internally it will handle and to optimize the performance of the hashmap so you need to make sure that you tell this information to the interviewer so once you explain all these scenarios interviewer will understand you have a deep working knowledge of the hashmap so this is how the put operation works in the hashmap and this is how the hashing works collision happens and what are the improvements as well if you come back now the next operation generally is the cat operation if you will be doing employees dot get operation and here you will be passing the key itself suppose i'm passing shabbir so what it will do is it will try to return me the value of the key that i am passing now for this get operation also it will do the same operation i am just passing the key sub area for that sub key it will call the hash code so hash code will return any of the particular integer value for that integer value the hashing operation will perform on the key and after the hashing operation the hashing will return any of the index so suppose it return the index 2 so it just now returning the index now at this particular point we have to do the equality check of the key so at this particular point we will check the key that we got that is the the key that we pass at the subway if that is equals to the key already stored or not if that is so then we can return the value if not then we can go to the next node available and we can go to the next node we will check again if the key that we pass is equal to the key that we store in the node or not if so if it's equal then return that value otherwise go to the next node until all the nodes are completed by the end of the cycle by the end of all the nodes that you have traversed if you didn't find any of the keys and the last node is null at the time you can directly return null that we did not find any key that is with the value this so the value of this key would be also null okay so that's how the get operation will also work where it will also do the hash code operation on the key then from that hash code the hashing will be performed that hashing will result into the index and with that index going to that index it will do the equality check using the equals method for each and every key that has been stored with the key that you have passed so whatever the keys that will be matched accordingly the data will be passed on back so this is how the hashmap will work and this is how you should answer the put operation get operation hashing collision and the hash code and equals contract and also the improvements done in the hashmap from java 8. so this was all about the hashmap in java and how you should answer this question in your interview so if you have any doubts regarding any of the things that we have covered then do let me know in the comment section below i will try to help you out as soon as possible if you are enjoying this content then do like this video and subscribe to this channel for upcoming awesome videos i will see you in the next video till then happy coding bye