java遍历机制性能的比较详解

缘由

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：申请域名、虚拟空间、营销软件、网站建设、岳池网站维护、网站推广。

近段时间在写leetcode的Lemonade Change时候，发现了for循环与forEach循环的耗时是不一致的，在提交记录上面差了一倍......

平常开发绝大部分业务逻辑的实现都需要遍历机制的帮忙，虽说也有注意到各数据结构操作的性能比较，但是忽视了遍历机制性能的差异。原本前两天就开始动手写，拖延症......

正文

现阶段我所知道JAVA遍历机制有三种

for循环
forEach循环
Iterator循环

JAVA数据结构千千万，但是大部分都是对基础数据结构的封装，比较HashMap依赖于Node数组，LinkedList底层是链表，ArrayList对数组的再封装......扯远了

总结来说，JAVA的基础数据结构，我觉得有两种

数组
链表

如果是加上Hash(Hash的操作与数组以及链表不太一致)，就是三种

因为平常开发大部分都优先选择包装后的数据结构，所以下面我会使用

ArrayList(包装后的数组)
LinkedList(包装后的链表)
HashSet(包装后的Hash类型数组)

这三种数据结构在遍历机制不同的时候时间的差异

可能有人对我为什么不对比HashMap呢，因为JAVA设计中，是先实现了Map，再实现Set。如果你有阅读过源码就会发现:每个Set子类的实现中，都有一个序列化后的Map对应属性实现，而因为Hash的查找时间复杂度为O(1)，得出key后查找value的时间大致是一致的，所以我不对比HashMap。

题外话

我在阅读《疯狂JAVA》读到:JAVA的设计者将Map的内部entry数组中的value设为null进而实现了Set。因为我是以源码以及官方文档为准，具体我不清楚正确与否，但是因为Hash中的key互不相同，Set中元素也互不相同，所以我认为这个观点是正确的。

为了测试的公平性，我会采取以下的限定

每种数据结构的大小都设置三种量级

10
100
1000

元素都采用随机数生成

遍历进行操作都为输出当前元素的值

注:时间开销受本地环境的影响，可能测量值会出现变化，但是总体上比例是正确的

ArrayList的比较

代码

public class TextArray {

  private static Random random;

  private static List list1;

  private static List list2;

  private static List list3;

  public static void execute(){
    random=new Random();
    initArray();
    testForWith20Object();
    testForEachWith20Object();
    testIteratorWith20Object();
    testForWith200Object();
    testForEachWith200Object();
    testIteratorWith200Object();
    testForWith2000Object();
    testForEachWith2000Object();
    testIteratorWith2000Object();
  }

  private static void testForWith20Object(){
    printFor(list1);
  }

  private static void testForWith200Object(){
    printFor(list2);
  }

  private static void testForWith2000Object(){
    printFor(list3);
  }

  private static void testForEachWith20Object(){
    printForeach(list1);
  }

  private static void testForEachWith200Object(){
    printForeach(list2);
  }

  private static void testForEachWith2000Object(){
    printForeach(list3);
  }

  private static void testIteratorWith20Object() {
    printIterator(list1);
  }

  private static void testIteratorWith200Object() {
    printIterator(list2);
  }

  private static void testIteratorWith2000Object() {
    printIterator(list3);
  }

  private static void printFor(List list){
    System.out.println();
    System.out.print("data:");
    long start=System.currentTimeMillis();
    for(int i=0,length=list.size();i list){
    System.out.println();
    System.out.print("data:");
    long start=System.currentTimeMillis();
    for(int temp:list){
      System.out.print(temp+" ");
    }
    System.out.println();
    long end=System.currentTimeMillis();
    System.out.println("foreach for "+list.size()+":"+(end-start)+"ms");
  }

  private static void printIterator(List list){
    System.out.println();
    System.out.print("data:");
    Iterator it=list.iterator();
    long start=System.currentTimeMillis();
    while(it.hasNext()){
      System.out.print(it.next()+" ");
    }
    System.out.println();
    long end=System.currentTimeMillis();
    System.out.println("iterator for "+list.size()+":"+(end-start)+"ms");
  }

  private static void initArray(){
    list1=new ArrayList<>();
    list2=new ArrayList<>();
    list3=new ArrayList<>();
    for(int i=0;i<10;i++){
      list1.add(random.nextInt());
    }
    for(int i=0;i<100;i++){
      list2.add(random.nextInt());
    }
    for(int i=0;i<1000;i++){
      list3.add(random.nextInt());
    }
  }
}

输出(忽略对元素的输出)

for for 10:1ms
foreach for 10:0ms
iterator for 10:2ms
for for 100:5ms
foreach for 100:4ms
iterator for 100:12ms
for for 1000:33ms
foreach for 1000:7ms
iterator for 1000:16ms

10 100 1000
for 1ms 5ms 33ms

forEach 0ms 4ms 7ms

Iterator 2ms 12ms 16ms

