Java中List效率的比较

　　inkfish原创，请勿商业性质转载，转载请注明来源（http://blog.csdn.net/inkfish ）。

　　Java Collections Framework(JCF) 是Java SE中一个基本的类集，几乎所有的项目都会用到，其中的List 则是JCF中最最常用的一个接口。围绕List 接口，有很多实现，诸如常用的ArrayList 、LinkedList 、Vector 、Stack ，还有Java5之后引入的CopyOnWriteArrayList ，也有不少List 的开源实现，如Apache commons-collections中的各类List 。（来源：http://blog.csdn.net/inkfish）

　　这么多的List 实现，如何选择？他们的运行效率具体怎样？本篇文章将用具体的代码来检测其中最最常用的一些List 实现。（来源：http://blog.csdn.net/inkfish）

测试环境：
　　处理器：Intel Core 2 Duo P8600 2.4GHz
　　内存：2G
　　硬盘：160G 7200rpm
　　Java：SUN JDK 1.6.0_15
　　开发环境：Eclipse 3.5
　　第三方类库：Apache commons-lang 2.4、Apache commons-collections 3.2.1（来源：http://blog.csdn.net/inkfish）

主要测试对象：
　　java.util.ArrayList;
　　java.util.LinkedList;
　　java.util.Stack;
　　java.util.Vector;
　　java.util.concurrent.CopyOnWriteArrayList;
　　org.apache.commons.collections.FastArrayList;
　　org.apache.commons.collections.list.TreeList; （来源：http://blog.csdn.net/inkfish）

测试用例：
　　1.测试List
　　　1.1顺序添加
　　　1.2随机插入
　　　1.3随机删除
　　　1.4随机访问
　　　1.5随机更新
　　　1.5顺序迭代
　　2.测试List 在三种情况下的排序效率
　　　2.1初始时List 中元素已从小到大有序排列（最优情况）
　　　2.2初始时List 中元素已从大到小有序排列（最差情况）
　　　2.3初始时List 中元素随机排列，无序
　　3.测试List 互相转换的效率
　　　3.1转化为TreeList
　　　3.2转化为ArrayList
　　　3.3转化为LinkedList
　　　3.4转化为CopyOnWriteArrayList
　　　3.5转化为Vector （来源：http://blog.csdn.net/inkfish）

测试代码： （来源：http://blog.csdn.net/inkfish）

