「集合底层」Vector底层结构及源码剖析_vector底层数据结构

「集合源码」Vector底层结构及源码剖析

一、基本介绍

Vector 是一个矢量队列，它的继承关系和ArrayList是一样的，同样实现了RandomAccess标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。Vector实现了Cloneable标记接口，用来指示Object.clone()方法可以合法地对该类实例按字段复制。如果在没有实现 Cloneable接口的实例上调用 Object 的 clone 方法，则会导致抛出 CloneNotSupportedException 异常。Serializable 接口： 类通过实现 java.io.Serializable 接口以启用其序列化功能。未实现此接口的类将无法使其任何状态序列化或反序列化。

---

二、类继承关系

---

三、Vector特性

• 1、底层由一个可以增长的数组组成
• 2、Vector 通过 capacity (容量) 和 capacityIncrement (增长数量) 来尽量少的占用空间
• 3、扩容时默认扩大两倍
• 4、最好在插入大量元素前增加 vector 容量，那样可以减少重新申请内存的次数
• 5、通过 iterator 和 lastIterator 获得的迭代器是 fail-fast 的
• 6、通过 elements 获得的老版迭代器 Enumeration 不是 fail-fast 的
• 7、同步类，每个方法前都有同步锁 synchronized

---

四、底层源码分析

1、四个构造器

<1> 无参构造器

/**
 * 默认无参构造函数
 */
public Vector() {
    // 调用只有一个参数的构造函数，给参数一个定值10
    this(10);
}
1
2
3
4
5
6
7

<2> 一个参数的构造函数

/**
 * 有一个参数的构造函数
 * @param   initialCapacity  创建对象时如果使用默认的无参构造函数，默认大小为10
 */
public Vector(int initialCapacity) {
    // 调用有两个参数的构造函数
    this(initialCapacity, 0);
}
1
2
3
4
5
6
7
8

<3> 有两个参数的构造函数

/**
 * 有两个参数的构造函数,第一个参数代表数组的初始化长度，第二个是数组需要进行扩容的的增量值
 * @param   initialCapacity     	 集合的初始化长度大小，如果创建集合时采用无参构造器，则默认为10
 * @param   capacityIncrement   	 Vector需要自动扩容时增加的容量值，不传递时默认为0		
 * @throws  IllegalArgumentException 发生异常时抛出异常
 */
