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提供了四个构造函数：

 /**

      * 构造一个空向量，使其内部数据数组的大小为 10，其标准容量增量为零。

      */

      public Vector() {

             this(10);

      }

     /**

      * 构造一个包含指定 collection 中的元素的向量，这些元素按其 collection 的迭代器返回元素的顺序排列。

      */

     public Vector(Collection<? extends E> c) {

         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);

     }

     /**

      * 使用指定的初始容量和等于零的容量增量构造一个空向量。

      */

     public Vector(int initialCapacity) {

         this(initialCapacity, 0);

     }

     /**

      *  使用指定的初始容量和容量增量构造一个空的向量。

      */

     public Vector(int initialCapacity, int capacityIncrement) {

         super();

         if (initialCapacity < 0)

             throw new IllegalArgumentException("Illegal Capacity: "+

                                                initialCapacity);

         this.elementData = new Object[initialCapacity];

         this.capacityIncrement = capacityIncrement;

     }

3.元素添加

将指定元素添加到此向量的末尾。

 public synchronized void addElement(E obj) {

         modCount++;

         ensureCapacityHelper(elementCount + 1);

         elementData[elementCount++] = obj;

     }

这个方法相对而言比较简单，具体过程就是先确认容器的大小，看是否需要进行扩容操作，然后将E元素添加到此向量的末尾。

 private void ensureCapacityHelper(int minCapacity) {

         //如果

         if (minCapacity - elementData.length > 0)

             grow(minCapacity);

     }

     /**

      * 进行扩容操作

      * 如果此向量的当前容量小于minCapacity，则通过将其内部数组替换为一个较大的数组俩增加其容量。

      * 新数据数组的大小姜维原来的大小 + capacityIncrement，

      * 除非 capacityIncrement 的值小于等于零，在后一种情况下，新的容量将为原来容量的两倍，不过，如果此大小仍然小于 minCapacity，则新容量将为 minCapacity。

      */

     private void grow(int minCapacity) {

         int oldCapacity = elementData.length;     //当前容器大小

         /*

          * 新容器大小

          * 若容量增量系数(capacityIncrement) > 0，则将容器大小增加到capacityIncrement

          * 否则将容量增加一倍

          */

         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);

     }

     /**

      * 判断是否超出最大范围

      * MAX_ARRAY_SIZE：private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

      */

     private static int hugeCapacity(int minCapacity) {

         if (minCapacity < 0)

             throw new OutOfMemoryError();

         return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;

     }

　　对于Vector整个的扩容过程，就是根据capacityIncrement确认扩容大小的，若capacityIncrement <= 0 则扩大一倍，否则扩大至capacityIncrement 。当然这个容量的最大范围为Integer.MAX_VALUE即，2^32 – 1，所以Vector并不是可以无限扩充的。

4.元素删除

 /**

      * 从Vector容器中移除指定元素E

      */

     public boolean remove(Object o) {

         return removeElement(o);

     }

     public synchronized boolean removeElement(Object obj) {

         modCount++;

         int i = indexOf(obj);   //计算obj在Vector容器中位置

         if (i >= 0) {

             removeElementAt(i);   //移除

             return true;

         }

         return false;

     }

     public synchronized void removeElementAt(int index) {

         modCount++;     //修改次数+1

         if (index >= elementCount) {   //删除位置大于容器有效大小

             throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);

         }

         else if (index < 0) {    //位置小于 < 0

             throw new ArrayIndexOutOfBoundsException(index);

         }

         int j = elementCount - index - 1;

         if (j > 0) {

             //从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。

             //也就是数组元素从j位置往前移

             System.arraycopy(elementData, index + 1, elementData, index, j);

         }

         elementCount--;   //容器中有效组件个数 - 1

         elementData[elementCount] = null;    //将向量的末尾位置设置为null

     }

　　因为Vector底层是使用数组实现的，所以它的操作都是对数组进行操作，只不过其是可以随着元素的增加而动态的改变容量大小，其实现方法是是使用Arrays.copyOf方法将旧数据拷贝到一个新的大容量数组中。Vector的整个内部实现都比较简单，这里就不在重述了。

