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

This article introduces the relevant knowledge of "what are the interview questions often asked by HashMap". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

(1) the implementation principle of HashMap?

This question can be composed of the following serial guns

Have you read the HashMap source code? do you know how it works?

Why use array + linked list?

What other solutions do you know about the hash conflict?

Can I use LinkedList instead of array structure?

Since it is possible, why does HashMap choose arrays instead of LinkedList?

Have you read the HashMap source code? do you know how it works?

To solve this problem, well, of course, you must read the HashMap source code. As for the principle, the following picture is clear:

HashMap uses the Entry array to store key-value pairs, each key-value pair forms an Entry entity, and the Entry class is actually an one-way linked list structure with Next pointers that can connect to the next Entry entity.

It's just that in JDK1.8, when the length of the linked list is greater than 8, the linked list will turn into a red-black tree!

Why use array + linked list?

The array is used to determine the position of the bucket, which is obtained by modulating the length of the array using the hash value of the element's key.

The linked list is used to solve the problem of hash conflicts. When the hash value is the same, a linked list is formed at the corresponding position on the array. Ps: the hash value here does not mean hashcode, but the hashcode is sixteen digits higher or lower than XOR. As to why you did it, move on.

What other solutions do you know about the hash conflict?

There are four famous ones: (1) open address method (2) chain address method (3) re-hash method (4) public overflow area method

Ps: if you are interested in expanding, you will understand it by searching it yourself. This will not be expanded!

Can I use LinkedList instead of array structure?

Let me explain a little bit here, what this question means is that the source code is like this.

Entry [] table = new Entry [capacity]

Ps:Entry is a linked list node.

Then I'll say it as follows.

List table = new LinkedList ()

Is it feasible?

The answer is obvious, it must be yes.

Since it is possible, why does HashMap choose arrays instead of LinkedList?

Because using arrays is the most efficient!

In HashMap, the position of the positioning bucket is obtained by modulating the length of the array using the hash value of the element's key. At this point, we have got the location of the bucket. Obviously, the lookup efficiency of the array is higher than that of LinkedList.

So ArrayList, the bottom layer is also an array, it is also fast to find, why not use ArrayList?

