Shulou(Shulou.com)06/03 Report--

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? Because this question examines the depth very deeply. This question often appears in senior or intermediate-to-senior interviews. Investment banks prefer to ask this question and may even ask you to implement HashMap to test your programming skills. This problem is further complicated by the introduction of ConcurrentHashMap and other synchronous collections. Let's begin the journey of exploration.

Let's start with some simple questions.

"have you ever used HashMap?" "what is HashMap? why do you use it?"

Almost everyone will answer "Yes" and then answer some of the features of HashMap, such as HashMap can accept null keys and values, while Hashtable cannot; HashMap is non-synchronized;HashMap quickly; and HashMap stores key-value pairs, and so on. This shows that you have used HashMap and are quite familiar with it. But the interviewer took a U-turn and started asking tricky questions about more basic details about 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 say, "I didn't go through the standard Java API, 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 in 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 and value objects as Map.Entry in bucket. This helps to understand the logic of getting an object. If you don't realize this, or mistakenly think that you only store values in bucket, 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 how hashing and HashMap work. But this is just the beginning of the story, and when the interviewer adds some of the actual scenarios that Java programmers encounter every day, there are plenty of wrong answers. The next question may be about collision detection (collision detection) in HashMap and how to resolve collisions:

"what happens when two objects have the same hashcode?" From here on, the real confusion begins, and some interviewers will say that because hashcode is the same, two objects are equal, HashMap will throw exceptions, or will not store them. The interviewer may then remind them that there are two methods, equals () and hashCode (), and tell them that even though the hashcode is the same, they may not be equal. Some interviewers may give up, while others can move on, saying, "because the hashcode is the same, so their bucket locations are the same, and 'collisions' will occur. Because HashMap uses linked lists to store objects, this Entry (a Map.Entry object with key-value pairs) is stored in the linked list." This answer is very reasonable, although there are many ways to deal with collisions, this method is the simplest, and it is the same with HashMap. But the story is not over, and the interviewer will continue to ask:

"how do you get the value object if the hashcode of the two keys is the same?" The interviewer will answer: when we call the get () method, HashMap uses the hashcode of the key object to find the bucket location and then gets the value object. The interviewer reminds him that if there are two value objects stored in the same bucket, he gives the answer: he will traverse the linked list until the value object is found. The interviewer will ask how do you make sure you find a value object because you don't have a value object to compare? Unless the interviewer stores key-value pairs in the linked list, it is impossible for the interviewer to answer this question.

Some of the interviewers who remember this important point of knowledge 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 they are looking for. The perfect answer!

In many cases, interviewers will make mistakes in this process because they confuse the hashCode () and equals () methods. Because hashCode () appears repeatedly before, while the equals () method appears only when you get a value object. Some good developers will point out that using immutable objects declared as final and using appropriate equals () and hashCode () methods will reduce the occurrence of collisions and improve efficiency. Immutability makes it possible to cache hashcode of different keys, which increases the speed of fetching the entire object, and using a wrapper class such as String,Interger as a key is a very good choice.

If you think it's over here, you'll be surprised to hear the following question: "what if the size of the HashMap exceeds the capacity defined by the load factor (load factor)?" Unless you really know how HashMap works, you won't be able to answer this question. The default load factor size is 0.75, that is, when a map fills 75% of the bucket, like other collection classes (such as ArrayList, etc.), an bucket array twice the size of the original HashMap will be created to resize the map and put the original objects 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 know what's wrong with resizing HashMap?" You may not be able to answer, and the interviewer will remind you that conditional competition (race condition) may occur in a multi-threaded situation.

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 resizing, the order of the elements stored in the linked list is reversed, because when you move to the new bucket location, HashMap does not place the element at the end of the linked list, but at the head, to avoid trailing (tail traversing). If the conditional competition occurs, then it will be a dead cycle. At this point, you can ask the interviewer why it is so strange to use HashMap in a multithreaded environment. :)

Enthusiastic readers contribute more questions about HashMap:

Why are wrapper classes like String and Interger suitable for keys? Wrapper classes such as String and Interger are perfect keys for HashMap, and String is the most commonly used. Because String is immutable and final, and the equals () and hashCode () methods have been overridden. Other wrapper classes also have this feature. Immutability is necessary because in order to calculate hashCode (), you have to prevent the key value from changing, and if the key value returns a different hashcode when you put it and when you get it, you can't find the object you want from HashMap. Immutability has other advantages such as thread safety. If you can guarantee that the field is unchanged simply by declaring a hashCode as final, do so. Because the equals () and hashCode () methods are used to get the object, it is important that the key object override these two methods correctly. If two unequal objects return different hashcode, they are less likely to collide, which can improve the performance of 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 follows the definition rules of the equals () and hashCode () methods, and will not change when the object is inserted into the Map. If this custom object is immutable, it already meets the condition as a key, because it cannot be changed after it is created.

Can we use CocurrentHashMap instead of Hashtable? This is another popular interview question, because more and more people use ConcurrentHashMap. We know that Hashtable is synchronized, but ConcurrentHashMap synchronization is better because it locks only a portion of map based on synchronization level. ConcurrentHashMap can certainly replace HashTable, but HashTable provides greater thread safety. Check out this blog to see the difference between Hashtable and ConcurrentHashMap.

Personally, I like this question very much, because the depth and breadth of this problem do not directly involve different concepts. Let's take a look at which knowledge points are designed for these questions:

The concept of hashing

The method of solving collision in HashMap

The application of equals () and hashCode () and their importance in HashMap

Benefits of immutable objects

Conditional contention of HashMap multithreading

Resize HashMap

Summary

How HashMap works

HashMap is based on the principle of hashing, and we store and retrieve objects through put () and get () methods. When we pass the key-value pair to the put () method, it invokes the hashCode () method of the key object to calculate the hashcode and then finds the bucket location to store the value object. When you get an object, you find the correct key-value pair through the equals () method of the key object, and then return the value object. HashMap uses linked lists to solve the collision problem, and when a collision occurs, the object will be stored in the next node of the linked list. HashMap stores key-value pairs in each linked list node.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.