Let’s talk about the conclusion first
1.ArrayList maintains an array elementData of type Object
2. When creating an ArrayList object, if a no-parameter constructor is used, the initial elementData capacity is 0. When adding for the first time, the elementData is expanded to 10. If it needs to be expanded again, the elementData is expanded to 1.5 times.
3. If the constructor of the specified size is used, the initial elementData capacity is the specified size. If expansion is required, directly expand the elementData to 1.5 times.
The following is the respective execution of the two logics
After reading this, you will have a clear understanding of the underlying logic of ArrayList.
The underlying expansion mechanism of calling ArrayList’s parameterless constructor
ArrayList list = new ArrayList();
for (int i = 0; i < 10; i + + ) {
list.add(i);
}
for (int i = 0; i <= 15; i + + ) {
list.add(i);
}
list.add(100);
list.add(200);
list.add(null);
for (Object o : list) {
System.out.println(o);
}
This piece of code creates a collection and then adds elements to the collection.
Let’s debug the next breakpoint and enter the source code to analyze step by step
Start debugging!
First, we go to the parameterless constructor of ArrayList. There is an array of elementData here. This array is of type Object and is empty at first. It will be expanded at the bottom layer.
Then enter the loop and perform the list.add method. First, a boxing will be performed to convert the incoming parameter into an Integer.
Let’s jump out of this method and enter the next operation
Let’s take a look at this method. The modCount variable is used to record the number of operations on the collection. This variable will increase each time the add method is entered.
We enter the add method. This method requires us to pass in an added object, an Object type array, and an integer data. This integer data is the size of the array (because we are calling the parameterless constructor of ArrayList, so there is no No size is specified, which is 0)
As you can see, there is an elementData array of type Object, and this array is actually operated on at the bottom level!
Let’s analyze step by step. In the first if statement, we get the length of the elementData array and compare it with the size. If it is the same, execute the following statement. In fact, it is to determine whether expansion is needed.
We enter the grow method
You can see that this method will return an array of type Object, that is, we continue to call the grow method within this method, and we continue to call the grow method with this size + 1 as a parameter.
How we enter
This is the method body of grow. Let’s analyze the source code.
First, we pass in size + 1 as a parameter, which is represented as a minimum size in this method
In the method, first save the length of the elementData array to oldCapacity, and then judge if the length of this array is greater than 0 or elemenData! =DEFAULTCAPACITY_EMPTY_ELEMENTDATA (This is an empty array, that is, it is judged that this array is not an empty array)
The length of our elementData is 0, and we are an empty array, so we will not enter the if statement to execute, but will execute the else statement.
Let’s look at the else statement. An array of type Object will be created in the else statement. The DEFAULT_CAPACITY length is 10
minCapacity is 1, and the Math.max method is used to judge these two numbers and return a maximum value.
This operation is to determine the size of minCapacity and DEFAULT_CAPACITY. If minCapacity does not reach 10, create an array of size 10 and return it. Otherwise, create an array of size minCapacity and return it.
Then returned this array
We continue to execute
As you can see, the size of the Object array has been expanded to 10
And the e object passed in is also put into the first position of the array
At the same time, this size will be + 1 accordingly
Continue execution and return to the add method
At this time the size has changed to 1
and returns a true indicating that the operation has been completed
At this point we can draw a staged conclusion–
If we call the parameterless constructor of ArrayList to add elements in the collection, then an elementData array of type Object will be created at the bottom layer, and the initial expansion will set the capacity to size 10!
Let’s continue to study in depth, how will the array be expanded when it is filled?
Then let’s continue, fill this array up and then add it.
We will set the breakpoint after the previous for loop has been executed (that is, when the array has been filled) and then add elements to analyze how the underlying source code is executed.
The first step is to pack the box. It’s the same as above, so I won’t show the picture.
We still enter the add method and still execute modCount. We can clearly see that due to our previous addition behavior, the size of the collection has changed to 10, and modCount has also changed to 11.
We enter the add method
You can see that this time our array size is 10, and s is also 10 (can be understood as the array subscript)
The if statement still determines whether the lengths of the s and elementData arrays are the same.
Enter the if statement execution and enter the grow method
re-enter
At this time our minCapacity becomes 11, which means our minimum capacity requires 11
Still store the length of the array into oldCapacity
Make a judgment. At this time, the length of our array is greater than 0, and we enter the if statement.
Execute the if statement. There is an additional variable newCapacity to represent the new length.
This is key!
An operation is performed here using ArraysSupport.newLength to expand the array.
Let me briefly introduce this method first
ArraysSupport.newLength method
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {}
Such a public static method requires three parameter values, namely:
oldLength – current length of the array (must be nonnegative): current container capacity, must be a nonnegative value
minGrowth – minimum required growth amount (must be positive): The minimum expansion amount, which must also be a positive number
prefGrowth – preferred growth amount: preferred value-added (capacity expansion)
That is, the original capacity plus one of the following two capacities
Then the first parameter passed in is oldCapacity–>the capacity of the current container
The second parameter minCapacity-oldCapacity–> is the minimum required amount-the existing amount, and the minimum expansion capacity is obtained.
The third parameter oldCapacity >> 2 –> divide the original capacity by 2
We can conclude that! This expansion is to increase the original array by 1.5 times
Then use the Arrays.copyOf method to copy the array, that is, copy the original array and expand it. Here, the original data is copied, and then null is placed in the expanded place, and then the new array is returned.
Continue execution
Go back to grow and return this array
Continue execution
Go back to add, then add the new object to the array, and the collection size + 1
Continue execution
Return a true to indicate that the operation is completed
We can see that the element has been added to the collection
And you can clearly see that all places that have not been assigned a value are null (in the elementData array)
Calling the underlying expansion mechanism of ArrayList’s parameterized constructor
This time we specify the initial size of the collection and put a breakpoint on the loop
We still conduct debug step-by-step analysis
The packing operation is the same as above
Enter the add method, the operation is the same as above
Enter the add method
Determine whether expansion is needed. Obviously there is no need to expand the capacity here, so just put the elements directly into the array.
Until our data has filled the collection and needs to be expanded
We enter the grow method
Continue execution
We will find that the expansion mechanism here is also expanding by 1.5 times, and this is the first expansion.
We can see what the collection looks like, which is a good proof of this.
So far, we have analyzed the underlying expansion mechanism of the two constructors that call ArrayLits.
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Java Skill TreeCollectionList Interface 138648 people are learning the system