5.Vector遍历

Vector支持4种遍历方式。建议使用随机访问方式去遍历Vector。

5.1 随机访问

由于Vector实现了RandomAccess接口，它支持通过索引值去随机访问元素。

 Integer value = null;

 int size = vec.size();

 for (int i=0; i<size; i++) {

     value = (Integer)vec.get(i);

 }

5.2 通过迭代器遍历。

即通过Iterator去遍历

 Iterator it = vec.iterator();

 while(it.hasNext()){

     value = it.next();

     //do something

 }

5.3 for循环

 Integer value = null;

 for (Integer integ:vec) {

     value = integ;

 }

5.4 Enumeration遍历

 Integer value = null;

 Enumeration enu = vec.elements();

 while (enu.hasMoreElements()) {

     value = (Integer)enu.nextElement();

 }

总结：对比Vector的遍历方式，使用索引的随机访问方式最快，使用迭代器最慢。

6.使用示例

示例代码：

 import java.util.Vector;

 import java.util.List;

 import java.util.Iterator;

 import java.util.Enumeration;

 /**

  * @desc Vector测试函数：遍历Vector和常用API

  *

  * @author skywang

  */

 public class VectorTest {

     public static void main(String[] args) {

         // 新建Vector

         Vector vec = new Vector();

         // 添加元素

         vec.add("1");

         vec.add("2");

         vec.add("3");

         vec.add("4");

         vec.add("5");

         // 设置第一个元素为100

         vec.set(0, "100");

         // 将“500”插入到第3个位置

         vec.add(2, "300");

         System.out.println("vec:"+vec);

         // (顺序查找)获取100的索引

         System.out.println("vec.indexOf(100):"+vec.indexOf("100"));

         // (倒序查找)获取100的索引

         System.out.println("vec.lastIndexOf(100):"+vec.lastIndexOf("100"));

         // 获取第一个元素

         System.out.println("vec.firstElement():"+vec.firstElement());

         // 获取第3个元素

         System.out.println("vec.elementAt(2):"+vec.elementAt(2));

         // 获取最后一个元素

         System.out.println("vec.lastElement():"+vec.lastElement());

         // 获取Vector的大小

         System.out.println("size:"+vec.size());

         // 获取Vector的总的容量

         System.out.println("capacity:"+vec.capacity());

         // 获取vector的“第2”到“第4”个元素

         System.out.println("vec 2 to 4:"+vec.subList(1, 4));

         // 通过Enumeration遍历Vector

         Enumeration enu = vec.elements();

         while(enu.hasMoreElements())

             System.out.println("nextElement():"+enu.nextElement());

         Vector retainVec = new Vector();

         retainVec.add("100");

         retainVec.add("300");

         // 获取“vec”中包含在“retainVec中的元素”的集合

         System.out.println("vec.retain():"+vec.retainAll(retainVec));

         System.out.println("vec:"+vec);

         // 获取vec对应的String数组

         String[] arr = (String[]) vec.toArray(new String[0]);

         for (String str:arr)

             System.out.println("str:"+str);

         // 清空Vector。clear()和removeAllElements()一样！

         vec.clear();

 //        vec.removeAllElements();

         // 判断Vector是否为空

         System.out.println("vec.isEmpty():"+vec.isEmpty());

     }

 }

运行结果：

 vec:[100, 2, 300, 3, 4, 5]

 vec.indexOf(100):0

 vec.lastIndexOf(100):0

 vec.firstElement():100

 vec.elementAt(2):300

 vec.lastElement():5

 size:6

 capacity:10

 vec 2 to 4:[2, 300, 3]

 nextElement():100

 nextElement():2

 nextElement():300

 nextElement():3

 nextElement():4

 nextElement():5

 vec.retain():true

 vec:[100, 300]

 str:100

 str:300

 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

http://www.jb51.net/article/42765.htm

http://www.cnblogs.com/skywang12345/p/3308833.html

巴特西