Capacity and expansion mode of ArrayList in Java

Directory view the source code of JDK1.8 ArrayList 1, the default initial capacity is 102, the maximum capacity is Integer.MAX_VALUE-83, expansion mode: Java ArrayList () expansion principle first look at the attributes and construction method of ArrayList, this is more important to see the initialization scene, and look at other scenes below, which is also quite simple

View the source code for JDK 1.8 ArrayList

1. The default initial capacity is 10

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

2. Maximum capacity is Integer.MAX_VALUE-8

    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

Reason: Before referring to others, it needs to be verified:

The array object has 1 additional metadata to represent the size of the array;

The array length size is of int type, with 32 bits and 1 sign bit, so the maximum length is Integer. MAX_VALUE = 2 ^ 31 = 2,147,483,648;

8bytes is used to store size;

3. Expansion method:

(1) First, a desired minimum capacity minCapacity is passed in;

(2) New capacity newCapacity = oldCapacity + (oldCapacity > > 1), that is, the new capacity is equal to 1.5 times of the original capacity;

(3) If minCapacity > newCapacity, newCapacity = minCapacity;

(4) If newCapacity > Maximum capacity MAX_ARRAY_SIZE, newCapacity = hugeCapacity (minCapacity);

(5) Copy original data with new capacity

   /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        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;
    }

Java ArrayList () Expansion Principle

Usually, ArrayList () is used directly. Today, I will look at the expansion principle of ArrayList ().

First, look at the attributes and construction method of ArrayList, which is more important

Look at the attributes first

// ArrayList  Default capacity size 
private static final int DEFAULT_CAPACITY = 10;
// 1 Shared empty arrays ,  Use when the instance is empty 
private static final Object[] EMPTY_ELEMENTDATA = {};
// 1 Shared empty arrays ,  Using the default  size  Use when an empty instance of 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/*
 Storage  ArrayList  Array buffer of element 
 Focus 1: ArrayList  Is the length of the array buffer 
 Focus 2:  It can also be seen from this element  ArrayList()  The bottom layer is 1 A  Object[]  
add  No. 1 1 Elements ,  Any with  elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA  Empty of  ArrayList  Will be extended to  DEFAULT_CAPACITY
*/
transient Object[] elementData;
// ArrayList  The size of ,  What we usually use  list.size()  This is recorded at the bottom  size
private int size;
// ArrayList  Maximum 
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

Look at the constructor again, the constructor with parameters

/*
 Parametric constructor ,  Parameter is capacity size ,  For example :  Initialization 1 Containers are  20  Type is  Integer  Adj.  ArrayList
ArrayList<Integer> list = new ArrayList<>(20);
*/
public ArrayList(int initialCapacity) {
 /*
  Initialization capacity  > 0, elementData  To an array of initialized capacity 
  Initialization capacity  = 0, elementData = EMPTY_ELEMENTDATA ( Empty array )
  Initialization capacity  < 0,  Throw an exception directly 
 */
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

Constructor with parameter Collection

/*
 Will 1 Parameters are  Collection  Converts the collection of to  ArrayList
*/
public ArrayList(Collection<? extends E> c) {
    // Collection  Convert to an array  Object[]  Type  
    elementData = c.toArray();
    //  Determines whether the current object size is equal to  Collection  Equal in length and not equal to  0, false  Words  elementData  Is equal to an empty array 
    if ((size = elementData.length) != 0) {
     // c.toArray()  May not return correctly 1 A  Object[]  Array, so use the  Arrays.copyOf()
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

Constructor without parameters

/*
 Constructors without parameters are just like we usually use 1 Sample ,  Direct  new 1 A  ArrayList  No parameters need to be passed 
 Construct method directly sets the  elementData  Initialized to  DEFAULTCAPACITY_EMPTY_ELEMENTDATA ( Empty array )
*/
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

Seeing this, we find that we can pass parameters directly to the constructor with parameters, but how does the default constructor initialize the capacity?

The add () method can get the answer directly.

public boolean add(E e) {
 //  This 1 Line is the key ,  Look below 
    ensureCapacityInternal(size + 1);
    //  Append an element to the end of the collection   If the current  size = 10 size++  Append to the  11  Bit 
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal () method call

private void ensureCapacityInternal(int minCapacity) {
 /*
 calculateCapacity()  Method ,  Returns when it is first initialized  10,  Other conditions return to the current  size + 1
 ensureExplicitCapacity()  Method ,  Call expansion 
 */
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) { 
 /*
  Using the parameterless constructor to create  ArrayList  Collection of ,  At this time 1 It must be equal 
 */
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
     /*
      Returns the maximum value by comparing two numbers ,  At this time  Math.max(10, 1); 
      Default capacity ,  It comes from this 
     */
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //  If it is not equal, only the current  size + 1
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    //  Increment ,  Record modification / Number of updates 
    modCount++;  
    
     //  Initialization : 10 - 0 > 0
     //  Others : size + 1 > 0
    if (minCapacity - elementData.length > 0)
     //  Expansion operation 
        grow(minCapacity);
}
private void grow(int minCapacity) {
    //  Old length ,  When initialized  0, 
    int oldCapacity = elementData.length;
    //  New length at this time  0 + (0 >> 1), newCapacity = 0
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //  Initialize the scene : 0 - 10 < 0 ? true newCapacity = 10
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //  Initialize the scene : 10 - 2147483639 > 0  Return  false
    if (newCapacity - MAX_ARRAY_SIZE > 0)
     //  Very long to execute this method ,  Must be greater than  MAX_ARRAY_SIZE 1 Not at all 
        newCapacity = hugeCapacity(minCapacity);
    //  Copy the elements in the original array ,  And expansion 
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Look at the initialization scene, and look at other scenes below, which is quite simple

private void ensureCapacityInternal(int minCapacity) {
 /*
 calculateCapacity()  Method ,  Normal expansion return  size + 1,  For example  10 + 1,  Because the default length is  10  When you add data again, you will start to expand 
 ensureExplicitCapacity()  Method ,  Call expansion 
 */
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) { 
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    /*
 elementData  Not equal to an empty array 
  Returns the current  size + 1,  I.e.  10 + 1  Return  11
 */
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    //  Increment ,  Record modification / Number of updates 
    modCount++;  
    
    //  Others : 11 - 10 > 0 true,  Triggered expansion ,  If the current table below is  5  Words  5 + 1 =6, 6 < 10  Yes ,  There will be no expansion at this time 
    if (minCapacity - elementData.length > 0)
     //  Expansion operation 
        grow(minCapacity);
}
private void grow(int minCapacity) {
    //  Old length  10
    int oldCapacity = elementData.length;
    //  New length at this time  10 + (10 >> 1), newCapacity = 15
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 15 - 11 < 0 ? false
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 15 - 2147483639 > 0  Return  false
    if (newCapacity - MAX_ARRAY_SIZE > 0)
     //  Very long to execute this method ,  Must be greater than  MAX_ARRAY_SIZE 1 Not at all 
        newCapacity = hugeCapacity(minCapacity);
    //  Copy the elements in the original array ,  And expansion  newCapacity = 15
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Conclusion

1. The key to triggering expansion is

Whether the current size + 1 is larger than the current capacity, if it is larger than the capacity, it proves that the set is not enough and needs to be expanded. If it is small and the current capacity, it proves that the collection still has capacity and does not need to be expanded!

2. The size of each expansion is

    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

0

Namely: 1.5 times the current capacity!