- 浏览: 204865 次
- 性别:
- 来自: 深圳
文章分类
最新评论
-
jongde1:
Axure太难学了,分享mockplus工具,有兴趣可以去了解 ...
Axure RP 原型设计工具 -
di1984HIT:
这里面提到了好几种解决办法。
Spring AOP对日志记录、Exception日志记录 -
di1984HIT:
学习一下。
spring struts2 零配置 -
di1984HIT:
不错,不错啊
Struts2防止表单重复提交 -
di1984HIT:
kettle怎么样啊。
Kettle初探
ArrayList、Vector、LinkedList之间的区别
ArrayList,LinkedList,Vestor这三个类都实现了java.util.List接口,但它们有各自不同的特性,主要如下:
一、同步性
ArrayList,LinkedList是不同步的,而Vestor是的。所以如果不要求线程安全的话,可以使用ArrayList或LinkedList,可以节省为同步而耗费开销。但在多线程的情况下,有时候就不得不使用Vector了。当然,也可以通过一些办法包装ArrayList,LinkedList,使他们也达到同步,但效率可能会有所降低。
二、数据增长
从内部实现机制来讲ArrayList和Vector都是使用Objec的数组形式来存储的。当你向这两种类型中增加元素的时候,如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度,Vector缺省情况下自动增长原来一倍的数组长度,ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势,因为你可以通过设置集合的初始化大小来避免不必要的资源开销。
三、检索、插入、删除对象的效率
ArrayList和Vector中,从指定的位置(用index)检索一个对象,或在集合的末尾插入、删除一个对象的时间是一样的,可表示为O(1)。但是,如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长:O(n-i),其中n代表集合中元素的个数,i代表元素增加或移除元素的索引位置。为什么会这样呢?以为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行(n-i)个对象的位移操作。
LinkedList中,在插入、删除集合中任何位置的元素所花费的时间都是一样的—O(1),但它在索引一个元素的时候比较慢,为O(i),其中i是索引的位置。
所以,如果只是查找特定位置的元素或只在集合的末端增加、移除元素,那么使用Vector或ArrayList都可以。如果是对其它指定位置的插入、删除操作,最好选择LinkedList
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。
ArrayList,LinkedList,Vestor这三个类都实现了java.util.List接口,但它们有各自不同的特性,主要如下:
一、同步性
ArrayList,LinkedList是不同步的,而Vestor是的。所以如果不要求线程安全的话,可以使用ArrayList或LinkedList,可以节省为同步而耗费开销。但在多线程的情况下,有时候就不得不使用Vector了。当然,也可以通过一些办法包装ArrayList,LinkedList,使他们也达到同步,但效率可能会有所降低。
二、数据增长
从内部实现机制来讲ArrayList和Vector都是使用Objec的数组形式来存储的。当你向这两种类型中增加元素的时候,如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度,Vector缺省情况下自动增长原来一倍的数组长度,ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势,因为你可以通过设置集合的初始化大小来避免不必要的资源开销。
三、检索、插入、删除对象的效率
ArrayList和Vector中,从指定的位置(用index)检索一个对象,或在集合的末尾插入、删除一个对象的时间是一样的,可表示为O(1)。但是,如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长:O(n-i),其中n代表集合中元素的个数,i代表元素增加或移除元素的索引位置。为什么会这样呢?以为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行(n-i)个对象的位移操作。
LinkedList中,在插入、删除集合中任何位置的元素所花费的时间都是一样的—O(1),但它在索引一个元素的时候比较慢,为O(i),其中i是索引的位置。
所以,如果只是查找特定位置的元素或只在集合的末端增加、移除元素,那么使用Vector或ArrayList都可以。如果是对其它指定位置的插入、删除操作,最好选择LinkedList
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。
发表评论
-
Linux下部署多个Tomcat多个域名
2015-12-12 19:02 3644一、安装JDK 1、安装jdk-7u79-linux-x64. ... -
linux下安装swftools和openOffice
2015-07-03 17:09 697最近公司实现一个仿豆丁网百度文库阅读器的功能,需要用到两个软件 ... -
redis Java develop
2014-10-23 18:01 6021. http://javacrazyer.iteye.com ... -
验证码 原理 破解
2014-08-20 17:52 579验证码 原理 破解 reference: http://bl ... -
HttpClient 学习经验
2014-08-14 11:01 596HttpClient学习经验 HttpCl ... -
P2P resources
2013-12-09 18:24 9231.P2P导航收录 http://www.p2peye.com ... -
运用加密技术保护Java源代码
2013-06-08 08:38 1066运用加密技术保护Java源代码 http://www.ibm ... -
log4j.properties配置详解
2013-03-15 17:00 0log4j.properties配置详解 Log4J的配置文 ... -
Struts 2 studing
2012-12-28 17:28 7051. Struts 2的基石——拦截器(Interceptor ... -
J2EE项目异常处理
2012-12-26 11:08 1042J2EE项目异常处理 为什 ... -
如何将基于 Struts、Spring 和 Hibernate 的应用从 Tomcat 迁移到 WebSphere Application Server
2012-12-21 10:28 1141引言 现在很多的企业都 ... -
详解spring事务属性
2012-12-20 10:22 780Spring声明式事务让我们从复杂的事务处理中得到解脱。使得我 ... -
Java List Copy,Remove容易出现的问题
2012-11-15 03:08 967懒程序员,在代码越写越多的情况下,总想着使用把代码精简一 ... -
MySQL---ORACLE序列解决方案
2012-11-13 00:55 1157MySQL自增长与Oracle序列的区别: 自增长只能用于表 ... -
使用反射循环查找所有父类属性
2012-11-02 01:28 2090使用反射循环查找所有父类属性 ... -
list,set,map,数组间的相互转换
2012-11-02 01:25 919list,set,map,数 ... -
java bean自动进行rowMapper or handler的类
2012-10-20 03:14 1254一般情况下在进行jdbc编程的时候避免不了的要写n多的bean ... -
URL encoding 乱码处理
2012-10-10 15:53 849搞了两三天的乱码处理,试了很多方法,过滤器啊,编码转换啊,试来 ... -
JAVA 按任意角度旋转图片,并生成新的旋转后图片
2012-07-11 11:03 3612JAVA 按任意角度旋转图片,并生成新的旋转 ... -
QR Code
2012-06-12 12:29 01. 在线生成QR Code 网站 http://www. ...
相关推荐
ArrayList Vector LinkedList 区别与用法.
Java ArrayList Vector LinkedList map区别 各种集合的区别 写得非常详细
ArrayList、LinkedList、Vector区别简介。
比较ArrayList,LinkedList,Vector三者随机读取,插入,删除性能。
对比Vector、ArrayList、LinkedList1
NULL 博文链接:https://lf6627926.iteye.com/blog/1297695
ArrayList、LinkedList、 Vector、Map 用法比较
ArrayList、Vector、LinkedList 的区别.docx
Java基础之集合List-ArrayList、LinkedList、Vector的底层实现和区别ArrayList底层实际是采用数组实现的(并且该数组的类型是
介绍),当处理的数据集比较小的时候,差距不明显,甚至还表现差一点;但是,当数据集增长到数万或百万以上时,提高就非常大了,具体还是取决于处理器和系统环境。排序算法
这是我从JDK中拿出的Arraylist,Vector,LinkedList源码,自己看源码的时候弄出来的,并写了一点自己的分析,仅供源码分析者使用
1. List概述List,就如图名字所示一样,是元素的有序列表 3. ArrayList示例[java] view plain copy public sta
Java容器集合(equals 和 hashCode+基础数据结构+ArrayList+Vector和LinkedList)
ArrayList,Vector底层是由数组实现,LinkedList底层是由双线链表实现,从底层的实现可以得出性能问题ArrayList,Vector插入速度较慢,查询速度较快,而LinkedList插入速度较快,而查询速度较慢。再者由于Vevtor使用了...
能学到什么:ArrayList的源码分析,自动扩容和自动缩容的源码分析,相关参数的深度解析,从是什么,为什么,怎么做三个角度进行讲解,用通俗易懂的白话进行介绍,LinkedList和Vector以及ArrayList的区别以及使用场景...
4 、ArrayList 和 LinkedList 的区别?分别用在什么场景? 5 、ArrayList 和 LinkedList 的底层数据结构是什么? 6 、ArrayList 默认大小是多少,是如何扩容的? 7 、List 是线程安全的吗?如果要线程安全要怎么做?...
主要介绍了Java中ArrayList与LinkedList列表结构的源码,文章最后对LinkedList和ArrayList以及Vector的特性有一个对比总结,需要的朋友可以参考下
Vector,ArrayList, LinkedList的区别是什么? 答: 1. Vector、ArrayList都是以类似数组的形式存储在内存中,LinkedList则以链表的形 式进行存储。 2. List中的元素有序、允许有重复的元素,Set中的元素无序、不允许...
《Vector、ArrayList、List使用深入剖析》-JAVA中文站(www_java-cn_com).htm
java8 源码 List相关实现类的源码解析(JDK1.8) 2018.9.22- List的架构图 ArrayList 继承关系: ArrayList -> AbstractList ...ArrayList ...与Java中的数组相比,它的容量能动态增长。...LinkedList 继承关系: LinkedLis