	10	100	1000
for	1ms	5ms	33ms
forEach	0ms	4ms	7ms
Iterator	2ms	12ms	16ms

结论

for的性能最不稳定，foreach次之，Iterator最好

使用建议

在数据量不明确的情况下(可能1w,10w或其他)，建议使用Iterator进行遍历
在数据量明确且量级小的时候，优先使用foreach
需要使用索引时，使用递增变量的开销比for的要小

LinkedList的比较

代码

public class TextLinkedList {

  private static Random random;

  private static List list1;

  private static List list2;

  private static List list3;

  public static void execute(){
    random=new Random();
    initList();
    testForWith20Object();
    testForEachWith20Object();
    testIteratorWith20Object();
    testForWith200Object();
    testForEachWith200Object();
    testIteratorWith200Object();
    testForWith2000Object();
    testForEachWith2000Object();
    testIteratorWith2000Object();
  }

  private static void testForWith20Object() {
    printFor(list1);
  }

  private static void testForEachWith20Object() {
    printForeach(list1);
  }

  private static void testIteratorWith20Object() {
    printIterator(list1);
  }

  private static void testForWith200Object() {
    printFor(list2);
  }

  private static void testForEachWith200Object() {
    printForeach(list2);
  }

  private static void testIteratorWith200Object() {
    printIterator(list2);
  }

  private static void testForWith2000Object() {
    printFor(list3);
  }

  private static void testForEachWith2000Object() {
    printForeach(list3);
  }

  private static void testIteratorWith2000Object() {
    printIterator(list3);
  }

  private static void printFor(List list){
    System.out.println();
    System.out.print("data:");
    long start=System.currentTimeMillis();
    for(int i=0,size=list.size();i list){
    System.out.println();
    System.out.print("data:");
    long start=System.currentTimeMillis();
    for(int temp:list){
      System.out.print(temp+" ");
    }
    System.out.println();
    long end=System.currentTimeMillis();
    System.out.println("foreach for "+list.size()+":"+(end-start)+"ms");
  }

  private static void printIterator(List list){
    System.out.println();
    System.out.print("data:");
    Iterator it=list.iterator();
    long start=System.currentTimeMillis();
    while(it.hasNext()){
      System.out.print(it.next()+" ");
    }
    System.out.println();
    long end=System.currentTimeMillis();
    System.out.println("iterator for "+list.size()+":"+(end-start)+"ms");
  }


  private static void initList() {
    list1=new LinkedList<>();
    list2=new LinkedList<>();
    list3=new LinkedList<>();
    for(int i=0;i<10;i++){
      list1.add(random.nextInt());
    }
    for(int i=0;i<100;i++){
      list2.add(random.nextInt());
    }
    for(int i=0;i<1000;i++){
      list3.add(random.nextInt());
    }
  }
}

输出(忽略对元素的输出)

for for 10:0ms
foreach for 10:1ms
iterator for 10:0ms
for for 100:1ms
foreach for 100:0ms
iterator for 100:3ms
for for 1000:23ms
foreach for 1000:25ms
iterator for 1000:4ms

10 100 1000
for 0ms 1ms 23ms

forEach 1ms 0ms 25ms

Iterator 0ms 3ms 4ms

