Java集合(3):Vector && Stack

时间:2021-06-11 17:54:31

一.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的类图关系如下:

Java集合(3):Vector && Stack

  • 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

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

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