Java 集合框架：Vector、Stack 的介绍、使用、原理与源码解析

作者：知新_RL | 2024-06-29 00:59:29

踩

大家好，我是栗筝i，这篇文章是我的 “栗筝i 的 Java 技术栈” 专栏的第 015 篇文章，在 “栗筝i 的 Java 技术栈” 这个专栏中我会持续为大家更新 Java 技术相关全套技术栈内容。专栏的主要目标是已经有一定 Java 开发经验，并希望进一步完善自己对整个 Java 技术体系来充实自己的技术栈的同学。与此同时，本专栏的所有文章，也都会准备充足的代码示例和完善的知识点梳理，因此也十分适合零基础的小白和要准备工作面试的同学学习。当然，我也会在必要的时候进行相关技术深度的技术解读，相信即使是拥有多年 Java 开发经验的从业者和大佬们也会有所收获并找到乐趣。

–

Java 集合框架（Java Collections Framework）是 Java 标准库中的一个核心组件，它提供了一套用于处理数据集合的接口和类。作为其中的重要成员，Vector 和 Stack 在特定场景中扮演着关键角色。Vector 是一种同步的动态数组，实现了 List 接口，适用于需要线程安全的场景；而 Stack 是 Vector 的子类，提供了后进先出（LIFO）的数据结构操作。本文将对 Vector 和 Stack 进行全面的介绍，探讨它们的使用方法、工作原理以及源码实现，以帮助开发者深入理解和高效使用这些集合类。同时，通过源码解析，我们将揭示其内部机制，为优化和定制提供有力支持。

文章目录

1、 Vector 与 Stack

写在前面：在开始介绍 Vector 与 Stack 之前，我们首先应该了解的是 Vector 与 Stack 这两个类在如今的 Java 版本中都早已过时，在 Java 出于对向后兼容性的考虑，才没有删除。但是我们不会因此认为 Vector 与 Stack 的实现是没有必要了解了，因为二者依旧会偶尔出现在面试问题当中。

1.1、Vector 概述

Vector 与 ArrayList 一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写 Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问 ArrayList慢。

Vector 的思路和 ArrayList 基本是相同的，底层是数组保存元素，Vector 默认的容量是10，有一个增量系数，如果指定，那么每次都会增加一个系数的大小，否则就扩大一倍。

Vector 扩容的时候，其实就是数组的复制，其实还是比较耗时间的，所以，我们使用的时候应该尽量避免比较消耗时间的扩容操作。

Vector 和 ArrayList 最大的不同，是它是线程安全的，几乎每一个方法都加上了 Synchronize 关键字，所以它的效率相对也比较低一点。ArrayList 如果需要线程安全，可以使用 Collections.synchronizedList(new ArrayList(...)); 方法，获取一个线程安全的 List。

1.2、Stack 概述

Stack 是 Java 集合框架中的一个类，它继承自 Vector，因此它本质上也是一个线程安全的动态数组。但是，Stack 类被设计为了一个后进先出（LIFO, Last In First Out）的数据结构，通常被称为栈。

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶；
出栈：栈的删除操作叫做出栈。出数据在栈顶。

2、Vector 的具体实现原理

2.1、Vector 底层的数据结构

与 ArrayList 类似（基本一致），Vector 内部也使用了动态数组来存储元素。

package java.util;

import ...
  

public class Vector<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  	// 省略其他方法和实现细节
  	...
      
    // 存储元素的数组  
    protected Object[] elementData;  
  
    // 当前向量中元素的数量  
    protected int elementCount;  
  
    // 容量增量，用于指定每次容量不足时增长的大小，如果小于等于0，则每次增长一倍  
    protected int capacityIncrement;     
  
      /**  
     * 构造一个具有指定初始容量和容量增量的空向量。  
     *  
     * @param initialCapacity 向量的初始容量  
     * @param capacityIncrement 向量的容量增量  
     * @throws IllegalArgumentException 如果指定的初始容量是负数  
     */  
    public Vector(int initialCapacity, int capacityIncrement) {  
        super();  
        if (initialCapacity < 0)  
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);  
        this.elementData = new Object[initialCapacity];  
        this.capacityIncrement = capacityIncrement;  
    }  
  
    /**  
     * 构造一个具有指定初始容量的空向量，其容量增量等于零。  
     *  
     * @param initialCapacity 向量的初始容量  
     * @throws IllegalArgumentException 如果指定的初始容量是负数  
     */  
    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
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
48
49
50
51
52
53
54
55

