1：HashMap Data structure of ？
A： Hash table structure （ List hash ： Array + Linked list ） Realization , Combine the advantages of arrays and linked lists . When the chain length exceeds 8 when , The linked list is converted to a red-black tree .
transient Node<K,V>\[\] table;
2：HashMap How it works ？
HashMap The bottom is hash Array and one-way linked list , Every element in the array is a linked list , from Node Inner class （ Realization Map.Entry Interface ） Realization ,HashMap adopt put & get Method to store and retrieve .
When storing objects , take K/V The key value is passed to put() Method ：
①、 call hash(K) Method to calculate K Of hash value , Then combine the array length , Calculated array subscript ;
②、 Resize array （ When the number of elements in the container is greater than capacity * loadfactor when , The container will be expanded resize by 2n）;
③、i. If K Of hash Values in HashMap Does not exist in the , Then insert , If exist , There's a collision ;
ii. If K Of hash Values in HashMap in , And both of them equals return true, Then update the key value pair ;
iii. If K Of hash Values in HashMap in , And both of them equals return false, Then insert the end of the list （ The tail interpolation ） Or in the red and black trees （ How to add a tree ）.
（JDK 1.7 Before using the head insertion method 、JDK 1.8 Use tail insertion ）（ Be careful ： When a collision causes the list to be larger than TREEIFY_THRESHOLD = 8 when , Turn the list into a red black tree ）
When getting objects , take K Pass to get() Method ：①、 call hash(K) Method （ Calculation K Of hash value ） So as to obtain the array subscript of the linked list where the key value is located ;②、 Traverse the list in sequence ,equals() Method to find the same Node In the list K Value corresponding V value .
hashCode It's positioning , Storage location ;equals It's qualitative , Compare whether the two are equal .
3. When two objects hashCode What will happen in the same way ？
because hashCode identical , It doesn't have to be equal （equals Methods to compare ）, So the subscripts of the array in which the two objects are located are the same ," Collision " It happened . Again because HashMap Use linked lists to store objects , This Node Will be stored in the linked list .
4. You know, hash The realization of ？ Why do we have to do this ？
JDK 1.8 in , It's through hashCode() The height of 16 The position is different or low 16 Bit implemented ：(h = k.hashCode()) ^ (h >>> 16), Mainly from speed , Efficiency and quality , Reduce system overhead , It will not cause that the high level does not participate in the calculation of the subscript , The resulting collision .
5. Why use exclusive or operator ？
Guaranteed the object's hashCode Of 32 As long as one bit of the bit value changes , Whole hash() The return value will change . Reduce collisions as much as possible .
6.HashMap Of table How to determine the capacity of ？loadFactor What is it? ？ How the capacity changes ？ What's the problem with this change ？
①、table Array size is determined by capacity This parameter determines , The default is 16, It can also be constructed with , The biggest limit is 1<<30;
②、loadFactor It's the loading factor , The main purpose is to confirm table Whether the array needs to be expanded dynamically , The default value is 0.75, such as table The array size is 16, The loading factor is 0.75 when ,threshold Namely 12, When table The actual size of is more than 12 when ,table We need dynamic expansion ;
③、 Add capacity , call resize() Method , take table The length has doubled （ Note that table length , instead of threshold）
④、 If the data is large , There will be a loss of performance when expanding , Where performance requirements are high , The loss is likely to be fatal .
7.HashMap in put Method process ？
answer ：“ Call hash function to get Key Corresponding hash value , Then calculate its array subscript ;
If there is no hash conflict , Put it directly into the array ; If there is a hash conflict , It is placed behind the list in the form of a linked list ;
If the length of the list exceeds the threshold ( TREEIFY THRESHOLD==8), Turn the list into a red black tree , The length of the list is less than 6, Turn the red and black trees back to the list ;
If the node key Already exist , Replace it value that will do ;
If the key value pair in the set is greater than 12, call resize Method to expand the array .”
8. The process of array expansion ？
Create a new array , It has twice the capacity of the old array , And recalculate the storage location of nodes in the old array . There are only two positions of nodes in the new array , Original subscript location or original subscript + The size of the old array .
9. The chain list is too deep caused by zipper method. Why not use binary search tree instead , And choose the red and black tree ？ Why don't you always use red black trees ？
The reason why red black tree is chosen is to solve the defect of binary search tree , The binary search tree will become a linear structure in special cases （ This is the same as the original structure of linked list , Cause deep problems ）, Traversal search can be very slow . recommend ： Interview ask red black tree , My face is green .
The red black tree may need to pass the left rotation after inserting new data , Right hand 、 Discoloration these operations to keep balance , Red black tree is introduced to find data quickly , Solve the problem of query depth of linked list , We know that the red black tree belongs to the balanced binary tree , But in order to keep “ Balance ” There is a price to pay , But the cost is less than traversing the linear list , So when the length is greater than 8 When , Can use red black tree , If the length of the list is very short , There's no need to introduce black and red trees , Introduction will be slow .
10. Tell me what you think of the red black tree ？
- Each node is not red or black
- The root node is always black
- If the node is red , Then its child nodes must be black （ On the contrary, it is not necessarily ）
- Each leaf node is a black, empty node （NIL node ）
- Every path from root to leaf or empty child , Must contain the same number of black nodes （ The same black height ）
11.jdk8 Chinese vs HashMap What changes have been made ？
stay java 1.8 in , If the length of the list exceeds 8, Then the list will be converted to a red black tree .（ The number of barrels must be greater than 64, Less than 64 When it's time to expand ）
happen hash collision ,java 1.7 Will insert... At the head of the list , and java 1.8 Will insert... At the end of the list
stay java 1.8 in ,Entry By Node replace ( Changed a vest .
12.HashMap,LinkedHashMap,TreeMap What's the difference? ？
LinkedHashMap Saved the insertion order of records , In use Iterator Ergodic time , The first records must be inserted first ; Traverse than HashMap slow ;
TreeMap Realization SortMap Interface , It can sort its saved records by key （ Default key value ascending sort , You can also specify a comparator for sorting ）
13.HashMap & TreeMap & LinkedHashMap Use scenarios ？
In general , The most used is HashMap.
HashMap： stay Map Insert 、 When deleting and positioning elements ;
TreeMap： When you need to traverse the keys in natural or custom order ;
LinkedHashMap： In the case that the order of output is the same as that of input .
14.HashMap and HashTable What's the difference? ？
①、HashMap It's not thread safe ,HashTable It's thread safe ;
②、 Because of thread safety , therefore HashTable It's not as efficient as HashMap;
③、HashMap Only one record can have a key of null, Multiple records are allowed to have a value of null, and HashTable Don't allow ;
④、HashMap The default initialization array size is 16,HashTable by 11, When the former is expanded , Tripled , The latter has tripled +1;
⑤、HashMap You have to recalculate hash value , and HashTable Directly using the hashCode
15.Java Another thread in is safe with HashMap What is a very similar class ？ It's also thread safe , It is associated with HashTable What's the difference in thread synchronization ？
ConcurrentHashMap class （ yes Java Contract issuance java.util.concurrent A thread provided in is safe and efficient HashMap Realization ）.
HashTable It's using synchronize The principle of keyword lock （ Is to lock the object ）;
And for the ConcurrentHashMap, stay JDK 1.7 Used in The way of sectional lock ;JDK 1.8 We have adopted CAS（ No lock algorithm ）+ synchronized.
16.HashMap & ConcurrentHashMap The difference between ？
Except for the lock , There's no big difference in principle . in addition ,HashMap Key value pairs of are allowed to have null, however ConCurrentHashMap Not allowed .
17. Why? ConcurrentHashMap Than HashTable Be efficient ？
HashTable Use a lock （ Lock the whole chain structure ） Dealing with concurrency , Multiple threads compete for a lock , Easy to block ;
- JDK 1.7 Use section lock in （ReentrantLock + Segment + HashEntry）, It's equivalent to putting a HashMap Divide into segments , Assign a lock to each segment , This supports multithreaded access . Lock granularity ： be based on Segment, Contains multiple HashEntry.
- JDK 1.8 Use in CAS + synchronized + Node + Red and black trees . Lock granularity ：Node（ Head node ）（ Realization Map.Entry）. The lock granularity is reduced .
18. in the light of ConcurrentHashMap Specific analysis of lock mechanism （JDK 1.7 VS JDK 1.8）
JDK 1.7 in , Adopt the mechanism of segmented lock , Implement concurrent update operations , Array is used at the bottom + Storage structure of linked list , There are two core static inner classes Segment and HashEntry.
①、Segment Inherit ReentrantLock（ Reentrant lock ） Used to act as a lock , Every Segment Object guards several buckets of each hash map ;
②、HashEntry The key used to encapsulate the mapping table - It's worth it ;
③、 Each bucket is made up of several HashEntry A linked list of objects
JDK 1.8 in , use Node + CAS + Synchronized To ensure concurrent security . Cancel class Segment, Direct use table Array stores key value pairs ; When HashEntry The length of the list of objects exceeds TREEIFY_THRESHOLD when , The linked list is converted to a red-black tree , Lifting performance . The bottom layer is changed to an array + Linked list + Red and black trees .
19.ConcurrentHashMap stay JDK 1.8 in , Why use built-in locks synchronized Instead of re-entry locks ReentrantLock？
①、 The granularity is reduced ;
②、JVM The development team didn't give up synchronized, And based on JVM Of synchronized More optimization space , More natural .
③、 Under a large number of data operations , about JVM Memory pressure , be based on API Of ReentrantLock It will cost more memory .
20.ConcurrentHashMap Brief introduction ？
①、 Important constants ：
private transient volatile int sizeCtl;
When it's negative ,-1 Indicates initializing ,-N Express N - 1 Threads are expanding ;
When it comes to 0 when , Express table It's not initialized yet ;
When it's a positive number , Indicates the size of initialization or next expansion .
②、 data structure ：
Node Is the basic unit of the storage structure , Inherit HashMap Medium Entry, For storing data ;
TreeNode Inherit Node, But the data structure is replaced by a binary tree structure , It's the storage structure of the red black tree , Used to store data in a red black tree ;
TreeBin It's encapsulation TreeNode The container of , Provide some conditions for conversion of red black tree and control of lock .
③、 When storing objects （put() Method ）：
If it's not initialized , Just call initTable() Method to initialize ;
without hash Conflict is direct CAS To insert without a lock ;
If expansion is needed , Just expand first ;
If there is hash Conflict , Add lock to ensure thread safety , Two cases ： One is the form of linked list which directly traverses to the end of insertion , One is that the red black tree is inserted according to the structure of the red black tree ;
If the number of the linked list is greater than the threshold 8, It needs to be converted into the structure of the red black tree first ,break Once again into the cycle
Call... If the addition is successful addCount() Methods statistics size, And check if you need to expand .
④、 Expansion method transfer()： Default capacity is 16, Add capacity , Double the capacity .
helpTransfer()： Call multiple worker threads to help expand capacity , This will be more efficient .
⑤、 When getting objects （get() Method ）：
Calculation hash value , Locate the table Index position , If it is the first node, it will return ;
In case of expansion , Will call flag expanding node ForwardingNode.find() Method , Find the node , Match and return ;
If none of the above is true , Just go down the node , Match and return , Otherwise, I will return to null.
21.ConcurrentHashMap What is the concurrency of ？
The program can be updated at the same time ConccurentHashMap The maximum number of threads without lock contention . The default is 16, And you can set... In the constructor .
When the user sets the concurrency ,ConcurrentHashMap The minimum value greater than or equal to the value will be used 2 Power index as actual concurrency （ If the user sets the concurrency as 17, The actual concurrency is 32）
The original author ： Rookie less than
Link to the original text ： [HashMap Interview must ask data structure related knowledge summary - Rookie less than - Blog Garden ][HashMap_ - _ -]
Original source ： Blog Garden
Invasion and deletion
Official account :java Treasure