Interview: HashMap 21 questions! Can you answer them all?

osc_ jvzgahav 2021-01-23 12:57:48
interview hashmap questions answer


  • 1:HashMap Data structure of ?

  • 2:HashMap How it works ?

  • 3. When two objects hashCode What will happen in the same way ?

  • 4. You know, hash The realization of ? Why do we have to do this ?

  • Put together a copy of Java Interview book full version PDF

  • 5. Why use exclusive or operator ?

  • 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 ?

  • 7.HashMap in put Method process ?

  • 8. The process of array expansion ?

  • 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 ?

  • 10. Tell me what you think of the red black tree ?

  • 11.jdk8 Chinese vs HashMap What changes have been made ?

  • 12.HashMap,LinkedHashMap,TreeMap What's the difference? ?

  • 13.HashMap & TreeMap & LinkedHashMap Use scenarios ?

  • 14.HashMap and HashTable What's the difference? ?

  • 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 ?

  • 16.HashMap & ConcurrentHashMap The difference between ?

  • 17. Why? ConcurrentHashMap Than HashTable Be efficient ?

  • 18. in the light of ConcurrentHashMap Specific analysis of lock mechanism (JDK 1.7 VS JDK 1.8)

  • 19.ConcurrentHashMap stay JDK 1.8 in , Why use built-in locks synchronized Instead of re-entry locks ReentrantLock?

  • 20.ConcurrentHashMap Brief introduction ?

  • 21.ConcurrentHashMap What is the concurrency of ?

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 . Why rewrite hashcode and equals Method ? It's recommended to have a look at .

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? ?

HashMap Refer to other questions ;

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 ;

ConcurrentHashMap

  • 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( First knot spot )( 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

 interview :HashMap Twenty one questions ! You can Can you answer that ?

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 .

 interview :HashMap Twenty one questions ! You can Can you answer that ?

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 direct traversal in the form of linked list

Insert... At the end , 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 . Put together a copy of Java Interview book full version PDF

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)

版权声明
本文为[osc_ jvzgahav]所创,转载请带上原文链接,感谢
https://javamana.com/2021/01/20210123125537417Q.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云