Java集合之Vector与Stack源码解析

Vector

Vector,一个可变长的数组,底层实现与ArrayList大同小异,但Vector是同步的(线程安全),Vector的很多方法之前都加了关键字synchronized,所以是线程安全的

由于Vector的实现和ArrayList的实现大同小异,这里就不再逐一分析Vector中的方法,主要分析一下和ArrayList不同的方法。

首先我们还是来看以下Vector中定义的变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

protected Object[] elementData; // 存储Vector中元素

protected int elementCount; // Vector中的元素个数

protected int capacityIncrement; // Vector的增长系数

private static final long serialVersionUID = -2767605614048989439L; // Vector的序列版本号

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 能够分配元素数量的最大值
}

构造方法

Vector有四个构造方法,其内部有两个重要的参数,一个是elementCount代表当前元素个数,一个是capacityIncrement代表当列表元素满了之后增加的容量。如果不设置capacityIncrement,那么Vector容量扩展时默认将扩展两倍,在ArrayList源码分析中,我们可以知道ArrayList在扩容时默认将扩展1.5倍。

ector初始时容量为10,而ArrayList初始容量为0

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
// Vector构造函数。默认容量是10。    
public Vector() {
this(10);
}

// 指定Vector容量大小的构造函数
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}

// 指定Vector"容量大小"和"增长系数"的构造函数
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
// 新建一个数组,数组容量是initialCapacity
this.elementData = new Object[initialCapacity];
// 设置容量增长系数
this.capacityIncrement = capacityIncrement;
}

// 指定集合的Vector构造函数。
public Vector(Collection<? extends E> c) {
// 获取“集合(c)”的数组,并将其赋值给elementData
elementData = c.toArray();
// 设置数组长度
elementCount = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

Vector中的构造器和ArrayList中的基本相同,只不过Vector中多了一个可以自定义增长系数的构造器public Vector(int initialCapacity, int capacityIncrement)

扩容机制

Vector中的添加元素和ArrayList中的大同小异,这里不再具体分析,这里只分析下Vector的扩容机制

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
/**
* 增加vector容量
* 如果vector当前容量小于至少需要的容量,它的容量将增加。
* 新的容量将在旧的容量的基础上加上capacityIncrement,除非capacityIncrement小于等于0,在这种情况下,容量将会增加一倍。
* 增加后,如果新的容量还是小于至少需要的容量,那就将容量扩容至至少需要的容量。
*/
public synchronized void ensureCapacity(int minCapacity) {
if (minCapacity > 0) {
modCount++;
ensureCapacityHelper(minCapacity);
}
}

/**
* ensureCapacity()方法的unsynchronized实现。
* ensureCapacity()是同步的,它可以调用本方法来扩容,而不用承受同步带来的消耗
*/
private void ensureCapacityHelper(int minCapacity) {
// 如果至少需要的容量 > 数组缓冲区当前的长度,就进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

/**
* 分派给arrays的最大容量
* 为什么要减去8呢?
* 因为某些VM会在数组中保留一些头字,尝试分配这个最大存储容量,可能会导致array容量大于VM的limit,最终导致OutOfMemoryError。
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
* 扩容,保证vector至少能存储minCapacity个元素。
* 首次扩容时,newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);即如果capacityIncrement>0,就加capacityIncrement,如果不是就增加一倍。
* 如果第一次扩容后,容量还是小于minCapacity,就直接将容量增为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) // overflow
throw new OutOfMemoryError();
//如果想要的容量大于MAX_ARRAY_SIZE,则分配Integer.MAX_VALUE,否则分配MAX_ARRAY_SIZE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

其他方法

Vector中添加一个枚举方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 返回一个枚举类型的对象
public Enumeration<E> elements() {
return new Enumeration<E>() {
int count = 0;

public boolean hasMoreElements() { // 判断后面是否还有数据
return count < elementCount;
}

public E nextElement() { // 返回一个数据
synchronized (Vector.this) {
if (count < elementCount) {
return elementData(count++);
}
}
throw new NoSuchElementException("Vector Enumeration");
}
};
}

其他类同方法请参考ArrayList源码分析

VectorArrayList的最大区别就是Vector是线程安全的,而ArrayList不是线程安全的。另外区别还有:

  • ArrayList不可以设置扩展的容量,默认1.5倍;Vector可以设置扩展的容量,如果没有设置,默认2
  • ArrayList的无参构造方法中初始容量为0,而Vector的无参构造方法中初始容量为10

下面我们再来分析下Vector的子类Stack方法。

Stack

Stack类代表最先进先出(LIFO)堆栈的对象。 它扩展了Vector五个操作,允许一个vector被视为堆栈。

五个方法分别是:

  • push() 添加元素到堆栈的顶部
  • pop() 删除堆栈顶部元素
  • peek() 查看堆栈顶部元素
  • empty() 判断堆栈是否为空
  • search() 返回元素所在位置
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
package java.util;

public
class Stack<E> extends Vector<E> {
/**
* Creates an empty Stack.
*/
public Stack() {
}

public E push(E item) {
addElement(item);
// 调用vector中的方法在栈顶添加一个元素
return item;
}

public synchronized E pop() {
E obj;
int len = size();

obj = peek();
removeElementAt(len - 1);
// 调用vector中的方法删除栈顶的元素
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;
}

public synchronized int search(Object o) {
int i = lastIndexOf(o);
// 因为LIFO 所以选择从后往前遍历
if (i >= 0) {
return size() - i;
}
return -1;
}

/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1224463164541339165L;
}
有收获再赞赏哦🤭
------ 本文结束感谢您的阅读-------------
0%