Working principle of a HashMap is common Java interview questions in recent years, almost every Java programmers know HashMap, know where to use HashMap, know the difference between Hashtable and HashMap, why is this so special interview questions? Because of this problem is to investigate the depth of the deep, this problem is often occur in the senior or senior interview, investment Banks prefer to ask this question, may even require you to achieve a HashMap to examine your programming skills, ConcurrentHashMap and the introduction of other synchronous collection make this problem become more complicated, let's begin to explore journey!

Some simple problems first
"You used HashMap?" "What is a HashMap? Why do you use it?"

Almost everyone can answer "yes", then answer some characteristics of the HashMap, such as a HashMap can accept null keys and values, while the Hashtable can't; A HashMap is synchronized; A HashMap soon; And is a key/value pair of HashMap storing, etc., it shows that you have used a HashMap, and quite familiar with it, but the interviewer to plummet, from this moment began to ask the tough questions, about the HashMap for more details, the interviewer may ask the following questions:

"Do you know the working principle of a HashMap?" "Do you know a HashMap the get () method works?"

You may answer, "I don't have a detailed survey of the standard Java API, you can look at the Java source code or Open JDK," "I can use Google to find the answer,"

But some candidates may be able to give an answer, "a HashMap is based on the principle of hashing, we use the put (key, value) store objects into a HashMap, using the get (key) obtained from the HashMap object, when we give the put () method as the key and the value is passed, we start to key invoking hashCode () method that returns the hashCode is used to find the position of the bucket to store Entry objects," the key point here is to point out that a HashMap key object is stored in the bucket and value object, as the Map. The Entry, it helps to understand the logic of access objects, if you do not realize this, or the wrong think only stores a value in the bucket, you will not answer how the object was obtained from the HashMap logic, the answer is quite right, also shows the interviewer really know of hashing and working principle of a HashMap, but this is just the beginning of the story, when the interviewer to join some Java programmers to meet the actual scene, the wrong answer is, the next question is probably about a HashMap of collision detection (collision detection) and collision solution:

"What will happen when two objects at the same hashcode?" Start from here, the real confusion began, because some interviewers will answer the same hashcode, so the two objects are equal, a HashMap will throw an exception, or not to store them, and then the interviewer is likely to remind them to have the equals () and hashcode () two methods, even if the same hashcode and told them the two objects, but they may not be equal, some candidates may give up, while others still can continue to advance, they answered, "because the same hashcode, so they are at the same position of the bucket, 'collision will happen, because a HashMap using linked lists to store objects, the Entry (contains a Map of key/value pair. Entry objects) are stored in the list," the answer is very reasonable, although there are many kinds of methods of dealing with the collision, the method is the simplest, is also a HashMap processing method, but the story is not end, the interviewer will continue to ask:

"If two keys at the same hashcode, how do you get the value object?" The interviewer will answer: when we call the get () method, a HashMap key will be used by the object's hashcode find the position of the bucket, then get the value object, the interviewer reminded him that if there are two value objects stored in the same bucket, he gives the answer: will traverse the list until you find the value object, the interviewer will ask because you didn't value objects to compare, how do you determine sure find value object? Unless the interviewer until HashMap in list is stored in key/value pair, otherwise they can not answer this question,

Some of them remember the important knowledge points of the interviewer will say, find the position of the bucket, invokes the keys. The equals () method to find the correct node in the linked list, and eventually find to find the value of the object, the perfect answer!

In many cases, the interviewer will go wrong in this link, because of their confusion of hashCode () and equals () method, because before this hashCode () often appear, and the equals () method just appear only when get the value object, will point out some good developers to use immutable, declared as final object, and use appropriate equals () and hashCode () method, will reduce the occurrence of collision, improve efficiency, immutability makes different keys to cache hashCode, this will improve the speed of the access object, using the String, Interger this wrapper class as the key is very good choice,

