ArrayList哪种循环效率更好你真的清楚吗

2020-04-28 本文已影响0人 java金融

ArrayList简介

声明：以下内容都是基于jdk1.8的

ArrayList 是一个数组队列，相当于动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。
看过ArrayList 源码的同学有没有注意过有这么一个细节：为什么ArrayList实现了RandomAccess这个接口，但是 LinkedList却没有实现这个接口？这是一个空接口，里面没有任何的方法，有什么作用呢？
答案: RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。也就是说，实现了这个接口的集合是支持快速随机访问策略的。而LinkedList是不能实现随机访问的。

ArrayList数据结构

ArrayList包含了两个重要的对象：elementData 和 size。

elementData 是"Object[]类型的数组"，它保存了添加到ArrayList中的元素。实际上，elementData是个 $\color{blue}{动态数组}$ 。
那是不是有人就会问既然ArrayList本质是数组，那为啥它的长度可以改变?
$\color{blue}{首先，数组的确长度不能改变。不过，ArrayList内部有一系列骚操作，大概就是它每次觉得长度不够就会创建一个新数组，这个新数组的容量比原来多出50%，把原来的数组copy过来，然后把以前的数组销毁掉。}$
size 则是动态数组的实际大小。

ArrayList遍历方式

第1种，普通for循环随机访问，通过索引值去遍历。

     // 随机访问
     List<String> list = new ArrayList<>();
     int size = list.size();
     for (int i = 0; i < size; i++) {
         value = list.get(i);
     }

第2种，通过迭代器遍历。即通过Iterator去遍历。

     // 增强for循环
    for (String s : list) {
        value = s;
    }

第3种，增强for循环遍历。

     // 迭代器遍历
    Iterator<String> iter = list.iterator();
    while (iter.hasNext()) {
        value = iter.next();
    }

第4种 forEach + lambda 循环遍历

     list.forEach(p -> {
                p.hashCode();
            });

既然有4种遍历，那我们看看哪种遍历效率下面我们通过一个实验来看下这四种循环的耗时吧：
测试代码

/**
 * @Date: 2020/4/23 
 * @Description:
 */
public class ArrayListTest {
    public static void main(String[] args) {
        // 数据预热
       /* List<String> testList = createTestList(10);
        testForEach(testList);
        testFor(testList);
        testRandFor(10,testList);*/
        List<Integer> integers = Arrays.asList(10, 50, 100,500,1000, 10000, 50000, 100000, 5000000, 10000000,30000000);
        for (Integer i : integers) {
            testRand(i);
        }

    }

    private static void testRand(int size) {
        System.out.println("-----------次数:" + size + "------------");
        List<String> list = createTestList(size);
        // 随机访问通过索引值去遍历。
        long time1 = System.nanoTime();
        testRandFor(size, list);
        long time2 = System.nanoTime();
        // 增强for循环
        testFor(list);
        long time3 = System.nanoTime();
        // 迭代器遍历
        testIterator(list);
        long time4 = System.nanoTime();
        // forEach + lambda
        testForEach(list);
        long time5 = System.nanoTime();

        System.out.println("随机访问\t\t" + (time2 - time1) / 1000 + " ms");
        System.out.println("增强for遍历\t\t" + (time3 - time2) / 1000 + " ms");
        System.out.println("迭代器遍历\t\t" + (time4 - time3) / 1000 + " ms");
        System.out.println("forEach遍历\t\t" + (time5 - time4) / 1000 + " ms");
        System.out.println();
    }

    private static void testRandFor(int size, List<String> list) {
        for (int i = 0; i < size; i++) {
            list.get(i).hashCode();
        }
    }

    private static void testFor(List<String> list) {
        for (String s : list) {
            s.hashCode();
        }
    }

    private static void testIterator(List<String> list) {
        Iterator<String> iter = list.iterator();
        while (iter.hasNext()) {
            iter.next().hashCode();
        }
    }

    private static void testForEach(List<String> list) {
        list.forEach(p -> {
            p.hashCode();
        });
    }

    public static List<String> createTestList(int size) {
        List<String> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            list.add(UUID.randomUUID().toString());
        }
        return list;
    }
}

测试数据结果如下：

-----------次数:10------------
随机访问        8 ms
增强for遍历     5 ms
迭代器遍历       2 ms
forEach遍历       40358 ms

-----------次数:50------------
随机访问        4 ms
增强for遍历     8 ms
迭代器遍历       7 ms
forEach遍历       5 ms

-----------次数:100------------
随机访问        13 ms
增强for遍历     18 ms
迭代器遍历       14 ms
forEach遍历       10 ms

-----------次数:500------------
随机访问        54 ms
增强for遍历     28 ms
迭代器遍历       24 ms
forEach遍历       57 ms

