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.
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:
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?
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:
// 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:
// 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