public Vector(int initialCapacity, int capacityIncrement) {
    // 调用父类的构造函数
    super();
    // 判断传递进来的默认初始化集合长度大小的值是否小于0，如果小于则抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    // 创建一个Object类型的数组，长度为传递进来的 initialCapacity ，用 elementData 接收
    this.elementData = new Object[initialCapacity];
    //  Vector需要自动扩容时增加的容量值，不传递时默认为0，在后面的扩容方法中会体现出来	
    this.capacityIncrement = capacityIncrement;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 变量说明

// 存放集合的元素值，类型Object类型，可以存储任意类型的数据
protected Object[] elementData;

// 数组需要进行扩容的的增量值，只有在调用有两个参数的构造函数是才可以改变其大小
// 如果采用其他两个构造函数创建集合，则默认是0
protected int capacityIncrement;

1
2
3
4
5
6
7

• Vector父类的构造函数

/**
 * Vector父类的构造函数，不做任何事情
 */
protected AbstractList() {}
1
2
3
4

<4> 有参构造器（传入一个Collection类型的集合）

/**
 * 在初始化的时候直接将一个集合传入，可以把传入集合的元素全部复制到创建的新集合中
 * @param c 					传入的集合
 * @throws NullPointerException   当传入的集合为空时，会抛出异常
 */
public Vector(Collection<? extends E> c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}
1
2
3
4
5
6
7
8
9
10
11

2. 添加一个元素的过程以及扩容机制

<1> 调用对应类型的装箱方法

在每次添加数据时，如果数据是基本数据类型，会先将基本数据类型进行装箱操作，把基本数据类型转换成对应的包装类型（引用数据类型）

// 例如：集合中存放Integer数据类型，在进行add操作时，会先进行装箱操作

/**
 * 将基本数据类转换为引用数据类型
 * @param  i 	传入的参数为一个基本型数据类型
 * @return 		返回的参数是一个基本数据类型的包装类（引用数据类型）
 */
public static Integer valueOf(int i) {
    if (i >= IntegerCache.low && i <= IntegerCache.high)
        return IntegerCache.cache[i + (-IntegerCache.low)];
    return new Integer(i);
}
1
2
3
4
5
6
7
8
9
10
11
12

<2> 调用 add() 方法

/**
 * 添加元素方法，成功返回true，失败会抛出异常
 * @param e 			需要进行添加的元素值
 * @return <tt>true</tt> 添加成功返回true，添加过程中如果失败会抛出异常
 */
public synchronized boolean add(E e) {
    // 记录集合被修改的次数
    modCount++;
    // 判断是否需要扩容
    ensureCapacityHelper(elementCount + 1);
    // 将传递进来的元素添加到数组的末尾
    elementData[elementCount++] = e;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 变量说明：

// 记录集合被修改的次数
protected transient int modCount = 0;

// 记录当前的vector集合中存储的实际元素个数
protected int elementCount;
1
2
3
4
5

<3> 判断是否需要扩容 ensureCapacityHelper()

/**
 * 按照传递进来的具体值，判断是否需要进行扩容操作
 * @param minCapacity 在原来集合实际元素个数的数目上加1，代表添加元素之后数组的实际长度
 */
private void ensureCapacityHelper(int minCapacity) {
    // 当实际需要的数组长度 - 数组实际的长度大于0时，表示需要进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity); 	// 扩容的核心方法
}
1
2
3
4
5
6
7
8
9

<4> 核心扩容方法 grow()

/**
 * 具体的扩容方法
 * @param minCapacity 经过判断之后存储数据的数组需要的容量大小
 */
private void grow(int minCapacity) {
    // 获取未扩容之前的数组长度
    int oldCapacity = elementData.length;
    // 判断 capacityIncrement 增量值是否大于0，如果大于0每次扩容大小是增量值，否则按原来长度的2倍扩容
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
    
    // 当扩容之后的长度小于实际需要的长度时，将实际需要的长度作为扩容之后的长度
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
    // 当扩容之后的长度大于限定的最大长度时
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    // 使用数组的 copyOf 对数组进行扩容
    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

• 变量说明：

// 整数类型的最大值减8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
1
2

<5> 当数组要求的扩容的长度超过限定的最大值时

/**
 * 具体的扩容方法
 * @param minCapacity 经过判断之后存储数据的数组需要的容量大小
 */
private static int hugeCapacity(int minCapacity) {
    // 判断是否是内存溢出
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
    
    // 判断实际需要的数组长度是否大于设置的最大值，是则返回整数类型的最大值，否则返回设置的最大值
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
1
2
3
4
5
6
7
8
9
10
11
12

<6> 回到add方法

// 将传递进来的元素添加到数组的末尾
elementData[elementCount++] = e;	
1
2

至此vector的一次add就完成了

---

五、Vector与ArrayList

共同点

• 1、都是基于数组
• 2、都支持随机访问
• 3、默认容量都是 10
• 4、都有扩容机制

区别

• 1、Vector 出生的比较早，JDK 1.0 就出生了，ArrayList JDK 1.2 才出来
• 2、Vector 比 ArrayList 多一种迭代器 Enumeration
• 3、Vector 是线程安全的，ArrayList 不是线程安全的
• 4、Vector 默认扩容2倍，ArrayList 是1.5倍
• 5、Vector相比ArrayList很多方法都使用了synchronized来保证线程安全，这也就意味着每次都需要获得对象同步锁，效率会明显比ArrayList要低。

---

参考

Java中的Vector源码解析

Vector总结及部分底层源码分析