ArrayList原理解析
共 7318字，需浏览 15分钟
·
2021-08-19 05:58
前言
ArrayList是Java集合框架中比较常用的数据结构了。继承自AbstractList，实现了List接口。底层基于数组实现容量大小动态变化。一看就是一个比较重要的模块，所以我们今天就来学习一下ArrayList相关知识。
ArrayList的数据结构和作用
ArrayList数据结构是数组，用来装载数据。
相对于LinkedList，查询效率高，因为底层是数组，分配的是连续的内存空间，CPU在读取时可以缓存连续的内存空间，大幅度降低读取的性能开销；增删效率低，相对于Vector来说是线程不安全。
虽然ArrayList是线程不安全的，但在我们实际的应用过程中，一般都是用来查询，涉及到增删的操作比较少，如果涉及到的增删操作比较频繁的场景，我们可以选择LinkedList，如果想保证线程安全，可以使用Vector、CopyOrWriteArray。
如何实现存放任意数量的对象
ArrayList构造器有无参构造和有参构造。在有参构造器中，ArrayList可以通过构造方法在初始化的时候进行指定底层数组的大小。但是我们在使用有参构造时，会不会初始化数组大小呢？我们先来看一下代码：
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);
}
}
由代码可知，我们可以很明确地得出结论：不会初始化数组大小。不信的话我们可以测试一下:
public static void main(String[] args){
//此处使用有参构造，大小为10
ArrayList arrayList = new ArrayList<>(10);
System.out.println("size:" + arrayList);
arrayList.set(1, "A");
}
看到这里是不是已经懵圈了？不要慌，我们慢慢来分析。我们的参数是 initialCapacity，这里是将参数基于 elementData 设置的，并不是直接设置的数组大小（值得注意的是，ensureCapacity();方法也是这种原理）。我们也可以理解为这个数组现在理论上最大可以装10个数据，但是他现在还是空的。
在无参构造器中，初始化出一个默认空的数组，数组容量为 0，当我们调用add();方法是，默认分配【DEFAULT_CAPACITY = 10】的初始容量。下面会具体介绍新增过程，此处不再赘述。
/**
* 数组默认初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于默认大小的空实例的共享空数组实例。
* 与 EMPTY_ELEMENTDATA 区分开来，以了解何时膨胀多少添加第一个元素。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 构造一个初始空列表。
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
但是，对于无参构造和有参构造，数组都是有长度限制的，ArrayList是通过什么方式去实现可以存放任意数量的对象，长度没有限制的呢？不要慌，原来这个地方也是用到了数组的扩容。
数组的扩容
当前我们有一个初始容器为10的数组，且每个位置已经插满数据，但是现在又要新增一条数据，这个时候当前数组已经不能满足我们的要求了，那我们就需要进行扩容；
然后我们就需要进行扩容，扩大到原来的1.5倍，即【10 + 10 / 2】；
最后将原数组的数据原封不动地移动到新数组，再返回新数组的地址，这样ArrayList中数据就是新的数组了。
接下来，我们就看一下源码中的具体实现吧
//扩容前置判断
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//minCapacity: 插入数据后容器大小或者默认容器大小
//当minCapacity比当前数组大时，说明需要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容具体过程
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//此处java 8采用了位运算，提升效率
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 直接使用数组的复制方法
elementData = Arrays.copyOf(elementData, newCapacity);
}
ArrayList的的新增
在ArrayList中，新增有三个方法分别是以下三种：
//1\. 将指定的元素附加到此列表的末尾
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//2\. 在此指定位置插入指定元素列表。
public void add(int index, E element) {
//判断指定参数是否超过范围
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//3\. 将指定集合中的所有元素追加到末尾这个列表，
// 按照它们返回的顺序指定集合的迭代器。
public boolean addAll(Collection c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
由代码可知，不管是哪种插入，我们都需要通过调用 ensureCapacityInternal(); 方法来校验数组长度，如果长度不够，就进行扩容，前面我们已经了解过。对于指定位置新增时，我们在校验完成之后通过调用 arraycopy(); 方法来实现数组的复制。下面我们就来了解一下指定位置插入的过程。
当前我们有一个长度为10，还有一个空位的数组；
现在我们需要插入一个【a】，目标位置是【5】，则先复制一个数组，指定位置之前的数据不变，从【5】开始把后面的数据从【5+1】的位置开始复制，新数组空出位置【5】；
上一步我们已经把【5】这个位置空出来了，然后将数据【a】插入空位，这样就完成了指定位置插入的操作了。
由上可知，ArrayList在新增的需要把数据复制一份，这个操作如果是针对大数据量List，再加上扩容的操作，那效率就慢了。
ArrayList的删除
话不多说，我们先来看一下代码：
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
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
return oldValue;
}
由代码可知，如果是删除末位，则直接删除就完成了操作；如果是将中间数据删除，则此过程中也是类似于插入操作，将数组进行了复制，调用arraycopy();方法。下面我们就来了解一下指定位置删除的过程。
当前我们有一个长度为10；
现在我们需要删除目标位置为【5】的数据，则先复制一个数组，指定位置之前的数据不变，从【5+1】之后的数据进行复制到新数组；
得到新的数组，就是删除了指定位置【5】数据的数组了。
同理，ArrayList的删除和新增一样效率比较低。对于数据量大的数组需要复制和移动的位置就比较大了。
ArrayList适合做队列吗
一般的队列是先进先出队列（FIFO），从尾部出入，头部删除。
对于数组是十分适合做队列的，比如 ArrayBlockingQueue内部的实现就是通过一个定长数组来实现一个环形定长队列，使用两个偏移量来标记数组的读位置和写位置，如果超过长度就折回到数组开头。但是前提必须是一个定长的数组。
因为在ArrayList中，底层虽然是数组，但是数组长度是不确定的。这样我们就需要进行大量的增加和删除操作，就算是指定位置的删除和新增，它也是需要经过数组复制，这样的话，会比较消耗性能。
因此，定长数组适合做队列，ArrayList不适合做队列。