Java entry series [7] collection ArrayList
Foreword
In the previous section, we implemented basic functions similar to ArrayList through queuing classes. Of course, there are still a lot of considerations, but they are prepared for us to learn collections. In this section, we will take a look at how common operations methods are performed in the ArrayList source code. Look down.
ArrayList source code analysis
In the previous section we instantiate the following ArrayList in the console and add a piece of data as follows
ArrayList <Integer> list = new ArrayList <> (); list.add (1 );
Initial capacity analysis
First instantiate the ArrayList collection. In the previous section we wrote the basic operation of a queuing class. Finally, we optimized the array capacity by placing it in the constructor. If the array capacity is not given, a capacity is given by default. Let’s take a look at what preparations have been done in advance to initialize a collection in the source code?
public ArrayList ( int initialCapacity) {
if (initialCapacity> 0 ) {
this .elementData = new Object [initialCapacity];
} else if (initialCapacity == 0 ) {
this .elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException ("Illegal Capacity:" +
initialCapacity);
}
}
public ArrayList () {
this .elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
.....
When we initialize the collection and the type is a basic data type, there will be two functions as above, one is the default constructor, and the other is a constructor with parameters. Because the example given does not contain parameters, it is to take the following constructor. Let us look at the variables defined in ArrayList as follows:
// The default initialization capacity is
private static final int DEFAULT_CAPACITY = 10 ;
// Array empty instance
private static final Object [] EMPTY_ELEMENTDATA = ();
// default empty array instance
private static final Object [] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = ();
// operated array
transient Object [] elementData;
// array size
private int size;
// Array maximum capacity
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE-8;
As above, when we don’t give the capacity, we initialize an empty array instance. If we give the capacity, we will follow the first constructor. If the capacity is greater than 0, the array capacity will be our given capacity. Is an empty array instance, otherwise the thrown capacity is illegal. Next comes the second step. When we add element 2, we will see how the add method works.
Add elemental analysis
// Add elements to implement
public boolean add (E e) {
ensureCapacityInternal (size + 1 );
elementData [size ++] = e;
return true ;
}
Let’s continue to look at the ensureCapacityInternal (size + 1) method. This method is used to calculate the array capacity and see the final method implementation, as follows:
private void ensureCapacityInternal ( int minCapacity) {
ensureExplicitCapacity (calculateCapacity (elementData, minCapacity));
}
// computing capacity
Private static int calculateCapacity (Object [] elementData of, int be minCapacity) {
// when not given array capacity or capacity is designated 0 instantiating set, then this time the array is empty array example
IF (== elementData of DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// At this time minCapacity 1, and by Math.max function minCapacity DEFAULT_CAPACITY (default size) [10] Compare Back
return Math.max (DEFAULT_CAPACITY, minCapacity);
}
// When instantiating the given array capacity is greater than 0, directly return the capacity after adding an element (size + 1)
return minCapacity;
}
// Determine whether to expand
private void ensureExplicitCapacity ( int minCapacity) {
modCount ++ ;
// If the calculated array capacity is greater than the array storage length, expand the capacity
if (minCapacity-elementData.length> 0 )
grow (minCapacity);
}
// Expand core implementation
private void grow ( int minCapacity) {
// The actual capacity of the operated array
int oldCapacity = elementData.length;
// New capacity = (actual capacity + actual capacity / 2 and remove the module) that is 1.5 times the old capacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
// If the new capacity is less than the array size, the array size is the new capacity
if (newCapacity-minCapacity <0 )
newCapacity = minCapacity;
// If the new capacity is greater than the defined maximum array size
if (newCapacity-MAX_ARRAY_SIZE> 0 )
newCapacity = hugeCapacity (minCapacity);
// The new array after the expansion
elementData = Arrays.copyOf (elementData, newCapacity);
}
// Calculate the maximum capacity of the array
private static int hugeCapacity ( int minCapacity) {
if (minCapacity <0) // overflow
throw new OutOfMemoryError ();
// If the maximum array size greater than the defined array size, the new maximum capacity is the maximum integer otherwise defined maximum size of the array
return (minCapacity> MAX_ARRAY_SIZE)?
Integer.MAX_VALUE:
MAX_ARRAY_SIZE;
}
The red marked above is the maximum capacity of the array defined by automatic expansion. Here we need to explain what oldCapacity >> 1 means. The school has returned everything to the teacher. After checking the information, it is understood. Here is a memo. >> In the computer, right shift is used. In most cases, we rarely use this operator, but why not directly multiply and divide here? And we also understand it. Using left and right shifts has fast calculation speed. Direct multiplication and division require CPU calculation to consume memory . At first I saw this as aggressive, but it was actually very simple. For example, 32, we have a binary representation of 100,000, how to calculate it, as follows:
(1 * 2 ^ 5) + (0 * 2 ^ 4) + (0 * 2 ^ 3) + (0 * 2 ^ 2) + (0 * 2 ^ 1) + (0 * 2 ^ 0) = 32 + 0 + 0 + 0 + 0 + 0 = 32.
![Java_entry_series_[7]_collection_ArrayList_0.png](http://www.codecoder.top/wp-content/uploads/2019/12/Java_entry_series_7_collection_ArrayList_0.png)
Well, we know that 32 is represented as binary [100000], then 32 >> 1 means that the decimal 32 is converted to binary and the whole is shifted one bit to the right, the left margin is complemented by 0, and the extra right is removed. If it is left, The shift is the opposite (note that the int is 32 bits, but the number is not so large, so the left side must be all 0, we have omitted it here), as follows:
![Java_entry_series_[7]_collection_ArrayList_1.png](http://www.codecoder.top/wp-content/uploads/2019/12/Java_entry_series_7_collection_ArrayList_1.png)
So 32 >> 1 is shifted one bit to the right as shown in the figure, then the calculation result is the same as the first picture above, as follows:
(0 * 2 ^ 5) + (1 * 2 ^ 4) + (0 * 2 ^ 3) + (0 * 2 ^ 2) + (0 * 2 ^ 1) + (0 * 2 ^ 0) = 0 + 16 + 0 + 0 + 0 + 0 = 16.
In order to verify the above results, we print the code to see if it is correct, as follows:
System.out.println (32 >> 1);
From the figure above, we can easily draw the conclusion: if the right shift is >>, then the original data is divided by the power of 2 digits and the modulus is removed. If the left shift is <<, then the original data is multiplied by 2 The power of the number of digits . For example, 11 >> 2, if you divide 11 by 2 ^ 2, the result is 2 immediately. If 11 << 2, then 11 * 2 ^ 2, the result will be 44. Analyzing the source code so far, we can draw the following conclusions:
If no initializing capacity is given, the default initializing capacity is 10 and the timing of initializing the default capacity is when an adding operation is performed.
The automatic expansion size is 1.5 times the original capacity.
The maximum capacity is Integer.MAX_VALUE, which is 2147483647.
Add specified index element analysis
In the above, we have just analyzed the initialization of the collection instance and added elements. Next, we add elements at the specified index position to see, as follows:
public static void main (String [] args) {
ArrayList <Integer> list = new ArrayList <> ();
list.add ( 1 );
list.add ( 2 );
// Add element 2 to index 5
list.add ( 5 , 2 );
}
According to our analysis above, because we did not specify the capacity when we initialized the collection, when we add elements, the capacity of the collection defaults to 10 at this time. Next, we add element 2 at the position of index 5, so is it right? Can it?
![Java_entry_series_[7]_collection_ArrayList_2.png](http://www.codecoder.top/wp-content/uploads/2019/12/Java_entry_series_7_collection_ArrayList_2.png)
We thought that the default capacity was 10, and there was no problem inserting the element at the specified index of 5, but the result was that an exception was thrown. This indicates that the default capacity of the array or the initial capacity provided is not the basis for the judgment, but the actual array Size to judge, in order to prove our point, let’s analyze the method of inserting elements at the specified index position, as follows:
// Add the specified index element
public void add ( int index, E element) {
// Check the index range and confirm whether to add
rangeCheckForAdd (index);
ensureCapacityInternal (size + 1 );
System.arraycopy (elementData, index, elementData, index + 1 ,
size - index);
elementData [index] = element;
size ++ ;
}
private void rangeCheckForAdd ( int index) {
// The index of the element to be added cannot be greater than the actual size of the array or less than 0, otherwise an exception is thrown
if (index> size || index <0 )
throw new IndexOutOfBoundsException (outOfBoundsMsg (index));
}
Some people may ask, does it have any meaning or function to analyze source code? There are too many functions. One is to understand the underlying principles behind the so-called “pits.” The other is to learn and write high-quality code. Three others and so on. Now that we have an understanding of the principle, let’s do a topic, as follows:
public static void main (String [] args) {
ArrayList <Integer> list = new ArrayList <> ();
list.add ( 1 );
list.add ( 2 );
list.add ( 3 );
list.add ( 4 );
list.add ( 5 );
list.add ( 6 );
list.add ( 7 );
list.add ( 8 );
list.add ( 9 );
list.add ( 10 );
list.add ( 6,2 );
}
Because we know that the default initialization capacity is 10, when adding elements to 11, that is, inserting element 2 at the position of index 6 above, the capacity will be automatically expanded at this time and the size is 15 (if you still do n’t understand, it is recommended to review the next chapter again) article). Next, let’s analyze the trimToSize method.
trimToSize analysis
First we look at the following piece of code:
public static void main (String [] args) {
ArrayList <Integer> list = new ArrayList <> (20 );
list.add ( 1 );
list.add ( 2 );
list.add ( 6,2 );
list.trimToSize ();
}
As mentioned above, we provide an initial capacity of 20, but as a result, we only added only three elements, and the remaining 17 elements in the array occupy a pit. So at this time, to solve such problems, we introduced the trimToSize method to solve The following three questions
Reduce the collection to the actual storage size of the current collection
Minimize storage of collection instances
When we need to shrink collections and minimize storage
public void trimToSize () {
ModCount ++ ;
// if the array size is less than the actual capacity of the array
IF (size < elementData.length) {
// If the actual size of the array is an array of empty instance 0, or replication array to the current array size
elementData = (size = = 0 )
? EMPTY_ELEMENTDATA
: Arrays.copyOf (elementData, size);
}
}
remove analysis
In java, you can delete the specified element at the index position, or you can directly delete the element. Let’s first look at deleting elements based on the index, as follows:
![Java_entry_series_[7]_collection_ArrayList_3.png](http://www.codecoder.top/wp-content/uploads/2019/12/Java_entry_series_7_collection_ArrayList_3.png)
// Delete the specified index element and return the value of the deleted element
public E remove ( int index) {
// Judge whether the index is smaller than the actual size of the array, otherwise throw the
rangeCheck (index);
modCount ++ ;
// Get the index element
E oldValue = elementData (index);
// Get the number of elements to be copied when copying the array
int numMoved = size-index-1 ;
if (numMoved> 0 )
System.arraycopy (elementData, index +1 , elementData, index,
numMoved);
// Set the deleted element to empty, so that the garbage collector can recycle
elementData [-size] = null ;
return oldValue;
}
If we want direct elements, such as deleting element 2 added above, the delete method is particularly overloaded at this time, and its parameter is an object, so we need to convert element 2 to a wrapper class, such as the following:
![Java_entry_series_[7]_collection_ArrayList_4.png](http://www.codecoder.top/wp-content/uploads/2019/12/Java_entry_series_7_collection_ArrayList_4.png)
// delete the specified element
public boolean remove (Object o) {
// if the object is empty
if (o == null ) {
// traverse the array
for ( int index = 0; index <size; index ++ )
// find the array Empty element
if (elementData [index] == null ) {
// find out the index where the element is located, fast delete
fastRemove (index);
// return delete successfully
return true ;
}
} else {
// If the object is not empty
for ( int index = 0; index <size; index ++ )
// Find the elements in the array that meet the conditions
if (o.equals (elementData [index])) {
// Find The index where the element is located is quickly deleted
fastRemove (index);
// Remove successfully
; return true ;
}
}
// Return delete failed
return false ;
}
// Fast delete (essentially copy)
private void fastRemove ( int index) {
modCount ++ ;
int numMoved = size-index-1 ;
if (numMoved> 0 )
System.arraycopy (elementData, index +1 , elementData, index,
numMoved);
elementData [ --size] = null ;
}
In fact, we see that many of the operation methods in the source code are copied internally, such as deleting, adding collections, etc. At the same time, we notice that when copying is involved, there are situations such as the above setting being empty. Let ’s take a look What’s the point of doing this under research?
public static void main (String [] args) {
ArrayList <Integer> list = new ArrayList <> ();
list.add ( 1 );
list.add ( 2 );
list.add ( 3 );
list.add ( 4 );
list.add ( 5 );
list.add ( 6 );
Integer [] array = list.toArray ( new Integer [0 ]);
System.arraycopy (array, 3, array, 2 ,
3 );
for ( int i = 0; i <array.length; i ++ ) {
System.out.println (array [i]);
}
}
As above, we simulate the deletion by calling the copy method provided by the system. We delete the 3 elements in the array, and then print the elements in the array, as follows:
According to the call to copy, the starting position of the copy is index 3, and then the elements 4, 5, and 6 in the array are copied, but the elements 3, 4, and 5 in the original array are overwritten, but at this time element 6 There is no element coverage, so there are still 6 elements in the array, so for GC, we need to set element 6 to empty and length to 5, which is the optimal code. It also reaches elementData [ –size] = null equivalent effect.
Summary
In this section, we analyze the source code of ArrayList in detail. ArrayList is essentially implemented by dynamically expanding a one-dimensional array . At the same time, it introduces several commonly used methods. Of course, there are no more traversal through lambda expressions such as those in java 8. Explain in detail one by one. In the follow-up study or project, I used the places that I need to add. I will go back and research again. For the time being, we will continue to learn other collections and analyze the source code in the next section. Read, see you in the next section.
Java entry series [1] string creation method
Java entry series [2] string features
Java entry series [3] stringbuilder string buffer
Java entry series [4] packaging class
Java entry series [5] inheritance abstract classes interfaceson
Java entry series [6] Principles of dynamic array
Java entry series [7] collection arraylist
Java entry series [8] principles of doubley linked list alogrithm
Java entry series [9] linkedlist source code analysis
Java entry series [10] Hash algorithm principle
Java entry series [11] Hashtable source code analysis
Java entry series [12] Hashcode and equals
Java entry series [13] Principles of the read-black tree algorithmn method
Java entry series [14] Hashmap source code ananlysis
Orignal link:https://www.cnblogs.com/CreateMyself/p/11442734.html