Is here if you think over, then listen to the question below, you will get a big surprise, "if the size of the HashMap over load factor (the load factor) of the definition of capacity, how to do?" Unless you really know the working principle of a HashMap, you will answer not the problem, the default load factor of the size is 0.75, that is to say, when a map is filled with 75% of the bucket, and other collection class (such as ArrayList), will create the original HashMap twice the size of the bucket array, to adjust the size of the map, and put the original object in a new bucket array, this process is called rehashing, because it calls the hash method found a new position of the bucket,

If you can answer this question, the following questions: "what you know to adjust the HashMap size problem?" You may not be able to answer up when the interviewer will remind you when multithreaded, conditions of competition may be produced (race condition),

When adjusting the size of a HashMap, real conditions of the competition, because if two threads are found HashMap need to adjust the size, they will try to adjust the size, at the same time, in the process of adjusting the size of the stored in the order of the elements in the list will, in turn, because when moving to a new position of the bucket, a HashMap will not put elements of the end of the list, but rather on the head, this is to avoid the tail traversal (tail traversing), if the conditions have taken place in the competition, then the infinite loop, this time, you can ask the interviewer, why such a strange, want to use a HashMap in a multithreaded environment? :)

Avid readers contributed more questions about the HashMap:

Why the String, Interger such wrapper classes for the key? String, Interger such wrapper classes as a HashMap key is perfect, and the String is most commonly used, because the String is immutable, also is the final, and rewrite the equals () and hashCode () method, the other wrapper classes have the characteristics of immutability is necessary, because in order to calculate the hashCode (), to prevent the key value change, if the key values are put into different hashCode, and get back when you can't find what you want from a HashMap object, immutability has other advantages such as thread safety, if you can only through a field declaration into final can ensure hashCode is constant, so please do it, because when acquiring the object will use the equals () and hashCode () method, then the key object of right to rewrite these two methods is very important, if the object of the two is not equal to return different hashCode, then the probability of collision will be smaller, so it can improve the performance of the HashMap
We can use a custom object as a key? This is an extension of the previous question, of course, you can use any object as a key, as long as it kept the equals () and hashCode () method defined rules, and when the object is inserted into the Map after will not be changed, if the custom object is immutable, it has been meet the conditions as the key, because when it creates has not changed,
We can use CocurrentHashMap instead of Hashtable? This is another popular interview questions, since ConcurrentHashMap more and more people use, we know the Hashtable is synchronized, but ConcurrentHashMap synchronization performance is better, because it just according to the level of synchronization to locked part of the map, ConcurrentHashMap can replace the Hashtable, but Hashtable provides more thread safety, see this blog to see the difference between Hashtable and ConcurrentHashMap,
I personally like this problem, because of the depth and breadth of the problem, also does not directly involve the different concepts, let's take a look at the question design which knowledge:

The concept of hashing
HashMap the ways to solve collision
Application of equals () and hashCode (), and the importance of them in a HashMap
The benefits of an immutable object
A HashMap multithreaded competition
the condition ofTo adjust the size of a HashMap
Conclusion
The working principle of a HashMap
HashMap based on hashing principle, we through the put () and get () method to store and retrieve objects, when we pass key/value pair to the put () method, it calls the key object of hashCode () method to calculate the hashCode, then find the position of the bucket to store a value object, when the access object, through the key object of the equals () method to find the right key/value pair, and then return the value object, HashMap using linked list to solve the problem of collision, when the collision, the object will be stored in the list of the next node, a HashMap in each list node storing keys to object,

When two different key objects of the same hashcode what happens? They will be stored in the same position of the bucket list, key object equals () method is used to find the key/value pair,

Because the benefits of a HashMap is very much, I used to use in the application of electronic commerce HashMap as cache, because of the financial sector is very much the use of Java, also for performance reasons, we often use a HashMap and ConcurrentHashMap, you can read more about HashMap,

CodePudding user response:

CodePudding user response:

Wow, good,,, the novice to learn,,,,,,,,

CodePudding user response:

Is Daniel can answer

CodePudding user response:

How much is the need to answer like this

CodePudding user response:

CodePudding user response:

I am a four thousand salary can't answer the question the value of forty thousand

CodePudding user response:

Looked at several times, this article from the beginning don't understand, to consult the data, then to see it again, feel relieved, nullnullnullnullnullnullnullnullnullnullnullnull