The working principle of HashMap is a common Java interview question in recent years. Almost every Java programmer knows HashMap, knows where to use HashMap, and knows the difference between Hashtable and HashMap. So why is this interview question so special? This is because this question is very deep. This question often appears in advanced or intermediate-level interviews. Investment banks prefer to ask this question and may even ask you to implement HashMap to examine your programming skills. The introduction of ConcurrentHashMap and other synchronous sets makes this problem more complicated. Let's start the journey of exploration!
Let's have some simple questions first
"Have you used HashMap?" "What is HashMap? Why did you use it?"
Almost everyone will answer "Yes", and then answer some features of HashMap, such as HashMap can accept null key values and values, while Hashtable cannot; HashMap is non-synchronized; HashMap is fast; and HashMap stores key-value pairs, etc. This shows that you have used HashMap and are quite familiar with it. But the interviewer took a quick turn and started asking some tricky questions from now on, about more basic details of HashMap. The interviewer may ask the following questions:
"Do you know how HashMap works?" "Do you know how HashMap's get() method works?"
You might answer, “I didn’t look up the standard Java API in detail, you can look at the Java source code or Open JDK.” “I can find the answer with Google.”
But some interviewers may be able to give the answer, "HashMap is based on the principle of hashing. We use put(key, value) to store objects into HashMap and use get(key) to get objects from HashMap. When we pass keys and values to the put() method, we first call the hashCode() method on the key, and the returned hashCode is used to find the bucket location to store the Entry object." The key point here is to point out that HashMap stores key objects and value objects in the bucket as Map.Entry. This helps to understand the logic of obtaining objects. If you don't realize this, or mistakenly think that you just store values in buckets, you won't answer the logic of how to get objects from HashMap. This answer is quite correct, and it also shows that the interviewer does know the hashing and how HashMap works. But this is just the beginning of the story. When the interviewer joins some actual scenes that Java programmers have to encounter every day, wrong answers appear frequently. The next question may be about collision detection in HashMap and the solution to collision:
"What happens when the hashcode of two objects is the same?" From here, the real confusion begins, and some interviewers will answer that because the hashcode is the same, the two objects are equal, and the HashMap will throw exceptions, or they will not be stored. Then the interviewer may remind them that there are two methods: equals() and hashCode(), and tell them that even if the hashcode is the same, they may not be equal. Some interviewers may give up, while others can continue to advance. They answered, "Because the hashcode is the same, their bucket position is the same, and 'collision' will happen. Because HashMap uses a linked list to store objects, this Entry (the Map.Entry object containing key-value pairs) will be stored in the linked list." This answer is very reasonable. Although there are many ways to deal with collisions, this method is the easiest, and it is the processing method of HashMap. But the story is not finished yet, and the interviewer will continue to ask:
"If the hashcode of the two keys is the same, how do you get the value object?" The interviewer will answer: When we call the get() method, HashMap will use the hashcode of the key object to find the bucket location and then get the value object. The interviewer reminds him that if two value objects are stored in the same bucket, he gives the answer: the linked list will be traversed until the value object is found. The interviewer will ask, because you do not have a value object to compare, how did you determine whether to find the value object? Unless the interviewer stores key-value pairs in the linked list until HashMap stores them in the linked list, they will not be able to answer this question.
Some of the interviewers who remember this important knowledge point will say that after finding the bucket location, they will call the keys.equals() method to find the correct node in the linked list and finally find the value object to be found. The perfect answer!
In many cases, interviewers will make mistakes in this link because they confuse the hashCode() and equals() methods. Because before this hashCode() appears repeatedly, and the equals() method only appears when obtaining the value object. Some excellent developers will point out that using immutable, declared objects as final, and using appropriate equals() and hashCode() methods will reduce the occurrence of collisions and improve efficiency. Immutability enables the hashcode of different keys to be cached, which will increase the speed of getting the entire object. Using wrapper classes like String and Interger as keys is a very good choice.
If you think it's over here, you'll be surprised when you hear the following question. "What if the size of HashMap exceeds the capacity defined by the load factor?" Unless you really know how HashMap works, you won't answer this question. The default load factor size is 0.75. That is to say, when a map fills up 75% buckets, like other collection classes (such as ArrayList, etc.), a bucket array that is twice the size of the original HashMap will be created to resize the map and put the original object into the new bucket array. This process is called rehashing because it calls the hash method to find the new bucket location.
If you can answer this question, the following question comes: "Do you understand what problems are there in resizing HashMap?" You may not be able to answer it. At this time, the interviewer will remind you that when multi-threading, there may be a race condition.
When resizing HashMap, there is indeed conditional competition, because if both threads find that HashMap needs to be resized, they will try to resize at the same time. During the resize process, the order of elements stored in the linked list will be reversed, because when moving to the new bucket position, HashMap does not place the elements at the end of the linked list, but at the head, which is to avoid tail traversing. If conditional competition occurs, then there is a vicious cycle. At this time, you can ask the interviewer why it is so strange that you need to use HashMap in a multi-threaded environment? :)
Enthusiastic readers contribute more questions about HashMap:
1. Why are wrapper classes like String and Interger suitable as keys? The wrapper class like String and Interger is the most suitable as a HashMap key, and String is the most commonly used. Because String is immutable and final, and the equals() and hashCode() methods have been rewritten. Other wrapper classes also have this feature. Immutability is necessary because in order to calculate hashCode(), you must prevent the key value from changing. If the key value returns a different hashcode when putting in and getting, you cannot find the object you want from the HashMap. Immutability has other advantages such as thread safety. If you can guarantee that the hashCode is unchanged just by declaring a field as final, then please do so. Because the equals() and hashCode() methods are used when obtaining objects, it is very important to rewrite these two methods correctly. If two unequal objects return different hashcodes, the chance of collision will be smaller, which can improve the performance of HashMap.
2. Can we use custom objects as keys? This is an extension of the previous question. Of course you may use any object as keys as long as it follows the definition rules of equals() and hashCode() methods and will not change again after the object is inserted into the map. If this custom object is immutable, then it already satisfies the condition as a key because it cannot be changed after it is created.
3. Can we use CocurrentHashMap to replace Hashtable? This is another very popular interview question, because more and more people use ConcurrentHashMap. We know that Hashtable is synchronized, but ConcurrentHashMap synchronization is better because it locks a portion of the map based on the synchronization level. ConcurrentHashMap can certainly replace HashTable, but HashTable provides stronger thread safety. Check out this blog to see the difference between Hashtable and ConcurrentHashMap.
I personally like this question very much because the depth and breadth of this question do not directly involve different concepts. Let's take a look at what knowledge points are about designing these questions:
Summarize
How HashMap works
HashMap is based on the hashing principle, and we store and get objects through put() and get() methods. When we pass the key-value pair to the put() method, it calls the hashCode() method of the key object to calculate the hashcode, and then finds the bucket position to store the value object. When obtaining the object, the correct key-value pair is found through the equals() method of the key object, and then the value object is returned. HashMap uses linked lists to solve the collision problem. When a collision occurs, the object will be stored in the next node of the linked list. HashMap stores key-value pair objects in each linked list node.
What happens when the hashcode of two different key objects is the same? They will be stored in the linked list at the same bucket location. The equals() method of the key object is used to find key-value pairs.
Because HashMap has many benefits, I used HashMap as a cache in e-commerce applications. Because Java is used a lot in the financial field, and for performance considerations, we often use HashMap and ConcurrentHashMap. You can view more articles about HashMap:
The difference between HashMap and Hashtable
The difference between HashMap and HashSet
Original link: Javarevisited Translation: ImportNew.com - Tang Xiaojuan Translation Link: http://www.importnew.com/7099.html