Why is ArrayList dynamic?

Anyone who has learned ArrayList systematically should have basic knowledge that ArrayList is a List based on dynamic array. You don’t have to worry about errors like ‘ArrayOutOfBoundary’, because the length, or size, is not static,unless you give it a boundary,or capacity when you initialize an ArrayList. How do Java achieve this function? Talk is cheap, read the code.


Before that, I believe it’s fairly essential to distinguish the differences between Capacity and size.
Capacity in numbers return the length of the Array, putting the null elements into consideration;
Size returns how many non-null elements the array contains.
For example:

int[] a = new int[10];
for(int i=0;i<5;i++){
    a[i]=i;
}
/*
The size of a is 5,while the capacity is 10,which never changes once you new it.
*/

Reading Comprehension Time!

//The default_capacity of ArrayList
private static final int DEFAULT_CAPACITY = 10;

//Empty Array Elements
transient Object[] elementData;

//default initial capacity
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

private int size;

//When using the default constructor
public ArrayList() {
    this.elementData =DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//size=10 if you just new the ArrayList using default constructor; 
public boolean add(E e) {
    ensureCapacityInternal(size +1);// modCount incremented
    elementData[size++] = e;
    return true;
}

/*initialize the ArrayList size to 10;
 * 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 ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

/*Why spend so much on pursing minimum capacity at the cost of
 *making the code so complicated?
 *To save the precious memory, I guess.
 */


//When the programmer use the constructor with parameters that limits the size;
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity)
            /*if the size is smaller than 10, it's no big deal if you create a 10 one,
            *since you can trim it;
            *but this is not the case when it's the opposite.
            */
             }
        return minCapacity;
    }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//modCount is to record how many times the capacity has changed;
        if (minCapacity - elementData.length > 0)
            /*if the size of Array at present is larger than the capacity of Array;
             *it works well even when minCapacity is set negative
             */
            grow(minCapacity);//literally, grow:)
    }


// There's a upper limit of the size of ArrayList
//Why MAX_VALUE-8? Because an array need a 8 bytes(size of an int)of memory 
//to store the size of itself
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;


private void grow(int minCapacity) {
    int oldCapacity = elementData.length;//oldCapacity is size
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //The new capacity is the 1.5 times larger than the old one
    if (newCapacity - minCapacity < 0)
        //make sure capacity is the smallest
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        //Of course, if the array is too big...
        newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
    //create an object array(a new one!) with all value from
    //elementData and a capacity of newCapacity 

    }

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) 
        // Capacity can't be a negative number,anyway
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        //if capacity is too big
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

Both remove(int index) and remove(Object o) calls fastRemove(int index):

 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; // clear to let GC do its work
    }

As you can see, capacity of array does not change when elements are removed. This is because if you clear the unused memory immediately, then you need to take extra time to allocate them when you eventually decide to use them, which is low-efficient.

Conclusion:

Concrete and detailed analysis is in annotation of the code above.

Three core private methods of ArrayList, ensureCapacityInternal(), ensureExplicitCapacity(), and grow() (all parameters ignored) explain why it is dynamic. Capacity in the very beginning is 0 after newed by defualt constructor until add() is called. When the programmer calls either add(int index, Object o) or add(Object o), and it happens that the size of the list is larger than the present capacity, ensureCapacityInternal() will be called. It first decides how much memory to allocate , then JVM calls ensureExplicitCapacity(), and finally grow() method is called. Method grow() directly expands the capacity by 1.5 times and in the end System.copyOf() copy everything of the array with small capacity to the new 1.5 larger one, and returns the new array to programmers. Since these core methods are private and encapsulated, ArrayList shows up in a dynamic appearance.

发表评论

电子邮件地址不会被公开。 必填项已用*标注