How HashMap works internally || Popular java interview question on collection (HashMap)

hi in this tutorial I'm going to talk about how the hash map works internally so this is a very popular in to be a person and been asked many times in many of the interviews so so well in this tutorial actually we're going to have a brief idea how the things works so here I'm going to use my white board so that I can draw some diagrams and can represent the thing in a little bit simpler way and once you get the overall idea over here then I'll I will use my Eclipse IDE where I'll give up the things and I'll show you the things up in a very practical way all right so let's get started and let's start going okay so now let's create a very simple map LS insert few banished to our map okay so now my map okay so now here I'm creating a very simple map here okay and here I'm packing string as a key Celtic string and tell you for very long I'm going to take integer right okay here we go so III assume that you already know how a map works ok so string is my key and using the key I can look up a belly right okay so here I'm taking the reference s map and I'll write a cure to new hash map so hash map is actually implementation of map interface right I assume you guys already have knowledge in it okay so new hash map all right ok so here I'll take the time and bracket and construct it over here so I'm not specifying anything inside the diamond bracket so if I'm not specify anything it's going to take the same as this okay so no confusion with that okay so whenever I write this line and I insert few values to my map what is going to be happen internally right so what will happen over here it is going to create an array of buckets okay so here I'm going to draw some pockets here okay so buckets means this like this okay it is going to create fewer array of buckets okay now this is very important that what are the size of buckets okay so the size will be 16 okay so there is 16 number of buckets is going to be created over here so let's do it over here very quickly so 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 and 16 so now you know that the array index starts from 0 right so it starts from 0 here so this is my turret index so 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 and 15 so judo 2qp at the 16 in size right so very simple I'm creating my map so internally an array of buckets is going to be created ok so now let's go a little ahead okay so is buckets here is called end node so is bucket here remember it's called it Noir okay and what is it node node means whenever I said no over here just think that it's a linked list okay so each pocket' is an or or his bucket is a linked list here okay so I think this point is clear right I'm writing this line an array of buckets is going to be created the size will be 16 and each bucket is an or or is a linked list okay very simple very straightforward so now what I'm going to do over here I'm going to insert few values to my map okay so let's insert few values over here so how do insert a value to a particular map to insert a to make some entries to the map table I'm going to use a map dot foot okay so map is my reference here what is the method right and okay so the key over here I'm taking here string right so let's say my key is ABC and the value is less than 1 okay so now we have already inserted a particular value to our map table okay so now let's see what happens into number right so you're using this foot method right so let me write this put method over here just assume that this is your foot matter and your put method is Kinki and is also taking a bend right so right bill you here and be okay so you put method actually does a lot of thing a lot up stops right so I'm not going to talk about everything it does over here okay so let's focus on the point that we are talking about right over here okay so you put matter what it does first it calculate the hash okay the hash of the key okay so why this calculating the hash okay that we are going to learn within few minutes chip so first it is going to calculate the hash of the key what is a key over here a key will be ABC right for ABC it is going to calculate the hash of it okay so what I mean by that is by using this stuff we are going to calculate the hash code okay we're going to calculate the hash code for the key so why we need the Hosko okay what is the need of a score over here and why we're talking the husk or okay because uh because the ha score will help us to store the key in a specific index okay and huskar will also help us while we are defining the key or we're tracking the value from a particular key Hospital make it really faster for the tribal right so that's why we are using hash code so right now let's calculate the hash code for a specific key okay so right now we're we're putting over here our our keys ABC okay so now let's say this ABC comes here let me remove this key and put this ABC here now for for ABC the hospital will be calculated right so now let's say the house code comes something like this 1 1 1 1 1 1 and 2 okay so this is generally an integer right so Hospital give you an integer right so okay so now as I said the hash code will help us to for or to put this particular key inside a specific bucket isn't it so right now the state we have only uh pairs available up to 15 the last bucket we which is available over here of 15 right I said the bucket size is 16 right so 0 to 15 is 16 but this one is very bigger value isn't it so right now this key need to be stored in a specific index which is 101 and 1/2 but wait there is a problem right we have only podcast available up to 50 now how this is going to be possible yes technically I mean purity girl you can create an array I mean such a big array for of this particular index and can store this particular key in that particular index but think practical is not possible because if I have several put operation over here and I do have several elements or several entity in my map and for each map I mean for each and during the map if you are going to create such big arrays then soon you are going to run out of the memory and it relates to our some several performance issue right so theoretically yes it is possible you can create such big arrests but technically it is not possible so what need to be done over here so for that modular oppressor need to be done okay okay so hum did that that thing will be done just like this right so they are calculating the hash and they are doing some ending the operation over here and there using n minus one and this thing is going to return you in next okay so what the thing I've written over here don't worry about it okay well we are going to talk about it in a much detail way in the following tutorials but here the important thing that you need to understand that it is going to return you an index okay and what this index is this index is one from these pockets okay you are going to get an index number okay so what we did over here we just put our key over here we have calculated at the high score right now the half score is further computed okay through this modular operation and we are going to get a index of it okay let's say we are going to get the index for from here okay so now this key ABC that you are entering over here this key ABC is called goes to this fourth index so what is important next so this is a foreignness right so here a link list will be created I told you each bucket is in Noi isn't it so note means a linked list okay I told you not mention linked list okay so a linked list should be created over here and this key value and this hospital firm ation is going to be stored inside this linked list okay so now let's explore it a bit more so okay so I told you these buckets are called nodes right so our linked list you can set okay so I have a tent over here so what this node is going to store inside it okay so this node or this linked list is going to store few informations inside it okay there are basically four information that it is going to store inside it okay and what are they first it is going to store the key okay and it's going to store at the high score okay it is going to store it or value and it is also going to store the next okay so if you don't understand what is this next delaurio cam but I'm just coming back to this particular point okay so now this thing howling clicks how a linked list loop likes okay so a limp list looks like something like this isn't it it will have some indexes and isn't it it looks like this and this last one is going to hold the address of the next node isn't it and similarly there will be a linked list available after this node and after this node okay so this is how a typical linked list looks like it will contain some values and the last index of this particular node is going to store the address of the next node okay so this is how the thing so now let me remove it and let stores our available information that we get from here over here okay so now this next is actually like that I explained over here this next is going to store the address of the next node if it is available okay so we'll be exploring it more you know as we progress in this tutorial okay so so now what we'll do where will you store every information which is present over here we're going to store it over here inside the fourth fourth index or fourth bucket because here for this particular key we already got the index number is four okay so now let's stores the information inside it okay first let's do on the high school so what is your high score our house code is people one two one two okay so let me make it over here three people 13.1 - okay so our high score get an entry right so now let's turn AutoKey our key is ABC okay and the value is one okay and then I understood this next okay so what is the next number here not this thing okay is there any other link to is present over here no there is no only simple expression over here so let's make it in all for now okay so this is how and typical entry works internally when you are talking about in hashmap I mean talking about a hashmap okay so now let's have some more entry over here and let's see how it happens okay so now let's say I'm having another entry over here a map dot put and I'm going to put unless they're a a okay so this is a string and my value is 2 now what is going to be happen now again this is my key right a a so the one the put method will be two over here this is going to calculate the hash I'm in the hash code for the key over here so what is my key a so it is going to calculate the hash code for this particular key so let's say it is going to get some value like 2 2 2 1 1 1 and 2 okay so this is the huh scope now this has 4 is further computed all right and it is going to return you the index number okay let's say the index number is returns is 7 okay so now this particular key goes into the seventh bucket all right okay so now let's see and they say a linked list will be created okay and it'll store the hash board the key the value and the next know what is the national right okay so what is my house forever here my for H 2 2 2 1 1 1 2 ok so let's make entry over here 2 2 2 1 1 1 & 2 alright and what is my key over here my keys a a ok so here it goes being a pig all right and what is my tell you my value is 2 so here it goes the value is 2 and is there any other place present over here no so this one will be no all right very simple very straightforward so right now whenever I'm I'll just have a put operation over here the hospital will be calculated then the index should be computed and the index number is going to be the pocket number that the entry goes to ok like that it will be it will put try to create every linked list over here and the value will be stored inside this particular buckets but wait what happens when there will be a hoss collision ok this is a very important thing to understand ok so now let's assume that I have an another put operation as they're not put and Here I am putting let's say let's say a a B ok so my key is a a B right and my value is let's say my value is 3 now what is going to be happen now this assume that this a B and a B C ok this both is going to return you the same hashcode just assume it right I really don't know technically it is going to give you the same hash for not probably not but assuming that this both key is going to be literally the same hashcode okay and we'll see you know how the things work after that so just see over here Mikey's a B so let's say I am replacing here a B and just think that the husk or that this particular kilotons is same as this particular key a ok so there's this thing that the hospitals is 2 2 2 1 1 1 and 2 and then again the further the index is computed and the index that we get from here is 7 now to see then there is already an entry inside the seventh index I'm sorry I made it 6 ok let's make it 6 sorry about it so let's say this goes into the sixth index okay all right so now just just think that inside the sixth index already and Lin please present okay with the same high score now when it is going to make an entry over here it found that is already a linked list present here isn't it so now what will be happen now that is an another linked list will be created right over here alright and it will store the high score the key the value and the pointer to the next node okay all right so not just thing how the things will happen okay so my high score is 10 2 2 2 1 1 1 and 2 so it will be 2 2 2 1 1 1 and 2 all right and now what is my value I mean what is my ki AAP so my key goes here a a B what is my value my value is 3 right so this is 3 okay and what is is there any other little is present after there no so it will be not for now let's say this is not right now I just think this this will not be enough because there is already a linked list present right after this particular linked list isn't it so this is going to point to this particular linked list all right so this is how happens I mean how the things will happen when there will be a hash collision so as you can see this poor things are returning the same house code returning the same index number and then I mean and that's how the things works up with that ok so another linked list will be created and it will store all the things all the four things over here and this one this index is going to point to the next linked list this will store the address of the next linked list we'll see how the things work while we are going to debug it okay so this is how people put a piston in hash mark works internally ok so now what we are going to do over here I will take you to my Eclipse and we're going to debug it and we'll see whatever the things that we have discussed for last 10 minutes which is a that's just actually working in a similar way or not okay so let's go for that and right over there I'm going to tell you how to get a present work in a typical hashmap okay so let's first debug the things and let's have a clarification and then let's have some better clarity on it all right so let's go for it okay but wait you know I just wanted you to tell one more thing okay it's very important interview point of view so what happens whenever you are adding a key with null values and you know in in in map we can enter knowledge a key right so if you're putting like let's say what happened to my marker map don't put and you are putting the knowledge the key and the value is for now which bucket this goes into right so this is another very selfish question of blood of interviewers right so don't be confused about it okay so whenever you see the key is null make sure it is goes into the unit's pocket so a linked list will be created over here and this particular I mean this particular particularly if null boils into the 0th index okay or 0th bucket so they are inside your map method they have few lines of code which will which will do that particular work okay you don't need to be worried about it you just remember what about the key is null crisco's it to the zeros bucket all right okay so that's it so now let's go ahead and let's devote it [Music]

Channel: Selenium Express

Views: 471,912

Keywords: hashmap in java, how hashmap works internally, how hashmap works internally in java hashmap in java with example, how hashmap works internally in java with example, how hashmap works internally in java 8, hashmap internal working in java, hashmap interview questions, java collections interview questions, java interview questions and answers, how hashmap works internally in java with diagram, java interview questions and answers for experienced, selenium express, collection, hashmap

Id: CojCE-ojdGY

Length: 19min 39sec (1179 seconds)

Published: Sat Jan 27 2018