-----------次数:1000------------
随机访问        106 ms
增强for遍历     56 ms
迭代器遍历       50 ms
forEach遍历       37 ms

-----------次数:10000------------
随机访问        1192 ms
增强for遍历     892 ms
迭代器遍历       861 ms
forEach遍历       594 ms

-----------次数:50000------------
随机访问        3651 ms
增强for遍历     2908 ms
迭代器遍历       2563 ms
forEach遍历       2712 ms

-----------次数:100000------------
随机访问        10693 ms
增强for遍历     5273 ms
迭代器遍历       9294 ms
forEach遍历       3638 ms

-----------次数:5000000------------
随机访问        238922 ms
增强for遍历     29914 ms
迭代器遍历       30533 ms
forEach遍历       28016 ms

-----------次数:10000000------------
随机访问        431047 ms
增强for遍历     47151 ms
迭代器遍历       46371 ms
forEach遍历       38943 ms

-----------次数:30000000------------
随机访问        1163935 ms
增强for遍历     137710 ms
迭代器遍历       139211 ms
forEach遍历       129960 ms

结论：如果数据量比较少的话貌似四种循环耗时都差不多，但是随着数据量的增长会发现foreach的效率是最好的。
但是从上面我们会发现一个奇怪的现象，第一次循环的时候forEach遍历的时间是最长的尽管数据量非常少也会这样。但是后面的耗时就正常了。如果放开测试里面的预热代码，每次跑出来的耗时也是正常的。
这个结论貌似和网上的一些结论有点误差：如果你在百度上搜索java for foreach java8 等关键词会出现很多的搜索结果，比如这几个循环效率的对比。并且很多博主的结论是java8的foreach循环是真的菜，效率不是差的一点点！！！慎用，之类的。
若java8的foreach效率如此低下，为何还要推出？难道jdk的开发人员不会优化一下？带着这个思考，我仔细看了“已往之不谏”的博主最后为java8 正名的博客，写的不错，测试也很充分（说实话，没有仔细的阅读）但是结论很明显。java8胜了。作者为了证明java8不是吃素的，确实下了不少功夫。最后的最后，作者提到了，“java8的foreach预热是jvm级别的，需要预热。”原文链接感兴趣的可以去看下。

ArrayList删除数据

虽然有四种遍历方式，但是能够正确删除数据的方式只有两种

第1种通过迭代器进行删除。这种方式的话，也是《阿里代码规约》所推荐的。

在这里插入图片描述

 Iterator<String> iter = list.iterator();
        while (iter.hasNext()) {
            iter.next().hashCode();
            iter.remove();
        }

第2种倒序循环删除

  for(int i = list.size()-1;i>=0;i--){
            list.remove(i);
        }

下面再演示下错误的删除操作

普通for循环正序删除，删除过程中元素向左移动，不能删除重复的元素

        List<String> list = new ArrayList<>();
        list.add("1");
        list.add("1");
        list.add("2");
        for(int i=0;i<list.size();i++){
           list.remove(i);
        }
        System.out.println(String.join(",",list));

结果输出：1

增强for循环删除会抛出 java.util.ConcurrentModificationException

ArryList注意点

谨慎使用ArrayList中的subList方法
- ArrayList的subList结果不可强转成ArrayList，否则会抛出ClassCastException 异常，即 java.util.RandomAccessSubList cannot be cast to java.util.ArrayList. 说明：subList 返回的是 ArrayList 的内部类 SubList，并不是 ArrayList ，而是 ArrayList 的一个视图，对于 SubList 子列表的所有操作最终会反映到原列表上。
```
    List<String> list = new ArrayList<>();
        list.add("1");
        list.add("1");
        list.add("2");
        ArrayList<String> strings =  (ArrayList)list.subList(0, 1);

运行结果：
Exception in thread "main" java.lang.ClassCastException: java.util.ArrayList$SubList cannot be cast to java.util.ArrayList
at com.workit.demo.listener.ArrayListTest.main(ArrayListTest.java:29)
```
- 在 subList 场景中，高度注意对原集合元素个数的修改，会导致子列表的遍历、增加、删除均会产ConcurrentModificationException 异常。

   List<String> list = new ArrayList<>();
        list.add("1");
        list.add("1");
        list.add("2");
        List<String> subList =  list.subList(0, 1);
        // 对原List增加一个值
        list.add("10");
        subList.add("11"); // 这一行会报 java.util.ConcurrentModificationException

初始化List的时候尽量指定它的容量大小。(尽量减少扩容次数)

ArrayList哪种循环效率更好你真的清楚吗

ArrayList简介

ArrayList数据结构

ArrayList遍历方式

ArrayList删除数据

ArryList注意点

猜你喜欢

热点阅读