系列文章：

• Java集合系列01之概览
• Java集合系列02之ArrayList源码分析
• Java集合系列03之LinkedList源码分析
• Java集合系列04之fail-fast机制分析
• Java集合系列05之Vector&Stack源码分析及List总结
• Java集合系列06之Map接口概览
• Java集合系列07之HashMap源码分析
• Java集合系列08之WeakHashMap源码分析
• Java集合系列09之TreeMap源码分析
• Java集合系列10之Hashtable源码分析

前言

Vector是矢量队列，JDK1.0版本添加的类，是一个动态数组，与ArrayList不同的是Vector支持多线程访问，是线程安全的，因为内部很多方法都被synchronized关键字修饰了，有同步锁，而且其内部有很多不属于集合框架的方法。其定义如下：

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

Vector继承了AbstractList，实现了List，RandomAccess, Cloneable， java.io.Serializable四个接口，支持随机访问。

Stack表示先进后出(FILO)的堆栈，是一种常见的数据结构，Stack继承了Vector，由于Vector是通过数组实现的，因此Stack也是通过数组实现的，而非链表。前面介绍LinkedList时，我们也说过可以把LinkedList当作Stack使用。

本文源码分析基于jdk 1.8.0_121

继承关系

Vector&Stack继承关系

java.lang.Object
  |___ java.util.AbstractCollection<E>
      |___ java.util.AbstractList<E>
          |___ java.util.Vector<E>
              |___ java.util.Stack<E>
所有已实现的接口：
Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess

关系图

Vector&Stack关系图

• elementData是Object[]类型的数组，保存了Vector的数据，是Vector的底层实现，它是个动态数组，在添加数据过程中不断扩展容量，初始化时若没有指定数组大小，则默认的数组大小是10；
• elementCount是动态数组的实际大小；
• capacityIncrement是数组容量增长的相关参数，创建Vector时如果指定了capacityIncrement，则Vector每次容量增加时，数组容量增加的大小就是capacityIncrement；创建Vector时没有指定capacityIncrement，则Vector每次容量增加一倍。

Stack中只定义了一些关于堆栈的操作方法，具体见下文。

构造函数

Vector一共有四个构造函数

// initialCapacity是Vector的默认容量大小
// capacityIncrement是每次数组容量增长的大小
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

// initialCapacity是Vector的默认容量大小
// 数组容量增加时，每次容量会增加一倍。
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

// 默认构造函数，默认容量为10
public Vector() {
    this(10);
}

// 创建包含集合c的数组
public Vector(Collection<? extends E> c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

Stack只有一个默认构造函数：

public Stack() {
}

API

Vector API

synchronized boolean        add(E e)
             void           add(int index, E element)
synchronized boolean        addAll(Collection<? extends E> c)
synchronized boolean        addAll(int index, Collection<? extends E> c)
synchronized void           addElement(E obj)
synchronized int            capacity()
             void           clear()
synchronized Object         clone()
             boolean        contains(Object o)
synchronized boolean        containsAll(Collection<?> c)
synchronized void           copyInto(Object[] anArray)
synchronized E              elementAt(int index)
Enumeration<E>              elements()
synchronized void           ensureCapacity(int minimumCapacity)
synchronized boolean        equals(Object o)
synchronized E              firstElement()
             E              get(int index)
synchronized int            hashCode()
synchronized int            indexOf(Object o, int index)
             int            indexOf(Object o)
synchronized void           insertElementAt(E obj, int index)
synchronized boolean        isEmpty()
synchronized E              lastElement()
synchronized int            lastIndexOf(Object o, int index)
synchronized int            lastIndexOf(Object o)
synchronized E              remove(int index)
             boolean        remove(Object o)
synchronized boolean        removeAll(Collection<?> c)
synchronized void           removeAllElements()
synchronized boolean        removeElement(Object obj)
synchronized void           removeElementAt(int index)
synchronized boolean        retainAll(Collection<?> c)
synchronized E              set(int index, E element)
synchronized void           setElementAt(E obj, int index)
synchronized void           setSize(int newSize)
synchronized int            size()
synchronized List<E>        subList(int fromIndex, int toIndex)
synchronized <T> T[]        toArray(T[] a)
synchronized Object[]       toArray()
synchronized String         toString()
synchronized void           trimToSize()

Stack API

       boolean     empty()
synchronized E     peek()
synchronized E     pop()
             E     push(E item)
synchronized int   search(Object o)

源码分析

Vector源码分析

成员变量

// 保存Vector数据
protected Object[] elementData;

// 实际数量
protected int elementCount;

// 容量增长数量
protected int capacityIncrement;

// 最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

改变容量值

// 将当前容量值设置为实际元素个数
public synchronized void trimToSize() {
    modCount++;
    int oldCapacity = elementData.length;
    if (elementCount < oldCapacity) {
        elementData = Arrays.copyOf(elementData, elementCount);
    }
}

确定容量

// 确认Vector容量，修改次数+1
public synchronized void ensureCapacity(int minCapacity) {
    if (minCapacity > 0) {
        modCount++;
        ensureCapacityHelper(minCapacity);
    }
}

// 帮助函数，minCapacity大于现在数组实际长度时扩容
private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 扩容，capacityIncrement>0 则将容量增大capacityIncrement
// 否则直接将容量扩大一倍
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);
}

