Understanding of ArrayList expansion method

Directory

foreword

ArrayList source code understanding

1. ArrayList construction method

1.1 ArrayList no-argument construction method: initialize the internal array to an empty array.

1.2 ArrayList has parameter construction method 1: initialize according to the specified capacity

1.3 Parameter construction 2: public ArrayList(Collection c): Initialize according to the incoming Collection

2. ArrayList expansion

2.1, add () method

2.2. Determine whether to expand the method ensureExplicitCapacity(), expand the core method grow()

Summarize

---

Foreword

ArrayList implements the List interface, and the bottom layer of ArrayList is an array, which is equivalent to a dynamic array. Compared with arrays in Java, its capacity can grow dynamically. Applications can use the ensureCapacity operation to increase the capacity of an ArrayList instance before adding a large number of elements.

ArrayList source code understanding

1.ArrayList construction method

1.1 ArrayList parameterless constructor: initialize the internal array to an empty array.

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};
    }

1.2 ArrayList has a parameter construction method 1: initialize according to the specified capacity

 public ArrayList(int initialCapacity) {
              //If initialCapacity is greater than 0, point the array to a new array with initialCapacity
        if (initialCapacity > 0) {
            this. elementData = new Object[initialCapacity];
              //If initialCapacity is equal to 0, point the array to an empty array
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
              // throw an exception in other cases
            throw new IllegalArgumentException("Illegal Capacity: " +
                                               initialCapacity);
        }
    }

2.ArrayList expansion

When we add elements to this collection through the add() method of ArrayList, what should we do if the collection is full? This involves the dynamic expansion of ArrayList.

2.1, add() method

public boolean add(E e) {
//Determine whether to expand
        ensureCapacityInternal(size + 1); // Increments modCount!!
 //add element
        elementData[size + + ] = e;
        return true;
    }

2.2. Determine whether to expand the method ensureExplicitCapacity(), expand the core method grow()

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

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

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

    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

   
    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 void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //If the array is still empty, the minimum capacity is 10 and the maximum value of the required minimum capacity
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        //If the minimum capacity is greater than the capacity of the array, expand the capacity
        if (minCapacity - elementData. length > 0)
        //Pass in the minimum capacity for expansion
            grow(minCapacity);
    }
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;//The capacity of the current array
        int newCapacity = oldCapacity + (oldCapacity >> 1);//The capacity of the new array is increased to 1.5 times the previous
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;//The capacity of the new array is the required minimum capacity
        if (newCapacity - MAX_ARRAY_SIZE > 0)
        //Call the hugeCapacity() method to ensure that the capacity will not overflow
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays. copyOf(elementData, newCapacity);
    }
private static int hugeCapacity(int minCapacity) {
//If the required minimum capacity is less than 0, it indicates that the maximum capacity has been exceeded
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
 //If the minimum capacity is greater than Integer.MAX_VALUE - 8, return Integer.MAX_VALUE, if not, return Integer.MAX_VALUE - 8
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

Summary

1. If the array is an empty array, when adding elements for the first time, the array capacity will be 10.
2. When the capacity of the array is insufficient, expand the capacity by 1.5 times the original capacity.
3. When the capacity of the array exceeds the range of Integer.MAX_VALUE – 8 and Integer.MAX_VALUE, an error will be thrown.