Detailed explanation of ArrayList expansion

Hello everyone , I meet you again , I'm your friend, Quan Jun .

This article discusses ArrayList Expansion process

ArrayList At the bottom is an array elementData, Used to store inserted data . The initial size is 0, When data is inserted , Default size DEFAULT_CAPACITY = 10. If you're creating ArrayList When it comes to initialCapacity, Then the initial size is ArrayList

1. Verify the code example of capacity expansion

As you can see from the example , When adding elements , If the number of elements +1> Current array length 【size + 1 > elementData.length】 when , super-popular , The size of the expanded array is ： oldCapacity + (oldCapacity >> 1)

Pass the contents of the old array Array.copyOf Copy all to the new array , At this time, the old and new lists size Same size , but elementData The length is different from the capacity

Be careful ： Expansion is not strict 1.5 times , Is to shift the length of the array one bit to the right before expansion + The length of the array before expansion

public class SimpleTest {
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        int size = 0;
        for (int i = 0; i < 100; i++) {
            list.add(i);
            if(getCapacity(list)>size) {
                 System.out.println("capacity:"+getCapacity(list) + ",size:"+list.size());
                size = getCapacity(list);
            }
        }
    }

    public static Integer getCapacity(ArrayList list) {
        Integer length = null;
        Class clazz = list.getClass();
        Field field;
        try {
            field = clazz.getDeclaredField("elementData");
            field.setAccessible(true);
            Object[] object = (Object[]) field.get(list);
            length = object.length;
            return length;
        } catch (Exception e) {
            e.printStackTrace();
        }
        return length;
    }
}

Copy

The operation results are as follows ：

capacity:10,size:1 capacity:15,size:11 capacity:22,size:16 capacity:33,size:23 capacity:49,size:34 capacity:73,size:50 capacity:109,size:74

2. Expansion related source code

 public boolean add(E e) {
       // Called a ensureCapacityInternal Method , Ensure that the array subscript does not cross the bounds 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

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

 private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

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

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

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
       // The new capacity is expanded to about 1.5 times , Moving one bit to the right is equivalent to dividing the original value by 2, Expansion is not strict 1.5 position 
        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);
    }

Copy

3. Why press about 1.5 Double expansion

Size selection of expansion factor , The following situations need to be considered ：

1. The expansion capacity cannot be too small , Prevent frequent expansion , Frequently apply for memory space + Arrays are copied frequently
2. The expansion capacity should not be too large , Need to make full use of space , Avoid wasting too much space ;

In order to make full use of the previously allocated memory space , It's better to set the growth factor to 1<k<2.

k=1.5 when , You can make full use of the space already released in front . If k >= 2, The new capacity is just right, which is always greater than the capacity of all abandoned arrays in the past

And make full use of the shift operation （ Moves to the right one ）, Reduce floating point numbers or operation time and number of operations

See ： C++ STL in vector After running out of memory , Why every time 2 Double growth , instead of 3 Times or other values ?

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/130890.html Link to the original text ：https://javaforall.cn