2.2、Vector 的扩容

Vector 的扩容方式依旧与 ArrayList 相同，当元素数量超过当前容量时，Vector 会复制一个新的更大容量的数组。可能在扩容上的主要不同就是 Array 的一次扩容为原数组的 1.5 倍（int newCapacity = oldCapacity + (oldCapacity >> 1)）而 Vector 的扩容在不指定 capacityIncrement 的值得情况下为 2 倍（int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); ）。

public class Vector<E>  
    extends AbstractList<E>  
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {  
  
    // ... 其他成员变量和方法 ...  
  
  	// 容量增量，用于指定每次容量不足时增长的大小，如果小于等于 0，则每次增长一倍  
    protected int capacityIncrement;     
  
  	// ... 其他成员变量和方法 ...  
  
    /**  
     * 将指定的元素作为此向量的最后一个元素插入。  
     *  
     * @param obj 要添加到此向量的元素  
     * @throws NullPointerException 如果指定的元素为 {@code null} 并且此向量不允许 null 元素  
     * (由具体实现决定)  
     */  
    public synchronized void addElement(E obj) {  
        modCount++; // 修改计数器增加，表示结构已修改  
        ensureCapacityHelper(elementCount + 1); // 确保容量足够  
        elementData[elementCount++] = obj; // 在当前末尾添加元素，并更新元素计数  
    }  
  
    /**  
     * 辅助方法，确保此向量的容量至少为指定的最小容量。  
     * 如果当前容量小于最小容量，则增加容量。  
     *  
     * @param minCapacity 所需的最小容量  
     */  
    private void ensureCapacityHelper(int minCapacity) {  
        // overflow-conscious code（防止溢出的代码）  
        if (minCapacity - elementData.length > 0)  
            grow(minCapacity); // 如果最小容量大于当前容量，则增加容量  
    }  
  
    /**  
     * 增加此向量的容量，以确保其至少能容纳指定的最小容量。  
     * 如果指定的最小容量大于当前容量，则此向量的容量将增加至大于或等于最小容量的最小可能值。  
     *  
     * @param minCapacity 所需的最小容量  
     */  
    private void grow(int minCapacity) {  
        // overflow-conscious code（防止溢出的代码）  
        int oldCapacity = elementData.length;  
        // 根据 capacityIncrement（如果大于0）或当前容量来计算新容量  
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?  
                                         capacityIncrement : oldCapacity);  
        // 如果新容量仍然小于最小容量，则直接使用最小容量  
        if (newCapacity - minCapacity < 0)  
            newCapacity = minCapacity;  
        // 检查新容量是否超过 MAX_ARRAY_SIZE，如果是，则调用 hugeCapacity 方法获取适当的大小  
        if (newCapacity - MAX_ARRAY_SIZE > 0)  
            newCapacity = hugeCapacity(minCapacity);  
        // 使用新的容量复制数组  
        elementData = Arrays.copyOf(elementData, newCapacity);  
    }  
  
  	// ... 其他成员变量和方法 ...  

}
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61

2.3、Vector 对线程安全的实现

Vector 类和 ArrayList 类的最大区别在于线程安全性。Vector 类是线程安全的，可以在多线程环境中使用，但是性能相对较低。而 ArrayList 类不是线程安全的，性能相对较高。

而 Vector 的线程安全性的实现方式就是在与 Array 基本相同的方法之前加 synchronized 关键字。

