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

 

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

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

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

 

 

// 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

 

 

// 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