Java 容器源码分析之 Vector 与 Stack

JDK 文档中对Vector的描述是这样的:Vector 类实现了一个可增长的对象数组。像数组一样,可以通过整型索引来获取内容,但是 Vector 的大小可以按照实际元素数量的需求进行增长或收缩。Vector 和 ArrayList 非常接近,区别在于 ArrayList 的实现是非同步的,在多线程环境中可能出现线程不安全的情况,而 Vector 则是线程安全的。

Stack 类实现的就是我们非常常用的一种数据结构,栈,也称之为后进先出队列(LIFO)。栈的基本概念自不必多说,Java 中 Stack 类是基于 Vector 来实现的。

实际上,Vector 和 Stack 类已经不被推荐使用了,之所以仍然还保留是出于兼容性方面的考虑。通常情况下可以使用 ArrayList 来替代 Vector,在一些需要保证线程安全的情况下在外部进行同步或者使用Collections.synchronizedList方法。至于 Stack,官方的推荐是使用 Deque 接口的实现进行替代。

概览

Vector 类和 Stack 类的声明如下:

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

class Stack<E> extends Vector<E>

从类的声明来看,Vector 类和 ArrayList 是完全一致的,实际上它们俩的内部实现也是大致相同的,只是 Vector 类中的所有方法都使用 synchronized 关键字进行了修饰。

Stack 就是 Vector 的子类,对栈的所有操作 pop()push()peek() 都是在 Vector 的基础上进行实现的。

底层结构

Vector 类的底层也是是用数组进行数据存储的,同时维护了一个整型变量记录目前容器中元素的数量。除此以外,还使用了一个整型变量记录扩容时应该增加的容量大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
protected Object[] elementData;
protected int elementCount;
protected int 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);
}

从扩容方法grow()中可以看到,如果在构造函数中没有指定每次扩容时应该增加的容量大小,则每次扩容默认为容量加倍。这个和 ArrayList 中不太一样,ArrayList每次扩容是容量默认增加0.5倍。

Satck 的操作

由于 Stack 是在 Vector 的基础上实现的,而 Vector 又是基于数组进行实现的,栈顶就可以看作数组的尾部。Stack 类的实现非常的简略,下面简要地列出栈操作的内部实现。

入栈

入栈即通过 push(E item) 方法向栈中压入一个元素,其实现方法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
//Satck.java
public E push(E item) {
addElement(item);

return item;
}

//Vector.java
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}

其实就是向数组尾部添加一个元素。

获取栈顶元素

peek()方法的实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//Stack.java
public synchronized E peek() {
int len = size();

if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}

//Vector.java
public synchronized E elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}

return elementData(index);
}

就是返回数组尾部的最后一个有效元素。

出栈

将栈顶的元素弹出栈,pop(),实现如下:

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
//Stack.java
public synchronized E pop() {
E obj;
int len = size();

obj = peek();
removeElementAt(len - 1);

return obj;
}

//Vector.java
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 */
}

就是移除数组尾部的最后一个元素,并返回该元素。

查询

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
//Stack.java
public synchronized int search(Object o) {
int i = lastIndexOf(o);

if (i >= 0) {
return size() - i;
}
return -1;
}

//Vector.java
public synchronized int lastIndexOf(Object o) {
return lastIndexOf(o, elementCount-1);
}

public synchronized int lastIndexOf(Object o, int index) {
if (index >= elementCount)
throw new IndexOutOfBoundsException(index + " >= "+ elementCount);

if (o == null) {
for (int i = index; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = index; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

小结

Vector 类的实现和 ArrayList 比较接近,都是基于数组及扩容操作来完成的。只是 Vector 类为了保证线程安全性,在每个方法的声明中都使用了 synchronized 关键字,这势必会影响它的性能。Satck 类则是扩展了 Vector 类,实现了栈的各种操作。由于 Stack 类继承自 Vector,则同样继承了 Vector 类的各种方法。这个其实比较奇怪,因为对栈操作只需要入栈和出栈操作就可以了,完全可以不使用继承的方式,而使用包含的方式,即在Satck对象中使用 Vector 的引用。之所以采用了继承的方式,估计还是因为历史的包袱吧。

官方已经不推荐使用 Vector 和 Stack。要使用线程安全的 List,可以用 Collections.synchronizedList包裹 ArrayList。至于栈,则推荐使用 Deque 接口的实现,如 LinkedList 和 ArrayDeque。