How HashMap works in Java
How HashMap works in Java or sometime how get method work in HashMap is common interview questions now days. Almost everybody who worked in Java knows what hashMap is, where to use hashMap or difference between hashtable and HashMap then why this interview question becomes so special? Because of the breadth and depth this question offers. It has become very popular java interview question in almost any senior or mid-senior level java interviews.
Questions start with simple statement
"Have you used HashMap before" or "What is HashMap? Why do we use it “
Almost everybody answers this with yes and then interviewee keep talking about common facts about hashMap like hashMap accpt null while hashtable doesn't, HashMap is not synchronized, hashMap is fast and so on along with basics like its stores key and value pairs etc.
This shows that person has used hashMap and quite familiar with the functionality HashMap offers but interview takes a sharp turn from here and next set of follow up questions gets more detailed about fundamentals involved in hashmap. Interview here you and come back with questions like
"Do you Know how hashMap works in Java” or
"How does get () method of HashMap works in Java"
And then you get answers like I don't bother its standard Java API, you better look code on java; I can find it out in Google at any time etc.
But some interviewee definitely answer this and will say "HashMap works on principle of hashing, we have put () and get () method for storing and retrieving data from hashMap. When we pass an object to put () method to store it on hashMap, hashMap implementation calls
hashcode() method hashMap key object and by applying that hashcode on its own hashing funtion it identifies a bucket location for storing value object , important part here is HashMap stores both key+value in bucket which is essential to understand the retrieving logic. if people fails to recognize this and say it only stores Value in the bucket they will fail to explain the retrieving logic of any object stored in HashMap . This answer is very much acceptable and does make sense that interviewee has fair bit of knowledge how hashing works and how HashMap works in Java.
But this is just start of story and going forward when depth increases a little bit and when you put interviewee on scenarios every java developers faced day by day basis. So next question would be more likely about collision detection and collision resolution in Java HashMap e.g
"What will happen if two different objects have same hashcode?”
Now from here confusion starts some time interviewer will say that since Hashcode is equal objects are equal and HashMap will throw exception or not store it again etc. then you might want to remind them about equals and hashCode() contract that two unequal object in Java very much can have equal hashcode. Some will give up at this point and some will move ahead and say "Since hashcode () is same, bucket location would be same and collision occurs in hashMap, Since HashMap use a linked list to store in bucket, value object will be stored in next node of linked list." great this answer make sense to me though there could be some other collision resolution methods available this is simplest and HashMap does follow this.
But story does not end here and final questions interviewer ask like
"How will you retreive if two different objects have same hashcode?”
Hmmmmmmmmmmmmm
Interviewee will say we will call get() method and then HashMap uses keys hashcode to find out bucket location and retrieves object but then you need to remind him that there are two objects are stored in same bucket , so they will say about traversal in linked list until we find the value object , then you ask how do you identify value object because you don't value object to compare ,So until they know that HashMap stores both Key and Value in linked list node they won't be able to resolve this issue and will try and fail.
But those bunch of people who remember this key information will say that after finding bucket location , we will call keys.equals() method to identify correct node in linked list and return associated value object for that key in Java HashMap. Perfect this is the correct answer.
In many cases interviewee fails at this stage because they get confused between hashcode () and equals () and keys and values object in hashMap which is pretty obvious because they are dealing with the hashcode () in all previous questions and equals () come in picture only in case of retrieving value object from HashMap.
Some good developer point out here that using immutable, final object with proper equals () and hashcode () implementation would act as perfect Java HashMap keys and improve performance of Java hashMap by reducing collision. Immutability also allows caching there hashcode of different keys which makes overall retrieval process very fast and suggest that String and various wrapper classes e.g Integer provided by Java Collection API are very good HashMap keys.
Now if you clear all this java hashmap interview question you will be surprised by this very interesting question "What happens On HashMap in Java if the size of the Hashmap exceeds a given threshold defined by load factor ?". Until you know how hashmap works exactly you won't be able to answer this question.
if the size of the map exceeds a given threshold defined by load-factor e.g. if load factor is .75 it will act to re-size the map once it filled 75%. Java Hashmap does that by creating another new bucket array of size twice of previous size of hashmap, and then start putting every old element into that new bucket array and this process is called rehashing because it also applies hash function to find new bucket location.
If you manage to answer this question on hashmap in java you will be greeted by "do you see any problem with resizing of hashmap in Java" , you might not be able to pick the context and then he will try to give you hint about multiple thread accessing the java hashmap and potentially looking for race condition on HashMap in Java.
So the answer is Yes there is potential race condition exists while resizing hashmap in Java, if two thread at the same time found that now Java Hashmap needs resizing and they both try to resizing. on the process of resizing of hashmap in Java , the element in bucket which is stored in linked list get reversed in order during there migration to new bucket because java hashmap doesn't append the new element at tail instead it append new element at head to avoid tail traversing. if race condition happens then you will end up with an infinite loop. though this point you can potentially argue that what the hell makes you think to use HashMap in multi-threaded environment to interviewer :)
I like this question because of its depth and number of concept it touches indirectly, if you look at questions asked during interview this HashMap questions has verified
Concept of hashing
Collision resolution in HashMap
Use of equals () and hashCode () method and there importance?
Benefit of immutable object?
race condition on hashmap in Java
Resizing of Java HashMap
Just to summarize here are the answers which does makes sense for above questions
How HashMAp works in Java
HashMap works on principle of hashing, we have put () and get () method for storing and retrieving object form hashMap.When we pass an both key and value to put() method to store on HashMap, it uses key object hashcode() method to calculate hashcode and they by applying hashing on that hashcode it identifies bucket location for storing value object.
While retrieving it uses key object equals method to find out correct key value pair and return value object associated with that key. HashMap uses linked list in case of collision and object will be stored in next node of linked list.
Also hashMap stores both key+value tuple in every node of linked list.
What will happen if two different HashMap key objects have same hashcode?
They will be stored in same bucket but no next node of linked list. And keys equals () method will be used to identify correct key value pair in HashMap.
In terms of usage HashMap is very versatile and I have mostly used hashMap as cache in electronic trading application I have worked . Since finance domain used Java heavily and due to performance reason we need caching a lot HashMap comes as very handy there.
to check some article on hashMap see here
Use of ConcurrentHashMap
SynchrnozedHashMap and ConcurrentHashMap
Difference between hashtable and hashMap
How HashMap works in Java or sometime how get method work in HashMap is common interview questions now days. Almost everybody who worked in Java knows what hashMap is, where to use hashMap or difference between hashtable and HashMap then why this interview question becomes so special? Because of the breadth and depth this question offers. It has become very popular java interview question in almost any senior or mid-senior level java interviews.
Questions start with simple statement
"Have you used HashMap before" or "What is HashMap? Why do we use it “
Almost everybody answers this with yes and then interviewee keep talking about common facts about hashMap like hashMap accpt null while hashtable doesn't, HashMap is not synchronized, hashMap is fast and so on along with basics like its stores key and value pairs etc.
This shows that person has used hashMap and quite familiar with the functionality HashMap offers but interview takes a sharp turn from here and next set of follow up questions gets more detailed about fundamentals involved in hashmap. Interview here you and come back with questions like
"Do you Know how hashMap works in Java” or
"How does get () method of HashMap works in Java"
And then you get answers like I don't bother its standard Java API, you better look code on java; I can find it out in Google at any time etc.
But some interviewee definitely answer this and will say "HashMap works on principle of hashing, we have put () and get () method for storing and retrieving data from hashMap. When we pass an object to put () method to store it on hashMap, hashMap implementation calls
hashcode() method hashMap key object and by applying that hashcode on its own hashing funtion it identifies a bucket location for storing value object , important part here is HashMap stores both key+value in bucket which is essential to understand the retrieving logic. if people fails to recognize this and say it only stores Value in the bucket they will fail to explain the retrieving logic of any object stored in HashMap . This answer is very much acceptable and does make sense that interviewee has fair bit of knowledge how hashing works and how HashMap works in Java.
But this is just start of story and going forward when depth increases a little bit and when you put interviewee on scenarios every java developers faced day by day basis. So next question would be more likely about collision detection and collision resolution in Java HashMap e.g
"What will happen if two different objects have same hashcode?”
Now from here confusion starts some time interviewer will say that since Hashcode is equal objects are equal and HashMap will throw exception or not store it again etc. then you might want to remind them about equals and hashCode() contract that two unequal object in Java very much can have equal hashcode. Some will give up at this point and some will move ahead and say "Since hashcode () is same, bucket location would be same and collision occurs in hashMap, Since HashMap use a linked list to store in bucket, value object will be stored in next node of linked list." great this answer make sense to me though there could be some other collision resolution methods available this is simplest and HashMap does follow this.
But story does not end here and final questions interviewer ask like
"How will you retreive if two different objects have same hashcode?”
Hmmmmmmmmmmmmm
Interviewee will say we will call get() method and then HashMap uses keys hashcode to find out bucket location and retrieves object but then you need to remind him that there are two objects are stored in same bucket , so they will say about traversal in linked list until we find the value object , then you ask how do you identify value object because you don't value object to compare ,So until they know that HashMap stores both Key and Value in linked list node they won't be able to resolve this issue and will try and fail.
But those bunch of people who remember this key information will say that after finding bucket location , we will call keys.equals() method to identify correct node in linked list and return associated value object for that key in Java HashMap. Perfect this is the correct answer.
In many cases interviewee fails at this stage because they get confused between hashcode () and equals () and keys and values object in hashMap which is pretty obvious because they are dealing with the hashcode () in all previous questions and equals () come in picture only in case of retrieving value object from HashMap.
Some good developer point out here that using immutable, final object with proper equals () and hashcode () implementation would act as perfect Java HashMap keys and improve performance of Java hashMap by reducing collision. Immutability also allows caching there hashcode of different keys which makes overall retrieval process very fast and suggest that String and various wrapper classes e.g Integer provided by Java Collection API are very good HashMap keys.
Now if you clear all this java hashmap interview question you will be surprised by this very interesting question "What happens On HashMap in Java if the size of the Hashmap exceeds a given threshold defined by load factor ?". Until you know how hashmap works exactly you won't be able to answer this question.
if the size of the map exceeds a given threshold defined by load-factor e.g. if load factor is .75 it will act to re-size the map once it filled 75%. Java Hashmap does that by creating another new bucket array of size twice of previous size of hashmap, and then start putting every old element into that new bucket array and this process is called rehashing because it also applies hash function to find new bucket location.
If you manage to answer this question on hashmap in java you will be greeted by "do you see any problem with resizing of hashmap in Java" , you might not be able to pick the context and then he will try to give you hint about multiple thread accessing the java hashmap and potentially looking for race condition on HashMap in Java.
So the answer is Yes there is potential race condition exists while resizing hashmap in Java, if two thread at the same time found that now Java Hashmap needs resizing and they both try to resizing. on the process of resizing of hashmap in Java , the element in bucket which is stored in linked list get reversed in order during there migration to new bucket because java hashmap doesn't append the new element at tail instead it append new element at head to avoid tail traversing. if race condition happens then you will end up with an infinite loop. though this point you can potentially argue that what the hell makes you think to use HashMap in multi-threaded environment to interviewer :)
I like this question because of its depth and number of concept it touches indirectly, if you look at questions asked during interview this HashMap questions has verified
Concept of hashing
Collision resolution in HashMap
Use of equals () and hashCode () method and there importance?
Benefit of immutable object?
race condition on hashmap in Java
Resizing of Java HashMap
Just to summarize here are the answers which does makes sense for above questions
How HashMAp works in Java
HashMap works on principle of hashing, we have put () and get () method for storing and retrieving object form hashMap.When we pass an both key and value to put() method to store on HashMap, it uses key object hashcode() method to calculate hashcode and they by applying hashing on that hashcode it identifies bucket location for storing value object.
While retrieving it uses key object equals method to find out correct key value pair and return value object associated with that key. HashMap uses linked list in case of collision and object will be stored in next node of linked list.
Also hashMap stores both key+value tuple in every node of linked list.
What will happen if two different HashMap key objects have same hashcode?
They will be stored in same bucket but no next node of linked list. And keys equals () method will be used to identify correct key value pair in HashMap.
In terms of usage HashMap is very versatile and I have mostly used hashMap as cache in electronic trading application I have worked . Since finance domain used Java heavily and due to performance reason we need caching a lot HashMap comes as very handy there.
to check some article on hashMap see here
Use of ConcurrentHashMap
SynchrnozedHashMap and ConcurrentHashMap
Difference between hashtable and hashMap
Posts
86 comments:
Nice article, Can you also give code example of how hashmap actually works in java. an example will made it more clear.
This same question was asked to me during my interview with a Investment bank for Java FIX developer position. I like follow up question though :)
Hi Sandeep,
Nice to see you here back. yes this is common core java interview question but when you ask cross question then half of developer fails. in most cases they forgot that hashmap stores both key and value in bucket.I have seen interviews where they think that only value is stored in bucket which leads to confusion when asking about duplicate hashcode.
Thanks
JAvin
Hi Dude Can we use hashMap in multithreaded scenario ? is there any issue with that ?
Good explanation. Some pictures and flowcharts will be good.
Well it is obvious that the only mandatory things to store in a dictionnary/map is the key and the value.
Without any more hypothesis, this will resort to O(n) when retriving from the key.
But O(n) is very very bad.
So you start to think at a way to have better performance. You can think about an index. You use ordered type and construct a tree.
Problem is that not all types can be ordered. The hash allow you to treat any type like an ordered one with the exception of collisions. Thus you have O(log n), but could have O(n) in worst case if all entry have the same hash.
But really I found your interview question to be confusing. I can describe what is a dictionnary, what strategy is basically used for it, but I can't say how JAVA implement it. This is a complex question that need basically that you have read the source code and that would depend of the JVM implementation you use.
And if you are really interrested for this matter you now that depending of the exact algorythm you use you have very different performance depending of your exact needs :
map with lot of entry
map with few entries.
how to optimise the partitioning what ever the hash you are given...
For hash and map keys : of course you should use only immuable key. A dictionnary/map is a nonscence if your key is mutable as it is likely that the hash change too. This is bad pratice.
I think I'm going to steal this as an interview question. Thank you for the idea :)
I took it upon myself to provide source for how to build your own (for educational purposes only) @ http://www.dzone.com/links/write_your_own_java_hashmap.html. I would expect a candidate to be able to pseudo-code something similar in an interview - or to admit they have no idea how it all actually works.
Hi Anonymous, Since HashMap is not synchronized there are issue while using it on multithreaded scenario e..g some times get() method of hashMap goes into infinite loop if rehashing and insertion occur in same time. there are other alternative available for multithreaded scenario e.g. ConcurrentHashMAp or Hashtable you can also see my article What is the difference between Synchronized Collection classes and Concurrent Collection Classes ? When to use what ?
Hi Gautam,
Thanks you like the article. I agree pictures and flowcharts will add value to article , will try to add those :)
Javin
Hi Foudres,
Thanks for your detailed comment.The idea behind this interview question is that whether interviewee is familiar to common concepts of hashing and its application in Java or not. as I mentioned there could be other ways to solve collision resolution also
Thanks
Javin
Hi Rod,
Thanks you like the idea and the link. its very relevant to the question and adds value to the blog.
Thanks
Javin
This is really helpful.
I want to know how hashset is implemented in java. Do we need to override equals method in addition to hashcode?
Hi Pallavi,
Internally HashSet is backed by HashMap. And generally yes, in case you have custom hashCode, you may want to override equals so they are consistent with one another.
Cheers
Oleksiy
This is unrealistic, why did you focus on collisions? Java handles that problem as you pointed out, but quite frankly if you're worried about collisions maybe you should be more worried about your perception of hashing. If collisions would be the problem, then you're doing it wrong, you should not use an hashmap in the first place.
I'm sorry but discussing this sounds a bit stupid to me. If you would ask when an hashmap should be used and why, you'll be selecting better candidates.
Hi Anonymous, I appreciate your thoughts but purpose here is to check whether interviewee is familiar with some common programming concepts or not. would you like to hire a guy who is familiar with how hashmap internally works or the one who just simply used hashmap for years but never bothered to think aabout it ? on a separate note yes your question "when an hashmap should be used and why" is also a starter on this topic.
Thanks for your comment.
It would have been nice, if u have added code with explanation. Because then this article is easy to understand.
Put code snippets and add few points why you have used HashMap over other data structure.
Also mention some of the improvements that can be made to your HashMap code snippets. Improvement w.r.t. performance,accuracy of retrieval.
it would be nice to mention overriding equals() method?
Very good article, i found it to be an excellent refresher.
http://fuzz-box.blogspot.com/2011/04/continuous-integration-in-screenshots.html
@Anonymous , Thanks for your comment. This is actually a interview question discussion so I didn't thought of any code example, if something would be required or suites well in length of blog post , I will definitely add.
@Ramakrishna , those are actually discussed but yes as a part of actual interview , It does make sense to ask interviewee to write equals() and hashcode() implementation for any class along with those followup.
@arapidhs , Thanks for your comments , good to here that you like this article.
Hi, Javin Paul.
My blog is written in Brazilian Portuguese. I'm translating it to english at http://rubphp.blogspot.com/
It is on beginning, but you're wellcome there.
Cheers
This is a fantastic post...Really helpful....Thanks for posting...!
SCJP and other Java related stuff @ http://sunjavasnips.blogspot.com/
SCJP SCWCD Dumps
Really helpful post not only for Interviews, also for getting a in-depth understanding of the HashMap which is used very frequently.
Nice article.
Can you explain bit more about put() operation in hashmap and get() operation in hashmap. Also what happens if one thread is iterating over hashmap and other thread is put element into hashmap ? or one thread iterates over hashmap and other thread get() elements from hashmap , any code example will be good. anyway nice java hashmap interview question.
I was looking for some information on how hashmap works internally and found your site, you covered almost everything related to what is hashmap in Java, How HashMap works internally in java and more importantly how get method of hashmap works in java. kudos to you buddy. thanks a lot
Hi Anonymous 1 , put operation in hashmap is used to insert object into hashmap, put method of hashmap takes two argument one is key object and other is value object. always make sure your key object in hashmap is immutable. how get method of hashmap works is clearly explain in the article itself.
Hi Anonymous, thanks you like this tutorial or interview experience. purpose of this tutorial is to let everybody knows high level internal working of hashmap in java.
Great Job...appreciate whole heartily..
Hi,
Nice article. This was the exact sequence I was asked in an interview and I totally messed it up due to lack of knowledge about equals and hashcode methods. Hope, After reading this, I will never ever repeat the same mistake.
Hi Javin, I am working on electronic trading system which we are going to design for foreign exchange and currency trading. I have some question related to FIX Protocol and how we can use FIX Protocol for currency trading. Can you please help me. since I don't have any prior experience on writing any electronic trading system, any suggestion will be appreciated
Nice Article. I understood how the insertion & retrieval work in HashMap. However, I have a very fundamental question:
As per java,
If two objects are equal by equals() method then their hashcode must be same.
Now, what is the rule is not followed.
Lets say we have 2 objects, obj1 & obj2. Lets assume equals method returns two on these 2 objects however the hashCode returns 2 different numbers.
If we try to add these 2 objects (as key) into a hashmap, we will end up having these 2 objects(& associated values) stored in 2 different buckets. (Had the hash code returned the same numbers, the second put() method would just have updated value of the first entry). So no issue with put() method.
Now when you try to retrieve values from hashmap using those two objects, you will successfully get 2 distinct entries created above. So, what's that I am missing?
Thanks.
Hi, Is it possible to replace HashMap in Java with ConcurrentHashMap ? we have a project where hashmap has used a lot and now we want to replace that with ConcurrentHashMap.
Hi ,
Thanks for presenting this article very clearly. I have been working for more than 5 yrs in java until now but never got the proper reason behind how hashmap works.
thanks for such a information
Best
NaiveGeek
@Anonymous you can't just replace HashMap with ConcurrentHashMap because one is not synchronized at all while other provides synchronization. you probably wanted to ask replacing Hashtable with ConcurrentHashMap but even on that case you need to make sure you are not entering into race condition by using putIfAbsent() method instead of put.
Great post, powerfull knowledge, and solid experience... 10x
Thanks Jalal MJADLI, good to know that you like my java hashmap interview experience.
I think your May 3 comment reveals that your approach is unreasonable. You say, "...I appreciate your thoughts but purpose here is to check whether interviewee is familiar with some common programming concepts or not. would you like to hire a guy who is familiar with how hashmap internally works or the one who just simply used hashmap for years but never bothered to think aabout it ?..."
Do you understand everything you've used for years? How does an internal combustion engine work? How about your microwave? How are your clothes made? You've used your body for years, so you should understand anatomy and physiology? Getting closer to programming, how is a keystroke sent to your text editor? What happens if you hit two keys simultaneously? How is the file system implemented? How does the compiler transform Java code to byte code? In Java, do you understand type erasure, generics, wildcards? By your logic, you should since you use it all the time.
Would you agree that we could find an everyday topic that you're not an expert at? If so, I think your interview should be more reasonable. Joel Spolsky is known for hiring some of the industry's truly best people; you can see how he does it here: http://www.joelonsoftware.com/articles/fog0000000073.html
@Anonymous,Thanks for your comment. I see you have a valid point but don't you agree that familiarity with common programming techniques and concept is essential especially if you are a professional programmer, A doctor definitely knows about anatomy of body , a mechanic definitely knows how internal combustion engine work. Also I have not said that don't hire a person because it just doesn't understand how hashmap works in java or what is difference between hashtable and hashmap, this question is more to see his appetite and attitude about its works and technology. Thanks for the link I been following Joel and benefited from his blog.
Awesome post. You've demonstrated your knowledge and desire to learn--you're one of the good guys, no doubt.
"... this question is more to see his appetite and attitude about its works and technology." Awesome! I agree is a fantastic thing to test an interviewee on, but I wonder if one could ask it more directly? Perhaps something like, "Can you tell me about the last time you really dug deep to understand a programming concept?" Maybe more abstractly as in "What are you passionate about?" or "What do you read?"
Thanks Anonymous for your kind comment. Yes those direct questions can be another good alternative.looking forward to see you again.
Thanks Javin. Its a wonderful article and I would like to read all the articles posted by you.
¬Shakshi
Great article Javin. Thanks a lot. A very good refresher indeed.
Amazing article. I wish i could have found this blog before my interview, where i was asked the very questions that you have answered. I was asked to write a HashMap implementation of my own and after reading this article it looks like i could have given a decent try.
Nice article Javin! Would be nice if you can talk more about how this discussion leads onto ConcurrentHashMap...
You have a point Gokul , ConcurrentHashMap is very popular data-structure for high frequency trading platform and it has lots of details which can be tested like Can we replace hashtable with ConcurrentHashMap, may be I will write on that sometime. Thanks for your comments.
Thanks Javin for posting this, easy ans simple way to understand how hash maps works.
Thanks,
Swapna Sangal
Thanks for your comment Swapna, Sample priciple applies on hashtable as well. you may also like my article How substring method works in Java
Superb way of explaining the concepts. I really love to read it. Thanks. Do you have any post on concurrentHashMap ?
Thanks Javin for this Article. Its really helping in understanding the basics of Hash Map.
Thats nice explanation of HashMap
Great article Javin
@Viraj, @ Anonymous and @Bhaskara , Thanks for your comments guys and good to know that you like my hashmap interview experience. you may also like How Substring works in Java
The Best!
This tutorial is simple and clear, very good.
May I ask a question that is about equal and hashcode?
I can't understand why the following code yield "False" ?
if( new Boolean("True") == new Boolean("True"))
System.out.println("True");
else
System.out.println("False");
I conduct 2 tests and still don't understand why the above is "False".
Boolean b1 = new Boolean("True");
Boolean b2 = new Boolean("True");
b1 and b2 is the same by the equal method
System.out.println(b1.equals(b2));
Hash code are the same
System.out.println(b1.hashCode());
System.out.println(b2.hashCode());
Thanks
because the operator "==" is used to verify the matching of objects reference, not the value. In other word you have created two distinct object using "new Boolean);" so you have different reference for two object allocated in different area of memory. I f you want compare object of same class and you want know if they have same hashcode you should use the method Equals(, it works well in this case in other case for you need to use the method compareTo() and compare().
Bye!
Hi ,
Anonymous brought up a valid point. Both equals() and hashCode() on an object should confirm the object equality. "If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result." .
Nice article Javin !
But what Anonymous and Surya pointed above seems correct.
Hi,
Sorry but I think that asking these kind of questions in a job interview proves nothing. Today you can find anything you need on the web so there's no point in memorizing implementations of HashMap, HashTable etc.
I believe that your questions could be good if you would ask about hashing in general (two objects has the same hashcode etc).
The most important thing for a developer, TMHO, is that she could THINK, not memorize...
Kind regards
N
Isn't other collection classes which is based on hashing e.g. HashSet or LinkedHashMap also works in Same principle ? Does HashSet also use equals and hashcode to insert and retrieve objects ?
does it stores key and value object in different node in the linked list or in same node?
Hi Anonymous, keys and values of One Entry in HashMap is stored at one node and that's how after finding bucket location it finds correct object in hashmap.
Good article, but created some confusion in my mind...
If the computed hashcode is same for two objects, hashMap will override the existing value for that key.
My question is what is the scenario the value would be overriden and added to same bucket in the HashMap.
The piece of code placed here for overriding
String s1 = new String("abc");
String s2 = new String("abc");
System.out.println("s1 hashcode: "+s1.hashCode());
System.out.println("s2 hashcode: "+s2.hashCode());
Map map = new HashMap();
map.put(s1, s1);
map.put(s2, new String("cdf"));
System.out.println(map);
Hi Shivu, if key is same i.e. equals by equals method in Java than hashcode would be same and value will be replaced but if key is not same i.e. not equal but hashcode is same (Which is possible in java) than bucked location would be same and collision would happen and second object will be stored on second node of linked list structure on Map.
isn't it all other hashing related data-structure like Hashtable, HashSet, LinkedHashMap is implemented in this way ? At least implementation of put() and get() should be same with some addition specific details related to individual collection.
You are just awesome.Have no words to praise you.You have explained in such difficult thing in such a simple way.Fantastic, Great work.
Mandakini
hi,
still i have little confusion over this
can you specify an example how can two different objects has same hash code(say for two custom objects)
In fact Hashset in java is simply a delegated hashmap: here's a snippet of the source to prove the point
private transient HashMap map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
// similar methods that delegate follow
Thanks for such nice article. Will be expecting such articles in future also.
Thanks Joe, good to know that you like this Java hashmap interview question.
@MJB, Indeed HashSet uses HashMap for hashing support and thank for putting the code snippet it makes the point much clearer.
@Mandakini Mishra , Thanks for your kind words, glad to hear you like this Java hashmap question answer article.
This is a great article, but if i have one complaint, it seems to be written poorly in terms of english (almost as thought a translator was used). i am finding it hard to understand some of the answers because of this.
@Anonymous, point noted. thanks for your comment.
Excellent tutorial!!!!!!!!!!!!!!
I have one comment regarding your explanation: key.equals() is used also when you use put() method, because if hashcode() of an existing key is the same with the one which you want to insert, yes, the new key will be the next one in the bucket, ONLY IF THE KEY IS UNIQUE. So in order to do that, it is used also method key.equals(), to prevent duplicates. (You said that we are talking about equal() method only when we are retriving data from HashMap)
Regards
@Anonymous, your observation is correct key.equals() is used on both put() and get() method call if object already exits in bucked location on hashmap and that's why tuples contains both key and value in each node. thanks for pointing it and making it more clear.
Hi,
Overriding equals and hashcode we can make the object as key in hashmap.While putting the the reference to the object as Key in hashmap or creating the object and setting it in put method , what difference does it make in retreiving the object?
Nice explanation..its very hard to find all valid reason at one place.thnx
For android see this
http://androidtrainningcenter.blogspot.in/
@Tofeeq thanks for your comment. Glad to hear that you like interview question on java hashmap.
Thanks Javin, great post again.
This is true that Hashmap are common questions someone can get in interview from a Java & Java EE perspective. I interview new members myself at my current company (CGI Inc.) and the typical questions that I ask, in a Java EE context are:
- What are best & known risks when using Hashmap data structure?
- What JDK Map data structure is more suitable to handle concurrent read & write operations in a Java EE environment?
The answer for the first one is all about adding proper synchronization when Hashmap is used in a concurrent Thread access scenario e.g. same Hashmap instance shared across multiple Threads.
Primary known risks are Hashmap internal index corruption and infinite looping, which can bring your JVM to its knees.
The answer about the second one is to use the ConcurrentHashMap, introduced in JDK 1.5, which provides Thread safe operations but no blocking get() operation; which is key for proper performance. This is the typical data structure used these days in modern Java EE container implementations.
If your readers are interested, I have a case study of a recent Hashmap infinite looping problem, actual Weblogic 11g defect (non Thread safe Hashmap)!
Thanks again for all that good work.
P-H
I am new to Java World! So I have this problem stated as under.....
I have sortedHashMap and hashMap2
Now i have to get hashMap3 based on sortedHashMap sorted order.
Secondly; I have also to limit hashMap3 as of first sorted 100 values.....rest map I dont need.
Please suggest me coding example or junk of code.
Thanks!
I was always curious on How HashMap stores object in Java or How HashMap is implemented in Java. I know about bucket and collision but What I missed was Map.Entry which is used to store both key and value object. HashMap stores Entry object which contains both key and value which then used in case of collision when more than one object is stored inside bucket to find out correct mapping. Correct me if this is not how hashmap stores objects in Java.
Isn't it Hashtable also works in similar way. Please let us know How Hashtable works in Java. I know about HashMap but now I am keen to know How Hashtable works internally.
Post a Comment