Gather relevant knowledge points and expand supplements

  Collection aggregate

List aggregate

ArrayList It's a dynamic array , The bottom layer is an implementation Object Array . When using a parameterless constructor ArrayList() when , Initial capacity elementData by 0. Capacity during the first expansion +10. When the capacity needs to be expanded again , Expanded to the original capacity 1.5 times . When using a parameterized constructor , The initial capacity is the capacity of the parameter passed in . When expansion is needed , Expanded to the original capacity 1.5 times .

ArrayList Maximum capacity of
    according to ArrayList Source code ,ArrayList The maximum capacity of is Integer.MAX_VALUE - 8 That is to say 2147483639. Why not Integer.MAX_VALUE Well ？ Because some virtual machines keep some in the array header words, So reserved 8 To prevent cross-border

LinkedList

LinkedList yes java Implemented bidirectional queue , He has three member variables .LinkedList Because it is the linked list that causes the addition and deletion operations faster than ArrayList, Modifications and queries are slower than ArrayList.

 Node( Find nodes by index )
LinkList Of Node() The method is to find nodes according to the index .Node() yes LinkedList The most important way , This method is required for addition, deletion, modification and query . This Node() It's not silly to go through it from beginning to end . He first judges the size of the index , If the index is greater than size/2 ( It's still a bit operation ), Then traverse forward from the tail . If the index is less than size/2, Then traverse from beginning to end .
 

indexOf( Find the index according to the node value )

This is really a silly traversal from beginning to end

Set
HashSet
When we new One. HashSet Then click into his constructor , We will be surprised to find HashSet The underlying implementation of HashMap. And when we pass in a collection ,HashMap The initial capacity of is max( Aggregate capacity /0.75+1,16).
HashSet The actual data of exists Node Inside key.Node Medium value A static variable is used PERSENT Occupy the pit

For details, see ：
————————————————
Copyright notice ： This paper is about CSDN Blogger 「OldZhangYH」 The original article of , follow CC 4.0 BY-SA Copyright agreement , For reprint, please attach the original source link and this statement .
Link to the original text ：https://blog.csdn.net/qq_40679774/article/details/123229719

jdk8 HashMap Underlying principle

HashMap As Map The main implementation class of ,jdk1.2 appear , Thread unsafe , Efficient , Can be stored null Of key and value,jdk7 Its underlying structure is only ： Array + Linked list ,jdk8 In its underlying structure ： Array + Linked list + Red and black trees , About jdk8 Of

HashMap attribute ruxia：
1）DEFAULT_INITIAL_CAPACITY: HashMap Default Capacity ：16（ The initial value and can be 0）
2）DEFAULT_LOAD_FACTOR： Hash Default load factor ：0.75
3）TREEIFY_THRESHOLD： When Linked list Data in the Greater than the default value , Convert to Red and black trees , The value is 8
4）MIN_TREEIFY_CAPACITY： In the bucket Node When being treelized The smallest hash Table capacity ：64
5）threshold: The critical value of expansion , be equal to Capacity * Fill factor ：16 * 0.75 =12

get hash After index , according to hash Index inserts data Map in .

If there is no element in that position, put it directly
If there is an element in that position , Then compare whether it is the same .（ Determine whether it is the same object and equals(),（ Different kinds of equals Is different . It depends on how it is rewritten ） Why not ）

•   Just give up if you are the same
•   Different, continue to compare the elements in the linked list at this position , It's different until the end of the linked list, and it's at the end .
  
  After the element is added to the linked list , If the length is greater than or equal to 8.
• Array length is greater than or equal to 64, Tree the linked list of this location
• Otherwise, expand the array .

 

and JDK1.8 in ,HashMap use Array + Linked list + Red and black trees Realization , When The length of the list exceeds threshold （8） when , take Linked list Convert to Red and black trees , This greatly reduces the search time .

​

  Details visible ：http://t.csdn.cn/VUVLx

http://t.csdn.cn/v5Gaf