阅读源码的主线是：构造方法->常用的API（增、删、改、查）->ArrayList扩容算法。
ArrayList是一个动态数组，其核心数据结构就是一个数组Object[] elementData,它继承自AbstractList<E>，实现了List<E>，RandomAccess，Cloneable，java.io.Serializable接口，其中RandomAccess接口代表了它具有随机快速访问的能力。
因为ArrayList核心数据结构是数组，所以它是有一定的容量的（数组的length）这就涉及到一个问题，当集合中的元素超过这个容量的时候，ArrayList便会进行扩容操作（关于扩容操作，后面会介绍到，这里先给一个大致的认知）。扩容操作是ArrayList的一个性能消耗比较大的地方，所以如果我们可以提前预知到数据的大小，此时我们应该通过带有指定集合大小参数的构造方法来创建ArrayList，而不是无脑使用无参构造，指定集合大小可以减少扩容次数，提高效率。
1、ArrayList构造方法
//数组默认容量为10
private static final int DEFAULT_CAPACITY = 10;
//空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//真正用来储存元素的数组
transient Object[] elementData;
//集合大小
private int size;
//无参构造，也是我们平时无脑使用的构造方法
public ArrayList() {
super();
//无参构造方法将空数组赋值给了elementData
this.elementData = EMPTY_ELEMENTDATA;
}
//带初始容量大小的构造方法
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
//初始容量小于0直接抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
//初始容量大于等于0时，直接创建一个容量大小为 initialCapacity 的数组
this.elementData = new Object[initialCapacity];
}
//利用其他集合类来创建一个 ArrayList集合
public ArrayList(Collection<? extends E> c) {
//这届利用 Collection.toArray()方法得到一个数组，并且把它赋值给 elementData
elementData = c.toArray();
//集合元素数量
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//这里 c.toArray 返回的可能不是 Object[]，之所以会有这个问题是因为继承的原因：
//父类实例的具体类型，实际上取决于在 new 的时候，我们使用的子类类型。
//具体的分析见：http://www.itread01.com/articles/1478295315.html
if (elementData.getClass() != Object[].class)
//如果 c.toArray 返回的不是 Object[] 时，利用 Arrays.copyOf() 方法，将 c 中元素复制到 elementData中。
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
至此，构造函数就走完了，此时会构建出数组 elementData。注意：若使用前面两个构造函数，此时 size还是0，也就是ArryList中还没有元素；若使用第三种构造函数，此时 ArryList 已经有了元素了，size 不为0。
2、增
2.1 add(E element) 方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;//在数组末尾追加一个元素，并修改 size 的值
return true;
}
//注意到ensureCapacityInternal()方法，每次 add 之前都会调用改方法
private void ensureCapacityInternal(int minCapacity) {
//如果时调用的第一个构造方法初始化的 ArrayList，则取 10 和
//minCapacity中的最大值作为 minCapacity，当且仅当无参构
//造函数第一次调用 add 才会进入这个 if 语句
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//如果需要扩容，会修改 modCount 的值
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//这个方法真正的去扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//创建一个 newCapacity 变量，它的大小等于原有大小加上原有大小的一半
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果 newCapacity 比我们期望扩容的值还小，那么就将我们期望扩容的值赋给 newCapacity
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:
//这里利用 Arrays.copyOf() 对 elementData数组进行扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
延伸：阿里巴巴Java开发手册中第一章第五小节第九条建议建议我们：9. 【推荐】集合初始化时， 指定集合初始值大小。它这样建议的依据是什么呢？假设我们需要一个容量为50的ArrayList，调用它的无参构造：
- 当第一次调用
add方法时，需要进行一次扩容，此时elementData数组容量为10； - 当元素数量小于等于10时都不会在扩容；
- 当元素数量大于10时，进行第二次扩容1.5倍，此时
elementData数组容量为15（10+5）； - 当元素数量大于15时，进行第三次扩容1.5倍，此时
elementData数组容量为22（15+7）； - 当元素数量大于22时，进行第四次扩容1.5倍，此时
elementData数组容量为33（22+11）； - 当元素数量大于33时，进行第五次扩容1.5倍，此时
elementData数组容量为49（33+16）； - 当元素数量大于49时，进行第六次扩容1.5倍，此时
elementData数组容量为73（49 + 24）；
也就是说我们需要一个容量为50 的ArrayList，最后却得到了一个容量为73 的ArrayList，这不仅浪费了空间，同时由grow()方法我们得知，每次都会进行数组copy，这是极其消耗性能的。这也验证了我们文章开头提出的观点，假如我们可以提前预知元素的数量的时候，建议集合初始化的时候就指定其大小，以减少多次扩容带来的效率问题。
2.2 add(int index,E element)方法
public void add(int index, E element) {
//这里可能会存在一些疑问，ArrayList进行第一次扩容之后，内部 elementData
//数组的长度为10，此时假设只有一个元素（0号位置），即 size = 1,
//调用add(int index, E element)，我们往2号位置插入一个元素
//（index = 2，size = 1），按理说数组的长度时足够的，但是在ArrayList
//却会抛出数组越界问题,这样的做法是为了保证ArrayList数据内存地址的连续性。
//同时也是为了避免后面取数据的时候出现数组越界问题，假如这里没有做边界检查，
//2号位置我们插入一个元素，即elementData[2]有数据，我们使用 list 去获取
//数据时，应该是list.get(1)发现并没有这个元素。
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//进入扩容算法
ensureCapacityInternal(size + 1); // Increments modCount!!
//将index开始的数据，向后移动一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;//将element元素插入index位置
size++;
}
2.3 addAll(Collection<? extends E> c)方法
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
//确定是否需要扩容
ensureCapacityInternal(size + numNew); // Increments modCount
//在这个list的末尾追加一个集合
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
2.4 addAll(int index,Collection<? extends E> c)方法
public boolean addAll(int index, Collection<? extends E> c) {
//判断是否越界
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//这里不需要判断c.toArray()类型是否为Object[].class 类型 ，
//后面 System.arraycopy()方法会将az中元素全部copy到elementData数组中，
//保证了类型一致问题
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
// 0<= index < size时走这个 if 分支
if (numMoved > 0)
//将elementData数组中从index开始的（size-index）个元素
//向右移动（index+numNew）位。
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//如果走了上一个if分支，就是填充上一个操作之后空出来的位置，
//否则，即index=size,就在末尾追加a数组
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
3、删
3.1 remove(int index)方法
public E remove(int index) {
//首先进行边界检查
rangeCheck(index);
//修改modCount，因为结构发生了变化
modCount++;
//需要删除的元素
E oldValue = elementData(index);
//需要向左移动的元素的个数
int numMoved = size - index - 1;
//除了删除最后一个元素均会走这个分支
if (numMoved > 0)
//将elementData数组中numMoved个元素分别向左移动一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将数组末尾置空，不再强引用，可以被GC回收
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
3.2 remove(Object o)方法
//删除该元素在书中中第一次出现的位置上的元素。
public boolean remove(Object o) {
if (o == null) {
//删除值为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;
}
//该方法不进行边界检查了，因为这里的index一定是0<=index<size的
private void fastRemove(int index) {
//修改modCount，因为结构已经发生了变化
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
//和remove(int index)方法原理一样了
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
3.3 removeAll(Collection<?> c)
//批量删除
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
关于批量删除分析详见我的另外一篇文章，这里就不再详细介绍了。
4、改
4.1 set(int index,E element)方法
//修改操作不会修改modCount的值，即不会修改结构，相对增删来说时高效操作。
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
5、查
5.1 get(int index) 方法
//查操作不会修改modCount的值，没有结构的变化，相对增删来说时高效操作
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
6、小结
1、通过源码分析我们知道增删改查四个操作中，如果增导致了扩容一定会修改modCount的值，而删除一定会修改modCount的值。改、查操作一定不会修改modCount的值。
2、扩容操作会导致数组的复制，删除操作除了删除最后一个元素均会导致数组复制，因此，相对来说增删操作时比较消耗性能的，而改查操作时相对高效的操作。如果需要频繁增删元素，那么就不是很推荐使用ArrayList这种数据结构了。
3、经过源码分析也验证了阿里巴巴Java开发手册中中提出的集合初始化时， 指定集合初始值大小建议的合理性。
以上是我阅读源码的一些思考和心得，如有写的不正确的地方，还请大神指出，以免误人子弟。
网友评论