硅谷杂志:Java中顺序表与向量应用浅析 |
2012-12-11 12:14 作者:龙 军 来源:硅谷网 HV: 编辑: 【搜索试试】
|
|
[硅谷网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-),男,安徽安庆人,本科,讲师,研究方向:计算机应用技术。
|
|
|
|
【对“硅谷杂志:Java中顺序表与向量应用浅析”发布评论】 |
版权及免责声明:
① 本网站部分投稿来源于“网友”,涉及投资、理财、消费等内容,请亲们反复甄别,切勿轻信。本网站部分由赞助商提供的内容属于【广告】性质,仅供阅读,不构成具体实施建议,请谨慎对待。据此操作,风险自担。
② 内容来源注明“硅谷网”及其相关称谓的文字、图片和音视频,版权均属本网站所有,任何媒体、网站或个人需经本网站许可方可复制或转载,并在使用时必须注明来源【硅谷网】或对应来源,违者本网站将依法追究责任。
③ 注明来源为各大报纸、杂志、网站及其他媒体的文章,文章原作者享有著作权,本网站转载其他媒体稿件是为传播更多的信息,并不代表赞同其观点和对其真实性负责,本网站不承担此类稿件侵权行为的连带责任。
④ 本网站不对非自身发布内容的真实性、合法性、准确性作担保。若硅谷网因为自身和转载内容,涉及到侵权、违法等问题,请有关单位或个人速与本网站取得联系(联系电话:01057255600),我们将第一时间核实处理。
|
|
|
|