public class Vector<E>  
    extends AbstractList<E>  
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {  
  
    // ... 其他成员变量和方法 ...  
  
		public synchronized E get(int index) {...}
  	public synchronized E set(int index, E element) {...}
    public boolean remove(Object o) {...}
    public void add(int index, E element) {...}
    
  	// ... 其他成员变量和方法 ...  

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3、Stack 的具体实现原理

Stack 的具体实现十分简单“

/**  
 * Stack 类表示后进先出（LIFO）的对象堆栈。  
 * 它继承自 Vector 类，提供了堆栈的一些基本操作，如 push、pop、peek 等。  
 *  
 * @param <E> 堆栈中元素的类型  
 */  
public class Stack<E> extends Vector<E> {  
  
    /**  
     * 无参构造函数，创建一个空的 Stack 实例。  
     */  
    public Stack() {  
    }  
  
    /**  
     * 将指定的元素推入此堆栈顶部。  
     *  
     * @param item 要推入堆栈顶部的元素  
     * @return 被推入堆栈的元素  
     */  
    public E push(E item) {  
        addElement(item);  
        return item;  
    }  
  
    /**  
     * 从此堆栈中弹出顶部对象，并返回该对象作为此函数的值。  
     *  
     * @return 堆栈顶部的元素（即最后一个添加的元素）  
     * @throws EmptyStackException 如果此堆栈为空  
     */  
    public synchronized E pop() {  
        E obj;  
        int len = size();  
  
        obj = peek();  
        removeElementAt(len - 1);  
  
        return obj;  
    }  
  
    /**  
     * 查看堆栈顶部的对象，但不从堆栈中移除它。  
     *  
     * @return 堆栈顶部的元素（即最后一个添加的元素）  
     * @throws EmptyStackException 如果此堆栈为空  
     */  
    public synchronized E peek() {  
        int len = size();  
  
        if (len == 0)  
            throw new EmptyStackException();  
        return elementAt(len - 1);  
    }  
  
    /**  
     * 测试此堆栈是否为空。  
     *  
     * @return 如果此堆栈不包含任何项，则返回 true；否则返回 false  
     */  
    public boolean empty() {  
        return size() == 0;  
    }  
  
    /**  
     * 返回此堆栈中最后一次出现的指定元素的索引（从 1 开始），  
     * 如果堆栈不包含此元素，则返回 -1。  
     *  
     * @param o 要搜索的元素  
     * @return 最后一次出现指定元素的索引（从 1 开始），如果未找到则返回 -1  
     */  
    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;  
}
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

4、Vector 与 Stack 的过时原因与替代类

4.1、不推荐使用 Vector 来实现线程安全的原因

在 Java 中，不推荐使用 Vector 来实现线程安全的 ArrayList，主要原因有以下几点：

同步机制效率低下：Vector 的所有方法都被同步（synchronized）了，这意味着每次对 Vector 的操作都会获取并释放锁。这种方式会导致大量的上下文切换和锁竞争，影响性能。特别是在高并发环境下，这种同步机制会成为瓶颈。
过时的设计：Vector 是 Java 1.0 引入的类，当时并没有考虑到并发编程的高效实现。后来，Java 引入了更高效的并发集合类，如 java.util.concurrent 包下的集合类，这些类在设计时充分考虑了并发环境下的性能问题。
更好的替代品：Java引入了 Collections.synchronizedList 方法，可以将普通的 ArrayList 包装成线程安全的集合。此外，java.util.concurrent 包下提供了更现代化的并发集合类，如 CopyOnWriteArrayList，它们在并发场景下表现更好。

一些替代Vector的推荐方法和类：

使用 Collections.synchronizedList：可以将一个普通的ArrayList转换为线程安全的集合
使用 CopyOnWriteArrayList ：CopyOnWriteArrayList 是 java.util.concurrent包提供的线程安全的列表实现，它在写操作时进行复制，因此在并发读多写少的场景下性能较好

4.2、Stack 过时的原因

同样的，Java 中的 Stack 类已经被标记为过时（deprecated）。从 Java 1.2 版本开始，Stack 类就不再被推荐使用。Java 官方建议使用 Deque（双端队列）来替代 Stack，因为 Deque 提供了与 Stack 类似的操作方法，如 push()、pop()、peek() 和 isEmpty() 等，同时还具有更灵活和高效的特点。

具体来说，Deque是一个接口，它支持在两端插入和删除元素，因此可以很方便地实现栈（Stack）的功能。而且，Deque接口的实现类（如LinkedList）在性能上通常优于Stack类。

以下是关于 Stack 类过时的一些关键点和原因：

历史遗留：Stack 类作为 Java 早期版本中的一个类，虽然提供了栈的基本功能，但随着 Java 集合框架的不断发展，更先进、更灵活的数据结构被引入，使得 Stack 类逐渐失去了其优势地位。
功能限制：Stack 类在功能上存在一些限制，比如它不支持并发访问，这在多线程编程中可能会导致问题。此外，Stack类的继承结构也使其在某些场景下使用不够灵活。
性能考虑：与 Deque 等现代数据结构相比，Stack 类在性能上可能存在不足。例如，Stack 类在插入和删除元素时可能需要进行额外的操作，从而降低了其效率。
替代方案：Java 提供了多种替代 Stack 类的方案，其中最常用的是 Deque 接口的实现类（如 LinkedList）。这些替代方案不仅提供了与 Stack 类类似的功能，而且在性能、灵活性和可扩展性方面都优于 Stack类。

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】