Internal Working and implementation of hashmap and hashset | Java Interview Questions | Code Decode
ฝัง
- เผยแพร่เมื่อ 5 ก.ย. 2024
- In this video of Java Interview Question and Answer series we have explained internal working of hashmap and hashset which is important question in Java interview questions and answers series
Udemy Course of Code Decode on Microservice k8s AWS CICD link:
openinapp.co/u...
Course Description Video :
yt.openinapp.c...
Relevel link : relvl.co/nqj4
We need to cover 3 min points in High level for this question:
It works on the principle of hashing
How Put Method works Internal working
How Get method Works internally
Hash Map internally works on the principle of Hashing.
Hashing means using some function or algorithm to map object data to some integer value, hashCode() method return you that hash code. Hence Its necessary to write hashCode() method properly for better performance of HashMap.
If you override hashCode() method, it’s necessary to fulfill Equals and Hashcode Contract.
MAP is an object that maps keys to values”
So, there must be some mechanism in HashMap to store this key-value pair.
Everything in Hashmap is stored in a bucket internally (of hash table - underling DS)
Firstly hash value is calculated using the key’s hash code by calling its hashCode() method. This hash value is used to calculate the index in the array for storing Entry object. JDK designers well assumed that there might be some poorly written hashCode() functions that can return very high or low hash code value. To solve this issue, they introduced another hash() function and passed the object’s hash code to this hash() function to bring hash value in the range of array index size.
With Hash Code in place , we put the newly created Entry object K,V in the bucket of Hash Table.
So, in case of collision, Entry objects are stored in linked list form. When an Entry object needs to be stored in particular index, HashMap checks whether there is already an entry?? If there is no entry already present, the entry object is stored in this location.
If there is already an object sitting on calculated index, its next attribute is checked. If it is null, and current entry object becomes next node in linkedlist. If next variable is not null, procedure is followed until next is evaluated as null.
What if we add the another value object with same key as entered before. Logically, it should replace the old value. How it is done? Well, after determining the index position of Entry object, while iterating over linkedist on calculated index, HashMap calls equals method on key object for each entry object.
All these entry objects in linkedlist will have similar hashcode but equals() method will test for true equality. If key.equals(k) will be true then both keys are treated as same key object. This will cause the replacing of value object inside entry object only.
We know that two unequal objects can have the same hash code value. This is a case of collision.
Hash collisions have negative impact on the lookup time of HashMap. When multiple keys end up in the same bucket, then values along with their keys used to be placed in a linked list. In case of retrieval, linked list has to be traversed to get the entry. In worst case scenario, when all keys are mapped to the same bucket, the lookup time of HashMap increases from O(1) to O(n).
Java 8 has come with the following improvements/changes of HashMap objects in case of high collisions.
The alternative String hash function added in Java 7 has been removed.
Buckets containing a large number of colliding keys will store their entries in a balanced tree instead of a linked list after certain threshold is reached.
Most Asked Core Java Interview Questions and Answers : • Core Java frequently a...
Advance Java Interview Questions and Answers : • Advance Java Interview...
Java 8 Interview Questions and Answers : • Java 8 Interview Quest...
Hibernate Interview Questions and Answers : • Hibernate Interview Qu...
Spring Boot Interview Questions and Answers : • Advance Java Interview...
Angular Playlist : • Angular Course Introdu...
GIT : • GIT
-------------------------------------------------------------------------------------------------------------------------------------
Subscriber and Follow Code Decode
Subscriber Code Decode : www.youtube.co...
Linkedin : / codedecodeyoutube
Instagram : / codedecode25
--------------------------------------------------------------------------------------------------------------------------------------
#internalworkinghashmap #javainterviewquestions #codedecode
Really liked the idea of explaining through slides also.
And thanks for explaining the functionality for Java 7 and Java 8 separately; insightful indeed.
Thanks Rahul 🙂👍
Thank you so much @code decode guys for your support. I cleared multiple interviews with your valuable videos. Hats off
thanks and all best Vijay for your future
The Best Video to understand Internal working of HashMap. Thanks a lot ❤
This channel is underrated! Great work.
Thanks for nice words
Hi Mam, All you videos are excellent and very helpful to clear interviews. Your are doing this video at 1 AM... Hatsoff to your dedication
Thanks a lot 🙂🙂. Yeah that's when we get spare time after office ends 😃. We all are working IT professionals. Btw nice observation 👏👏
Thank you for taking us through the source code of these classes. I used to be afraid of checking such files. But this is how we get to learn good coding practice also.
Very true Shekhar. Very glad to see u are going through them. 👏👏👏
Best video I've ever seen about HashMap's working!
Thanks Shreyash 🙂🙂
I was searching for this type of video for a long time.
This video is very informative and helped me better understand the concepts.
Thanks for sharing such insightful content.
Thanks 🙏🙏👍
Hi Mam! You are helping us a lot. Please keep teaching like this And also if possible please make a complete session on Collections frame work end to end. There are many tutorials on youtube, but nobody can teach us the way you do. I found your tutorials very helpful and easiest way to understand.
Sure Sai. Thanks a ton for the nice words. We do have videos on collection framwork. Can u plz tell what all topics u need apart from what are uploaded.
@@CodeDecode Linked List, Stack, Vector, HashSet Vs LinkedHashSet Vs TreeSet..Thanks in Advance..
You delivered a nice explanation. It was needed for interview because it is important. I found this video and it helped me out. Thanks.
Thanks Devanshu 🙂👍
Excellent explanation of internals of hashmap as well as hasheet with proper proof
Thanks Arun 🙂👍
@@CodeDecodeone video for arrayList internals
nice explaination
😊
Simple and accurate explaination - good job
thanks
Thankyou so much dear❤ your videos are good to go for interview topics.. crisp and perfect .. Interviewer bhi khush hojaye😂
Haha Thanks a lot Akanksha🙂🙂 and we will be happy when u land at awesome job Girl ❤❤. Keep learning keep rocking girl 🎊🎊👍👍👍👍🎂
Thanks Mam for such à deep knowledge. God Bless you. Keep posting 🎉
Have been checking all your videos..Inspiring work and content!!!
Thanks a ton Divya 🙂
Too good of explanation :) thanks lot - great work - keep going
Thanks Raghu 👍🙂
Wonderful video explaining exactly what changed with Java8. Can you please create one for ConcurrentHashMap as well
Thanks 🙂Sure Aniket 🙂👍
Thanks, Your channel is very helpful...
Thanks a ton Gaurav. It means a lot 👍🙂🙂👍
13:32 “while converting the list to binary hashcode is used as branching variable” - couldn’t get this part as hashcode is same then they are getting converted to linked list and then equals method is being used to add the values in the linked list. So the question is if it has reached a certain threshold and then how different values of hashcode can come to get converted into tree?
you r an amazing teacher..
Thanks 🙂
Very good Explanation.
Thanks Vinay 🙂👍
Thankyou for the video mam
You're welcome sreeja
Nice explanation.. Great help .. thanks
Thanks Abhishek 🙂👍
Hi
I have one doubt
In bucket, all elements with same hascode only?
Is it possible, different hashcodes in same bucket as you mentioned in video@13:59?
I guess it should be when 2 keys that are different but having same hashcode?
Just a feedback - There is too much of juggling btw screens...
Understood. We will try to reduce it. 👍👍
Great explanation Mam.
Thanks 🙂👍
Thank you very much.. Could you please do if possible tree set and tree map
Nice topic. Sure we will do that
After finding such great videos, I am feeling blessed :D Thanks a lot !
This is pure Quality Content !!
Thanks a lot Akash 🙂👍
Awesome Explanation
Thanks Krishna 🙂👍
Ur videos are too good to prepare for interview. I have a question here. Whe linked list is converted into binary tree then which hash code is used to determine the left or right node? As per my understanding hash code of all keys is same because of which collision is happening so now which hash code to use for node calculation?
Awesome explanation
thanks
excellent explanation
Thanks 🙂🙂
Thanks! Could you please do a video of executor service future get and completablefuture from java
how to handle if anyone executor service tasks takes too long
Nice topics Rajya, we will surely put video on these
The content is really great, explaining everything in details which makes the internal working of HashMap and HashSet very clear. However, I have one question. Do we need this understanding for programming in real projects as generally we need to use HashMaps and HashSets to store and retrieve collection data and can also iterate using iterators, or is this just for interview purpose ?
nice explanation keep it up we will support you and my request to you please make a video on time complexity and space complexity
Yeah that's s tough one to understand. We will create video on that soon 👍👍
@@CodeDecode thanks pl create on that topic
Really liked the explanation can you please create a telegram channel so that we can have communication and polling advantage and discuss our doubts
still usefull video
😊
Nice explanation
Thanks 👍
Next Level
Thanks Vaibhav 🙂🙂👍👍
I have a doubt if anyone could help. Since all entries within a bucket index have the same hash code (due to being placed in the same bucket), how can the hash code determine an Entry object's placement to left or right. Instead, the Comparable interface or custom comparator only will be used to maintain the ordering within the binary tree. Am I getting it right? Since not the whole bucket is changed to a Binary tree, only a particular bucket index is!
@shashwatidash8524 as per my understanding, the first element(for particular bucket) which you will be adding , will be acting as root node of that tree.
Thanks for sharing!
🙂👍
neatly explained what changed with Java8
Thanks
Please continue all data structures (linear,non linear in graphs, hash table)
Sure 🙂👍
Great mam...
Thanks 👍🙂
Mam, please make a video on multi threading concepts..with basic and advanced ..
th-cam.com/play/PLyHJZXNdCXsdUXzeeBZIADof_U-40jBJO.html
Keep up the good work!
Thanks Maarten 🙂👍
14:29 how can we have different hash values if there is hash collision, it's bit confusing there 😮
How can we use hashcode to compare elements while adding to the binary tree. Unless the hashcode was the same we wouldn't push in the same bucket. Right.?
Dose Linked List in the bucket (specific index calculated after hashing) is going to convert to tree or is it the complete bucket is getting converted into tree
a) if it is linked list at specific bucket index then how the hashcode less or greater then calculation will happen as per me at that point hashcode would be same for both element isn't it?
b) if the complete bucket is getting converted into tree then why we are saying linked list will get convert to tree...if i heard right!
🤔🤔🤔 Please help me understand the concept
Thank you!
🙂👍
If same hashcode is there then what will happen in binary tree fornat how key can be comparable will you give example, it's confusing for me
can you plz explain about memory allocation enhancement in 1.8 feature.
How will it work if the value is a list
Map m = new hashmap();
At 14:12 you mentioned that in tree the main comparison will be on the basis of hashcode, But in a bucket when there are several entries and all of them have same hashCode then how are we comparing on the basis of hashCode.
I hope to be that fortunate winner...
Plz Like✓ SHARE✓ SUBSCRIBE✓
Maam, most of the comment section has the doubt of collision at 14:29 please explain the doubt, it is really confusing
👌👌👏👏👏🙏
traversing linked list and tree logn and O(n) then how hashmap complexity isO(1) ?
It's said best case complexity o(1) worst case o(logn)
do you have link for all the presentation slides that we can access? It will be really helpful to go through it as a revision before interview.
14:29 im having doubt on why there will be different hashcodes in same bucket??
Yea.. same doubt. Linked list gets created when there is hash collision then how can be there different hash code values
Hi Mam,
I have a doubt in the put() method of hashmap..
If the hashCode of few keys are same means all those will be stored inside same bucket in linked list format (if threshold is increased by 8 means it converts to balanced tree)
* Right branch will be higher value of hashCode and left will be lower than that..
My Doubt is all the variables present in same bucket will have same hashCode.. Then how they will be compared while storing in balanced tree?
I also have the same doubt. How different hashcode can be present in same bucket because different objects will land on same bucket only when hashcode for them is same.
Thanks but do you have video of say passing hashmap as parameter etc
What do u need? M unable to understand the requirement. Can you plz elaborate?
@@CodeDecode I was looking for below found it ,in future can you show some examples like say taking hashmap as parameter, taking hashmap returning list etc, no need for video you can post in github that would help, for you these might seem very simple and common task but for starters this would help a lot,thanks again for all your videos. // returning hashmap
public HashMap asHashMap( K[] keys,V[] values ) {
HashMap result = new HashMap();
if (keys == null || values == null || keys.length != values.length )
throw new IllegalArgumentException();
for (int i =0; i
@@CodeDecode I had just given a suggestion,otherwise learnt a lot from your video series 👍
Do you have any java course from beginner level to advanced in Core to Advanced java
Very good explanation, but I have a doubt: while explaining handling collisions in java8 nd above, u mentioned that if the hash code is same in a bucket, then we go with comparing keys , but collision is caused because of same code na, my doubt is all the entries in a bucket will having same hashcode ryt that is how they are placed in a bucket , keys may be different but hascode remains same based on hashcode only we are choosing the bucket na, please clear my doubt.
All entries in a bucket may not have same hash value though they will have same index. Remember we first calculated hashcode which again converted to some hash value. This hash value is then mapped to some index. And this is the point where two different hash values may result in same index. So while doing get operation first hash values are equated and then keys are equated.
@@CodeWithCB sry what do u mean by hash code and hash value both are same ryt , for a given key we will find hashcode , what is hash value. I didn't get u, please elaborate
@@shivachanda2438 internal implementation of Hashmap frist calculates hashcode of key as per hashcode() given for key object. Then internally it converts this hashcode to hashvalue h using formula (h = key.hashCode()) ^ (h >>> 16) . This is done to spread keys across the array causing less collisions. And this hashvalue is used further to find actual index using formula index = (n - 1) & hash.
From where do you learn Java ? I also want to read from there.
Mostly docs helps us a lot in understanding the concepts
14:29 in second point how come is this possible that in one bucket will have keys with different hashcode as we assigned bucket on basis of hashcode itself. I guess binary search tree is based upon keys.
I'm also having the same doubt. The hashcode enters the bucket only if it is same and the keys are used to compare amongst the elements in that bucket. Im confused here..please explain here....
Hashmap concept was awesome.. Hashset is not much clear.
How can we help Malai? What is unclear can u plz tell us so that we can clarify that to u?
Mam i went through the video again now it's clear. Thanks
Awesome Malai 🙂👍
1:27 Explain slowly
Hi what will happen if we have overriden equals method but it always returns true.
Just do it in eclipse, if equal returns true every time then i think hashmap will store only 1 key if same has code come
please share the document of this class
Which document are you asking for Lakshmaiah?
Explanation fine but i am unable to catch that flow. Listened more than 3times. Little bit confusion. Could you please explain in less technical way. Atleast one simple example
Sure we will do that👍👍
@@CodeDecode I listened in very slow motion and put a diagram in a paper. Then i understood the concept. I think it is fine for me. No need to do any other video with examples. Another thing is , I tried to donate thank you, but not redirecting to payment page. Will check and update you again.
Didi please please please please Me and You not going anywhere.
If we learn well or quickly, it does not mean that you speak so fast.
Please explain with some breath at normal speed or read calmly bs itna kahen hai please mam please
use chatgt thats way more clear
why is your voice shivering. Looks like you are worried of something. 👀
It might be cold here or mic u
Issues. Not sure. We will check 🙂👍
very confusing explaination . please make it short and understandable for interview pont of view purpose
Hi mam can I know your name
Hello. You can call us team code Decode ❤️. Happy to be connected 🙂
it was bit confusing
Bad explanation
Hi Amit. Can you please suggest what went Wrong ? We will try to rectify the issue you faced
Vest fello
nice explaination
Thanks
Great explanation
Thanks Jeeba