1. 简介

Vector跟ArrayList一样是一个基于数组实现的List，只不过Vector是线程安全的，在可能出现线程安全性问题的方法，Vector都加上了关键字synchronized。
与ArrayList一样，Vector查找元素的时间复杂度是O(1)，插入删除时间复杂度为O(n)。

2. 实现

属性

1
2
3
4
5
6
7
8
// 数组最大大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 存储元素的数组
protected Object[] elementData;
// 元素数量
protected int elementCount;
// 扩容增量
protected int capacityIncrement;

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 自定义初始容量与扩容增量
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    // 初始容量小于0抛出非法参数异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

// 未给出扩容增量默认为0，以后每次扩容后大小都为原来大小的2倍
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

// 默认初始容量为10
public Vector() {
    this(10);
}

扩容函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 确保最小容量为minCapacity
private void ensureCapacityHelper(int minCapacity) {
    // 判断是否需要扩容，需要则扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 扩容函数
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 如果扩容增量大于0则扩大capacityIncrement，否则扩容为原来的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);
}

增删改查方法

Vector在这些方法的实现上与ArrayList基本一致，但为保证线程安全所以在所有可能出现线程安全问题的方法一律加上synchronized关键字，这在非多线程下使用效率不及ArrayList高，而要想要高效的使用
线程安全的List，CopyOnWriteArrayList是一个更好的选择。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 获取数组指定索引上的元素
E elementData(int index) {
    return (E) elementData[index];
}

// 获取指定索引上的值，增加了index的有效范围判断
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(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;
}

// 添加元素e到List后面
public synchronized boolean add(E e) {
    modCount++;
    // 确保最小容量
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

// 移除指定索引上的元素
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;
}