「vector」Java8源码-Vector

vector

前几天学习了ArrayList源码和迭代器模式在ArrayList源码中的使用，今天开始学习vector源码。参考的JDK版本为1.8。

相信大家对Vector的使用已经很熟悉了，它和ArrayList的最大的不同是它是线程安全的，这点在Vector源码中也有说明。Vector源码中注释有这么一句“Vector is synchronized. If a thread-safe implementation is not needed, it is recommended to use ArrayList in place of Vector”，意为“Vector 是同步的。如果不需要线程安全的实现，推荐使用ArrayList代替Vector”。Vector 是如何线程安全的？除了线程安全之外，它和ArrayList 还有其他不同吗？本文将分析Vector 的内部结构及实现原理，帮助大家更好的使用它。

Vector 层次结构图

先来看看ArrayList的定义

public class Vector<E> extends AbstractList<E> implements List<E>,RandomAccess, cloneable, java.io.serializable

从中我们可以了解到

Vector<E>：说明它支持泛型
extends AbstractList<E> implements List<E>：说明它继承了extends AbstractList<E>，并实现了implements List<E>。
implements RandomAccess：表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。下面是jdk1.8中对RandomAccess的介绍：

Marker interface used by <tt>List</tt> implementations to indicate that they support fast (generally constant time) random access.  The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when APPlied to either random or sequential access lists.

implements Cloneable：表明其可以调用clone()方法来返回实例的field-for-field拷贝。
implements java.io.Serializable：表明该类是可以序列化的。

但继承实现信息还不够完整，我建议大家以后查看一个类的继承实现关系的时候，使用类结构层次图。

如何查看类层次结构图可以参考我写过的一篇文章：

Eclipse-查看继承层次图/继承实现层次图

全局变量

/**
 * 保存vector中元素的数组。vector的容量是数组的长度，数组的长度最小值为vector的元素个数。
 * 
 * 任何在vector最后一个元素之后的数组元素是null。
 * 
 * @serial
 */
protected Object[] elementData;

/**
 * vector中实际的元素个数。
 * 
 * @serial
 */
protected int elementCount;

/**
 * vector需要自动扩容时增加的容量。
 * 
 * 当vector的实际容量elementCount将要大于它的最大容量时，vector自动增加的容量。
 * 
 * 如果capacityIncrement小于或等于0，vector的容量需要增长时将会成倍增长。
 * @serial
 */
protected int capacityIncrement;

/**
 * 序列版本号
 */
private static final long serialversionuid = -2767605614048989439L;

构造方法

接下来，看Vector提供的构造方法。ArrayList提供了四种构造方法。

1.构造一个指定容量为capacity、自增容量为capacityIncrement的空vector。

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new illegalargumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

2.构造一个指定容量为initialCapacity、自增容量为0的空vector。

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

3.构造一个指定容量为10、自增容量为0的空vector。

public Vector() {
    this(10);
}

4.使用指定的Collection构造vector。

public Vector(Collection<? extends E> c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

方法

copyInto

/**
 * 将vector中的所有元素拷贝到指定的数组anArray中
 * 
 * @param  anArray 指定的数组anArray，用来存放vector中的所有元素
 * 
 * @throws NullPointerException 如果指定的数组anArray为null
 * @throws IndexOutOfBoundsException 如果指定的数组anArray的容量小于vector的元素个数
 * @throws ArrayStoreException 如果vector不能被拷贝到anArray中
 * @see #toArray(Object[])
 */
public synchronized void copyInto(Object[] anArray) {
    System.arraycopy(elementData, 0, anArray, 0, elementCount);
}

trimToSize()

/**
 * 将底层数组的容量调整为当前vector实际元素的个数，来释放空间。
 */
public synchronized void trimToSize() {
    modCount++;
    int oldCapacity = elementData.length;
    ////当实际大小小于底层数组的长度
    if (elementCount < oldCapacity) {
        //将底层数组的长度调整为实际大小
        elementData = Arrays.copyOf(elementData, elementCount);
    }
}

ensureCapacity

该方法的实现和ArrayList中大致相同。不同的是在第一次扩容时，vector的逻辑是：

newCapacity = oldCapacity + ((capacityIncrement > 0) ?

capacityIncrement : oldCapacity);

即如果capacityIncrement>0，就加capacityIncrement，如果不是就增加一倍。

而ArrayList的逻辑是：

newCapacity = oldCapacity + (oldCapacity >> 1);

即增加现有的一半。

/**
 * 增加vector容量
 * 如果vector当前容量小于至少需要的容量，它的容量将增加。
 * 
 * 新的容量将在旧的容量的基础上加上capacityIncrement，除非capacityIncrement小于等于0，在这种情况下，容量将会增加一倍。
 *
 * 增加后，如果新的容量还是小于至少需要的容量，那就将容量扩容至至少需要的容量。
 *
 * @param minCapacity 至少需要的容量
 */
public synchronized void ensureCapacity(int minCapacity) {
    if (minCapacity > 0) {
        modCount++;
        ensureCapacityHelper(minCapacity);
    }
}


/**
 * ensureCapacity()方法的unsynchronized实现。
 * 
 * ensureCapacity()是同步的，它可以调用本方法来扩容，而不用承受同步带来的消耗
 * 
 * @see #ensureCapacity(int)
 */
private void ensureCapacityHelper(int minCapacity) {
    // 如果至少需要的容量 > 数组缓冲区当前的长度，就进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * 分派给arrays的最大容量
 * 为什么要减去8呢？
 * 因为某些VM会在数组中保留一些头字，尝试分配这个最大存储容量，可能会导致array容量大于VM的limit，最终导致outofmemoryERROR。
 */
private static final int MAX_ARRAY_SIZE = integer.MAX_VALUE - 8;

/**
* 扩容，保证vector至少能存储minCapacity个元素。
* 首次扩容时，newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);即如果capacityIncrement>0，就加capacityIncrement，如果不是就增加一倍。
* 
* 如果第一次扩容后，容量还是小于minCapacity，就直接将容量增为minCapacity。
* 
* @param minCapacity 至少需要的容量
*/
private void grow(int minCapacity) {
    // 获取当前数组的容量
    int oldCapacity = elementData.length;
    // 扩容。新的容量=当前容量+当前容量/2.即将当前容量增加一倍
    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) {
    //如果minCapacity<0，抛出异常
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //如果想要的容量大于MAX_ARRAY_SIZE，则分配Integer.MAX_VALUE，否则分配MAX_ARRAY_SIZE
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

用到的设计模式

详情请参考：Vector与迭代器模式

总结

从源码中，我们不难论证以前对Vector的了解

Vector底层是数组。

/**
 * 保存vector中元素的数组。vector的容量是数组的长度，数组的长度最小值为vector的元素个数。
 * 
 * 任何在vector最后一个元素之后的数组元素是null。
 * 
 * @serial
 */
protected Object[] elementData;

有序。Vector底层是数组，数组是有序的。
可重复。数组是可重复的。
随机访问效率高，增删效率低。通过索引可以很快的查找到对应元素，而增删元素许多元素的位置都要改变。
线程安全。很多方法都是synchronized的。

本文已收录于Java8容器源码札记专栏。

Java8源码-Vector

vector

Vector 层次结构图

全局变量

构造方法

方法

copyInto

trimToSize()

ensureCapacity

用到的设计模式

相关阅读

栏目导航

推荐阅读

热门阅读