`
pterodactyl
  • 浏览: 746540 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

Java 中Vector、ArrayList和LinkedList 的区别时间

    博客分类:
  • java
阅读更多

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

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics