Let's talk about how ArrayList is dynamically resized and what kind of mechanism is it?

ArrayList Source code analysis and overall analysis

ArrayList And LinkedList contrast

1） Expansion code

The above two articles , Click for details , This chapter mainly analyzes the capacity expansion mechanism ,ArrayList How to expand the capacity ？

    /** * Default initial capacity. *  Default initial capacity  */
    private static final int DEFAULT_CAPACITY = 10;

 private void ensureCapacityInternal(int minCapacity) {
    
 		// Determine the initialization elementData Is it an empty array , That is, there is no length 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    
            //Math.max Get the maximum ,DEFAULT_CAPACITY=10;
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
		
        ensureExplicitCapacity(minCapacity);
    }

 /** * Judge the present ArrayList Whether expansion is needed  **/
 private void ensureExplicitCapacity(int minCapacity) {
    
        // Quick error reporting mechanism 
        modCount++;

        //minCapacity If it is greater than the actual elementData The length of , Then it means elementData The length of the array is not enough , If it's not enough, it's necessary to increase elementData Of length
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

2）minCapacity Real understanding

When to go for real capacity expansion ？ That must be minCapacity - elementData.length > 0, That is to say elementData Its length is not enough .
minCapacity The size follows directly add The call has something to do with . There are two situations ：

1. add(E e) When called ,minCapacity=size + 1, for the first time add When , That is to say minCapacity=1, Determine the initial value as 10, So the final Math.max obtain minCapacity The size is also 10;
2. add(int index, E element) Call the parameterized construction initialization ‘ Minimum array capacity required after adding elements ’ Is the actual number of elements after adding elements

3）grow Core expansion logic

// The maximum capacity 
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

// Increase the capacity to ensure that it can accommodate at least the number of elements specified by the minimum capacity parameter .
// Parameters ：minCapacity –  Minimum capacity required 
private void grow(int minCapacity) {
    
        // Capacity size before assignment 
        int oldCapacity = elementData.length;
        // New capacity size = Previous capacity size 1.5 times 
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // Capacity after expansion < Previous capacity 
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // Capacity after expansion > The maximum capacity 
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //Arrays.copyOf Space for time expansion strategy 
       
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

private static int hugeCapacity(int minCapacity) {
    
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

call Arrays.copyOf Methods will elementData When the array points to a new memory space newCapacity Continuous space of
And will elementData Copy the data to the new memory space

4） Why? ArrayList The maximum array size of is Integer.MAX_VALUE-8？

Reference article ： Please click here

2^31 = 2,147,483,648 , As one's own needs 8 bytes Storage size Array of 2,147,483,648

5） Code debugging , Verify expansion logic

We wrote an article about reflection before ：
How to use reflection to get attribute values
Yes elementData We also get through reflection .

test demo as follows ：

public static void main(String[] args) {
    
		List<Integer> list = new ArrayList<>();
		//  Define an array , Lecture put 21 It's worth , See how to dynamically expand capacity ？
		for (int i = 0; i < 21; i++) {
    
			list.add(i);
			//  Without adding an element , Are obtained through reflection mechanism elementData value , And print 
			Class<ArrayList> arrayListClass = ArrayList.class;
			try {
    
				Field field = arrayListClass.getDeclaredField("elementData");
				field.setAccessible(true);
				Object[] objects = (Object[]) field.get(list);
				System.out.println(" The first " + i + " After the expansion of elements elementData： " + objects.length);
			} catch (NoSuchFieldException | IllegalAccessException e) {
    
				e.printStackTrace();
			}
		}
	}

Output results ：

The first 0 After the expansion of elements elementData： 10
The first 1 After the expansion of elements elementData： 10
The first 2 After the expansion of elements elementData： 10
The first 3 After the expansion of elements elementData： 10
The first 4 After the expansion of elements elementData： 10
The first 5 After the expansion of elements elementData： 10
The first 6 After the expansion of elements elementData： 10
The first 7 After the expansion of elements elementData： 10
The first 8 After the expansion of elements elementData： 10
The first 9 After the expansion of elements elementData： 10
The first 10 After the expansion of elements elementData： 15
The first 11 After the expansion of elements elementData： 15
The first 12 After the expansion of elements elementData： 15
The first 13 After the expansion of elements elementData： 15
The first 14 After the expansion of elements elementData： 15
The first 15 After the expansion of elements elementData： 22
The first 16 After the expansion of elements elementData： 22
The first 17 After the expansion of elements elementData： 22
The first 18 After the expansion of elements elementData： 22
The first 19 After the expansion of elements elementData： 22
The first 20 After the expansion of elements elementData： 22

We can clearly see the expansion

• When list size <10, Capacity is the default value, that is 10
• When 10=<list<15, Capacity of 1.5 times , That is to say 10*1.5=15
• When 15=<list<21, Capacity expansion 15 times , That is to say 15*1.5=22.5, The whole number is 22

Be careful ： If not field.setAccessible(true); What's going to be output ？？