Java项目里List集合使用的一些坑

ArrayList踩坑

首先我们来看一段代码

List<String> temp = new ArrayList();
//获取一堆数据
List<String> all = getData();
for (String str : all) {
    temp.add(str);
}

这段代码有什么问题呢？ 其实在大部分情况下这都是没啥问题，无非就是循环的往ArrayList中写入数据而已。

但在特殊情况下，比如这里的getData()返回数据非常巨大时后续temp.add(str)就会有问题了。

比如这里返回的数据有时会高达2000W，这时ArrayList写入的问题就凸显出来了。 我们知道ArrayList是由数组实现，而数据的长度有限；需要在合适的时机对数组扩容。

这里以插入到尾部为例 add(E e)。

ArrayList temp = new ArrayList<>(2) ;
temp.add("1");
temp.add("2");
temp.add("3");

当我们初始化一个长度为2的ArrayList，并往里边写入三条数据时ArrayList就得扩容了，也就是将之前的数据复制一份到新的数组长度为3的数组中。

之所以是3因为新长度 = 原有长度 * 1.5。

通过源码我们可以得知ArrayList的默认长度为 10。

但其实并不是在初始化的时候就创建了DEFAULT_CAPACITY=10的数组。

而是在往里边add第一个数据的时候会扩容到10。 既然知道了默认的长度为10，那说明后续一旦写入到第九个元素的时候就会扩容为10*1.5=15。这一步为数组复制，也就是要重新开辟一块新的内存空间存放这15个数组。 一旦我们频繁且数量巨大的进行写入时就会导致许多的数组复制，这个效率是极低的。 但如果我们提前预知了可能会写入多少条数据时就可以提前避免这个问题。 比如我们往里边写入1000W条数据，在初始化的时候就给定数组长度与用默认10的长度之间性能是差距巨大的。

用JMH验证如下：

package com.uw.kurisu.alice.common.utils;

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.TimeUnit;

/**
 * @author Kurisu
 * 2020-01-20 10:06 上午
 */
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
public class TestDemo {

    private static final int TEN_MILLION = 10000000;

    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MICROSECONDS)
    public void arrayList() {
        List<String> array = new ArrayList<>();
        for (int i = 0; i < TEN_MILLION; i++) {
            array.add("123");
        }
    }

    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MICROSECONDS)
    public void arrayListSize() {
        List<String> array = new ArrayList<>(TEN_MILLION);
        for (int i = 0; i < TEN_MILLION; i++) {
            array.add("123");
        }
    }


    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(TestDemo.class.getSimpleName())
                .forks(1)
                .build();
        new Runner(opt).run();
    }
}

运行结果如下： Score指执行完函数所消耗的时间。 根据结果可以看出预设长度的效率会比用默认的效率高上很多。 所以这里强烈建议大家：在有大量数据写入ArrayList时，一定要初始化指定长度。

再一个是一定要慎用add(intindex,E element)向指定位置写入数据。 通过源码我们可以看出，每一次写入都会将 index 后的数据往后移动一遍，其实本质也是要复制数组；

但区别于往常规的往数组尾部写入数据，它每次都会进行数组复制，效率极低。

LinkedList

提到ArrayList就不得不聊下LinkedList这个孪生兄弟；虽说都是List 的容器，但本质实现却完全不同。 LinkedList是由链表组成，每个节点又有头尾两个节点分别引用了前后两个节点；因此它也是一个双向链表。

所以理论上来说它的写入非常高效，将不会有ArrayList中效率极低的数组复制，每次只需要移动指针即可。

测试

我们一直说linkedList写入效率高于ArrayList,事实真的如此吗？

@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public void linkedList() {
   List<String> array = new LinkedList<>();
    for (int i = 0; i < TEN_MILLION; i++) {
       array.add("123");
    }
 }

话不多说了，结果显而易见。

而查询就不用多说了，ArrayList可以支持下标随机访问，效率非常高。 LinkedList由于底层不是数组，不支持通过下标访问，而是需要根据查询index所在的位置来判断是从头还是从尾进行遍历。 但不管是哪种都得需要移动指针来一个个遍历，特别是index靠近中间位置时将会非常慢。

总结

• 在使用ArrayList时如果能提前预测到数据量大小，比较大时一定要指定其长度。
• 尽可能避免使用add(index,e) api，会导致复制数组，降低效率。
• 再额外提一点，我们常用的另一个 Map 容器 HashMap 也是推荐要初始化长度从而避免扩容。