Java集合（3）：Vector && Stack
一.Vector介绍
Vector可以实现可增长的动态对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。不过，Vector的大小是可以增加或者减小的，以便适应创建Vector后进行添加或者删除操作。Vector和ArrayList也很相似，但是Vector是同步访问的(线程安全的)，且Vector包含了许多不属于集合框架的传统方法。
1.Vector的继承关系
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Vector的类图关系如下：
- Vector实现List接口，继承AbstractList类，所以我们可以将其看做队列，支持相关的添加、删除、修改、遍历等功能。
- Vector实现RandmoAccess接口，即提供了随机访问功能，提供提供快速访问功能。在Vector我们可以直接访问元素。
- Vector 实现了Cloneable接口，支持clone()方法，可以被克隆。
二.Vector源码解析
1.私有属性
Vector提供了elementData , elementCount， capacityIncrement三个成员变量。其中
elementData ：”Object[]类型的数组”，它保存了Vector中的元素。按照Vector的设计elementData为一个动态数组，可以随着元素的增加而动态的增长，其具体的增加方式后面提到（ensureCapacity方法）。如果在初始化Vector时没有指定容器大小，则使用默认大小为10.
elementCount：Vector 对象中的有效组件数。
capacityIncrement：向量的大小大于其容量时，容量自动增加的量。如果在创建Vector时，指定了capacityIncrement的大小；则，每次当Vector中动态数组容量增加时>，增加的大小都是capacityIncrement。如果容量的增量小于等于零，则每次需要增大容量时，向量的容量将增大一倍。
2.Vector的构造方法
Vector提供了四个构造函数：
1 /** 2 * 构造一个空向量，使其内部数据数组的大小为 10，其标准容量增量为零。 3 */ 4 public Vector() { 5 this(10); 6 } 7 8 /** 9 * 构造一个包含指定 collection 中的元素的向量，这些元素按其 collection 的迭代器返回元素的顺序排列。 10 */ 11 public Vector(Collection<? extends E> c) { 12 elementData = c.toArray(); 13 elementCount = elementData.length; 14 // c.toArray might (incorrectly) not return Object[] (see 6260652) 15 if (elementData.getClass() != Object[].class) 16 elementData = Arrays.copyOf(elementData, elementCount, 17 Object[].class); 18 } 19 20 /** 21 * 使用指定的初始容量和等于零的容量增量构造一个空向量。 22 */ 23 public Vector(int initialCapacity) { 24 this(initialCapacity, 0); 25 } 26 27 /** 28 * 使用指定的初始容量和容量增量构造一个空的向量。 29 */ 30 public Vector(int initialCapacity, int capacityIncrement) { 31 super(); 32 if (initialCapacity < 0) 33 throw new IllegalArgumentException("Illegal Capacity: "+ 34 initialCapacity); 35 this.elementData = new Object[initialCapacity]; 36 this.capacityIncrement = capacityIncrement; 37 }
3.元素添加
将指定元素添加到此向量的末尾。
1 public synchronized void addElement(E obj) { 2 modCount++; 3 ensureCapacityHelper(elementCount + 1); 4 elementData[elementCount++] = obj; 5 }
这个方法相对而言比较简单，具体过程就是先确认容器的大小，看是否需要进行扩容操作，然后将E元素添加到此向量的末尾。
1 private void ensureCapacityHelper(int minCapacity) { 2 //如果 3 if (minCapacity - elementData.length > 0) 4 grow(minCapacity); 5 } 6 7 /** 8 * 进行扩容操作 9 * 如果此向量的当前容量小于minCapacity，则通过将其内部数组替换为一个较大的数组俩增加其容量。 10 * 新数据数组的大小姜维原来的大小 + capacityIncrement， 11 * 除非 capacityIncrement 的值小于等于零，在后一种情况下，新的容量将为原来容量的两倍，不过，如果此大小仍然小于 minCapacity，则新容量将为 minCapacity。 12 */ 13 private void grow(int minCapacity) { 14 int oldCapacity = elementData.length; //当前容器大小 15 /* 16 * 新容器大小 17 * 若容量增量系数(capacityIncrement) > 0，则将容器大小增加到capacityIncrement 18 * 否则将容量增加一倍 19 */ 20 int newCapacity = oldCapacity + ((capacityIncrement > 0) ? 21 capacityIncrement : oldCapacity); 22 23 if (newCapacity - minCapacity < 0) 24 newCapacity = minCapacity; 25 26 if (newCapacity - MAX_ARRAY_SIZE > 0) 27 newCapacity = hugeCapacity(minCapacity); 28 29 elementData = Arrays.copyOf(elementData, newCapacity); 30 } 31 32 /** 33 * 判断是否超出最大范围 34 * MAX_ARRAY_SIZE：private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 35 */ 36 private static int hugeCapacity(int minCapacity) { 37 if (minCapacity < 0) 38 throw new OutOfMemoryError(); 39 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; 40 }
对于Vector整个的扩容过程，就是根据capacityIncrement确认扩容大小的，若capacityIncrement <= 0 则扩大一倍，否则扩大至capacityIncrement 。当然这个容量的最大范围为Integer.MAX_VALUE即，2^32 – 1，所以Vector并不是可以无限扩充的。
4.元素删除
1 /** 2 * 从Vector容器中移除指定元素E 3 */ 4 public boolean remove(Object o) { 5 return removeElement(o); 6 } 7 8 public synchronized boolean removeElement(Object obj) { 9 modCount++; 10 int i = indexOf(obj); //计算obj在Vector容器中位置 11 if (i >= 0) { 12 removeElementAt(i); //移除 13 return true; 14 } 15 return false; 16 } 17 18 public synchronized void removeElementAt(int index) { 19 modCount++; //修改次数+1 20 if (index >= elementCount) { //删除位置大于容器有效大小 21 throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); 22 } 23 else if (index < 0) { //位置小于 < 0 24 throw new ArrayIndexOutOfBoundsException(index); 25 } 26 int j = elementCount - index - 1; 27 if (j > 0) { 28 //从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。 29 //也就是数组元素从j位置往前移 30 System.arraycopy(elementData, index + 1, elementData, index, j); 31 } 32 elementCount--; //容器中有效组件个数 - 1 33 elementData[elementCount] = null; //将向量的末尾位置设置为null 34 }
因为Vector底层是使用数组实现的，所以它的操作都是对数组进行操作，只不过其是可以随着元素的增加而动态的改变容量大小，其实现方法是是使用Arrays.copyOf方法将旧数据拷贝到一个新的大容量数组中。Vector的整个内部实现都比较简单，这里就不在重述了。
5.Vector遍历
Vector支持4种遍历方式。建议使用随机访问方式去遍历Vector。
5.1 随机访问
由于Vector实现了RandomAccess接口，它支持通过索引值去随机访问元素。
1 Integer value = null; 2 int size = vec.size(); 3 for (int i=0; i<size; i++) { 4 value = (Integer)vec.get(i); 5 }
5.2 通过迭代器遍历。
即通过Iterator去遍历
1 Iterator it = vec.iterator(); 2 while(it.hasNext()){ 3 value = it.next(); 4 //do something 5 }
5.3 for循环
1 Integer value = null; 2 for (Integer integ:vec) { 3 value = integ; 4 }
5.4 Enumeration遍历
1 Integer value = null; 2 Enumeration enu = vec.elements(); 3 while (enu.hasMoreElements()) { 4 value = (Integer)enu.nextElement(); 5 }
总结：对比Vector的遍历方式，使用索引的随机访问方式最快，使用迭代器最慢。
6.使用示例
示例代码：
1 import java.util.Vector; 2 import java.util.List; 3 import java.util.Iterator; 4 import java.util.Enumeration; 5 6 /** 7 * @desc Vector测试函数：遍历Vector和常用API 8 * 9 * @author skywang 10 */ 11 public class VectorTest { 12 public static void main(String[] args) { 13 // 新建Vector 14 Vector vec = new Vector(); 15 16 // 添加元素 17 vec.add("1"); 18 vec.add("2"); 19 vec.add("3"); 20 vec.add("4"); 21 vec.add("5"); 22 23 // 设置第一个元素为100 24 vec.set(0, "100"); 25 // 将“500”插入到第3个位置 26 vec.add(2, "300"); 27 System.out.println("vec:"+vec); 28 29 // (顺序查找)获取100的索引 30 System.out.println("vec.indexOf(100):"+vec.indexOf("100")); 31 // (倒序查找)获取100的索引 32 System.out.println("vec.lastIndexOf(100):"+vec.lastIndexOf("100")); 33 // 获取第一个元素 34 System.out.println("vec.firstElement():"+vec.firstElement()); 35 // 获取第3个元素 36 System.out.println("vec.elementAt(2):"+vec.elementAt(2)); 37 // 获取最后一个元素 38 System.out.println("vec.lastElement():"+vec.lastElement()); 39 40 // 获取Vector的大小 41 System.out.println("size:"+vec.size()); 42 // 获取Vector的总的容量 43 System.out.println("capacity:"+vec.capacity()); 44 45 // 获取vector的“第2”到“第4”个元素 46 System.out.println("vec 2 to 4:"+vec.subList(1, 4)); 47 48 // 通过Enumeration遍历Vector 49 Enumeration enu = vec.elements(); 50 while(enu.hasMoreElements()) 51 System.out.println("nextElement():"+enu.nextElement()); 52 53 Vector retainVec = new Vector(); 54 retainVec.add("100"); 55 retainVec.add("300"); 56 // 获取“vec”中包含在“retainVec中的元素”的集合 57 System.out.println("vec.retain():"+vec.retainAll(retainVec)); 58 System.out.println("vec:"+vec); 59 60 // 获取vec对应的String数组 61 String[] arr = (String[]) vec.toArray(new String[0]); 62 for (String str:arr) 63 System.out.println("str:"+str); 64 65 // 清空Vector。clear()和removeAllElements()一样！ 66 vec.clear(); 67 // vec.removeAllElements(); 68 69 // 判断Vector是否为空 70 System.out.println("vec.isEmpty():"+vec.isEmpty()); 71 } 72 }
运行结果：
1 vec:[100, 2, 300, 3, 4, 5] 2 vec.indexOf(100):0 3 vec.lastIndexOf(100):0 4 vec.firstElement():100 5 vec.elementAt(2):300 6 vec.lastElement():5 7 size:6 8 capacity:10 9 vec 2 to 4:[2, 300, 3] 10 nextElement():100 11 nextElement():2 12 nextElement():300 13 nextElement():3 14 nextElement():4 15 nextElement():5 16 vec.retain():true 17 vec:[100, 300] 18 str:100 19 str:300 20 vec.isEmpty():true
三. Vector和ArrayList的比较
1.相同点：
- 都继承于AbstractList，并且实现List接口
- 都实现了RandomAccess和Cloneable接口
- 都是通过数组实现的，本质上都是动态数组，默认数组容量是10
- 都支持Iterator和listIterator遍历
2.不同点：
- ArrayList是非线程安全，而Vector是线程安全的
- ArrayList支持序列化，而Vector不支持
- 容量增加方式不同，Vector默认增长为原来一培，而ArrayList却是原来的一半+1
- Vector支持通过Enumeration去遍历，而List不支持
四. Stack
java工具包中的Stack是继承于Vector。
五. List应用场景
截止本文，Java集合框架中有关List的常用的类基本总结完了，下面来看一下各种List类适合的应用场景。如果涉及到“栈”、“队列”、“链表”等操作，应该考虑用List，具体的选择哪个List，根据下面的标准来取舍。
- 对于需要快速插入，删除元素，应该使用LinkedList。
- 对于需要快速随机访问元素，应该使用ArrayList。
- 对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)；对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)。
参考：http://cmsblogs.com/?p=1180