ArrayList概述
ArrayList是一个的可变数组的实现，实现了所有可选列表操作，并允许包括 null 在内的所有元素。每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。
注意，此实现不是同步的。如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。
ArrayList的源码阅读：
- 底层容器
ArrayList是一个Object的数组，还有一个size属性来记录当前容器的容量。
transient Object[] elementData; // non-private to simplify nested class access
private int size;
- 构造函数
ArrayList提供了三种方式的构造器，可以构造一个默认初始容量为0的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列的。
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 传入初始容量的构造函数
public ArrayList(int initialCapacity) {
if (initialCapacity > ) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == ) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// 默认的构造函数
public ArrayList() {
// 默认的是一个空数组实例，等用到的时候再扩容
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 传入外部集合的构造函数
public ArrayList(Collection<? extends E> c) {
//持有传入集合的内部数组的引用
elementData = c.toArray();
//更新集合元素个数大小
if ((size = elementData.length) != ) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
//判断引用的数组类型, 并将引用转换成Object数组引用
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
- 添加元素
ArrayList有四种添加元素的方法：add(E e)，add(int index, E element)，addAll(Collection<? extends E> c)，addAll(int index, Collection<? extends E> c)
// 添加一个元素
public boolean add(E e) {
//添加前先检查是否需要拓展数组, 此时数组长度最小为size+1
ensureCapacityInternal(size + ); // Increments modCount!!
//将元素添加到数组末尾
elementData[size++] = e;
return true;
}
// 插入一个元素
public void add(int index, E element) {
//插入位置范围检查
rangeCheckForAdd(index);
//检查是否需要扩容
ensureCapacityInternal(size + ); // Increments modCount!!
//挪动插入位置后面的元素
System.arraycopy(elementData, index, elementData, index + ,
size - index);
//在要插入的位置赋上新值
elementData[index] = element;
//将容器的容量+1
size++;
}
// 添加一个集合数据
public boolean addAll(Collection<? extends E> c) {
// 把Collection中的数据按照迭代器的排列复制到临时数组a中
Object[] a = c.toArray();
int numNew = a.length;
// 检查是否需要扩容
ensureCapacityInternal(size + numNew); // Increments modCount
// 将数据插入到容器的末尾
System.arraycopy(a, , elementData, size, numNew);
// 更新容器的容量
size += numNew;
return numNew != ;
}
// 插入一个集合数据
public boolean addAll(int index, Collection<? extends E> c) {
// 插入范围检查
rangeCheckForAdd(index); Object[] a = c.toArray();
int numNew = a.length;
//检查是否需要扩容
ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index;
if (numMoved > )
// 在elementData的index位置开始，往后移动numNew个位置
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 将数据插入的index处
System.arraycopy(a, , elementData, index, numNew);
size += numNew;
return numNew != ;
}
细读里面上的代码：
- System.arraycopy
System.arraycopy(elementData, index, elementData, index + numNew,numMoved);
这时的index=1 numNew=3,numMoved=4,那么执行上面的代码后：
然后执行
System.arraycopy(a, 0, elementData, index, numNew);
2. ensureCapacityInternal
//集合最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - ; private void ensureCapacityInternal(int minCapacity) {
// 如果是空数组（默认初始化时的数组）
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 容量不能小于默认容量10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
} private void ensureExplicitCapacity(int minCapacity) {
// 更新容器被修改的次数
modCount++; // overflow-conscious code
//如果最小容量大于数组长度就扩增数组
if (minCapacity - elementData.length > )
grow(minCapacity);
}
//增加数组的长度
private void grow(int minCapacity) {
// overflow-conscious code
//获取数组原先的容量
int oldCapacity = elementData.length;
// 新数组容量，在原来的基础上增加1.5倍
int newCapacity = oldCapacity + (oldCapacity >> );
//检查新的容量是否小于最小容量
if (newCapacity - minCapacity < )
newCapacity = minCapacity;
//检查新的容量是否超过最大数组容量
if (newCapacity - MAX_ARRAY_SIZE > )
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 增加新容量的数组，并把原先的数据拷贝到新容量的数组
elementData = Arrays.copyOf(elementData, newCapacity);
} private static int hugeCapacity(int minCapacity) {
if (minCapacity < ) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
每次添加元素前会调用ensureCapacityInternal这个方法进行集合容量检查。在这个方法内部会检查当前集合的内部数组是否还是个空数组，如果是就新建默认大小为10的Object数组。如果不是则证明当前集合已经被初始化过，那么就调用ensureExplicitCapacity方法检查当前数组的容量是否满足这个最小所需容量，不满足的话就调用grow方法进行扩容。
在grow方法内部可以看到，每次扩容都是增加原来数组长度的一半，扩容实际上是新建一个容量更大的数组，将原先数组的元素全部复制到新的数组上，然后再抛弃原先的数组转而使用新的数组。
- 删除元素
// 删除指定下标的元素
public E remove(int index) {
//index不能大于size
rangeCheck(index);
//更新容器被修改的次数
modCount++;
E oldValue = elementData(index); int numMoved = size - index - ;
if (numMoved > )
//将index后面的值往前移一位
System.arraycopy(elementData, index+, elementData, index,
numMoved);
//清空最后一个元素
elementData[--size] = null; // clear to let GC do its work return oldValue;
} // 删除对象元素
public boolean remove(Object o) {
if (o == null) {
for (int index = ; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = ; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
} private void fastRemove(int index) {
modCount++;
int numMoved = size - index - ;
if (numMoved > )
System.arraycopy(elementData, index+, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
- 修改元素
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}- 查询元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}- 增删改查总结
增(添加)：仅是将这个元素添加到末尾。操作快速。如果有扩容的情况，会涉及数组的复制，操作较慢。
增(插入)：由于需要移动插入位置后面的元素，并且涉及数组的复制，所以操作较慢。
删：由于需要将删除位置后面的元素向前挪动，也会设计数组复制，所以操作较慢。
改：直接对指定位置元素进行修改，不涉及元素挪动和数组复制，操作快速。
查：直接返回指定下标的数组元素，操作快速。
- Fail-Fast机制
ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。在看下面iterator()方法的源代码时会发现，再通过迭代器操作ArrayList时都会调用checkForComodification方法，如果modCount被修改了会抛出ConcurrentModificationException.
public Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + ;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < )
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -;
// 把modCount重新赋值，所以我们可以使用iterator的remove方法来删除ArrayList里的元素，而不会导致ConcurrentModificationException.
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - ;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}