Vector源码分析

Vector简介

Vector在JDK 1.0被引入，基于数组实现，并且是一个动态数组，其容量可以自动增长。在很多方法的实现上，Vector加入了同步语句，因此一般来说Vector是线程安全的，可以在多线程环境中运用。

本文对Vector源码的分析基于JDK 1.8.0_111，并仅对常用的方法进行分析。

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Vector类继承自AbstractList，AbstractList是一个抽象类，实现了List接口，AbstractList提供了实现一个List的基本骨架，包括add，remove，get，set，indexOf等方法。Vector实现了RandomAccess接口，因此可以随机访问。实现了Cloneable接口，允许克隆。实现了Serializable接口，可以被序列化。

实例变量

Vector内包含3个实例变量。

protected Object[] elementData;
protected int elementCount;
protected int capacityIncrement;

elementData是一个数组，用于存储Vector容器的元素，该数组有一个对应的属性capacity，capacity描述了elementData当前的长度。
elementCount描述了elementData内有效元素的个数。
capacityIncrement刻画了当要存储的元素的个数大于elementData的capacity时，elementData需要扩容的空间大小，即容器增长系数。

构造方法

Vector定义了4个构造方法。

Vector(int initialCapacity, int capacityIncrement);
Vector(int initialCapacity);
Vector();
Vector(Collection<? extends E> c);

当我们直接new一个Vector时，即调用Vector的默认构造方法，实际上，Vector的默认构造方法调用this(10)，即调用Vector(int initialCapacity)，并将initialCapacity设置为10，接着Vector(int initialCapacity)再调用this(initialCapacity, 0)，并将capacityIncrement设置为0。从以上我们可以得知，对于一个默认构造的Vector对象，它的默认存储空间可以存储10个元素，且容器增长系统等于0。

私有方法

Vector定义了3个重要的私有方法ensureCapacityHelper(int minCapacity)、void grow(int minCapacity)和int hugeCapacity(int minCapacity)，这3个方法用于实现Vector的自动扩容，Vector中很多涉及到影响Vector元素变化的操作都会直接或者间接的调用这3个方法，源码如下。

private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

我们可以关注Vector的add(E e)方法，在往Vector内新增元素前，需要确保存储Vector元素的数组elementData有充足的空间，这一步通过ensureCapacityHelper来实现，ensureCapacityHelper接收elementCount + 1作为参数，确保Vector至少有一个空闲的空间存储新增的元素。当Vector不具备多余的空间时（minCapacity - elementData.length > 0），ensureCapacityHelper就会调用grow方法扩充elementData数组。在扩充数组时，如果capacityIncrement不大于0，那么Vector就会开辟出2倍于原elementData数组长度的空间，并通过Arrays.copyOf将原elementData中的元素拷贝到新地址空间。另外，Vector容量的扩充也是有限制的，从hugeCapacity方法可以看出，Vector的容量最大扩充至Integer.MAX_VALUE。

Vector中定义了大量的用于操作容器的方法，其中绝大多数设计到改变容器大小的方法都是在底层做两件事，一是开辟新的存储空间（如果有必要），二是进行数组的拷贝。这些方法理解起来并不难，此处不再赘述。

线程安全

在很多面试环节中，经常被问到的问题是ArrayList和Vector的区别是什么？关于这个问题，最频繁的回答可能是Vector是线程安全的，而ArrayList是非线程安全的。这样回答的原因是在Vector的方法中，几乎所有的操作容器的方法上都加了synchronized，这意味着访问这些方法前都需要获得对象的锁。因此，这些方法不会被多个线程同时访问，从而实现线程安全。

Java并发编程实战一书中提到：如果只是将每个方法都作为同步方法（比如Vector，简单的在方法前加上synchronized），那么并不足以确保复合操作是原子的，以Vector为例，观察如下代码片段。

if(!vector.contains(element)) {
    vector.add(element);
}

这是一个经典的put-if-else问题，虽然通过synchronized已确保contains方法和add方法都是原子的，但是如果把多个操作合并为一个复合操作，仍旧需要额外的加锁机制。否则，多线程环境下，在contains方法和add方法的执行间隙期间完全有可能经历一个线程获取contains上的锁，执行完contains方法后释放锁，然后锁又被另一线程获取，并执行了add方法，然后释放锁，锁又被原来执行contains方法的线程获取，然后执行add方法，此时，该线程可能已经基于一个错误的假设在执行add方法了（Vector内可能已经存在该线程即将要add的元素了）。