(when Brother Yan wrote here, I couldn't help feeling that I really had an idea. I asked myself to death, but luckily I came up with an answer.)

Because of the basic array structure, the capacity expansion mechanism can be defined by itself. In HashMap, the array expansion is just the power of 2, so it is efficient to do modular operation.

The expansion mechanism of ArrayList is 1.5x expansion, so why ArrayList is 1.5x expansion is not explained in this article.

(2) under what conditions does HashMap expand its capacity?

This question can be composed of the following serial guns

Under what conditions does HashMap expand its capacity?

Why is the expansion to the nth power of 2?

Why is it necessary to have 16 bits higher or lower than 16 bits before taking the modular operation?

Under what conditions does HashMap expand its capacity?

If the bucket is full (more than load factor*current capacity), resize is required.

Load factor is 0.75.To avoid hash conflicts as much as possible

Current capacity is the current array size.

Why is capacity expansion to the power of 2?

HashMap in order to access efficient, to minimize collisions, that is, try to distribute the data evenly, each linked list is roughly the same length, this implementation is the algorithm to which the data is stored in the linked list; this algorithm is actually modular, hash%length.

However, everyone knows that this kind of operation is not as fast as displacement operation.

Therefore, hash& (length-1) is optimized in the source code.

In other words, hash%length==hash& (length-1)

Then why is it to the n power of 2?

Because the n-th power of 2 is actually n-1 followed by 1, and it is actually n 1.

For example, when the length is 8, 3 & (8-1) = 32 & (8-1) = 2, there is no collision in different positions.

When the length is 5, 3 & (5-1) = 0.2 & (5-1) = 0, all on 0, there is a collision.

Therefore, to ensure that the volume is 2 to the n power is to ensure that when doing (length-1), everyone can & 1, that is, and 1111. 1111111 carries on and calculates.

Why is it necessary to have 16 bits higher or lower than 16 bits before taking the modular operation?

Let me show you the hash method in jdk1.8 first. 1.7 is more complicated, so let's not watch it.

Hashmap did this only to reduce the chances of hash conflicts.

For example, when our length is 16, the hash code (the hash code corresponding to the key of the string "abcabcabcabcabc") pair (16-1) and the operation, for the hashCode generated by multiple key, as long as the last 4 bits of the hash code are 0, no matter how the high bit changes, the final result is 0.

As shown in the following figure

After adding the "disturbance function" of high 16 bits or low 16 bits, the results are as follows

It can be seen that before the disturbance function optimization: 1954974080 16 = 1954974080 & (16-1) = 0 after the disturbance function optimization: 1955003654 16 = 1955003654 & (16-1) = 6 obviously reduces the probability of collision.

(3) tell me about the get/put process of hashmap?

This question can be composed of the following serial guns

Do you know the process of the put element in hashmap?

Do you know the process of the get element in hashmap?

What other hash algorithms do you know?

Tell me about the implementation of hashcode in String? (this question has been asked by many big manufacturers)

Do you know the process of the put element in hashmap?

Do hash operation on hashCode () of key to calculate index

If there is no collision, put it directly into the bucket.

If there is a collision, after buckets exists in the form of a linked list

If the collision causes the linked list to be too long (greater than or equal to TREEIFY_THRESHOLD), convert the linked list to a red-black tree (changes in JDK1.8)

Replace old value if the node already exists (ensure the uniqueness of key)

If the bucket is full (more than load factor*current capacity), resize is required.

Do you know the process of the get element in hashmap?

Do hash operation on hashCode () of key to calculate index

If it is directly hit in the first node in bucket, it returns directly.

If there is a conflict, then use key.equals (k) to find the corresponding Entry

If it is a tree, find it in the tree by key.equals (k), O (logn)

If it is a linked list, look for it through key.equals (k) in the linked list, O (n).

What other hash algorithms do you know?

Let's talk about what the hash algorithm does. The Hash function refers to mapping a large range to a small range. The purpose of mapping a large area to a small area is often to save space and make data easy to save.

The more famous ones are MurmurHash, MD4, MD5 and so on.

Tell me about the implementation of hashcode in String? (this question is very frequent.)

Public int hashCode () {int h = hash; if (h = = 0 & & value.length > 0) {char val [] = value; for (int I = 0; I

< value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h;} String类中的hashCode计算方法还是比较简单的，就是以31为权，每一位为字符的ASCII值进行运算，用自然溢出来等效取模。 哈希计算公式可以计为s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1] 那为什么以31为质数呢? 主要是因为31是一个奇质数，所以31*i=32*i-i=(i>

16)

After the expansion, the elements are either in the original position or move to the second power position in the original position, and the order of the linked list remains the same.

The last one is the key point, because the last change, hashmap in 1.8, will not have an endless cycle.

Why not use a red-black tree directly when resolving hash conflicts? And choose to use the linked list first, and then turn to the red-black tree?

Because red-black trees need to perform left-handed, right-handed, and discoloration operations to maintain balance, while single-linked lists are not needed.

When the number of elements is less than 8, the linked list structure can guarantee the query performance when the query operation is done at this time. When the number of elements is greater than 8, a red-black tree is needed to speed up the query, but the efficiency of the new nodes becomes slower.

Therefore, if you use the red-black tree structure in the first place, there are too few elements and the efficiency of adding is relatively slow, which is undoubtedly a waste of performance.

I don't need a red-black tree. Can I use binary to find the tree?

Sure. But in special cases, the binary search tree will become a linear structure (which is the same as using the linked list structure, causing a deep problem), traversing the search will be very slow.

Then why is the threshold 8?

I don't know, waiting for the jdk author to answer.

The answer to this question that can be found on the Internet is bullshit.

I will post a random net of answers, as shown in the following figure

Do you see bug? The intersection point is 6.64? The intersection point is clearly four, okay.

Log4=2,4/2=2 .

The author of jdk chooses 8, which must have gone through strict calculation, and thinks that when the length is 8, instead of ensuring the lookup cost of the linked list structure, it is better to convert it to a red-black tree and maintain its balanced cost instead.

When a linked list becomes a red-black tree, when does it degenerate into a linked list?

Turn back to a linked list when it is 6. There is a difference of 7 to prevent frequent transitions between linked lists and trees. Suppose that if the number of linked lists is more than 8, the linked list will be converted into a tree structure, and if the number of linked lists is less than 8, then the tree structure will be converted into a linked list. If a HashMap keeps inserting and deleting elements, the number of linked lists will hover around 8, then tree to linked list and linked list to tree will occur frequently, and the efficiency will be very low.

(5) the concurrency problem of HashMap?

This question can be composed of the following serial guns

What's wrong with HashMap in a concurrent programming environment?

Do you still have these problems in jdk1.8?

How do you usually solve these problems?

What's wrong with HashMap in a concurrent programming environment?

(1) the problem of endless cycle caused by multi-thread expansion

(2) when multithreading put, elements may be lost.

(3) after put non-null elements, null comes out of get.

Do you still have these problems in jdk1.8?

In jdk1.8, the problem of an endless loop has been solved. The other two problems still exist.

How do you usually solve these problems?

Such as thread-safe collection classes such as ConcurrentHashmap,Hashtable.

(6) what do you usually use as the key of HashMap?

This question can be composed of the following serial guns

Can the key be null?

What do you usually use as the key of HashMap?

What's wrong with using variable classes as key for HashMap?

What if you are asked to implement a custom class as the key of HashMap?

Can the key be null?

It must be possible. When key is null, the last value of the hash algorithm is calculated as 0, which is placed in the first position of the array.

What do you usually use as the key of HashMap?

Immutable classes such as Integer and String are generally used as HashMap as key, and String is the most commonly used.

(1) because the string is immutable, the hashcode is cached when it is created and does not need to be recalculated. This makes strings suitable for use as keys in Map, and strings are processed faster than other key objects. This is why keys in HashMap tend to use strings.

(2) because the equals () and hashCode () methods are used to get the object, it is very important that the key object overrides these two methods correctly, and these classes have normatively overridden the hashCode () and equals () methods.

What's wrong with using variable classes as key for HashMap?

The hashcode may change so that the value entered by put cannot be get out, as shown below

HashMap changeMap = new HashMap (); List list = new ArrayList (); list.add ("hello"); Object objectValue = new Object (); changeMap.put (list, objectValue); System.out.println (changeMap.get (list)); list.add ("hello world"); / / hashcode has changed System.out.println (changeMap.get (list))

The output values are as follows

Java.lang.Object@74a14482null

What if you are asked to implement a custom class as the key of HashMap?

This question examines two knowledge points

What are the considerations for overriding the hashcode and equals methods?

How to design an immutable class

For problem one, just remember the following four principles

(1) if two objects are equal, hashcode must be equal.

(2) the two objects are different, and the hashcode is not necessarily different.

(3) hashcode is equal, but two objects are not necessarily equal.

(4) the hashcode varies, and the two objects must be different.

For problem 2, remember how to write an immutable class

(1) the class adds a final modifier to ensure that the class is not inherited.

If the class can be inherited will break the immutability mechanism of the class, as long as the inherited class overrides the methods of the parent class and the inherited class can change the value of member variables, then once the subclass appears as a parent class, there is no guarantee that the current class is mutable.

(2) ensure that all member variables must be private and decorated with final

In this way, member variables are guaranteed to be immutable. But only this step is not enough, because if it is an object member variable, it is possible to change its value externally. So the fourth point makes up for this deficiency.

(3) No methods are provided to change member variables, including setter

Avoid changing the value of member variables through other interfaces, destroying immutable properties.

(4) initialize all members through the constructor for deep copy (deep copy)

If the object passed in by the constructor is assigned directly to the member variable, you can still change the value of the internal variable by modifying the incoming object. For example:

Public final class ImmutableDemo {private final int [] myArray; public ImmutableDemo (int [] array) {this.myArray = array; / / wrong}}

This approach does not guarantee immutability. MyArray and array point to the same block of memory address, and users can change the value inside the myArray by changing the value of the array object outside the ImmutableDemo.

To ensure that the internal values are not modified, you can use the depth copy to create a new memory to hold the incoming values. The right thing to do:

Public final class MyImmutableDemo {private final int [] myArray; public MyImmutableDemo (int [] array) {this.myArray = array.clone ();}}

(5) in the getter method, do not directly return the object itself, but clone the object and return a copy of the object

This practice is also to prevent object leakage and prevent direct manipulation of member variables after obtaining internal variable member objects through getter, resulting in changes in member variables.

This is the end of the content of "what are the interview questions often asked by HashMap". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.