硅谷杂志：Java中顺序表与向量应用浅析

　　[硅谷网12月11日文] 据《硅谷》杂志2012年第18期刊文，对顺序表与向量做简单介绍，着重比较两者的数据结构、容量增长、线程安全性和运行效率，
得出各自适用范围，并通过示例方便读者了解两者的应用。

　　
程序设计语言中通过数组将若干同类型数据有序的集合在一起，各元素位置固定，元素个数就是数组的长度。但当集合中删除或
插入元素时，数组就显得捉襟见肘，c++使用链表，Java先是用向量（Vector），后又可通过顺序表（ArrayList）完成。Vector和ArrayList均可保存一列数据，并提供
众多方法来操作这些数据。在JDK1.5之后，Vector被重新设计为泛型，成为AbstractList的子类，实现了Iterator接口，与集合充分兼容。

　　1顺序表（ArrayList）与向量（Vector）的基本概念

　　ArrayList是一个泛型类，支持动态数组，通过类型参数表示其存储元素的类型。它预先给ArrayList对象分配">存储空间，插入元素时，若空间不够则自动增加空间，删除时则自动减少空间。ArrayList常用的方法有add（插入）、get（获得）、remove（删除）、set（设置）、size（获得容量）等。

　　Vector继承自AtrastractList，实现了Serializable，Cloneable，Iterable，
Collection，List，RandomAccess的接口，是曾经使用最为广泛的顺序表。Vector常用的方法除了ArrayList的还有addElement（增加）、elementAt（获得）、indexOf和lastindexOf（
查找）、setSize（设置容量）等，并含有capacityIncrement（容量增长数目）、elementCount（元素数目）、elementData（数据实际存储区域）3个成员变量。

　　2顺序表（ArrayList）与向量（Vector）的比较

　　2.1ArrayList与Vector的数据结构比较

　　ArrayList和Vector均将数据存储在私
有的Object数组中，ArrayList源代码是：“privatetransientObjectelementData[];”，Vector源代码是：“protectedObjectelementData[];”。在增加数据时（如用add()及addAll()），先判断elementData[]的
大小是否够用，若不够则构造一更大的数组，用System.arraycopy()将原数组elementData[]拷贝到这个数组中，并把add()的参数增加进去。

　　2.2容量增长算法比较

　　ArrayList和Vector内部都用数组存储对象，但在构造新数组确定容量时采用了不同的算法。Vector通过私有成员变量“capacityIncrement”进行控制，当数组大小不够时，若capacityIncrement为正数，新数组容量增加capacityIncrement；若capacityIncrement为非正，新数组容量将扩容为原数组的两倍。源代码见下表：

　　intoldCapacity=elementData.length;

　　intnewCapacity=(capacityIncrement>0)?(oldCapacity+capacityIncrement)

　　:(oldCapacity*2);

　　ArrayList扩充数组容量时均按照新数组容量是原数组1.5倍的原则进行。源代码如下：intnewCapacity=(oldCapacity*3)/2+1;

　　当遇到添加元素过多，如调用addAll()方法，元素个数超过新数组容量时，Vector和ArrayList都会自动再扩容到新数组要求的最小容量。源代码如下：

　　if(newCapacity<minCapacity)newCapacity=minCapacity;

　　2.3线程的安全性比较

　　Vector是线程安全的，它通过同步机制保证多个线程存储时不会出现错误。而ArrayList没有使用同步机制，适合单线程的存储，效率更高。

　　2.4运行效率比较

　　当查找一个指定位置的元素或在末尾增加、移除一个元素时，ArrayList和Vector所需时间相同。当在其他位置增加或移除元素时，时间则呈线形增长，这时一般选择其他的集合操作类。

　　3使用顺序表（ArrayList）和向量（Vector）的示例

　　笔者通过模拟扑克发牌进行ArrayList和Vector应用研究和比较。程序用了3个类，“play”类主程序生成玩家和发牌机的对象，开启发牌机并显示扑克牌；“wj”类描述玩家获得的牌，并进行排序；“fp”类用于发牌，在构造方法中分别用ArrayList或Vector生成52张扑克牌，在“get_card”方法中用随机算法依次抽出牌你
提出给玩家，每抽出一张牌，发牌机的容量自动减1。

　　1.使用顺序表编写的fp类：

　　importjava.util.ArrayList;

　　importjava.util.Random;

　　publicclassfp{

　　ArrayList<Integer>a;

　　publicfp(){

　　 a=newArrayList<Integer>(52);

　　 for(inti=0;i<52;i++)

　　  a.add(newInteger(i));}

　　publicintget_card(){

　　 intindex=-1;

　　 Randomr=newRandom();

　　 inti=r.nextInt(a.size());

　　 index=((Integer)a.get(i)).intValue();

　　 a.remove(i);

　　 returnindex;}} 2.使用Vector编写的fp类：

　　importjava.util.Random;

　　importjava.util.Vector;

　　publicclassfp{

　　Vector<Integer>v;

　　publicfp(){

　　v=newVector<Integer>(52);

　　for(inti=0;i<52;i++)

　　 v.addElement(newInteger(i));}

　　publicintget_card(){

　　intindex=-1;

　　Randomr=newRandom();

　　inti=r.nextInt(v.size());

　　index=((Integer)v.elementAt(i)).intValue();

　　v.removeElementAt(i);

　　 returnindex;}}

　　程序运行结果

　　

　　4顺序表（ArrayList）与向量（Vector）的比较结论

　　Vector通过同步机制保证多个线程存储时不会出现错误，但效率下降，而ArrayList不使用同步机制，适合单线程的存储。

　　当集合中元素数目大于当前集合数组的长度时，Vector增长率为现长度的100%，而Arraylist增长率为现长度的50%，但Vector可以通过设置成员变量“capacityIncrement”的值控制增加量。
所以当使用数据量较大时，用Vector可以节省资源开销。

　　作者简介：

　　龙军(1971-)，男，安徽安庆人，本科，讲师，研究方向：计算机应用技术。