JAVA三种遍历机制的性能比较

骑猪看日落 2022-10-01 13:58 199阅读 0赞

小城大白兔 2019-06-11 20:01:00

# 正文 #

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

*  for循环
 *  forEach循环
 *  Iterator循环

![JAVA三种遍历机制的性能比较][JAVA]

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的比较 #

*  代码

package com.example.service;
    
    import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.List;
    import java.util.Random;
    
    /**
     * Created by admin on 2019/6/12.
     */
    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 forEach 0ms 4ms Iterator 2ms 12ms
 *  结论
 *  **for的性能最不稳定，foreach次之，Iterator最好**
 *  使用建议

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

# LinkedList的比较 #

*  代码

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 forEach 1ms 0ms Iterator 0ms 3ms
 *  结论
 *  **foreach的性能最不稳定，for次之，Iterator最好**
 *  使用建议：

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

# HashSet的比较 #

*注：因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 Iterator 0ms 6ms
 *  结论：**foreach性能遥遥领先于Iterator**
 *  使用建议：以后就选foreach了，性能好，写起来也方便。

# 总结 #

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

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

**更多资料展示如下，需要的小伙伴们转发，私信口令：资料，即可获得以下资料！！！**

![JAVA三种遍历机制的性能比较][JAVA 1]

[JAVA]: http://p1.pstatp.com/large/dfic-imagehandler/65aa917d-1e74-4d83-addb-1cedf99f755c
[JAVA 1]: http://p1.pstatp.com/large/pgc-image/09095f08573e47adb10ec49ac7efc985