Detailed explanation of ArrayList expansion, expansion principle [easy to understand]

Hello everyone , I meet you again , I'm your friend, Quan Jun .

ArrayList Detailed explanation of capacity expansion , Expansion principle

ArrayList It's based on arrays , It's a dynamic array , Its capacity can grow automatically . ArrayList Not thread safe , It can only be used in single thread environment . Realized Serializable Interface , So it supports serialization , Able to transmit... Through serialization ; Realized RandomAccess Interface , Support fast random access , In fact, it is a quick access through subscript sequence number ; Realized Cloneable Interface , Can be cloned .

Dynamic capacity

One initialization

First, there are three ways to initialize ：

public ArrayList();

Copy

Default constructor , The internal array will be initialized with the default size

public ArrayList(Collection<? extends E> c)

Copy

Use one ICollection Object to construct , And add the elements of the collection to ArrayList

public ArrayList(int initialCapacity) 

Copy

Initializes the internal array with the specified size

The latter two ways are understandable , By creating objects , Or specify the size to initialize the internal data . Let's focus on the implementation of the parameterless constructor ：

/** * Constructs an empty list with an initial capacity of ten. */
    public ArrayList() { 
   
      // DEFAULTCAPACITY_EMPTY_ELEMENTDATA It's an empty array 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { 
   };

Copy

You can see that its default array is length 0. And before JDK1,6 in , The parameterless constructor code has an initial length of 10. JDK6 The code is like this ：

public ArrayList() { 
   
    this(10);
    }
  public ArrayList(int initialCapacity) { 
   
    super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
    this.elementData = new Object[initialCapacity];
    }

Copy

Next , If you want to expand the capacity , It must be ArrayList.add In the method . Let's take a look at the implementation .

Two Ensure internal capacity

Let's take parameterless construction as an example , On initialization , The array length is 0. Now I'm going to add data , How does the length of the array change ？

public boolean add(E e) { 
   
        // Ensure internal capacity ( By judgment , If enough, do not operate ; If the capacity is insufficient, expand the capacity to ensure the internal capacity )
        ensureCapacityInternal(size + 1);  // ①Increments modCount!!
        elementData[size++] = e;//②
        return true;
    }

Copy

① ensureCapacityInternal The English of the method name is roughly “ Ensure internal capacity ”,size It represents the number of elements before adding , Is not ArrayList The capacity of , Capacity should be array elementData The length of .ensureCapacityInternal This method compares the capacity of the existing element number array . See if you need to expand , Then expand the capacity . ② Is to put the element to be added into the corresponding array . Let's look at it in detail ensureCapacityInternal(size + 1);

// ①  How to judge and expand .
private void ensureCapacityInternal(int minCapacity) { 
   
      // If the array is actually stored   It's an empty array , Then the minimum required capacity is the default capacity 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
   
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) { 
   
        modCount++;
        // If the array （elementData) The length of is less than the minimum required capacity （minCapacity） Capacity expansion 
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    /** * Default initial capacity. */
    private static final int DEFAULT_CAPACITY = 10;

Copy

above ,elementData Is an array used to store the actual content .minExpand Is the minimum expansion capacity . DEFAULTCAPACITY_EMPTY_ELEMENTDATA Shared empty array instances are used for empty instances of the default size . According to the incoming minimum required capacity minCapacity To compare with the capacity length of the array , if minCapactity Greater than or equal to the array capacity , It needs to be expanded .

3、 ... and Capacity expansion

/* * Add capacity , To ensure that it can at least accommodate  * The number of elements specified by the minimum capacity parameter . * @param mincapacity Minimum capacity required  */
    private void grow(int minCapacity) { 
   
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //>> An operation , Move one right .  The whole is equivalent to newCapacity =oldCapacity + 0.5 * oldCapacity 
        // jdk1.7 Using bit operation is faster than the previous calculation 
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
       //jdk1.7 Here, the maximum number judgment of the number of elements is added ,jdk1.7 In the past, there was no maximum judgment ,MAX_ARRAY_SIZE  by int Subtract... From the maximum 8（ It is not clear why this value is used for comparison ）
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //  The most important method of copying elements 
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

Copy

in summary ,ArrayList Equivalent to not specifying initialCapacity The delay is used to allocate the object array space , Assign only when the element is first inserted 10（ Default ） An object space . If there is 20 Data needs to be added , Then they will separate at the first time , take ArrayList The capacity of becomes 10 ( As shown in Figure 1 ); After that, the capacity will be expanded according to 1.5 Times the growth . That is, when adding the second 11 Data ,Arraylist Continue to expand capacity and become 10*1.5=15( As shown in Figure 2 ); When the 16 When a data , Continue to expand capacity and become 15 * 1.5 =22 individual ( As shown in Figure 4 ).：

**　　 When adding the first element to the array , The array capacity is 10.**

**　　 Add... To the array 10 Element time , The array capacity is still 10.**

**　　 Add... To the array 11 Element time , Expand the array capacity to 15.**

**　　 Add... To the array 16 Element time , Expand the array capacity to 22.**

Each expansion is through Arrays.copyOf(elementData, newCapacity) In this way .

**　　 Compare and summarize ：**

This paper introduces ArrayList The whole process of dynamic capacity expansion . If we use nonparametric construction , The initial array capacity is 0, When you actually add an array , To really allocate capacity . Every time according to 1.5 times （ An operation ） The ratio of... To copeOf Expansion by . stay JKD1.6 The implementation in is , If we use nonparametric construction , The initial array capacity is 10, Each time through copeOf After expansion, the capacity will be the original 1.5 times , The above is the principle of dynamic capacity expansion .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/131193.html Link to the original text ：https://javaforall.cn