	10	100	1000
for	0ms	1ms	23ms
forEach	1ms	0ms	25ms
Iterator	0ms	3ms	4ms

结论

foreach的性能最不稳定，for次之，Iterator最好

使用建议

尽量使用Iterator进行遍历
需要使用索引时，使用递增变量的开销比for的要小

HashSet的比较

注：因Hash遍历算法与其他类型不一致，所以取消了for循环的比较

代码

public class TextHash {

  private static Random random;

  private static Set set1;

  private static Set set2;

  private static Set set3;

  public static void execute(){
    random=new Random();
    initHash();
    testIteratorWith20Object();
    testForEachWith20Object();
    testIteratorWith200Object();
    testForEachWith200Object();
    testIteratorWith2000Object();
    testForEachWith2000Object();
  }

  private static void testIteratorWith20Object() {
    printIterator(set1);
  }

  private static void testForEachWith20Object() {
    printForeach(set1);
  }

  private static void testIteratorWith200Object() {
    printIterator(set2);
  }

  private static void testForEachWith200Object() {
    printForeach(set2);
  }

  private static void testIteratorWith2000Object() {
    printIterator(set3);
  }

  private static void testForEachWith2000Object() {
    printForeach(set3);
  }

  private static void initHash() {
    set1=new HashSet<>();
    set2=new HashSet<>();
    set3=new HashSet<>();
    for(int i=0;i<10;i++){
      set1.add(random.nextInt());
    }
    for(int i=0;i<100;i++){
      set2.add(random.nextInt());
    }
    for(int i=0;i<1000;i++){
      set3.add(random.nextInt());
    }
  }

  private static void printIterator(Set data){
    System.out.println();
    System.out.print("data:");
    long start=System.currentTimeMillis();
    Iterator it=data.iterator();
    while (it.hasNext()){
      System.out.print(it.next()+" ");
    }
    System.out.println();
    long end=System.currentTimeMillis();
    System.out.println("iterator for "+data.size()+":"+(end-start)+"ms");
  }

  private static void printForeach(Set data){
    System.out.println();
    System.out.print("data:");
    long start=System.currentTimeMillis();
    for(int temp:data){
      System.out.print(temp+" ");
    }
    System.out.println();
    long end=System.currentTimeMillis();
    System.out.println("foreach for "+data.size()+":"+(end-start)+"ms");
  }
}

输出(忽略对元素的输出)

iterator for 10:0ms
foreach for 10:0ms
iterator for 100:6ms
foreach for 100:0ms
iterator for 1000:30ms
foreach for 1000:9ms

10 100 1000
foreach 0ms 0ms 9ms

Iterator 0ms 6ms 30ms

	10	100	1000
foreach	0ms	0ms	9ms
Iterator	0ms	6ms	30ms

结论

foreach性能遥遥领先于Iterator

使用建议

以后就选foreach了，性能好，写起来也方便。

总结

for循环性能在三者的对比中总体落于下风，而且开销递增幅度较大。以后即使在需要使用索引时我宁愿使用递增变量也不会使用for了。
Iterator的性能在数组以及链表的表现都是最好的，应该是JAVA的设计者优化过了。在响应时间敏感的情况下(例如web响应)，优先考虑。
foreach的性能属于两者之间，写法简单，时间不敏感的情况下我会尽量选用。

以上就是我对常见数据结构遍历机制的一点比较，虽然只是很初步，但是从中我也学到了很多东西，希望你们也有所收获。

好了，以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对创新互联的支持。

分享名称：java遍历机制性能的比较详解
当前链接：http://kswjz.com/article/jeedpj.html

扫二维码与项目经理沟通

我们在微信上24小时期待你的声音

解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流

java遍历机制性能的比较详解

扫二维码与项目经理沟通

其他资讯

行业动态

企业网站建设的重要性！

服务项目

网站建设

移动端/APP

微信/小程序

技术支持

其它服务

更多服务项目

联系吧在百度地图上找到我们

电话：13518219792

java遍历机制性能的比较详解

扫二维码与项目经理沟通

其他资讯

行业动态

企业网站建设的重要性！

服务项目

网站建设

移动端/APP

微信/小程序

技术支持

其它服务

更多服务项目

联系吧 在百度地图上找到我们

电话：13518219792

联系吧在百度地图上找到我们