Understand the ArrayList expansion policy from the source level

ArrayList is used very much in our daily development. We know that ArrayList is implemented internally by an Object array, and the length of an array cannot be changed once it is defined.

So how does ArrayList scale?

Let’s start by looking at what member variables are in the ArrayList class.

Member variables of ArrayList

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

/** * Shared array instance used for empty instances. * Shared array instance used for empty instances. * /
private static final Object[] EMPTY_ELEMENTDATA = {};

/** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA To know how much to inflate when * first element is added. * * The shared empty array instance is used with the default size empty instance. * We distinguish DEFAULTCAPACITY_EMPTY_ELEMENTDATA from EMPTY_ELEMENTDATA in order to know how much to expand when adding the first element. * /
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be Expanded to DEFAULT_CAPACITY when the first element is added. * * Object[] Used to actually store the elements of the ArrayList. The capacity of an ArrayList is the length of the array. * When the first element is added, any empty ArrayList (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) * capacity will be increased to DEFAULT_CAPACITY. * /
transient Object[] elementData; // non-private to simplify nested class access

/** * The size of The ArrayList (The number of elements it contains). * The size of The ArrayList (The number of elements it contains)@serial* /
private int size;
Copy the code

How to understand size and capacity in ArrayList?

Size is used to record the number of elements in the elementData array in the ArrayList instance, and Capacity is the length of the elementData array (both used and unused array space). If ArrayList is used as a drinking cup, capacity is the volume of the cup, which represents how much water the cup can hold, and size is the volume of water the cup already holds. The glass may or may not be full of water.

To use a class, you first create an instance of the class, so let’s take a look at what constructors ArrayList has, which is what we care about.

Constructor of the ArrayList

1. No-parameter construction method

The comment says, construct an empty list with an initial capacity of 10. In fact, delayed initialization is used in Java8. Instead of creating an array of length 10 right away with the no-argument constructor, the elementData array is initialized when the add method is called to add the first element (as you’ll see later).

/** * Constructs an empty list with an initial capacity of ten. */
public ArrayList(a) {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

2, specify the initial capacity construction method

If the initialCapacity is greater than 0, create an array of objects with the specified size. If the initial capacity is zero, elementData points to the shared empty array instance EMPTY_ELEMENTDATA. If the initial capacity is less than zero, throw an IllegalArgumentException.

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
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); }}Copy the code

3. Specify the constructor of the initial collection

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if((size = elementData.length) ! =0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

Question 2: Why do you define two Object arrays in the ArrayList source? EMPTY_ELEMENTDATA and DEFAULTCAPACITY_EMPTY_ELEMENTDATA

As you can see from the above source code, both of these constants are references to an empty Object array, and both represent the empty state of an ArrayList instance, that is, there are no elements in the elementData array. EMPTY_ELEMENTDATA uses the constructor ArrayList(int initialCapacity) (the initialCapacity size is 0) and the constructor ArrayList(Collection<? Extends E> c) with an initial collection size of 0. DEFAULTCAPACITY_EMPTY_ELEMENTDATA is used when the no-parameter constructor is used.

Now that we have the constructor, let’s look at how to add an element to the ArrayList container.

Add elements

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
Copy the code

The add method adds an element to the ArrayList. To ensure the array size inside the ArrayList, the add method first calls the ensureCapacityInternal method, MinCapacity is the actual number of elements in the ArrayList, size + 1.

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
Copy the code

EnsureCapacityInternal calls the calculateCapacity method internally to calculateCapacity, and if the ArrayList is created with a no-argument constructor, If (DEFAULTCAPACITY_EMPTY_ELEMENTDATA == DEFAULTCAPACITY_EMPTY_ELEMENTDATA); if (DEFAULTCAPACITY_EMPTY_ELEMENTDATA); Constructs an empty list with an initial capacity of ten. Constructs an empty list with an initial capacity of ten

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // If the ArrayList is empty, the capacity is the maximum of DEFAULT_CAPACITY and minCapacity
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
Copy the code

I read math. Max (DEFAULT_CAPACITY, minCapacity); DEFAULT_CAPACITY == DEFAULTCAPACITY_EMPTY_ELEMENTDATA == DEFAULTCAPACITY_EMPTY_ELEMENTDATA == DEFAULTCAPACITY_EMPTY_ELEMENTDATA Why even compare. AddAll (Collection<? Extends E> c) extends E> c) extends E> c) extends E> c) extends E> C) extends E> C) extends E> C) extends E> C) extends E> C) extends E> C We should take the maximum DEFAULT_CAPACITY and minCapacity.

MinCapacity is equal to the actual number of elements in ArrayList + the number of new elements. MinCapacity is the minimum length of the expanded Object array.

The ensureExplicitCapacity method ensures that the ArrayList has sufficient capacity to store the new elements.

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
Copy the code

If the capacity is insufficient, the grow method is called.

Scale operation

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

/**
 * 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;
    // The new capacity is expanded to 1.5 times the original capacity
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        // If the new capacity is still less than the minimum capacity required, make the new capacity equal to the minimum capacity required
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // If the new capacity exceeds Integer.MAX_VALUE - 8, the calculation continues
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // The minimum capacity required is close to size
    elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code

Int newCapacity = oldCapacity + (oldCapacity >> 1); OldCapacity >> 1 is a right shift of a bit operation. A right shift is equal to dividing by 2. NewCapacity is 1.5 times the previous capacity.

elementData = Arrays.copyOf(elementData, newCapacity); Expand the elementData array.

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

Question 3: Does ArrayList expand by 1.5 times the original capacity each time?

As you can see from the source code, when an ArrayList instance is created using the no-parameter constructor and the add method is called to add the first element, the calculateCapacity method returns the default initial capacity DEFAULT_CAPACITY of 10; When an ArrayList instance is created with the specified initial capacity and the addAll method is called to add multiple elements, a larger array (no larger than integer.max_value) will be created to hold the elements.

Question 4: How to optimize the add operation of ArrayList?

Capacity expansion requires data to be moved, which affects performance. The key to tuning is to avoid internal scaling within the ArrayList as much as possible. For add operations, if the number of elements to be added is known, it is best to create an ArrayList instance using the constructor that specifies the initial capacity or to execute the ensureCapacity method before adding the elements to ensure that there is enough capacity to hold the elements for the add operation.

Shoulders of giants

Github.com/weizhiwen/k…

Stackoverflow.com/questions/5…

Stackoverflow.com/questions/3…

“More exciting content please follow the public geekymv, like please share with more friends oh”