源码阅读(1):Java中主要的List结构——概述》)
java.util.Vector类是从Java较早版本就开始提供的List形式的集合结构(从JDK 1.0开始),其主要的继承体系如下图所示:
从上图我们可知,Vector是支持“随机访问”特性的,该特性在上一篇文章中已经进行了讲解,这里就不再赘述了。如果严格描述Vector的特性的话,那么Vector是一个支持集合元素读写、且大小可变、且线程安全、最后还支持“随机访问”特性的List性质的集合。下面我们就对Vector类中的典型操作进行详细介绍,首先我们需要详细描述的是存在于Vector类中和其上级AbstractList类中的重要变量信息:
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
protected Object[] elementData;
protected int elementCount;
protected int capacityIncrement;
}
通过对以上三个重要变量的描述,我们可以大致知晓Vector集合的基本结构,其包括了一个数组,一个指向当前数组的可验证“边界”,以及一个数组扩容的参考值,如下图所示:
elementCount变量的在Vector集合中非常重要,它在Vector集合进行addXXXX()、removeXXXX()性质的操作时都会发生变化。elementCount变量的值可能小于elementData数组的容量大小(capacity()方法可获取当前数组的容量大小),也可能和elementData数组的容量大小相等——当整个elementData数组的每一个索引位置都已经设定了元素(元素也可以设置为null)。
另外一个已知的知识点是,Java中的数组是内存中的一个连续地址,一旦完成了初始化其大小不可变化。那么如果理解上文中提到的“变长”了,我们将在下文中专门讲解Vector集合的扩容操作。搞清楚了Vector集合中的重要变量信息后,我们就可以介绍Vector类中的典型操作方法了。
3.1、Vector集合的扩容操作
上文已经描述过Vector集合支持扩容操作,说得具体一点就是支持Vector类中用于真实存储数据的“elementData”数组的大小允许变化,再说得根本一点,就是允许重新为“elementData”数组变量指定新的地址引用。
3.1.1、什么时候扩容?
Vector集合在两种情况下需要进行扩容。首先Vector集合在初始化时会进行扩容,其“elementData”数组变量将从Null第一次指向一个新的数组地址;其次当Vector集合中“elementCount”代表的元素数量将要超出“elementData”数组的最大容量capacity时,也会进行扩容操作,这时“elementData”数组中的元素将会被“拷贝”到另一个更大的数组中,并且“elementData”数组变量将从新指向后者。
首先关注以下Vector集合的构造函数:
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector() {
this(10);
}
以上三个构造函数的执行内容和关联关系一目了然,不需要在做过多介绍。通过以上的代码片段我们知道,如果没有在Vector集合初始化时指定集合的初始化容量(initialCapacity),那么初始化容量将设定为10;如果没有在Vector集合初始化时指定扩容增量(capacityIncrement),那么扩容增量的值将被设定为0;从上文中的介绍我们还可以知道,一旦扩容增量(capacityIncrement)被设置成了0,那么随后进行的每次扩容中,“elementData”数组的大小都会变为当前大小的一倍,也就是说说 10->20->40->80…………以此类推。
- 当前Vector集合的数据总量将超出数组容量限制时也会进行扩容:
我们来看一下的判定方法:
private void ensureCapacityHelper(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
ensureCapacityHelper方法中的内容很简单:如果当前调用该私有方法时,入参所传入的最小容量(minCapacity)如果大于当前Vector集合elementData数组的大小,则进行扩容——调用grow(int)方法。而ensureCapacityHelper方法的调用广泛存在于那些“可能引起Vector集合内数据量发生变化”的方法中,例如:setSize()方法、insertElementAt()方法、addElement()方法、add()方法、addAll()方法等等,以及那些主动寻求容量验证的方法:ensureCapacity()方法。
3.1.2、怎样进行扩容?
当Vector集合进行初始化时的扩容操作很简单,实际上就是elementData数组的初始化过程;这里我们主要讲解grow(int)方法,也就是上文提到的ensureCapacityHelper()方法中调用的grow(int)方法,首先上源代码:
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;
}
以上的方法注释已经把每一句源代码描述得很清楚了,这里重点说明一下Arrays.copyOf()方法和hugeCapacity()方法。
- Arrays.copyOf(T[] original, int newLength)方法:该方法是一个工具性质的方法,其方法意义为复制指定数组(original)为一个新的数组对象,后者的长度为给定的新长度(newLength)。按照这样的描述,根据给定的新长度(newLength)就会出现两种不同的情况:第一种情况是新长度(newLength)小于指定的数组(original)的原始长度,那么无法复制的数组部分将会被阶段;第二种情况是新长度(newLength)大于等于指定的数组(original)的原始长度,这时原始数组中的所有元素对象(的引用地址)将依据原来的索引位置被依次复制到新的数组中,多出来空余的部分将被填充null值。如下图所示:
注意上图所代表的过程描述中,并不包括新长度(newLength)参数无效的情况,例如当newLength为负数时,该方法会抛出java.lang.NegativeArraySizeException异常。那么有的读者会问当newLength为0时会出现的情况,这种情况满足以上描述的第一种情况的输出——没有任何元素可以进行填充,当然就是输出一个空数组
上图所代表的过程描述中,也不包括类似int[]、long[]、float[]等java基础类型数组进行复制的场景,在这些基础类型数组的复制过程中,新数组中多余的位置将填充这个基础类型的默认值,例如int[]数组的复制过程中,新数组的多余的位置将被填充“0”。
- hugeCapacity()方法:
该方法中出现了两个关键的常量MAX_ARRAY_SIZE和MAX_VALUE,MAX_ARRAY_SIZE的大小为2147483639(7FFF FFF7),表示支持的最大数组大小;MAX_VALUE的大小为2147483647(7FFF FFFF),标识32位int类型所代表的最大整数值。那么按照上文源代码的意义,Vector集合最大支持的数组容量就是2147483647。
3.2、add(E) 方法
add(E)方法的意义是在Vector集合的尾部增加一个新的元素,这个尾部并不是以当前Vector集合中elementData数组的长度决定,而是以Vector集合中当前元素数量elementCount来决定的——elementData的长度永远大于或者等于elementCount。
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
那么整个add方法的操作过程实际上就分为两种情况,第一种情况当elementCount代表的集合中元素数量小于当前elementData数组大小时,这时不必进行elementData数组的“扩容”,直接在elementData数组的第elementCount的位置增加新的数据即可;当elementCount代表的集合中元素数量大于或者等于当前elementData数组大小时,就需要先进行elementData数组的“扩容”操作,再进行新数据在elementCount位置的添加操作。
3.3、set(int , E) 方法
该方法在指定的索引位置设定指定的元素,指定的元素可以为null。该方法有两个参数第一个参数为int类型的索引位置,第二参数为需要在这个索引位置设定的新的元数值。该方法有几个关键点:
public synchronized E set(int index, E element) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
3.4、removeElementAt(int) 方法
该方法用于移除Vector集合中elementData数组指定位置的数据值,并且改变其索引位置的指向。在操作者看来这个操作可以成功移除索引位置X上的元素(X < elementCount),并且操作成功后,操作者虽然依旧可以使用索引位置X取得数据(X < elementCount),但是之后取得的值将是“紧邻”的数据。如下图所示:
上图展示了removeElementAt(int) 方法的运行实质:既是以当前指定索引位置为几点,将后续元素位置向前一次移动一个索引位置,请看该方法的源代码:
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;
}
首先来描述一下以上代码中的System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)方法,该方法是一种JNI native方法,是JDK提供的进行两个数组中元素复制的性能最快的方法。其参数意义描述如下:
- src:该参数只能传入数组,表示当前进行数组元素复制的来源
- srcPos:该参数描述源数组中进行复制操作时的起始元素位置
- dest:该参数同样只能传入数组,标识当前进行数组元素复制的目标数组
- destPos:该参数描述目标数组中进行复制操作时的起始元素位置
- length:该参数指定进行复制的长度。
那么这样,以上代码段落中使用System.arraycopy方法的意图就很好理解了,如下图所示:
上图所示,虽然完成了数组自身的元素移动,但这时数组最后一个元素的值并没有改变,所以需要人工进行数组中元素值的减少,并手动设置最后一个位置上的元素为null。所以会出现上文中源代码的内容:
public synchronized void removeElementAt(int index) {
elementCount--;
elementData[elementCount] = null;
}
====================
(接下文《源码阅读(3):Java中主要的List结构——ArrayList集合》)