谈谈对ArrayList的理解以及扩容机制

标签：扩容元素容量 ArrayList elementData 谈谈数组 size

1.浅谈ArrayList

ArrayList类又称动态数组，同时实现了Collection和List接口，其内部数据结构由数组实现，因此可对容器内元素实现快速随机访问。但因为ArrayList中插入或删除一个元素需要移动其他元素，所以不适合在插入和删除操作频繁的场景下使用。

　　ArrayList的容量可以随着元素的增加而自动增加，因此不用担心ArrayList容量不足的问题。

　　ArrayList是非线程安全的。

先看看他的原码吧

// 默认的容量大小（常量）
private static final int DEFAULT_CAPACITY = 10;

// 定义的空数组（final修饰，大小固定为0）
private static final Object[] EMPTY_ELEMENTDATA = {};

// 定义的默认空容量的数组（final修饰，大小固定为0）
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 定义的不可被序列化的数组，实际存储元素的数组
transient Object[] elementData; 

// 数组中元素的个数
private int size;

谈谈对ArrayList的理解以及扩容机制_ci

2.ArrayList有三种构造方法:

　　　　1.无参的构造方法

// 无参的构造方法
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

谈谈对ArrayList的理解以及扩容机制_数组_02

可以看出来，当我们直接创建ArrayList时，elementData被赋予了默认空容量的数组。注意，因为默认空容量数组是被final修饰的，此时ArrayList数组是空的、固定长度的，也就是说其容量此时是0，元素个数size为默认值0。

　　　　2.根据传入的数值大小，创建指定长度的数组

// 传容量的构造方法
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);
    }
}

谈谈对ArrayList的理解以及扩容机制_数组_03

当initialCapacity > 0时，会在堆上new一个大小为initialCapacity的数组，然后将其引用赋给elementData，此时ArrayList的容量为initialCapacity，元素个数size为默认值0。

　　当initialCapacity = 0时，elementData被赋予了默认空数组，因为其被final修饰了，所以此时ArrayList的容量为0，元素个数size为默认值0。

　　当initialCapacity < 0时，会抛出异常。

　　　　3.通过传入Collection元素列表进行生成

// 传入Collection元素列表的构造方法
public ArrayList(Collection<? extends E> c) {
    // 将列表转化为对应的数组
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 此处见下面详细解析
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 赋予空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

谈谈对ArrayList的理解以及扩容机制_数组_04

　传入Collection元素列表后，构造方法首先会将其转化为数组，将其索引赋给elementData。

　　如果此数组的长度为0，会重新赋予elementData为空数组，此时ArrayList的容量是0，元素个数size为0。

　　如果此数组的长度大于0，会更新size的大小为其长度，也就是元素的个数，然后执行里面的程序。大家对里面的代码可能不理解，让我们等会看下面解析。执行完后此时ArrayList的容量为传入序列的长度，也就是size的大小，同时元素个数也为size，也就是说，此时ArrayList是满的。

3.ArrayList的扩容机制

当我们探讨扩容时，肯定要从ArrayList的add方法走起，让我们来看看吧。

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

谈谈对ArrayList的理解以及扩容机制_ci_05

这是最基本的add方法，当然，也是可以说明问题的。可以看到，此add方法的参数就是一个被加元素，moCount是记录ArrayList被修改次数的，可以不用管。然后是另一个add方法，所传的值是被加元素、当前数组和当前数组的元素个数，让我们来看看这个add方法吧。

private void add(E e, Object[] elementData, int s) {
    // 判断元素个数是否等于当前容量
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

谈谈对ArrayList的理解以及扩容机制_ci_06

首先，它判断了元素个数是否等于当前数组的容量，也就是判断当前数组是不是满的，如果当前空间是满的，就需要扩容了，grow函数就是扩容函数了，扩容后再将被加元素加到数组中。

　　下面我们来看看grow函数是什么样子的：

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

谈谈对ArrayList的理解以及扩容机制_ci_07

它里面又调用了一个带参的grow函数，参数是当前元素个数+1，也就是当前容量+1。返回的是这个函数的返回值，让我们进一步研究这个带参的函数。

private Object[] grow(int minCapacity) {
    // 获取老容量，也就是当前容量
    int oldCapacity = elementData.length;
    // 如果当前容量大于0 或者 数组不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    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);
    // 如果 数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA（容量等于0的话，只剩这一种情况了）
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

谈谈对ArrayList的理解以及扩容机制_数组_08

首先，它是记录了一下老容量的大小，然后再进行下面的操作。

　　如果当前容量大于0，或者当前数组不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，前面说明过，DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个被final修饰的空数组，在三个构造方法中，只有无参构造方法中elementData被赋予了DEFAULTCAPACITY_EMPTY_ELEMENTDATA。也就是说，这个if语句中不会处理用默认无参构造方法创建的数组的初始扩容情况，那么其余的扩容情况都是由此if语句来处理的。

　　我们来看一下if里面的操作，先创建一个新的数组，然后将旧数组拷贝到新数组并赋给elementData返回。ArraysSupport.newLength函数的作用是创建一个大小为oldCapacity + max（minimum growth， preferred growth）的数组。

　　minCapacity是传入的参数，我们上面看过，它的值是当前容量（老容量）+1，那么minCapacity - oldCapacity的值就恒为1，minimum growth的值也就恒为1。

　　oldCapacity >> 1的功能是将oldCapacity 进行位运算，右移一位，也就是减半，preferred growth的值即为oldCapacity大小的一半。

4.总结

ArrayList的特点：

　　1.ArrayList的底层数据结构是数组，所以查找遍历快，增删慢。

　　2.ArrayList可随着元素的增长而自动扩容，正常扩容的话，每次扩容到原来的1.5倍。

　　3.ArrayList的线程是不安全的。

ArrayList的扩容：

　　扩容可分为两种情况：

　　第一种情况，当ArrayList的容量为0时，此时添加元素的话，需要扩容，三种构造方法创建的ArrayList在扩容时略有不同：

　　　　1.无参构造，创建ArrayList后容量为0，添加第一个元素后，容量变为10，此后若需要扩容，则正常扩容。

　　　　2.传容量构造，当参数为0时，创建ArrayList后容量为0，添加第一个元素后，容量为1，此时ArrayList是满的，下次添加元素时需正常扩容。

　　　　3.传列表构造，当列表为空时，创建ArrayList后容量为0，添加第一个元素后，容量为1，此时ArrayList是满的，下次添加元素时需正常扩容。

　　第二种情况，当ArrayList的容量大于0，并且ArrayList是满的时，此时添加元素的话，进行正常扩容，每次扩容到原来的1.5倍。

标签：扩容,元素,容量,ArrayList,elementData,谈谈,数组,size
From： https://blog.51cto.com/u_16291421/8345971