List是Java中非常常用的数据结构，而ArrayList是其中最常用的实现，ArrayList正如它的名称一样，它的本质是一个数组，所有的元素都会以数组的形式保存在内存中，然后提供各种操作数组的方法。
初始化
既然对象要存到数组，那么肯定就需要预先分配好内存，这也是ArrayList优化的核心因素。
ArrayList提供了三个构造函数：
public ArrayList()public ArrayList(int initialCapacity)public ArrayList(Collection<? extends E> c)
先来说说最简单的无参构造方法ArrayList()：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空的数组，采用这种初始化方式，就意味着我们需要使用ArrayList的默认设置（默认不初始化数组），有意思的是在jdk1.6中，这个方法里面只是简单地调用了一下另外一个构造方法ArrayList(10)。
再来看第二种构造形式：ArrayList(int initialCapacity)：
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根据这个值来分配数组的大小。
第三种构造方法：ArrayList(Collection<? extends E> c)则是将Collection对象转换成数组（通过collection内置的方法），然后拷贝到ArrayList的元素中，不是一种特别高效的方式:
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
在以上的源码中所展示的一样，ArrayList拥有一个elementData数组对象，它所有的储存的元素都会保存在这个对象数组中。
添加元素
在初始化这个容器之后，我们现在最需要做的就是将数据存到ArrayList里面，ArrayList提供了几种添加元素的方法:
public void add(int index, E element)public boolean add(E e)-
public boolean addAll(Collection<? extends E> c)// 由AbstractCollection提供，内部其实使用了add()方法 -
public boolean addAll(int index, Collection<? extends E> c)// 由AbstractList提供，内部也是使用了add()方法
那么让我们由最简单的add()方法，来解析ArrayList是如何将数据存入数组的。
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
这里使用一个参数size，这个参数保存了当前ArrayList中存储元素数量。
ensureCapacityInternal(int size)函数是一个私有方法，负责确认数组是否需要扩容，以及是否需要调整参数的大小，看看它内部具体的实现：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
这个函数中，我们发现有一句特意为无参构造方法写的if语句，DEFAULT_CAPACITY的值为10，ensureExplicitCapacity方法会判断数组是不是真的需要扩容，然后会调用grow()函数执行真正的数组扩容。
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 这是为迭代器快速失败提供的一个参数，可以暂时忽略
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
所以，这意味着如果我们初始化的是一个空的ArrayList，那么数组直到被add的时候才会扩容，相比1.6中一经初始化就占用空间，是做了一些调整的。
那么grow()方法中又是如何为数组扩容的呢：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 右移一位，二进制中高位减少一个数量级，即除以2
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);
}
从中可以看到ArrayList在确认扩容之后利用Arrays.copyOf()方法产生一个空间为原来1.5倍的新数组，并将老的数组复制到新的数组中，也就是将老的元素，整体从一个位置挪到了另外一个位置，老的数组等待被GC释放。
在确认数组的大小能够容纳下新的元素之后，我们回到add()方法，新添加的元素添加到索引为size值的位置，然后扩大size的值。
说到扩容，ArrayList为我们提供了一个公开的方法ensureCapacity()，帮助我们手动扩容：
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
因为扩容总是1.5倍，有时候这并非我们希望的数组大小，如果我们事先已经预知代码执行到某一段的时候，需要扩容的操作，那么我们就可以使用ensureCapacity()方法手动扩容到期望的大小。
删除元素
既然元素可以被添加的，那么也应该可以被删除，ArrayList提供了几个删除方法：
这里我们分析下最常用的remove(int index)方法
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;
}
这个方法中，rangeCheck(index)会检查传入的参数是否超出数组大小越界。
之后remove()方法通过elementData()方法查询出要被删除的数据：
E elementData(int index) {
return (E) elementData[index];
}
使用System.arraycopy函数复制数据覆盖原先的索引位置上的数据，并将最后一位制空并减少size值，等待被GC回收内存。
查询数据
ArrayList可以通过get()方法查询数据：
public E get(int index) {
// 检查传入的参数是否越界
rangeCheck(index);
// 从 elementData 数组中取出对应索引位置的数据,强转成对应的类型
return elementData(index);
}
由于是基于数组的容器，查询的时候知道位置，数组大小可以被确定，查询的复杂度为复杂度O(1)，查询的速度是非常快的。
当然既然是数组，更多的时候，我们需要遍历整个数组，在Java8提供了lambda之后，ArrayList也提供了一个forEach()方法完成整个数组的遍历：
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
从中不难发现，forEach()方法遍历数组的本质其实还是利用了最基本的for循环，然后直接通过索引位置取得数据。
总结
ArrayList作为最常用的数据结构，需要更好地了解才能更好地使用它。从以上的分析中也不难看出ArrayList最大的消耗来自于到处数组拷贝，几乎所有操作元素的地方，都可能(对，只是可能)出现数组的拷贝，这本身是一个非常大的消耗，而大量老数组等待被GC也增加了GC的负担。
所以使用ArrayList最好的姿势，应该是初始化的时候，估算好数组的大小，然后将元素放入容器之后，尽量不要再做一些修改容器的操作。
网友评论