HashMap works like a Common Java interview question in recent years. Almost every Java programmer knows a HashMap, knows where to use a HashMap, and knows the difference between a Hashtable and a HashMap, so what makes this interview question so special? Because this is a very deep problem. This question is often used in advanced or mid-level interviews. Investment banks prefer to ask this question and will even ask you to implement a HashMap to test your programming skills. The introduction of ConcurrentHashMap and other synchronous sets makes the problem more complicated. Let’s begin the journey of discovery!
Let’s start with some easy questions
“Have you ever used HashMap?” “What is a HashMap? Why did you use it?”
Almost everyone answers “yes,” and then some features of HashMap, such as the fact that HashMap can accept null keys and values, whereas Hashtable cannot; A HashMap is synchronized; A HashMap soon; HashMap stores key-value pairs and so on. This shows that you have already used HashMap and are quite familiar with it. But the interviewer took a sharp turn and started asking tricky questions about the more basic details of the HashMap. The interviewer may ask the following questions:
“Do you know how HashMap works?” “Do you know how the Get () method of HashMap works?”
You might reply, “I didn’t go through the standard Java API, you can look at the Java source code or Open JDK.” “I can use Google to find out.”
But some interviewers might say, “HashMap is based on hashing. We use put(key, value) to store objects in HashMap, and get(key) to get objects out of HashMap. When we pass the key and value to the put() method, we call the hashCode() method on the key first, and the hashCode returned is used to find the bucket location to store the Entry object.” The key point here is to point out that a HashMap stores key objects and value objects in a bucket as map.entry. This helps you understand the logic of getting objects. If you don’t realize this, or mistakenly think you’re only storing values in buckets, you won’t answer the logic of how to get objects from a HashMap. This answer is pretty accurate, and shows that the interviewer really knows how hashing and HashMap work. But that was just the beginning of the story, and when the interviewer added some real-world scenarios that Java programmers encounter every day, the wrong answers cropped up. The next question might be about collision detection in HashMap and how to resolve collisions:
“What happens when two objects have the same Hashcode?” This is where the real confusion begins, with some interviewees answering that because hashCode is the same, so two objects are equal, the HashMap will throw exceptions, or it won’t store them. The interviewer might then remind them of equals() and hashCode() and tell them that even if the hashCode is the same, two objects might not be equal. Some candidates might just give up, while others might just go ahead and say, “Because hashcodes are the same, their bucket locations are the same, and a ‘collision’ will occur. Because HashMap uses linked lists to store objects, this Entry(the Map.entry object with key-value pairs) is stored in the linked list.” This is a very reasonable answer, and while there are many ways to handle collisions, this one is the simplest, and it’s the way HashMap handles them. But that’s not the end of the story, as interviewers continue to ask:
“If two keys have the same Hashcode, how do you get the value object?” The interviewer will reply that when we call the get() method, the HashMap uses the hashcode of the key object to find the bucket position and then retrieves the value object. The interviewer reminded him that if he had two value objects stored in the same bucket, he answered that he would iterate through the list until he found the value object. The interviewer will ask because you don’t have a value object to compare, how did you make sure you found a value object? Unless a HashMap stores key-value pairs in a linked list, the candidates cannot answer this question.
Some interviewees who remember this important point will say that after finding the bucket location, they will call keys.equals() to find the correct node in the linked list and finally find the value object they are looking for. Perfect answer!
In many cases, interviewers make mistakes in this section because they confuse the hashCode() and equals() methods. This is because hashCode() has been used a lot before, and equals() has only been used to fetch value objects. Some good developers will point out that using immutable objects declared final and using the appropriate equals() and hashCode() methods will reduce collisions and increase efficiency. Immutability makes it possible to cache hashCode with different keys, which improves the speed of retrieving the entire object. Using Wrapper classes like String and Interger as keys is a good choice.
If you thought you were done here, you may be in for a surprise. “What if the size of the HashMap exceeds the capacity defined by the Load factor?” Unless you really know how HashMap works, you won’t be able to answer this question. The default load factor is 0.75, which means that when a map is 75% full of buckets, as with other collection classes such as ArrayList, an array of buckets 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 up: “Do you understand the problem with resizing a HashMap?” You may not be able to answer the question, and the interviewer will remind you that race conditions can occur when there are multiple threads.
There is indeed a conditional race when resizing a HashMap, because if both threads find that the HashMap needs to be resized, they will try to resize it at the same time. During resizing, the order of the elements stored in the list is reversed because the HashMap does not place the elements at the end of the list when moving to the new bucket location, but at the head to avoid tail traversing. If conditional competition occurs, then the cycle is endless. At this point, you can ask the interviewer why it’s so weird to use HashMap in a multi-threaded environment. 🙂
Avid readers contributed more questions about HashMap:
Why are wrapper classes like String and Interger good for keys? Wrapper classes like String and Interger are perfect for HashMap keys, and String is the most commonly used. Because strings are immutable and final, and the equals() and hashCode() methods have been overridden. Other Wrapper classes have this feature as well. Immutability is necessary because in order to evaluate hashCode(), the key is prevented from changing, and if the key returns a different hashCode when it is put in and when it is retrieved, then the object you want cannot be found in the HashMap. Immutability has other advantages such as thread safety. If you can guarantee that hashCode is immutable simply by declaring a field final, do so. Because the equals() and hashCode() methods are used to get objects, it is important that the key object overrides them properly. If two objects that are not equal return different Hashcodes, there is less chance of collisions, thus improving the performance of the HashMap.
Can we use custom objects as keys? This is an extension of the previous question. Of course, you can use any object as a key, as long as it complies with the rules for defining equals() and hashCode() methods, and does not change once the object is inserted into the Map. If the custom object is immutable, it already qualifies as a key because it cannot be changed once it is created.
Can we use CocurrentHashMap instead of Hashtable? This is another popular interview question because ConcurrentHashMap is increasingly used. We know that Hashtable is synchronized, but ConcurrentHashMap performs better because it locks only part of the map based on the synchronization level. ConcurrentHashMap can certainly replace HashTable, but HashTable provides greater thread-safety. Check out this blog post to see the difference between Hashtable and ConcurrentHashMap.
I personally like this question because of its depth and breadth, and it doesn’t directly involve different concepts. Let’s take a look at these questions:
The concept of hashing
Methods to resolve collisions in HashMap
Equals () and hashCode(), and their importance in the HashMap
Benefits of immutable objects
HashMap multi-threaded conditional competition
Resize the HashMap
conclusion
How HashMap works
HashMap is based on hashing, where we store and retrieve objects using the put() and get() methods. When we pass the key-value pair to the put() method, it calls the key object’s hashCode() method to compute the hashCode, and then finds the bucket location to store the value object. When an object is retrieved, the correct key-value pair is found through the equals() method of the key object, and the value object is returned. A HashMap uses a linked list to solve collisions, and when a collision occurs, the object is stored in the next node in the list. HashMap stores key-value pair objects in each linked list node.
What happens when two different key objects have the same Hashcode? They are stored in a linked list at the same bucket location. The equals() method of key objects is used to find key-value pairs.
Because of the benefits of HashMap, I have used HashMap as a cache in e-commerce applications. Because Java is heavily used in finance, and for performance reasons, we often use HashMap and ConcurrentHashMap.