ArrayList哪种遍历效率最好，你真的弄明白了吗？

程序员文章站 2024-03-12 16:47:14

...

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是个动态数组。
那是不是有人就会问既然ArrayList本质是数组，那为啥它的长度可以改变?
首先，数组的确长度不能改变。不过，ArrayList内部有一系列骚操作，大概就是它每次觉得长度不够就会创建一个新数组，这个新数组的容量比原来多出50%，把原来的数组copy过来，然后把以前的数组销毁掉。
size 则是动态数组的实际大小。

ArrayList遍历方式

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

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

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

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

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

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

第4种 forEach + lambda 循环遍历

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

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

 1/**
 2 * @Date: 2020/4/23 
 3 * @Description:
 4 */
 5public class ArrayListTest {
 6    public static void main(String[] args) {
 7        // 数据预热
 8       /* List<String> testList = createTestList(10);
 9        testForEach(testList);
10        testFor(testList);
11        testRandFor(10,testList);*/
12        List<Integer> integers = Arrays.asList(10, 50, 100,500,1000, 10000, 50000, 100000, 5000000, 10000000,30000000);
13        for (Integer i : integers) {
14            testRand(i);
15        }
16
17    }
18
19    private static void testRand(int size) {
20        System.out.println("-----------次数:" + size + "------------");
21        List<String> list = createTestList(size);
22        // 随机访问通过索引值去遍历。
23        long time1 = System.nanoTime();
24        testRandFor(size, list);
25        long time2 = System.nanoTime();
26        // 增强for循环
27        testFor(list);
28        long time3 = System.nanoTime();
29        // 迭代器遍历
30        testIterator(list);
31        long time4 = System.nanoTime();
32        // forEach + lambda
33        testForEach(list);
34        long time5 = System.nanoTime();
35
36        System.out.println("随机访问\t\t" + (time2 - time1) / 1000 + " ms");
37        System.out.println("增强for遍历\t\t" + (time3 - time2) / 1000 + " ms");
38        System.out.println("迭代器遍历\t\t" + (time4 - time3) / 1000 + " ms");
39        System.out.println("forEach遍历\t\t" + (time5 - time4) / 1000 + " ms");
40        System.out.println();
41    }
42
43    private static void testRandFor(int size, List<String> list) {
44        for (int i = 0; i < size; i++) {
45            list.get(i).hashCode();
46        }
47    }
48
49    private static void testFor(List<String> list) {
50        for (String s : list) {
51            s.hashCode();
52        }
53    }
54
55    private static void testIterator(List<String> list) {
56        Iterator<String> iter = list.iterator();
57        while (iter.hasNext()) {
58            iter.next().hashCode();
59        }
60    }
61
62    private static void testForEach(List<String> list) {
63        list.forEach(p -> {
64            p.hashCode();
65        });
66    }
67
68    public static List<String> createTestList(int size) {
69        List<String> list = new ArrayList<>(size);
70        for (int i = 0; i < size; i++) {
71            list.add(UUID.randomUUID().toString());
72        }
73        return list;
74    }
75}

测试数据结果如下：

 1-----------次数:10------------
 2随机访问        8 ms
 3增强for遍历        5 ms
 4迭代器遍历        2 ms
 5forEach遍历        40358 ms
 6
 7-----------次数:50------------
 8随机访问        4 ms
 9增强for遍历        8 ms
10迭代器遍历        7 ms
11forEach遍历        5 ms
12
13-----------次数:100------------
14随机访问        13 ms
15增强for遍历        18 ms
16迭代器遍历        14 ms
17forEach遍历        10 ms
18
19-----------次数:500------------
20随机访问        54 ms
21增强for遍历        28 ms
22迭代器遍历        24 ms
23forEach遍历        57 ms
24
25-----------次数:1000------------
26随机访问        106 ms
27增强for遍历        56 ms
28迭代器遍历        50 ms
29forEach遍历        37 ms
30
31-----------次数:10000------------
32随机访问        1192 ms
33增强for遍历        892 ms
34迭代器遍历        861 ms
35forEach遍历        594 ms
36
37-----------次数:50000------------
38随机访问        3651 ms
39增强for遍历        2908 ms
40迭代器遍历        2563 ms
41forEach遍历        2712 ms
42
43-----------次数:100000------------
44随机访问        10693 ms
45增强for遍历        5273 ms
46迭代器遍历        9294 ms
47forEach遍历        3638 ms
48
49-----------次数:5000000------------
50随机访问        238922 ms
51增强for遍历        29914 ms
52迭代器遍历        30533 ms
53forEach遍历        28016 ms
54
55-----------次数:10000000------------
56随机访问        431047 ms
57增强for遍历        47151 ms
58迭代器遍历        46371 ms
59forEach遍历        38943 ms
60
61-----------次数:30000000------------
62随机访问        1163935 ms
63增强for遍历        137710 ms
64迭代器遍历        139211 ms
65forEach遍历        129960 ms

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

ArrayList删除数据

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

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

在这里插入图片描述

1 Iterator<String> iter = list.iterator();
2        while (iter.hasNext()) {
3            iter.next().hashCode();
4            iter.remove();
5        }

第2种倒序循环删除

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

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

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

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

结果输出：1。第二个1没有被删除掉。

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

ArryList注意点

谨慎使用ArrayList中的subList方法(Arrays.asListfa)

ArrayList的subList结果不可强转成ArrayList，否则会抛出ClassCastException 异常，即 java.util.RandomAccessSubList cannot be cast to java.util.ArrayList. 说明：subList 返回的是 ArrayList 的内部类 SubList，并不是 ArrayList ，而是 ArrayList 的一个视图，对于 SubList 子列表的所有操作最终会反映到原列表上。

1    List<String> list = new ArrayList<>();
2        list.add("1");
3        list.add("1");
4        list.add("2");
5        ArrayList<String> strings =  (ArrayList)list.subList(0, 1);
6
7运行结果：
8Exception in thread "main" java.lang.ClassCastException: java.util.ArrayList$SubList cannot be cast to java.util.ArrayList
9  at com.workit.demo.listener.ArrayListTest.main(ArrayListTest.java:29)

在 subList 场景中，高度注意对原集合元素个数的修改，会导致子列表的遍历、增加、删除均会产ConcurrentModificationException 异常。

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

初始化List的时候尽量指定它的容量大小。(尽量减少扩容次数)
ArrayList线程非安全的。

Java面试题专栏

【61期】MySQL行锁和表锁的含义及区别（MySQL面试第四弹）

【62期】解释一下MySQL中内连接，外连接等的区别（MySQL面试第五弹）

【63期】谈谈MySQL 索引，B+树原理，以及建索引的几大原则（MySQL面试第六弹）

【64期】MySQL 服务占用cpu 100%，如何排查问题? （MySQL面试第七弹）

【65期】Spring的IOC是啥?有什么好处?

【66期】Java容器面试题：谈谈你对 HashMap 的理解