Stack&Vector源码分析

今天来分析一下Stack的源码。还是先看一下Stack类的声明。

public class Stack<E> extends Vector<E>

可以看到Stack类扩展了Vector类,这点有些出乎人的意料。不读源码的话,我想我是不会猜到Stack类竟然还会是Vector的子类。我们知道Vector是一种线程安全的数据结构,而我们前面分析的LinkedList和ArrayList都不是线程安全的。除了线程是否安全之外,Vector和ArrayList功能上大概可以等同。不过随着jdk的发展,jdk中提供了更加强大的并发类,而在每个方法上都使用synchronized来修饰从而实现线程安全目的的Vector慢慢的就淡出了人们的使用。

在Stack的源码注释中,就有如下的声明。

A more complete and consistent set of LIFO stack oerations is provided by the Deque interface and its implementions, which should be used in preference to this class. For example:

Deque stack = new ArrayDeque();

可以看出,官方同样也并不推荐继续使用Stack。有类似需求的话,应该优先使用实现了Deque接口的类,比如ArrayDeque。

Stack相对来说比较简单,一共就提供了五个函数的实现peek()、pop()、push()、empty()、indexOf(),对应了栈的常用操作。功能实现上真的超级简单,并没有什么需要说明的,注意一下Stack是线程安全的类就可以了。

Stack分析完,就顺势分析一下Vector的源码吧。

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

以上就是Vector的声明,发现了什么?想一下ArrayList的声明,是不是完全一样?

前面提到过,Vector是线程安全的类,实现的方式是通过在所有的方法中添加了synchronized修饰符。synchronized修饰符保证了同一时刻只有一个线程能够访问,避免了在多个线程征用情况下带来的数据竞争问题。不过带来的负面作用就是牺牲了性能。因此,官方推荐在单线程使用的情况下,使用ArrayList代替Vector类。

先来看一下定义的变量。

protected Object[] elementData;
protected int elementCount;

有了ArrayList的基础,这两个变量不用多说。elementData是用来存放数据的数组,elementCount是Vector中真正的元素个数。

protected int capacityIncrement

这个变量用于标识当vector需存储的数据个数大于它的容量的时候,自动增长的大小。当这个变量小于等于0的时候,vector的容量会在它需要扩容的时候增长为原来的两倍。

The amount by which the capacity of the vector is automatically incremented when its size becomes greater than its capacity. if the capacity increment is less than or equal to zero, the capacity of the vector is doubled each time it needs to grow.

现在来看的话,好像并不很能理解这个变量的作用。下面分析到具体代码的时候,再行分析。

看一下Vector提供的构造函数。

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

public Vector() {
    this(10);
}

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

从以上代码中,我们能够明白两件事情。

  1. 在不提供默认容量的情况下,Vector的初始容量是10。
  2. 由以上的构造函数中,清楚了上面所说的capacityIncrement变量的作用。这个变量可以在构造Vector的时候进行手动的指定。如果不指定的话,默认为0。即在进行Vector扩容的时候,扩容之后容量变为原来的2倍。
  3. 无参的构造函数,默认构造了一个容量为10的数组。这与ArrayList不同,无参构造中,ArrayList会先构造一个空数组,在首次进行数据新增的时候,才会扩容成为一个容量为10的数组(或是更大容量)。

清楚了上面第二点之后,我们下面来看一下Vector的扩容操作的相关函数。

public synchronized void ensureCapacity(int minCapacity) {
    if (minCapacity > 0) {
        modCount++;
        ensureCapacityHelper(minCapacity);
    }
}

private void ensureCapacityHelper(int minCapacity) {
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

private void grow(int minCapacity) {
    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);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) {
        throw new OutOfMemoryError();
    }
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

相比之下,Vector的扩容操作比ArrayList的扩容操作也简单了一下。大概分为如下几步。

  1. 根据capacityIncrement的大小来确定第一个新容量值。
  2. 如果新的容量值还是小于需要的最小容量值的话,直接把容量值设置为最小容量值。
  3. 如果新的容量值大于MAX_ARRAY_SIZE的话,则进入hugeCapacity逻辑。hugeCapacity主要用于判断是否发生了溢出。

Vector还有另外一个接收Collection的参数。

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

在以上代码中,使用了Arrays.copyOf函数。Arrays.coyOf的内部实现中使用了System.arraycopy函数,无需多说。

关于Vector的add、remove等操作,和ArrayList的操作大同小异,不再进行具体分析。同时,Vector也同样提供了iter()、listIterator()、listIterator(int index)操作函数。

Comments
Write a Comment