- 浏览: 746540 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
webcover:
最新的中文网络记事本: 破笔记
网络记事本:http://w ...
五个最佳的免费网络记事本 -
fred_nxh:
很好,长见识了
java中堆(heap)和堆栈(stack)有什么区别 -
efeige:
兄弟,请问一下,为什么我的2003系统 网站属性 里面没有“服 ...
启用IIS Gzip 页面压缩技术 加速网页的浏览速度 -
252401762:
同样的问题啊,不知道楼主是否已经转做售前了
售前和 开发的选择 -
yuan:
膜拜玩静电的现在呢?
来回顾一下,当年的“发烧史”吧:
Java 中Vector、ArrayList和LinkedList 的区别时间:
2009-05-27 08:24:53来源:网络 作者:未知 点击:899次
SDK 提供了有序集合接口java.util.List的几种实现,其中三种最为人们熟知的是Vector、ArrayList和LinkedList。有关这 些List类的性能差别是一个经常被问及的问题。在这篇文章中,我要探讨的就是LinkedList和Vector/Array
SDK 提供了有序集合接口java.util.List的几种实现,其中三种最为人们熟知的是Vector、ArrayList和LinkedList。有关这 些List类的性能差别是一个经常被问及的问题。在这篇文章中,我要探讨的就是LinkedList和Vector/ArrayList之间的性能差异。
为全面分析这些类之间的性能差异,我们必须知道它们的实现方法。因此,接下来我首先从性能的角度出发,简要介绍这些类的实现特点。
一、Vector和ArrayList的实现
Vector和ArrayList都带有一个底层的Object[]数组,这个Object[]数组用来保存元素。通过索引访问元素时,只需简单地通过索引访问内部数组的元素:
public Object get(int index)
{ //首先检查index是否合法...此处不显示这部分代码 return
elementData[index]; }
内部数组可以大于Vector/ArrayList对象拥有元素的数量,两者的差值作为剩余空间,以便实现快速添加新元素。有了剩余空间,添加元素变得非常简单,只需把新的元素保存到内部数组中的一个空余的位置,然后为新的空余位置增加索引值:
public boolean add(Object o)
{ ensureCapacity(size + 1); //稍后介绍 elementData[size++] = o; return true;
//List.add(Object) 的返回值 }
把元素插入集合中任意指定的位置(而不是集合的末尾)略微复杂一点:插入点之上的所有数组元素都必须向前移动一个位置,然后才能进行赋值:
public void add(int index, Object element) {
//首先检查index是否合法...此处不显示这部分代码
ensureCapacity(size+1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
剩 余空间被用光时,如果需要加入更多的元素,Vector/ArrayList对象必须用一个更大的新数组替换其内部Object[]数组,把所有的数组元 素复制到新的数组。根据SDK版本的不同,新的数组要比原来的大50%或者100%(下面显示的代码把数组扩大100%):
public void ensureCapacity(int minCapacity) {
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = Math.max(oldCapacity * 2, minCapacity);
elementData = new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);
}
}
Vector 类和ArrayList类的主要不同之处在于同步。除了两个只用于串行化的方法,没有一个ArrayList的方法具有同步执行的能力;相反, Vector的大多数方法具有同步能力,或直接或间接。因此,Vector是线程安全的,但ArrayList不是。这使得ArrayList要比 Vector快速。对于一些最新的JVM,两个类在速度上的差异可以忽略不计:严格地说,对于这些JVM,这两个类在速度上的差异小于比较这些类性能的测 试所显示的时间差异。
通过索引访问和更新元素时,Vector和ArrayList的实现有着卓越的性能,因为不存在除范围检查之外的 其他开销。除非内部数组空间耗尽必须进行扩展,否则,向列表的末尾添加元素或者从列表的末尾删除元素时,都同样有着优秀的性能。插入元素和删除元素总是要 进行数组复制(当数组先必须进行扩展时,需要两次复制)。被复制元素的数量和[size-index]成比例,即和插入/删除点到集合中最后索引位置之间 的距离成比例。对于插入操作,把元素插入到集合最前面(索引0)时性能最差,插入到集合最后面时(最后一个现有元素之后)时性能最好。随着集合规模的增 大,数组复制的开销也迅速增加,因为每次插入操作必须复制的元素数量增加了。
二、LinkedList的实现
LinkedList通过一个双向链接的节点列表实现。要通过索引访问元素,你必须查找所有节点,直至找到目标节点:
public Object get(intindex) {
//首先检查index是否合法...此处不显示这部分代码
Entry e = header; //开始节点
//向前或者向后查找,具体由哪一个方向距离较
//近决定
if (index < size/2) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
把元素插入列表很简单:找到指定索引的节点,然后紧靠该节点之前插入一个新节点:
public void add(int index, Object element) {
//首先检查index是否合法...此处不显示这部分代码
Entry e = header; //starting node
//向前或者向后查找,具体由哪一个方向距离较
//近决定
if (index < size/2) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
Entry newEntry = new Entry(element, e, e.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
}
线程安全的LinkedList和其他集合
如 果要从Java SDK得到一个线程安全的LinkedList,你可以利用一个同步封装器从Collections.synchronizedList(List)得到 一个。然而,使用同步封装器相当于加入了一个间接层,它会带来昂贵的性能代价。当封装器把调用传递给被封装的方法时,每一个方法都需要增加一次额外的方法 调用,经过同步封装器封装的方法会比未经封装的方法慢二到三倍。对于象搜索之类的复杂操作,这种间接调用所带来的开销不是很突出;但对于比较简单的方法, 比如访问功能或者更新功能,这种开销可能对性能造成严重的影响。
这意味着,和Vector相比,经过同步封装的LinkedList在 性能上处于显著的劣势,因为Vector不需要为了线程安全而进行任何额外的间接调用。如果你想要有一个线程安全的LinkedList,你可以复制 LinkedList类并让几个必要的方法同步,这样你可以得到一个速度更快的实现。对于所有其它集合类,这一点都同样有效:只有List和Map具有高 效的线程安全实现(分别是Vector和Hashtable类)。有趣的是,这两个高效的线程安全类的存在只是为了向后兼容,而不是出于性能上的考虑。
对于通过索引访问和更新元素,LinkedList实现的性能开销略大一点,因为访问任意一个索引都要求跨越多个节点。插入元素时除了有跨 越多个节点的性能开销之外,还要有另外一个开销,即创建节点对象的开销。在优势方面,LinkedList实现的插入和删除操作没有其他开销,因此,插入 -删除开销几乎完全依赖于插入-删除点离集合末尾的远近。
ArrayList和Vector通常比LinkedList和同步 封装之后的LinkedList有着更好的性能。即使在你认为LinkedList可能提供更高性能的情况下,你也可以通过修改元素加入的方式从 ArrayList争取更好的性能,例如翻转集合元素的次序。
有些情况下LinkedList会有更好的性能,例如,当大量元素需要同 时加入到大型集合的开头和末尾时。但一般而言,我建议你优先使用ArrayList/Vector类,只有当它们存在明显的性能问题而 LinkedList能够改进性能时,才使用LinkedList。
本篇文章来源于:网贝建站 http://www.netbei.com 原文链接:http://www.netbei.com/2009/0527/4717.html
发表评论
-
ocx插件插入网页实现自动更新与安装注册
2010-07-27 16:17 6566ocx插件插入网页实现 ... -
JIRA
2010-04-02 16:28 1168JIRA 百科名片 JIRA是集项目计划、任务分配、需求管 ... -
ArrayList和LinkedList的用法区别
2010-03-17 10:58 1824ArrayList和LinkedList的用法区别 (2 ... -
多层架构的Web开发框架模型
2010-03-14 00:31 1902摘要:在经典的J2EE四层体系结构的基础上增加数据持久层,提出 ... -
Java语言编码规范(Java Code Conventions
2010-03-08 01:17 7441 介绍(Introduction)1.1 为什么要有编码规范 ... -
IT 的规划
2010-02-21 21:07 735本文说的这位网友,在I ... -
记忆学
2010-02-10 00:50 622http://bbs.jiyifa.cn/read.php?t ... -
java析构函数替代者finalize()解说
2010-01-21 22:18 2488java析构函数替代者finali ... -
Java的GC机制总结(0) ---finalize()方法
2010-01-21 22:00 1168其实了解JAVA的人,都知道JAVA的GC机制是其的一大优点, ... -
Java认证考试
2010-01-14 12:30 800Java认证考试 关于Java方面,Sun推出四项认证:Su ... -
集合框架
2010-01-13 23:24 607java 集合框架 对象的集合 如果程序的 ... -
Java集合框架使用总结
2010-01-13 21:31 626Java集合框架使用总结 ... -
关于JAVA中的线程安全
2010-01-13 10:34 1505关于JAVA中的线程安全 ... -
Java 理论与实践: 并发集合类
2010-01-13 01:27 741DougLea的 util.concurrent 包除了包含许 ... -
java main 主函数
2010-01-10 14:28 2283java主函数一般定义如下:public static ... -
java新式for循环
2009-12-29 15:51 748java新式for循环 2008-08-04 13:48:2 ... -
2009年的Java技术发展趋势展望
2009-11-08 21:28 722已经有14岁的Java在日新月异的IT技术领域内不算年轻,但它 ... -
MyEclipse要注册
2009-11-07 18:37 1654yEclipse怎么注册都不知道。我说他没有注册,他硬要说已经 ... -
浅谈设计模式在JAVA中的具体运用
2009-10-27 23:32 907浅谈设计模式在JAVA ... -
BBSCS 代码阅读
2009-10-26 18:38 638发布的时候,出现乱码================== 如何 ...
相关推荐
Java ArrayList Vector LinkedList map区别 各种集合的区别 写得非常详细
Java基础之集合List-ArrayList、LinkedList、Vector的底层实现和区别ArrayList底层实际是采用数组实现的(并且该数组的类型是
ArrayList的源码分析,自动扩容和自动缩容的源码分析,相关参数的深度解析,从是什么,为什么,怎么做三个角度进行讲解,用通俗易懂的白话进行介绍,LinkedList和Vector以及ArrayList的区别以及使用场景,时间复杂度...
Java容器集合(equals 和 hashCode+基础数据结构+ArrayList+Vector和LinkedList)
ArrayList、Vector、LinkedList 的区别.docx
1. List概述List,就如图名字所示一样,是元素的有序列表 3. ArrayList示例[java] view plain copy public sta
《Vector、ArrayList、List使用深入剖析》-JAVA中文站(www_java-cn_com).htm
主要介绍了Java中ArrayList与LinkedList列表结构的源码,文章最后对LinkedList和ArrayList以及Vector的特性有一个对比总结,需要的朋友可以参考下
ArrayList,Vector底层是由数组实现,LinkedList底层是由双线链表实现,从底层的实现可以得出性能问题ArrayList,Vector插入速度较慢,查询速度较快,而LinkedList插入速度较快,而查询速度较慢。再者由于Vevtor使用了...
4 、ArrayList 和 LinkedList 的区别?分别用在什么场景? 5 、ArrayList 和 LinkedList 的底层数据结构是什么? 6 、ArrayList 默认大小是多少,是如何扩容的? 7 、List 是线程安全的吗?如果要线程安全要怎么做?...
与Java中的数组相比,它的容量能动态增长。不是线程安全的。ArrayList包含了两个重要的对象:elementData(Object[]类型的数组) 和 size 遍历ArrayList时,使用随机访问(即,通过索引序号访问)效率最高 转数组:...
25. ArrayList 和 LinkedList 的区别是什么? 26. 如何实现数组和 List 之间的转换? 27. ArrayList 和 Vector 的区别是什么? 28. Array 和 ArrayList 有何区别? 29. 在 Queue 中 poll()和 remove()有什么区别? ...
为什么ArrayList,Vector等都不支持循环中remove1 ...其实,在Vector,ArrayList,LinkedList中,删除有两种方式进行删除: 1.循环中删除 2.直接删除 1 Vector 直接删除 直接删除首先调用indexOf方法,得到目标元素
Vector,ArrayList, LinkedList的区别是什么? 答: 1. Vector、ArrayList都是以类似数组的形式存储在内存中,LinkedList则以链表的形 式进行存储。 2. List中的元素有序、允许有重复的元素,Set中的元素无序、不允许...
java集合在日常开发中经常用到,对基础的掌握尤其重要,其中List,Set,Map的作用以及使用的场景和分类描述,其中Arraylist 与 LinkedList 区别,HashSet与TreeSet与LinkedHashSet对⽐,LinkedHashMap和HashMap,...
1. java.util.*包的UML结构图。 2. Vector和ArrayList、LinkedList区别? Hashtable 和 HashMap之间的区别 3. String、StringBuffer,StringBuilder之间区别。
JAVAJava软件测试中的Java列表对象的性能分析和测试SDK提供了有序集合接口java.util.List的几种实现,其中三种最为人们熟知的是Vector、ArrayList和LinkedList。有关这些List类的性能差别是一个经常被问及的问题。在...
ArrayList 底层结构和源码分析 Vector 底层结构和源码剖析 LinkedList 底层结构 ArrayList 和 LinkedList 比较 Set 接口和常用方法 Map 接口和常用方法 总结-开发中如何选择集合实现类(记住) Collections工具类 泛型...
2. Vector和ArrayList、LinkedList区别? Hashtable 和 HashMap之间的区别 LinkedList内部以链表形式存储数据。 ArrayList内部以数组形式存储数据。 ? Vector同ArrayList,不过它与ArrayList比较起来是thread-safe...
在这篇文章中,我要探讨的就是LinkedList和Vector/ Java列表对象的性能分析和测试 软件测试 SDK提供了有序集合接口java.util.List的几种实现,其中三种最为人们熟知的是Vector、ArrayList和LinkedList。...