ArrayList类图
先看下ArrayList类图，比较直观。
ArrayList构造函数
先看ArrayList的成员变量：
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
transient Object[] elementData;
private int size;
private static final int MAX_ARRAY_SIZE = 2147483639;
初始容量DEFAULT_CAPACITY是10，当容量不足以容纳全部元素时，会自动扩张容量，新的容量 = 1.5*初始容量，对大容量MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8即231-1-8=2147483639，为啥最大容量要定义这个数字呢？可以看下这个知乎上的解释，意思是说是否减8没那么重要(只是为了避免一些机器内存溢出)。
ArrayList一共有三个构造器，无参构造器a，参数为int型有参构造器b，参数为Collection型的有参构造器c。
public ArrayList() {//a构造器
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int var1) {//b构造器
if (var1 > 0) {
this.elementData = new Object[var1];
} else {
if (var1 != 0) {
throw new IllegalArgumentException("Illegal Capacity: " + var1);
}
this.elementData = EMPTY_ELEMENTDATA;
}
}
public ArrayList(Collection<? extends E> var1) {//c构造器
this.elementData = var1.toArray();
if ((this.size = this.elementData.length) != 0) {
if (this.elementData.getClass() != Object[].class) {
this.elementData = Arrays.copyOf(this.elementData, this.size, Object[].class);
}
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
通过上面的源码可以看出，a构造器直接将DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData；b构造器和c构造器很相似，如果参数int为0或者参数Collection长度为0，会将EMPTY_ELEMENTDATA赋值给elementData。DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA都是长度为0的数组，我感觉其实用一个数组变量就应该够用了，为啥还要分开成两个数组呢？
ArrayList核心操作
ArrayList核心操作包括：
trimToSize()(遍历操作也放在这部分讲解)rangeCheck(var1:int)get(pos:int):Eset(pos:int, val:E)add(val:E):booleanadd(pos:int, val:E)remove(val:int)remove(val:Object):booleansize():intisEmpty(pos:int):booleanindexOf(val:Object):intclone():Object
size()
public int size() {
return this.size;
}
返回的是元素的个数size，而不是elementData数组的长度。因为ArrayList容量增长后的容量是原来的1.5倍，所以elementData数组的长度一般都会大于size，如果手动调用或者系统调用了方法trimToSize，那么elementData数组会通过数组的拷贝方式被赋值为一个容量更小且容量等于size的数组并保存原有的数据(具体介绍在方法trimToSize分析中)，这时候elementData数组的长度才会等于size。
isEmpty(pos:int):boolean
public boolean isEmpty() {
return this.size == 0;
}
源码不解释......
indexOf(val:Object):int
public int indexOf(Object var1) {
int var2;
if (var1 == null) {
for(var2 = 0; var2 < this.size; ++var2) {
if (this.elementData[var2] == null) {
return var2;
}
}
} else {
for(var2 = 0; var2 < this.size; ++var2) {
if (var1.equals(this.elementData[var2])) {
return var2;
}
}
}
return -1;
}
源码非常清晰简单，上面代码的第11行(简书文章代码怎么显示代码的行数呀？)是对元素的内容进行的比较而不是引用。
这里顺便提一下contains(Object var1):boolean这个函数：
public boolean contains(Object var1) {
return this.indexOf(var1) >= 0;
}
trimToSize()
源码中只提供了这个方法，但是没有被调用，估计是内存紧张的时候被系统调用的。源码：
public void trimToSize() {
++this.modCount;
if (this.size < this.elementData.length) {
this.elementData = this.size == 0 ? EMPTY_ELEMENTDATA : Arrays.copyOf(this.elementData, this.size);
}
}
代码的第二行为啥要对modCount自加呢？顾名思义，modCount就是值更改的次数，增加、删除、修改ArrayList结构的操作都算是更改，所有都要对modCount这个变量自增1。ArrayList的遍历是不安全的，它的迭代器是fail-fast的，而fail-fast机制就是依赖modCount这个变量实现的。在使用Iterator遍历(下标遍历不存在这个问题)开始的时候用变量expectedModCount保存modCount原来的值，如果遍历时改变了集合的结构(增删等操作，这时modCount会和预期的值expectedModCount不一样)而抛出ConcurrentModificationException异常，具体流程如下(ArrayList的迭代器Itr的源码)：
private class Itr implements Iterator<E> {
int cursor;
int lastRet = -1;
int expectedModCount;
Itr() {
this.expectedModCount = ArrayList.this.modCount;
}
//......后面的操作省略
//首先看到Itr保存了一个expectedModCount变量
public E next() {
this.checkForComodification();
//......后面的操作省略
}
final void checkForComodification() {
if (ArrayList.this.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
}
}
}
可以看到，在方法checkForComodification中可能会抛出异常。
顺便提一下ArrayList的三种遍历方式：
public void arrayListTraversal(List<Integer> lists){
/* 第一种遍历方式 ===-随机访问遍历*/
System.out.print("for循环的遍历方式：");
for (int i = 0; i < lists.size(); i++) {
System.out.print(lists.get(i));
}
System.out.println();
/* 第二种遍历方式 =-=-强制for循环遍历，这种方式和第三种方式关系有点暧昧*/
System.out.print("foreach的遍历方式：");
for (Integer list : lists) {
System.out.print(list);
}
System.out.println();
/* 第三种遍历方式-=-=迭代器遍历*/
System.out.print("Iterator的遍历方式：");
for (Iterator<Integer> list = lists.iterator(); list.hasNext();) {
System.out.print(list.next());
}
}
其实通过反编译可以看到，第二种便利方式(foreach)底层是使用了Iterator迭代器进行的遍历，所以在遍历的时候进行增删等操作也会和第三种遍历一样抛出ConcurrentModificationException异常，而第一种遍历方式不存在这个问题而且遍历效率最高，举个例子：
ArrayList<Integer> list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
for (int i = 0; i < list.size; i++) {
int av = list.get(i);
if (av == 2) {
list.add(666);
}
System.out.println("av: " + av);
}
System.out.println("list: " + list);
上面代码的执行结果是：
ArrayList<Integer> list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
for (int av : list) {
if (av == 2) {
list.add(666);
}
System.out.println("av: " + av);
}
System.out.println("list: " + list);
上面代码的执行结果是：
在Java的java.util包下的集合框架中，所有的Iterator遍历都是fail-fast的，java.util.concurrent包下的集合框架中，所有的Iterator遍历都是fail-safe的。
Java8提供了两种新的遍历方法：list.forEach(action:Consumer<? super T>)和list.stream().forEach(action:Consumer<? super T>)。对于前者，Iterable提供了默认的实现(可以看到是基于迭代器的)：
//Iterable.java
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
而ArrayList覆盖了这个方法：
//ArrayList.java
@Override
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();
}
}
可以清楚看到，ArrayList的这个方法中采用的机制和Iterable的机制是不一样的，ArrayList采用下标遍历，同时采用了和迭代器一样的fas-fail的机制。
而后者forEach 方法接收一个 Lambda 表达式，然后在 Stream 的每一个元素上执行该表达式。一般认为，stream().forEach 和常规 for 循环的差异不涉及到性能，它们仅仅是函数式风格与传统 Java 风格的差别。另外一点需要注意，forEach 是 terminal 操作，因此它执行后，Stream 的元素就被“消费”掉了，你无法对一个 Stream 进行两次 terminal 运算。下面的代码是错误的： Java 8 中的Streams API 详解 - IBM
stream.forEach(System.out::println);
stream.forEach(System.out::println);
讲完了遍历，回到开始，继续分析trimToSize方法。如果elementData数组包含空闲位置，第三行代码满足，如果容量不为0，那么会调用Arrays.copyOf(this.elementData, this.size)，这行代码干嘛呢？看下Arrays.java的源码：
public static <T> T[] copyOf(T[] var0, int var1) {
return (Object[])copyOf(var0, var1, var0.getClass());
}
public static <T, U> T[] copyOf(U[] var0, int var1, Class<? extends T[]> var2) {
Object[] var3 = var2 == Object[].class ? (Object[])(new Object[var1]) : (Object[])((Object[])Array.newInstance(var2.getComponentType(), var1));
System.arraycopy(var0, 0, var3, 0, Math.min(var0.length, var1));
return var3;
}
可以看到最终会调用System.arraycopy这个方法，返回一个新的数组赋值给elementData，而这个新的数组是将原来数组的闲置位置删除后的。
rangeCheck(var1:int)
private void rangeCheck(int var1) {
if (var1 >= this.size) {
throw new IndexOutOfBoundsException(this.outOfBoundsMsg(var1));
}
}
get(pos:int):E
public E get(int var1) {
this.rangeCheck(var1);
return this.elementData(var1);
}
set(pos:int, val:E)
public E set(int var1, E var2) {
this.rangeCheck(var1);
Object var3 = this.elementData(var1);
this.elementData[var1] = var2;
return var3;
}
add(val:E):boolean
前面几个方法很简单，只贴了源码都没有解释一句，因为不需要解释，而add这个方法就有点复杂了(其实代码只有很简单的五行)：
public boolean add(E var1) {
this.ensureCapacityInternal(this.size + 1);
this.elementData[this.size++] = var1;
return true;
}
首先是调用了ensureCapacityInternal(var1:int)这个方法来保证容量并且判断是否需要扩充容量。
private void ensureCapacityInternal(int var1) {
if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
var1 = Math.max(10, var1);
}
this.ensureExplicitCapacity(var1);
}
private void ensureExplicitCapacity(int var1) {
++this.modCount;
if (var1 - this.elementData.length > 0) {
this.grow(var1);
}
}
因为add操作更改了ArrayList的结构，所以第二行对modCount加1，第三行表示如果add后新的容量比原来容量大，就调用grow(var:int)进行扩容，看下grow(var:int)的源码：
private void grow(int var1) {
int var2 = this.elementData.length;
int var3 = var2 + (var2 >> 1);
if (var3 - var1 < 0) {
var3 = var1;
}
if (var3 - 2147483639 > 0) {
var3 = hugeCapacity(var1);
}
this.elementData = Arrays.copyOf(this.elementData, var3);
}
第三行很关键，表示新的容量是原来的1.5倍，第八行的hugeCapacity是一种容错机制，如果超出了最大容量，那么容量就是最大容量+8：
private static int hugeCapacity(int var0) {
if (var0 < 0) {
throw new OutOfMemoryError();
} else {
return var0 > 2147483639 ? 2147483647 : 2147483639;
}
}
add(pos:int, val:E)
public void add(int var1, E var2) {
this.rangeCheckForAdd(var1);
this.ensureCapacityInternal(this.size + 1);
System.arraycopy(this.elementData, var1, this.elementData, var1 + 1, this.size - var1);
this.elementData[var1] = var2;
++this.size;
}
源码也很简单，扩容操作与add(val:E):boolean一模一样，特别的地方在第四行进行了数组的拷贝操作。
remove(val:int)
public E remove(int var1) {
this.rangeCheck(var1);
++this.modCount;
Object var2 = this.elementData(var1);
int var3 = this.size - var1 - 1;
if (var3 > 0) {
System.arraycopy(this.elementData, var1 + 1, this.elementData, var1, var3);
}
this.elementData[--this.size] = null;
return var2;
}
关键点还是第七行的System.arraycopy数组拷贝操作。
remove(val:Object):boolean
public boolean remove(Object var1) {
int var2;
if (var1 == null) {
for(var2 = 0; var2 < this.size; ++var2) {
if (this.elementData[var2] == null) {
this.fastRemove(var2);
return true;
}
}
} else {
for(var2 = 0; var2 < this.size; ++var2) {
if (var1.equals(this.elementData[var2])) {
this.fastRemove(var2);
return true;
}
}
}
return false;
}
private void fastRemove(int var1) {
++this.modCount;
int var2 = this.size - var1 - 1;
if (var2 > 0) {
System.arraycopy(this.elementData, var1 + 1, this.elementData, var1, var2);
}
this.elementData[--this.size] = null;
}
clone():Object
克隆出一个新的ArrayList，注意是浅拷贝。
public Object clone() {
try {
ArrayList var1 = (ArrayList)super.clone();
var1.elementData = Arrays.copyOf(this.elementData, this.size);
var1.modCount = 0;
return var1;
} catch (CloneNotSupportedException var2) {
throw new InternalError(var2);
}
}
Vector和Stack
理解了ArrayList，那么Vector就很简单了。首先，Vector 的扩容策略不太一样，不是1.5倍扩容，而是int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);，其中capacityIncrement是一个成员变量，其次Vector 是线程安全的，同步的，可用于多线程，基本上增删改查都是用关键synchronized进行修饰。
Stack就更简单了，Stack继承Vector，是利用Vector达到Stack特性(先进后出first in last out)。
