Hi everyone, welcome to Java Techie. If you attend any interview as a Java developer, then you must face this question, how HashMap internally works in Java. If you attend 10 interview, then most probably you will get this question 8 times. Because this is one of the most favorite interview question for Java developer, right.
So in this tutorial, I will walk you through internal flow of HashMap with an example. So without any further delay, let's get started. To explain this question what I can do I created one animation which will help you to understand this has map internal flow ok now let's say I created one map object ok When we created a hash map object internally it create a bucket structure like this.
Since initial capacity of map is 16 initially it will create 16 buckets. So if you observe here 0 1 2 3 4 5 up to 15 index begin from 0 and it end with 15 right. So it created 16 buckets.
Each bucket internally uses a linked list. So in this 15 bucket, bucket 0 1 And every bucket is considered as a linked list. And this linked list contains one node.
Now if you observe see the internal structure of node it contains key value has and next. So it means each bucket can be considered as a linked list and each linked list or each bucket can have n number of node. So on that node structure will be key value has and next.
next fine we created map object now let's create few employee object to store in map so i created here four employee object now when i put map.put e1 and then some string value e1 is nothing my employee one object now how your hasmap will identify this entry where you need to keep this entry between this 0 to 15 right so what hasmap internally do When we internally call this put method inside the put method there is a method called hash. Okay it will take the argument is your key my key is nothing employee one object. So it will pass this hash function and it will evaluate some hash value and then based on the modular operator it will identify the index.
For example let's assume this first entry it evaluate index 6. Now simply this entry or this node will go and store in bucket 6 my bucket 6 is nothing a linked list and it store one node as i mentioned above the high level diagram this node contains key which is nothing the e1 and value is nothing my dev then some hash value and if you observe the last bucket or the last entry is null because there is no more element in this bucket so there is no pointer so that's the reason it is null okay Now similarly let's assume I am trying to add my second object. Okay. And again it come to the put method and it evaluate the hash then it evaluate the index.
Let's assume it evaluate the index as 9. Now simply this node will go and store in my bucket 9. So if you observe again it store key value hash then next reference which is null because there is no element in this bucket. Okay. Now third time let me try to add this E3. Okay.
with some different string again it come to the put method and evaluate the hash then it find the index coincidentally let's assume that it find the same index which is 6 now if you will go and check in 6 there is already one node now in the same entry or in the same linked list if you will find multiple node or you can say if in a same bucket if you will find multiple node then that concept is called hashing collision okay so in that hashing collision directly my map will not add this entry to the bucket number which is evaluated by this index right which is six so what it will internally do since both having the same hash so it placed on the same bucket immediately map go and check the equals method to check the content wise both are different or same so it will go and check e2 dot equals e3 okay because already sorry this should be e1 because e1 is already there in bucket right e1 equals e3 if it find different then immediately it will store that entry to the same bucket which is nothing the six and now this will not be null this will be the next reference it means in the bucket six there will be two node this one is the e1 is the first node and e3 is the next node so that's the reason e1 next point to the second node okay so this is placed in six only i don't have space so i added it down so don't consider this placed in seven bucket okay So it means if in a same bucket there is multiple node then this condition is called hashing collision to avoid that hashing collision map internally use double equal operator to check the reference if both are same reference or different reference if it found same reference it will just replaced if it found a different reference then immediately it will go and check the content okay so content between e1 and e3 okay e1 equals to e3 if it is true then again it will replace if it found different then it will just add as a next node right to the first node okay now we have one more element which is e4 right so i am trying to add this map.put this entry okay again it come to the put method it will evaluate the hash it will find the index let's assume it find the index 7 okay then that node directly go to the 7 bucket okay now interviewer immediately ask you let's say i pass the key as a null okay in map i passed key as a null value as a null then where it will place because we cannot evaluate the hash or index based on null right the straightforward answer for this tricky question directly you can say if key is null then that entry will be placed in the zero bucket okay that is fixed if there is null key then that entry will be placed in the zero bucket so this is how hashmap internally works so you know you need to understand this high level link list node what it contains then with this diagrammatic way you can answer to the interviewer so that there will be no further question in hashmap okay now the next question from the interviewer you can expect if you mention java 8 then he can immediately ask you what is the enhancement done in hashmap in java 8 okay so to answer to that you can specify Initially, this hash map each bucket is used as a linked list. But on certain threshold, it will convert it to the balanced tree mechanism. That will not be linked list.
In Java 8, they used balanced tree instead of linked list but in some certain threshold. Let's say there is a hashing collision. In the same bucket, they found 5 nodes. Then immediately, that link list will convert it to the balance tree and then it will maintain the balance between the node okay i am not very sure about the internal implementation of this balance tree you just have a look on the google you will find but at high level they implemented something called balance tree if there is a some threshold initially it will use link list only but after after certain threshold it will convert it to the balance tree okay now at high level if you want to see the flow of this hash map i found this image from the google so it's not very clear but you can understand the flow so initially you added key value to the map then it find hash code of the key okay based on that hash function it will evaluate the index and it will placed it if it there is a hashing collision means if a node is placed on the same bucket where already one bucket one node exists if there is hashing collision If there is no hashing collision then simply add to linked list as first node. Okay, if there is a hashing collision then go and check the equals with the existing key.
If both are same just replaced or overwrite if both are different then add it. That's what we understand right. This is where we have the hashing collision E1 and E3 and it check E1 dot equals E3. So this diagram makes sense right.
That's All about this particular video guys. Thanks for watching this video. Meet you soon with a new concept.