package test; import static java.lang.System.out; import java.util.ArrayList; import java.util.Collections; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Stack; import java.util.Vector; import java.util.concurrent.CopyOnWriteArrayList; import org.apache.commons.collections.FastArrayList; import org.apache.commons.collections.list.TreeList; import org.apache.commons.lang.StringUtils; import org.apache.commons.lang.time.StopWatch; @SuppressWarnings("unchecked") public class ListPerformance { public static void main(String[] args) { ListPerformance test = new ListPerformance(10 * 10000); out.print(StringUtils.center("Test List Performance: loop=" + test.loop, 80, '-')); out.printf("/n%20s%10s%10s%10s%10s%10s%10s", "", "add", "insert", "remove", "get", "set", "iterator"); test.benchmark(new FastArrayList()); test.benchmark(new TreeList()); test.benchmark(new ArrayList()); test.benchmark(new LinkedList()); test.benchmark(new CopyOnWriteArrayList()); test.benchmark(new Vector()); test.benchmark(new Stack()); //2.测试排序 out.print("/n/n"); out.print(StringUtils.center("Test List sort Performance: loop=" + test.loop, 80, '-')); out.printf("/n%20s%10s%10s%10s", "", "optimize", "worst", "random"); test.benchmarkSort(new FastArrayList()); test.benchmarkSort(new TreeList()); test.benchmarkSort(new ArrayList()); test.benchmarkSort(new LinkedList()); //test.benchmarkSort(new CopyOnWriteArrayList());//UnsupportedOperationException test.benchmarkSort(new Vector()); test.benchmarkSort(new Stack()); //3.测试各种数据结构间转化 out.print("/n/n"); out.print(StringUtils.center("Test List convert Performance: loop=" + test.loop, 80, '-')); out.printf("/n%20s%10s%10s%10s%10s%10s", "", "Tree", "Array", "Linked", "CopyOnWrite", "Vector"); test.benchmarkConvert(new FastArrayList()); test.benchmarkConvert(new TreeList()); test.benchmarkConvert(new ArrayList()); test.benchmarkConvert(new LinkedList()); test.benchmarkConvert(new CopyOnWriteArrayList()); } /**测试循环次数*/ private int loop = 10000; public ListPerformance(int loop) { this.loop = loop; } public void benchmark(List list) { out.printf("/n%20s", list.getClass().getSimpleName()); int j; StopWatch watch = null; //1.测试顺序性能(Add) (watch = new StopWatch()).start(); for (int i = 0; i < loop; i++) { list.add(new Integer(i)); } watch.stop(); out.printf("%10d", watch.getTime()); //2.测试随机插入性能(Random insert) (watch = new StopWatch()).start(); for (int i = 0; i < loop; i++) { j = (int) (Math.random() * loop); list.add(j, new Integer(-j)); } watch.stop(); out.printf("%10d", watch.getTime()); //3.测试随机索引删除(Random remove) (watch = new StopWatch()).start(); for (int i = 0; i < loop; i++) { j = (int) (Math.random() * loop); list.remove(j); } watch.stop(); out.printf("%10d", watch.getTime()); //4.测试随机取数性能(Random get) (watch = new StopWatch()).start(); for (int i = 0; i < loop; i++) { j = (int) (Math.random() * loop); list.get(j); } watch.stop(); out.printf("%10d", watch.getTime()); //5.测试随机更新性能(Random set) (watch = new StopWatch()).start(); for (int i = 0; i < loop; i++) { j = (int) (Math.random() * loop); list.set(j, j); } watch.stop(); out.printf("%10d", watch.getTime()); //6.测试迭代性能(Iterator) (watch = new StopWatch()).start(); Iterator<Object> iter = list.iterator(); while (iter.hasNext()) { iter.next(); } watch.stop(); out.printf("%10d", watch.getTime()); } public void benchmarkConvert(List list) { out.printf("/n%20s", list.getClass().getSimpleName()); StopWatch watch = null; //1.转TreeList (watch = new StopWatch()).start(); new TreeList(list); watch.stop(); out.printf("%10d", watch.getTime()); //2.转ArrayList (watch = new StopWatch()).start(); new ArrayList(list); watch.stop(); out.printf("%10d", watch.getTime()); //3.转LinkedList (watch = new StopWatch()).start(); new LinkedList(list); watch.stop(); out.printf("%10d", watch.getTime()); //4.转CopyOnWriteArrayList (watch = new StopWatch()).start(); new CopyOnWriteArrayList(list); watch.stop(); out.printf("%10d", watch.getTime()); //5.转Vector (watch = new StopWatch()).start(); new Vector(list); watch.stop(); out.printf("%10d", watch.getTime()); } public void benchmarkSort(List list) { out.printf("/n%20s", list.getClass().getSimpleName()); StopWatch watch = null; //1.顺序List for (int i = 0; i < loop; i++) { list.add(new Integer(i)); } (watch = new StopWatch()).start(); Collections.sort(list); watch.stop(); out.printf("%10d", watch.getTime()); //2.逆序List for (int i = loop - 1; i > 0; i--) { list.add(new Integer(i)); } (watch = new StopWatch()).start(); Collections.sort(list); watch.stop(); out.printf("%10d", watch.getTime()); //3.随机顺序List for (int i = 0, j = 0; i < loop; i++) { j = (int) (Math.random() * loop); list.add(new Integer(j)); } (watch = new StopWatch()).start(); Collections.sort(list); watch.stop(); out.printf("%10d", watch.getTime()); } }

测试结果： （来源：http://blog.csdn.net/inkfish）

-----------------------Test List Performance: loop=100000----------------------- add insert remove get set iterator FastArrayList 16 8609 8360 15 47 0 TreeList 110 187 156 47 110 78 ArrayList 15 8313 8344 0 15 0 LinkedList 47 50110 80671 59016 55391 78 CopyOnWriteArrayList 54016 484003 370891 16 105406 0 Vector 15 8266 8328 0 16 0 Stack 31 8281 8266 0 16 0 --------------------Test List sort Performance: loop=100000--------------------- optimize worst random FastArrayList 47 78 110 TreeList 15 47 110 ArrayList 32 47 78 LinkedList 15 109 125 Vector 0 63 94 Stack 16 46 78 -------------------Test List convert Performance: loop=100000------------------- Tree Array LinkedCopyOnWrite Vector FastArrayList 0 0 0 0 0 TreeList 0 0 0 0 0 ArrayList 0 0 0 0 0 LinkedList 0 0 0 0 0 CopyOnWriteArrayList 0 0 0 0 0

结论：
　　1.随机插入、随机删除操作中，用TreeList 效率最高；
　　2.在只需要追加、迭代的环境下，LinkedList 效率最高；
　　3.平均效率来讲，ArrayList 相对平衡，但如果海量随机操作，还是会造成性能瓶颈；
　　4.CopyOnWriteArrayList 因为线程安全的原因，致使性能降低很多，所以慎用；
　　5.Vector 没有传说中那么低的效率；
　　6.让Stack 来做List 的事可以，不过语义上Stack 不应该做过多的List 的事情；
　　7.在排序中，ArrayList 具有最好的性能，TreeList 平均性能也不错，LinkedList 的排序效率受元素初始状态的影响很大。
　　8.各种List 间转换几乎没有时间损耗。（来源：http://blog.csdn.net/inkfish）