How many questions can you answer?

Java dictionary 2021-02-23 16:00:54
questions answer

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 .

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

本文为[Java dictionary]所创,转载请带上原文链接,感谢

  1. Spring can still play like this! Ali's new spring product has successfully overturned my understanding of spring!
  2. IntelliJ idea can also draw mind maps. It's really the strongest ide!
  3. JavaScript performance optimization [inline cache] V8 engine features
  4. linux 配置java环境
  5. linux find 查找文件
  6. 深入理解 Web 协议 (三):HTTP 2
  7. IntelliJ IDEA 相关问题记录
  8. Deep understanding of Web protocol (3): http 2
  9. 深入理解 Web 协议 (三):HTTP 2
  10. 腾讯IEG开源AI SDK:自动化测试吃鸡、MOBA类游戏
  11. Mysql Command
  12. Configuring Java environment with Linux
  13. Find files in Linux
  14. docker-Dockerfile 创建镜像
  15. Redis Cluster
  16. 深入理解 Web 协议 (三):HTTP 2
  17. JavaScriptBOM操作
  18. JavaScriptBOM操作
  19. Deep understanding of Web protocol (3): http 2
  20. Record of IntelliJ idea related problems
  21. Deep understanding of Web protocol (3): http 2
  22. Tencent IEG open source AI SDK: automatic testing of chicken eating and MoBa games
  23. Mysql Command
  24. Docker dockerfile create image
  25. Redis Cluster
  26. 死磕Spring之IoC篇 - 文章导读
  27. Deep understanding of Web protocol (3): http 2
  28. JavaScript BOM operation
  29. JavaScript BOM operation
  30. 死磕Spring之IoC篇 - 文章导读
  31. k8s node 操作与维护
  32. k8s 证书更新
  33. 【Java面试题第三期】JVM中哪些地方会出现内存溢出?出现的原因是什么?
  34. HashMap连环问你能答出几道?
  35. k8s-cronjob
  36. k8s-cert
  37. 头条面试官:说说Kafka的消费者提交方式,怎么实现的
  38. 什么是HTTPS以及如何实施HTTPS?
  39. Spring: an introduction to IOC
  40. Spring: an introduction to IOC
  41. Operation and maintenance of k8s node
  42. K8s certificate update
  43. vue使用sdk进行七牛上传
  44. k8s-dns
  45. JavaScript 邮箱验证 - 正则验证
  46. k8s-dashboard
  47. HashMap连环问你能答出几道?
  48. Where does memory overflow occur in the JVM? What are the reasons for this?
  49. How many questions can you answer?
  50. k8s-cronjob
  51. spring注解--Transactional
  52. k8s-cert
  53. Will the Spring Festival holiday be extended to February 27 in 2021? Here comes the response
  54. Headline Interviewer: talk about Kafka's consumer submission method, how to achieve it
  55. 【k8s集群】搭建步骤
  56. k8s-kubeadm
  57. k8s-etcd
  58. What is HTTPS and how to implement it?
  59. Java中使用HashMap改进查找性能
  60. maven发布jar包运行时找不到类问题