ArrayList、Vector和Collections.synchronizedList()

ArrayList和Vector

前两天看了ArrayList的源码，然后想起Vector来，常常会将两者一起做对比。不过一想起Vector马上要被判死刑了，就懒得去看Vector的源码，于是网上查了一下两者的区别。

1. ArrayList是线程不安全的，Vector是线程安全的。
2. 两者扩容方式不同。在底层数组容量不足时，ArrayList会将容量扩容为原来的1.5倍。而Vector支持在创建的时候主动声明扩容时增加的容量的大小，通过Vector(int initialCapacity, int capacityIncrement)构造函数实现。如果没有声明，或者capacityIncrement <= 0，那么默认扩容为原来的2倍。见下列代码：

// Vector的扩容方法
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);
}

Vector和Collections.synchronizedList

好吧，其实今天不是要讨论扩容方面的差异，主要是要看一下线程安全方面的。

虽然是ArrayList是线程不安全的，但是通过Collections.synchronizedList()方法可以将线程不安全的List转成线程安全的List。但是呢，在oracle的文档里，有这么一句话：

If you need synchronization, a Vector will be slightly faster than an ArrayList synchronized with Collections.synchronizedList.

Vector比Collections.synchronizedList快一点点？那这一点点到底是快在哪里呢？我们看一下SynchronizedList的代码。

public static <T> List<T> synchronizedList(List<T> list) {
   return (list instanceof RandomAccess ?
           new SynchronizedRandomAccessList<>(list) :
           new SynchronizedList<>(list));
}

static class SynchronizedList<E>
   extends SynchronizedCollection<E>
   implements List<E> {
   private static final long serialVersionUID = -7754090372962971524L;

   final List<E> list;

   SynchronizedList(List<E> list) {
       super(list);
       this.list = list;
   }
   SynchronizedList(List<E> list, Object mutex) {
       super(list, mutex);
       this.list = list;
   }

   public boolean equals(Object o) {
       if (this == o)
           return true;
       synchronized (mutex) {return list.equals(o);}
   }
   public int hashCode() {
       synchronized (mutex) {return list.hashCode();}
   }

   ...下面的代码大多类似，就省略了
}

从代码中可以看出，SynchronizedList<E>类使用了委托(delegation)，实质上存储还是使用了构造时传进来的list，只是将list作为底层存储，对它做了一层包装。正是因为多了一层封装，所以就会比直接操作数据的Vector慢那么一点点。

从上面的代码我们也可以看出来，SynchronizedList的同步，使用的是synchronized代码块对mutex对象加锁，这个mutex对象还能够通过构造函数传进来，也就是说我们可以指定锁定的对象。而Vector则使用了synchronized方法，同步方法的作用范围是整个方法，所以没办法对同步进行细粒度的控制。而且同步方法加锁的是this对象，没办法控制锁定的对象。这也是vector和SynchronizedList的一个区别。

线程安全并不"安全"

可能有些同学有在多线程环境下使用List的需求，所以选择了Vector或者Collections.SynchronizedList，然后就以为可以再多线程环境下安全地操作List了。但是这种想法可能会导致代码出现不可预料的错误，因为虽然Vector(以Vector为例)实现了各个方法操作的线程安全，但是当多个方法之间进行协作时，却依然会出现race condition。

比如if(!list.contains(o)) list.add(o);，还有Collections.swap(list, i, j);，如果不在外部手工加锁的话，多线程环境下，这都会出现问题。尤其是对于List经常会使用到的迭代。看一下下面这段代码：

public static void main(String[] args) throws InterruptedException {
    Vector<Integer> vector = new Vector<>();
    // 先存放1000个值让iterator有值可以遍历
    for (int i = 0; i < 1000; i++) {
        vector.add(i);
    }

    Thread iteratorThread = new Thread(new IteratorRunnable(vector));
    iteratorThread.start();

    // 主线程休眠5秒，让iteratorThread能够充分跑起来。这段时间是不会有问题的。
    TimeUnit.SECONDS.sleep(5);

    // 该线程启动之后，会结构化修改Vector，然后就会抛出ConcurrentModificationException异常
    Thread modifyVectorThread = new Thread(new ModifyVectorRunnable(vector));
    modifyVectorThread.start();
}

/**
 *  这个Runnable会不断使用迭代器(for-each语句)遍历Vector
 */
private static class IteratorRunnable implements Runnable {

    private Vector<Integer> vector;

    public IteratorRunnable(Vector<Integer> vector) {
        this.vector = vector;
    }

    @Override
    public void run() {
        while(true) {
            for (Integer i : vector) {

            }
        }
    }
}

/**
 * 这个Runnable会不断添加新元素，也就是会结构化修改Vector
 */
private static class ModifyVectorRunnable implements Runnable {
    private Vector<Integer> vector;

    public ModifyVectorRunnable(Vector<Integer> vector) {
        this.vector = vector;
    }

    @Override
    public void run() {
        while(true) {
            vector.add(1);
        }
    }
}

IteratorRunnable用来模拟迭代Vector的线程，ModifyVectorRunnable用来模拟结构化修改Vector的线程。在main函数中，iteratorThread首先开始运行，不断迭代Vector的值。主线程休眠5s，在这5s内，iteratorThread是没有问题的。5s过后，modifyVectorThread开始运行，该线程会向Vector内添加元素，也就是结构化修改Vector。

有些同学可能觉得这段代码不会有问题，因为Vector是线程安全的，在多线程环境下理应正常运行。但是这个线程安全是有缺陷的，再迭代的情况下，我们需要的实际上是对整个迭代过程加锁，而不是对迭代器的hasNext、next等单独的方法加锁。这段代码会报ConcurrentModificationException异常。如图：

结果

解决方案很简单，对IteratorRunnable的迭代过程加锁就可以了：

public void run() {
    while(true) {
        // 对迭代过程加锁
        synchronized (vector) {
            for (Integer i : vector) {

            }
        }
    }
}

参考资料：Vector vs Collections.synchronizedList(ArrayList)

Vector vs SynchronizedList performance