在平时的工作中，ArrayList是使用的最多的集合之一，这次通过阅读源码，希望能更一步地理解集合（jdk版本为1.8.0_201）。
ArrayList简介
ArrayList特点：底层由数组实现，可动态扩缩容的集合，由于数组的特点，ArrayList适用于查询场景。
ArrayList类结构：
1569509609668.png
类中的属性
//序列化ID
private static final long serialVersionUID = 8683452581122892189L;
//缺省容量
private static final int DEFAULT_CAPACITY =10;
//空元素数组，用于带参构造器且容量为0时初始化elementData
private static final Object[]EMPTY_ELEMENTDATA = {};
//缺省空元素数组, 用于无参构造器时初始化elementData
private static final Object[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//元素数组
transient Object[]elementData;
//集合大小
private int size;
//最大数组容量，一些虚拟机会在数组中保留一些header word，所以最大值-8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
1、构造器
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//初始化elementData
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
//这里的Collection可能是用户自己实现的，返回的不是Object[]类型，这种情况需要转成Object[]
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
2、主要方法
2.1 add(E)
public boolean add(E e) {
//确保容量足够
ensureCapacityInternal(size + 1);
//将元素放入数组中，size+1
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算当前容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//判断是否为空数组，DEFAULTCAPACITY_EMPTY_ELEMENTDATA用于无参构造器初始化elementData
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//返回缺省容量和所需最小容量中最大的一个
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
//modCount是AbstractList中的属性，用于记录集合内部元素变化情况。
modCount++;
//判断容量是否足够
if (minCapacity - elementData.length > 0)
//扩容
grow(minCapacity);
}
private void grow(int minCapacity) {
//元素数组的实际大小
int oldCapacity = elementData.length;
//扩容后的大小，默认为原来大小的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//elementData为空的情况下，oldCapacity为0，newCapacity也为0，minCapacity为10
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判断是否超出限制，如果超出限制就给予newCapacity可以给到的最大值
//newCapacity可能超出Integer的限制变成负数，所以这里先做减法在与0比较
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//copy数组，改变大小
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
//minCapacity < 0 说明size已经到最大了，在+1变成了负数。
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
2.2 add(int, E)
//插入元素到指定位置
public void add(int index, E element) {
//检查下标是否越界
rangeCheckForAdd(index);
//确保容量足够
ensureCapacityInternal(size + 1);
//将下标以及下标后所有的元素都向后挪一位
System.arraycopy(elementData, index, elementData, index + 1, size - index);
//将元素放在目标位置上
elementData[index] = element;
size++;
}
addAll方法和上面差不多，也很简单，就不贴代码了。
2.3 remove(int)
public E remove(int index) {
//检查下标
rangeCheck(index);
//记录一次变更
modCount++;
E oldValue = elementData(index);
//要移动的元素数量
int numMoved = size - index - 1;
if (numMoved > 0)
//把index位置后的所有元素向左挪一位，覆盖掉了index位置的元素
System.arraycopy(elementData, index+1, elementData, index, numMoved);
//在将最后一个位置的元素置为空，size-1
elementData[--size] = null;
return oldValue;
}
2.4 remove(Object)
//逻辑很简单，循环找出元素所在位置，调用fastRemove删除，只会删除第一个。
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//删除指定下标的元素，和之前的逻辑是一样的
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null;
}
2.5 iterator()
//返回一个迭代器
public Iterator<E> iterator() {
return new Itr();
}
//迭代器，是一个内部类，这里我只贴了主要方法
private class Itr implements Iterator<E> {
//下一个返回的元素下标，缺省为0
int cursor;
//上一个返回元素的下标，没有为-1
int lastRet = -1;
//记录当前修改次数
int expectedModCount = modCount;
public boolean hasNext() {
//如果下标等于长度的话表示遍历结束了
return cursor != size;
}
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 + 1;
//返回当前位置元素，记录lastRet
return (E) elementData[lastRet = i];
}
//这里的删除是删除上一个next输出的数据
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
//删除数据，并重新赋值cursor，lastRet和expectedModCount
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
//通过这个方法保证在使用迭代器时，原集合没有被修改过，所以在使用迭代器的过程中不能使用add、remove等改变元素内部数据的方法
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
2.6 subList(int, int)
//返回范围内的子集合
public List<E> subList(int fromIndex, int toIndex) {
//检查下标是否越界
subListRangeCheck(fromIndex, toIndex, size);
//这里返回的是一个内部类，所以使用subList是不能强转为ArrayList
return new SubList(this, 0, fromIndex, toIndex);
}
private class SubList extends AbstractList<E> implements RandomAccess {
//父集合，指当前的ArrayList
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
public E get(int index) {
//检查下标
rangeCheck(index);
//检查是有有改动
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
//调用父集合添加
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
//代码太多，就不贴了，知道了subList使用的还是ArrayList中的数据就行了，所以我们改变的subList的数据，其实改变的还是对应的ArrayList中的数据，并且和Iterator一样，改变了ArrayList后就不能再操作subList了
…… ……
}
总结
ArrayList内部是由数组实现的，但因为数组大小是固定的，所以扩容是通过复制的方式实现的，扩容大小为1.5倍。由此可见，如果提前能估计出集合大小，那么使用ArrayList时给上初始容量，以避免不必要的扩容，造成资源浪费。
数据有可能超出类型限制时不能简单的比较，考虑多种情况的可能，ArrayList中先做减法在与0比较。
使用iterator和subList时不能调用ArrayList修改数据，并且iterator和subList操作的都是ArrayList中的数据。
ArrayList是线程不安全的。
