JAVA遍历机制的性能的比较

共计 8376 个字符，预计需要花费 21 分钟才能阅读完成。

本文首发于 cartoon 的博客
转载请注明出处:https://cartoonyu.github.io/cartoon-blog/post/java/java%E9%81%8D%E5%8E%86%E6%9C%BA%E5%88%B6%E7%9A%84%E6%80%A7%E8%83%BD%E6%AF%94%E8%BE%83/

近段时间在写 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
元素都采用随机数生成
遍历进行操作都为输出当前元素的值

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

代码

public class TextArray {

    private static Random random;

    private static List<Integer> list1;

    private static List<Integer> list2;

    private static List<Integer> list3;

    public static void execute(){random=new Random();
        initArray();
        testForWith10Object();
        testForEachWith10Object();
        testIteratorWith10Object();
        testForWith100Object();
        testForEachWith100Object();
        testIteratorWith100Object();
        testForWith1000Object();
        testForEachWith1000Object();
        testIteratorWith1000Object();}

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

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

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

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

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

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

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

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

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

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

    private static void printForeach(List<Integer> 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<Integer> list){System.out.println();
        System.out.print("data:");
        Iterator<Integer> 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

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

代码

public class TextLinkedList {

    private static Random random;

    private static List<Integer> list1;

    private static List<Integer> list2;

    private static List<Integer> list3;

    public static void execute(){random=new Random();
        initList();
        testForWith10Object();
        testForEachWith10Object();
        testIteratorWith10Object();
        testForWith100Object();
        testForEachWith100Object();
        testIteratorWith100Object();
        testForWith1000Object();
        testForEachWith1000Object();
        testIteratorWith1000Object();}

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

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

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

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

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

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

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

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

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

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

    private static void printForeach(List<Integer> 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<Integer> list){System.out.println();
        System.out.print("data:");
        Iterator<Integer> 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

结论
foreach 的性能最不稳定，for 次之，Iterator 最好
使用建议
1. 尽量使用 Iterator 进行遍历
2. 需要使用索引时，使用递增变量的开销比 for 的要小

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

代码

public class TextHash {

    private static Random random;

    private static Set<Integer> set1;

    private static Set<Integer> set2;

    private static Set<Integer> set3;

    public static void execute(){random=new Random();
        initHash();
        testIteratorWith10Object();
        testForEachWith10Object();
        testIteratorWith100Object();
        testForEachWith100Object();
        testIteratorWith1000Object();
        testForEachWith1000Object();}

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

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

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

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

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

    private static void testForEachWith1000Object() {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<Integer> data){System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        Iterator<Integer> 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<Integer> 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

结论
foreach 性能遥遥领先于 Iterator
使用建议
以后就选 foreach 了，性能好，写起来也方便。

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

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

如果你喜欢本文章，可以收藏阅读，如果你对我的其他文章感兴趣，欢迎到我的博客查看。

列表项目

缘由

正文

ArrayList 的比较

LinkedList 的比较

HashSet 的比较

总结

Just My Socks（注册教程内含优惠码）

JAVA遍历机制的性能的比较

缘由

正文

ArrayList 的比较

LinkedList 的比较

HashSet 的比较

总结

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）