Java-进阶二

ArrayList的源代码分析（扩容原理）

• 1 使用空参构造的集合，在底层创建一个容量为0的数组。
• 2 添加第一个元素时，底层会扩容创建一个容量为10的数组。
• 3 存满时会扩容1.5倍。
• 4 如果一次添加多个元素，1.5倍还放不下，那么扩容以实际需要的数组大小来扩容。

空参构造-初始化：

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

1 这里的elementData是一个Object数组

transient Object[] elementData; // non-private to simplify nested class access

2 长度为0的一个数组赋值给这里的Object数组

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

长度初始化

数组长度与与接下来应该添加的元素位置：（默认为0）

private int size;

添加元素-扩容：（代码为逐层调用）

1

    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

e为添加元素的名称

elementData为底层数组名称

size为添加位置/也是未添加前数组长度

2

    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

先有一个判断：如果数组长度已经等于数组中元素的个数，那么数组已经满了

需要实现grow()扩容

然后再实现对s(添加位置)进行赋值，最后再将数组长度加一。

3

    private Object[] grow() {
        return grow(size + 1);
    }

现有个数加一进行扩容

    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        modCount++;
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);
        System.arraycopy(a, 0, elementData, s, numNew);
        size = s + numNew;
        return true;
    }

将添加的集合变成数组，获取长度，如果这个需要添加的数组的长度大于数组还剩下的长度那么调用grow扩容

最后调用System.arraycopy方法进行填充赋值

4

    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

这里的MinCapacity未上面传参的size+1

oldCapacity为数组原先的长度

首次扩容oldCapacity为0，执行else这一路径的代码

此时扩容为10     max（10，1）

private static final int DEFAULT_CAPACITY = 10;

之后会执行if中的代码

newCapacity为重新赋值的数据，这里调用的时ArraySupport.newLength方法

传入的三个参数分别是

oldCapacity老容量

MinCapacity-oldCapacity我们理论上应该扩容的容量

oldCapacity<<1默认新增容量的大小（0.5倍）

最后再使用Arrays.copyOf（原先的数组，新数组的长度）

实现扩容并且拷贝

5

    public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        // preconditions not checked because of inlining
        // assert oldLength >= 0
        // assert minGrowth > 0

        int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
        if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
            return prefLength;
        } else {
            // put code cold in a separate method
            return hugeLength(oldLength, minGrowth);
        }
    }

这里的PreLength为

老数组长度加上理论扩容大小（主要是应对addAll方法可能会出现添加多个元素）与

默认扩容大小（0.5倍）的最大值

补充：这里的else是出现数组容量超出范围的情况（一般情况下不会遇到）

最大长度

public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

代码展示

    private static int hugeLength(int oldLength, int minGrowth) {
        int minLength = oldLength + minGrowth;
        if (minLength < 0) { // overflow
            throw new OutOfMemoryError(
                "Required array length " + oldLength + " + " + minGrowth + " is too large");
        } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
            return SOFT_MAX_ARRAY_LENGTH;
        } else {
            return minLength;
        }
    }

原文地址：https://blog.csdn.net/2302_79847831/article/details/142718483

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！