Detailed array expansion analysis --- take you step by step analysis

Let's first take a look ArrayList Constructor for

Before that , We need to simply remember these variables , If you don't see the back, you may get confused

transient Object[] elementData; //  For loading List An array of sets 
private static final Object[] EMPTY_ELEMENTDATA = {
    };// The parameters used for the second construction method are 0 when element The initialization and third construction method parameters of are empty sets elementData The initialization 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
    };// For nonparametric construction elementData The initialization 
private int size;// Used to obtain elementData The length of 
private static final int DEFAULT_CAPACITY = 10;// For nonparametric construction elementData Before adding elements , Give initial capacity 10

Now let's start with nonparametric construction , Discuss expansion methods , The other two construction methods will be introduced in turn , The principles are roughly the same ：

Then let's take a look at add() Method ：

Then let's take a look at ensureCapacityInternal() Method ：

You can see ensureCapacityInternal() Method defines two methods , Let's go through one calculateCapacity(elementData,minCapacity) Method , Then another ensureExplicitCapacity(). So let's look at these two methods respectively ：

Then we put the calculateCapacity(elementData,minCapacity) Back to 10 It's passed on to ensureExplicitCapacity(), Now let's take a look ensureExplicitCapacity() Method implementation ：

Now take a look at grow() Method ：


After the above , We can see that elementData stay add( First element ） after , Go first ensureCapacityInternal(size+1) Complete the initialization of the array , the elementData The length of the array becomes 10, Then the first element is added, namely elementData[0]. Then add the second , What about the third element ？
When adding the second element size=1, here minCapacity(size+1) Turned into 2, Now enter ensureCapacityInternal(size+1)：

According to the above, we can know , When size=0 when ( Add the first element ),elementData.length become 10, Back when size=1-9 When , Corresponding minCapacity become 1-10,elementData All of them correspond to 10, Will not achieve grow() Method , That is, expand the capacity , But when size=10 when （ Add para 11 Element time ） Corresponding minCapacity Turned into 11,elementData The corresponding is 10, At this point grow() Method , super-popular . We'll see grow() Method ：

here elementData The array is updated to the figure above . Then analogy in turn is the front size=15,add( Add para 16 Elements ) There will be a second expansion , The expansion size is ：15+floor(15/2)=22. So far ArrayList We are very clear about the parameterless construction method of ： Initial elementData by 0, When we add( First element ) The array is initialized to elemenData[10]. When the 11, The first 16, The first 23 When it's an element , We continue to expand …
In order to verify our above conclusion ： We do validation .


Next, let's look at two parametric construction methods ： The first is public ArrayList(int initialCapacity)：

When add( Add para 6 Elements ) In execution grow(6) Method , Again from 5 Capacity expansion becomes 7：

Let's see if innitialCapcity If 0, Then we can analyze it again ：






We can see when initialCapcity=0, When you add the first element , We only give an initial capacity 1, When the second element is added, it will expand to 2, When the third element is added, it will be expanded to 3, When adding the fourth element, it will expand to 4, When adding the fifth element, it will be expanded to 6, Then there is the seventh 7 Element is expanding , Expand to 9. The first 10 Expand the capacity when there are elements , Expand to 13 By analogy .
When using .
Now let's analyze the expansion principle of the last construction method, as shown in the figure below ：

The remaining analysis and expansion methods are similar to the second construction method, and will not be repeated , Just list the conclusions , For your reference ： If you enter an empty set , So when adding the first four elements , Every time it's capacity expansion 1, When the 5 When it's an element , Expand to 6, Then there is the seventh 7 Element is expanding , Expand to 9. The first 10 Expand the capacity when there are elements , Expand to 13 By analogy . If the element in the input set is before 4 If the value of , Add to 4 Elements （ Contains the fourth element ） Every expansion is 1, When added to section 5 When it's an element , Expand to 6, Then there is the seventh 7 Element is expanding , Expand to 9. The first 10 Expand the capacity when there are elements , Expand to 13 By analogy .
Finally, I hope you can make more corrections