当前位置 博文首页 > 龚厂长的博客：java8 常用集合类汇总详解之List
java提供了众多的集合类，比如List、Set等，本文及后面的几篇文章将对常用的集合类的实现原理做汇总介绍。
下图是常用的集合类接口。
接下来对每个接口，我都找出常用的实现类，介绍一下它们的实现原理。
List的实现类主要是ArrayList、LinkedList、Vector、CopyOnWriteArrayList、Stack。
ArrayList是使用数组实现的线性表，或者说是使用顺序存储结构实现的线性表。
它内部有一个数组elementData用于存储元素：
transient Object[] elementData;
在java8以前，创建ArrayList如果不指定初始元素个数，java默认是16个，在java8里面如果不指定元素个数，java会创建一个空的数组对象，等到添加元素时，java8在重新创建一个长度为10的数组。代码如下：
//调用add方法添加一个元素
public boolean add(E e) {
//如果没有设置初始容量，size =0
ensureCapacityInternal(size + 1); //检查数组容量是否可以，如果不可以则扩长
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算数组容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果是调用ArrayList()构造方法创建的对象，那么elementData初始值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//DEFAULT_CAPACITY=10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
//扩大空间
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//默认每次在原来容量的基础上增加一半
int newCapacity = oldCapacity + (oldCapacity >> 1);
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()创建ArrayList对象时，第一次添加元素，数组长度会被更新为10，之后当容量不足时，都会在原来基础上增加原来的一半。
而如果初始时，设置容量为0：new ArrayList(0)，那么添加元素时，一开始是长度会被更新为1，之后是2,3,4,6，再往后才会每次都在原来基础上增加原来的一半。
删除元素不会造成数组长度的减少。
LinkedList是使用链表结构实现的线性表。该类只有三个属性：
//表示元素个数
transient int size = 0;
//链表的头结点
transient Node<E> first;
//链表的尾结点
transient Node<E> last;
下面是Mode的定义：
private static class Node<E> {
E item;//当前节点元素值
Node<E> next;//下一个节点
Node<E> prev;//上一个节点
}
Node使用next和prev将链表连接起来，形成下面这个结构：
大家很容易看出来，这是一个双向链表，LinkedList确实也是一个双向链表，它实现了Deque接口。
创建LinkedList对象时，first和last都会设置为null，当新增一个元素时，first和last都会指向该元素：
因此，只要是first或者last等于null，就表示链表是空的。
与ArrayList不同，LinkedList没有设置初始容量的构造方法。另外，尽管LinkedList是一个双向链表的，但是调用add(int index, E element)指定在index位置新增元素，如果index超过了链表的长度，LinkedList会抛出异常IndexOutOfBoundsException。
Vector与ArrayList类似，也是数组结构的，使用下面的数组存储元素：
protected Object[] elementData;
如果不指定初始容量，Vector默认创建一个长度为10的数组：
public Vector() {
this(10);//10表示elementData的初始长度
}
与ArrayList不同的是，我们还可以设置当容量不足时，数组每次扩充的长度。
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
//capacityIncrement表示容量不足，elementData需要增加的元素个数
this.capacityIncrement = capacityIncrement;
}
当容量不足时，调用下面的方法扩充数组长度：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//如果capacityIncrement不为0，那么每次数组扩长capacityIncrement
//否则每次扩长一倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
Vector的大部分方法都有synchronized关键字，也就意味着每次增加、删除、修改、查询都只能单线程操作。但也并不意味着该对象可以在多线程环境中安全使用。
Stack表示栈，它是Vector的子类，栈这个数据结构比较简单，只能操作栈顶元素。该类提供了压栈（push）和出栈（pop和peek，pop删除栈顶元素，peek不删除只返回）。
CopyOnWriteArrayList使用写时复制技术，保证了该类是线程安全的。它也是使用数组存储元素：
private transient volatile Object[] array;
初始时，如果不指定容量，数组长度为0：
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
每次新增元素时，都在原长度基础上加1，删除元素时，数组array的长度也会减少，这也就是说数组array的长度与元素个数完全一致。
那么CopyOnWriteArrayList是如何保证线程安全的？下面来看一下add()方法：
public boolean add(E e) {
final ReentrantLock lock = this.lock;//锁
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
//新建一个长度为len+1的数组
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
CopyOnWriteArrayList提供了一个锁lock，下面是属性lock的定义：
final transient ReentrantLock lock = new ReentrantLock();
每次需要做结构性修改（增减元素、替换元素、排序）时，都是先上锁，上锁成功后，新建一个数组，并将原数组元素都拷贝到新数组中，之后在新数组的基础上修改，修改完成后，替换旧数组。
因为做结构性修改的操作都需要先加锁，因此保证了同时只有一个线程对数组做修改，而且修改是在新数组的基础上，对旧数组没有影响，因此读操作是可以并行处理的。它适用于读多写少的场景。
cshttp://ifeve.com/java-copy-on-write/