// 当minCapacity超出Integer.MAX_VALUE时，minCapacity变为负数，抛出异常
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

// 设置容量值为 newSize
public synchronized void setSize(int newSize) {
    modCount++;
    // 如果newSize大于elementCount，则调整容量
    if (newSize > elementCount) {
        ensureCapacityHelper(newSize);
    } else { 
        // 如果newSize小于或等于elementCount，则将newSize位置开始的元素都设置为null
        for (int i = newSize ; i < elementCount ; i++) {
            elementData[i] = null;
        }
    }
    elementCount = newSize;
}

返回Enumeration

// 返回Vector中所有元素对应的Enumeration
public Enumeration<E> elements() {
    return new Enumeration<E>() {
        int count = 0;
        
        // 是否有下一个元素 类似Iterator的hasNext()
        public boolean hasMoreElements() {
            return count < elementCount;
        }
        
        // 获取下一个元素
        public E nextElement() {
            synchronized (Vector.this) {
                if (count < elementCount) {
                    return elementData(count++);
                }
            }
            throw new NoSuchElementException("Vector Enumeration");
        }
    };
}

增加元素

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

// index处添加元素
public void add(int index, E element) {
    insertElementAt(element, index);
}

// 在index处插入元素
public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

// 添加集合c
public synchronized boolean addAll(Collection<? extends E> c) {
    modCount++;
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityHelper(elementCount + numNew);
    System.arraycopy(a, 0, elementData, elementCount, numNew);
    elementCount += numNew;
    return numNew != 0;
}

// index处开始，将集合c添加到Vector中
public synchronized boolean addAll(int index, Collection<? extends E> c){
    modCount++;
    if (index < 0 || index > elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityHelper(elementCount + numNew);

    int numMoved = elementCount - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    elementCount += numNew;
    return numNew != 0;
}

// 将给定元素添加到Vector中
public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

删除元素

// 查找并删除元素obj
// 查找到则删除，返回true
// 查找不到则返回false
public synchronized boolean removeElement(Object obj) {
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

// 删除index处元素
public synchronized void removeElementAt(int index) {
    modCount++;
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    int j = elementCount - index - 1;
    if (j > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, j);
    }
    elementCount--;
    elementData[elementCount] = null; /* to let gc do its work */
}

// 删除所有元素
public synchronized void removeAllElements() {
    modCount++;
    // Let gc do its work
    for (int i = 0; i < elementCount; i++)
        elementData[i] = null;

    elementCount = 0;
}

// 删除元素o
public boolean remove(Object o) {
    return removeElement(o);
}

// 删除index位置处元素，并返回该元素
public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}

设置元素

// 设置index处元素为element，并返回index处原来的值
public synchronized E set(int index, E element) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

// 设置index处元素为obj
public synchronized void setElementAt(E obj, int index) {
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    elementData[index] = obj;
}

获取元素

// 获取index处元素
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

Stack源码分析

package java.util;

public class Stack<E> extends Vector<E> {
   
    // 构造函数
    public Stack() {
    }

    // 栈顶元素入顶
    public E push(E item) {
        // addElement的实现在Vector.java中
        addElement(item);
        return item;
    }

    // 删除栈顶元素
    public synchronized E pop() {
        E obj;
        int len = size();
        obj = peek();
        // removeElementAt的实现在Vector.java中
        removeElementAt(len - 1);
        return obj;
    }

    // 返回栈顶元素，不执行删除操作
    public synchronized E peek() {
        int len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    // 是否为空
    public boolean empty() {
        return size() == 0;
    }

    // 查找元素o在栈中位置，由栈底向栈顶方向
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);
        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

    // 版本ID
    private static final long serialVersionUID = 1224463164541339165L;
}

Stack的源码比较简单，内部也是通过数组实现的，执行push时将元素追加到数组末尾，执行peek时返回数组末尾元素（不删除该元素），执行pop时取出数组末尾元素，并将该元素从数组中删除。

Vector遍历方式

• 迭代器遍历

Iterator iter = vector.iterator();
while(iter.hasNext()) {
    iter.next();
}

• 随机访问

for (int i=0; i<vector.size(); i++) {
    vector.get(i);        
}

• foreach循环

for (Integer integ:vector) {
    ;
}

• Enumeration遍历

Enumeration enu = vector.elements();
while(enu.hasMoreElements()) {
    enu.nextElement();
}

以上各种方式中，随机访问效率最高。

List总结

概述

下面是List的关系图：

List

• List是接口，继承Collection，是一个有序队列
• AbstractList是抽象类，继承了AbstractCollection类，并实现了List接口，提供了 List 接口的大部分实现
• AbstractSequentialList 继承自 AbstractList，是 LinkedList 的父类，提供了List接口大部分实现。 AbstractSequentialList 实现了链表中的“随机访问”方法
• ArrayList，LinkedList，Vector，Stack是四个队列集合，List的四个实现类

比较

参考内容

• Java 集合系列06之 Vector详细介绍(源码解析)和使用示例
• Java 集合系列07之 Stack详细介绍(源码解析)和使用示例