- 浏览: 60467 次
- 性别:
- 来自: 应县
最新评论
-
fc19861011:
请问你解决了吗?poi修改word中生成的图表数据找了好久没发 ...
jacob 怎么改变 word图表的数据呢? -
longgol:
GridPanel中mouseover事件获取列index
...
GridPanel中mouseover事件获取行index
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。
为全面分析这些类之间的性能差异,我们必须知道它们的实现方法。因此,接下来我首先从性能的角度出发,简要介绍这些类的实现特点。
一、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。
发表评论
-
Tomcat集群与负载均衡
2011-01-26 16:00 592在单一的服务器上执行W ... -
xalan-2.7.0.jar下载地址
2011-01-26 15:59 3181xalan-2.7.0.jar下载地址:http://svn. ... -
provider org.apache.xalan.processor.TransformerFactoryImpl not found
2011-01-26 15:58 948完整的Exception: Exception startin ... -
Apache与Tomcat整合的简单方法
2011-01-26 15:57 6781、准备,下载需要的文件。这里假定你已经正确安装配置好了JDK ... -
(转)Tomcat源码学习(一)
2011-01-26 15:57 595Tomcat源码学习(一) http://carllgc.bl ... -
Tomat源码学习(二) [图片]
2011-01-26 15:55 714Tomat源码学习(二) Tomat6的整体架构 在上篇文 ... -
Tomat6架构探讨(续)
2011-01-26 15:54 703Tomat源码学习(二) 下面,我们重点针对Catalin ... -
JNDI
2011-01-26 15:49 696Java术语 英文全称是:Java ... -
JSP内建对象- - 转
2011-01-26 15:48 556① out - javax.servlet.jsp.jspWr ... -
全面理解String(JAVA复习)- -
2011-01-26 15:48 5851. 首先String不属 ... -
初学者如何开发出高质量的J2EE系统 (转载)
2011-01-26 15:47 699J2EE学习者越来越多,J2E ... -
关于JSP中的taglib uri
2011-01-26 15:47 1010自定义标签在jsp中应用是需要声明标签库,有下面两种方式: 1 ... -
context-param和init-param区别
2011-01-26 15:46 446web.xml里面可以定义两种参数: (1)applicati ... -
javax.servlet.Filter运用
2011-01-26 15:46 687Servlets Filter 是Servlet 2.3 规范 ... -
javax.servlet.FilterChain
2011-01-26 15:45 964javax.servlet Interface Filter ... -
引用 五个有用的过滤器 Filter
2011-01-26 15:45 622引用 xyz 的 五个有用的过滤器 Filter 来源:htt ... -
spring:简单的属性参考
2011-01-26 15:43 549在定义文件(XML配置文件)中定义Bean时,可以直接指定一个 ... -
spring:Inversion of Control具体实现【资料搜集】
2011-01-26 15:42 598IoC(Inversion of Control)控制反转的具 ... -
学习Spring前必须了解的几点【资料搜集】
2011-01-26 15:42 848轻量级(Lightweight) 轻量级的形容是相对于 ... -
struts2:主题: Interceptor在Struts2中的应用... [图片]
2011-01-26 15:41 666Interceptor(拦截器)将Action共用的行为独立出 ...
相关推荐
ArrayList、LinkedList、Vector区别简介。
比较ArrayList,LinkedList,Vector三者随机读取,插入,删除性能。
ArrayList Vector LinkedList 区别与用法.
对比Vector、ArrayList、LinkedList1
介绍),当处理的数据集比较小的时候,差距不明显,甚至还表现差一点;但是,当数据集增长到数万或百万以上时,提高就非常大了,具体还是取决于处理器和系统环境。排序算法
NULL 博文链接:https://lf6627926.iteye.com/blog/1297695
Java ArrayList Vector LinkedList map区别 各种集合的区别 写得非常详细
ArrayList、Vector、LinkedList 的区别.docx
Java容器集合(equals 和 hashCode+基础数据结构+ArrayList+Vector和LinkedList)
《Vector、ArrayList、List使用深入剖析》-JAVA中文站(www_java-cn_com).htm
ArrayList、LinkedList、 Vector、Map 用法比较
这是我从JDK中拿出的Arraylist,Vector,LinkedList源码,自己看源码的时候弄出来的,并写了一点自己的分析,仅供源码分析者使用
Java基础之集合List-ArrayList、LinkedList、Vector的底层实现和区别ArrayList底层实际是采用数组实现的(并且该数组的类型是
能学到什么:ArrayList的源码分析,自动扩容和自动缩容的源码分析,相关参数的深度解析,从是什么,为什么,怎么做三个角度进行讲解,用通俗易懂的白话进行介绍,LinkedList和Vector以及ArrayList的区别以及使用场景...
1. List概述List,就如图名字所示一样,是元素的有序列表 3. ArrayList示例[java] view plain copy public sta
Vector,ArrayList, LinkedList的区别是什么? 答: 1. Vector、ArrayList都是以类似数组的形式存储在内存中,LinkedList则以链表的形 式进行存储。 2. List中的元素有序、允许有重复的元素,Set中的元素无序、不允许...
ArrayList,Vector底层是由数组实现,LinkedList底层是由双线链表实现,从底层的实现可以得出性能问题ArrayList,Vector插入速度较慢,查询速度较快,而LinkedList插入速度较快,而查询速度较慢。再者由于Vevtor使用了...
2. Vector和ArrayList、LinkedList区别? Hashtable 和 HashMap之间的区别 LinkedList内部以链表形式存储数据。 ArrayList内部以数组形式存储数据。 ? Vector同ArrayList,不过它与ArrayList比较起来是thread-safe...
为什么ArrayList,Vector等都不支持循环中remove1 ...其实,在Vector,ArrayList,LinkedList中,删除有两种方式进行删除: 1.循环中删除 2.直接删除 1 Vector 直接删除 直接删除首先调用indexOf方法,得到目标元素
可以把接口的好处5体现出来,如果ArrayList()不满足需求,直接更换就可以。 接口的好处: 1.程序的耦合度降低 2.更自然的使用多态 3.设计与实现完全分离 4.更容易搭建程序框架 5.更容易更换具体实现 ArrayList: ...