性能评测
了解了数组和链表的基础知识之后，接下来我们正式进入性能评测环节。
在正式开始之前，我们先来明确一下测试目标，我们需要测试的点其实只有 6 个：
- 从头部/中间部分/尾部进行添加操作的性能测试；
- 从头部/中间部分/尾部开始查询的性能测试。
因为添加操作和删除操作在执行时间层面基本是一致的，比如数组添加需要移动后面的元素，删除也同样是移动后面的元素；而链表也是如此，添加和删除都是改变自身和相连节点的信息，因此我们就把添加和删除的测试合二为一，用添加操作来进行测试。
测试说明：
- 在 Java 语言中，数组的代表为
ArrayList，而链表的代表为LinkedList，因此我们就用这两个对象来进行测试； - 本文我们将使用 Oracle 官方推荐 JMH 框架来进行测试，点击查看更多关于 JMH 的内容；
- 本文测试环境是 JDK 1.8、MacMini、Idea 2020.1。
1.头部添加性能测试
import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.infra.Blackhole; 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.LinkedList; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) // 测试完成时间 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热次数和时间 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 @Fork(1) // fork 1 个线程 @State(Scope.Thread) public class ArrayOptimizeTest { private static final int maxSize = 1000; // 测试循环次数 private static final int operationSize = 100; // 操作次数 private static ArrayList<Integer> arrayList; private static LinkedList<Integer> linkedList; public static void main(String[] args) throws RunnerException { // 启动基准测试 Options opt = new OptionsBuilder() .include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类 .build(); new Runner(opt).run(); // 执行测试 } @Setup public void init() { // 启动执行事件 arrayList = new ArrayList<Integer>(); linkedList = new LinkedList<Integer>(); for (int i = 0; i < maxSize; i++) { arrayList.add(i); linkedList.add(i); } } @Benchmark public void addArrayByFirst(Blackhole blackhole) { for (int i = 0; i < +operationSize; i++) { arrayList.add(i, i); } // 为了避免 JIT 忽略未被使用的结果计算 blackhole.consume(arrayList); } @Benchmark public void addLinkedByFirst(Blackhole blackhole) { for (int i = 0; i < +operationSize; i++) { linkedList.add(i, i); } // 为了避免 JIT 忽略未被使用的结果计算 blackhole.consume(linkedList); } }
从以上代码可以看出，在测试之前，我们先将 ArrayList 和 LinkedList 进行数据初始化，再从头部开始添加 100 个元素，执行结果如下：
从以上结果可以看出，LinkedList 的平均执行（完成）时间比 ArrayList 平均执行时间快了约 216 倍。
2.中间添加性能测试
import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.infra.Blackhole; 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.LinkedList; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) // 测试完成时间 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热次数和时间 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 @Fork(1) // fork 1 个线程 @State(Scope.Thread) public class ArrayOptimizeTest { private static final int maxSize = 1000; // 测试循环次数 private static final int operationSize = 100; // 操作次数 private static ArrayList<Integer> arrayList; private static LinkedList<Integer> linkedList; public static void main(String[] args) throws RunnerException { // 启动基准测试 Options opt = new OptionsBuilder() .include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类 .build(); new Runner(opt).run(); // 执行测试 } @Setup public void init() { // 启动执行事件 arrayList = new ArrayList<Integer>(); linkedList = new LinkedList<Integer>(); for (int i = 0; i < maxSize; i++) { arrayList.add(i); linkedList.add(i); } } @Benchmark public void addArrayByMiddle(Blackhole blackhole) { int startCount = maxSize / 2; // 计算中间位置 // 中间部分进行插入 for (int i = startCount; i < (startCount + operationSize); i++) { arrayList.add(i, i); } // 为了避免 JIT 忽略未被使用的结果计算 blackhole.consume(arrayList); } @Benchmark public void addLinkedByMiddle(Blackhole blackhole) { int startCount = maxSize / 2; // 计算中间位置 // 中间部分进行插入 for (int i = startCount; i < (startCount + operationSize); i++) { linkedList.add(i, i); } // 为了避免 JIT 忽略未被使用的结果计算 blackhole.consume(linkedList); } }
从以上代码可以看出，在测试之前，我们先将 ArrayList 和 LinkedList 进行数据初始化，再从中间开始添加 100 个元素，执行结果如下：
从上述结果可以看出，LinkedList 的平均执行时间比 ArrayList 平均执行时间快了约 54 倍。
3.尾部添加性能测试
import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.infra.Blackhole; 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.LinkedList; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) // 测试完成时间 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热次数和时间 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 @Fork(1) // fork 1 个线程 @State(Scope.Thread) public class ArrayOptimizeTest { private static final int maxSize = 1000; // 测试循环次数 private static final int operationSize = 100; // 操作次数 private static ArrayList<Integer> arrayList; private static LinkedList<Integer> linkedList; public static void main(String[] args) throws RunnerException { // 启动基准测试 Options opt = new OptionsBuilder() .include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类 .build(); new Runner(opt).run(); // 执行测试 } @Setup public void init() { // 启动执行事件 arrayList = new ArrayList<Integer>(); linkedList = new LinkedList<Integer>(); for (int i = 0; i < maxSize; i++) { arrayList.add(i); linkedList.add(i); } } @Benchmark public void addArrayByEnd(Blackhole blackhole) { int startCount = maxSize - 1 - operationSize; for (int i = startCount; i < (maxSize - 1); i++) { arrayList.add(i, i); } // 为了避免 JIT 忽略未被使用的结果计算 blackhole.consume(arrayList); } @Benchmark public void addLinkedByEnd(Blackhole blackhole) { int startCount = maxSize - 1 - operationSize; for (int i = startCount; i < (maxSize - 1); i++) { linkedList.add(i, i); } // 为了避免 JIT 忽略未被使用的结果计算 blackhole.consume(linkedList); } }
以上程序的执行结果为：
从上述结果可以看出，LinkedList 的平均执行时间比 ArrayList 平均执行时间快了约 32 倍。
4.头部查询性能评测
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.LinkedList; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) // 测试完成时间 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热次数和时间 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 @Fork(1) // fork 1 个线程 @State(Scope.Thread) public class ArrayOptimizeTest { private static final int maxSize = 1000; // 测试循环次数 private static final int operationSize = 100; // 操作次数 private static ArrayList<Integer> arrayList; private static LinkedList<Integer> linkedList; public static void main(String[] args) throws RunnerException { // 启动基准测试 Options opt = new OptionsBuilder() .include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类 .build(); new Runner(opt).run(); // 执行测试 } @Setup public void init() { // 启动执行事件 arrayList = new ArrayList<Integer>(); linkedList = new LinkedList<Integer>(); for (int i = 0; i < maxSize; i++) { arrayList.add(i); linkedList.add(i); } } @Benchmark public void findArrayByFirst() { for (int i = 0; i < operationSize; i++) { arrayList.get(i); } } @Benchmark public void findLinkedyByFirst() { for (int i = 0; i < operationSize; i++) { linkedList.get(i); } } }
以上程序的执行结果为：
从上述结果可以看出，从头部查询 100 个元素时 ArrayList 的平均执行时间比 LinkedList 平均执行时间快了约 1990 倍。
5.中间查询性能评测
import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.infra.Blackhole; 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.LinkedList; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) // 测试完成时间 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热次数和时间 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 @Fork(1) // fork 1 个线程 @State(Scope.Thread) public class ArrayOptimizeTest { private static final int maxSize = 1000; // 测试循环次数 private static final int operationSize = 100; // 操作次数 private static ArrayList<Integer> arrayList; private static LinkedList<Integer> linkedList; public static void main(String[] args) throws RunnerException { // 启动基准测试 Options opt = new OptionsBuilder() .include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类 .build(); new Runner(opt).run(); // 执行测试 } @Setup public void init() { // 启动执行事件 arrayList = new ArrayList<Integer>(); linkedList = new LinkedList<Integer>(); for (int i = 0; i < maxSize; i++) { arrayList.add(i); linkedList.add(i); } } @Benchmark public void findArrayByMiddle() { int startCount = maxSize / 2; int endCount = startCount + operationSize; for (int i = startCount; i < endCount; i++) { arrayList.get(i); } } @Benchmark public void findLinkedyByMiddle() { int startCount = maxSize / 2; int endCount = startCount + operationSize; for (int i = startCount; i < endCount; i++) { linkedList.get(i); } } }
以上程序的执行结果为：
从上述结果可以看出，从中间查询 100 个元素时 ArrayList 的平均执行时间比 LinkedList 平均执行时间快了约 28089 倍，真是恐怖。
6.尾部查询性能评测
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.LinkedList; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) // 测试完成时间 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热次数和时间 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 @Fork(1) // fork 1 个线程 @State(Scope.Thread) public class ArrayOptimizeTest { private static final int maxSize = 1000; // 测试循环次数 private static final int operationSize = 100; // 操作次数 private static ArrayList<Integer> arrayList; private static LinkedList<Integer> linkedList; public static void main(String[] args) throws RunnerException { // 启动基准测试 Options opt = new OptionsBuilder() .include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类 .build(); new Runner(opt).run(); // 执行测试 } @Setup public void init() { // 启动执行事件 arrayList = new ArrayList<Integer>(); linkedList = new LinkedList<Integer>(); for (int i = 0; i < maxSize; i++) { arrayList.add(i); linkedList.add(i); } } @Benchmark public void findArrayByEnd() { for (int i = (maxSize - operationSize); i < maxSize; i++) { arrayList.get(i); } } @Benchmark public void findLinkedyByEnd() { for (int i = (maxSize - operationSize); i < maxSize; i++) { linkedList.get(i); } } }
以上程序的执行结果为：
从上述结果可以看出，从尾部查询 100 个元素时 ArrayList 的平均执行时间比 LinkedList 平均执行成时间快了约 1839 倍。
7.扩展添加测试
接下来我们再来测试一下，正常情况下我们从头开始添加数组和链表的性能对比，测试代码如下：
import org.openjdk.jmh.annotations.*; import org.openjdk.jmh.infra.Blackhole; 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.LinkedList; import java.util.concurrent.TimeUnit; @BenchmarkMode(Mode.AverageTime) // 测试完成时间 @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 预热次数和时间 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 @Fork(1) // fork 1 个线程 @State(Scope.Thread) public class ArrayOptimizeTest { private static final int maxSize = 1000; // 测试循环次数 private static ArrayList<Integer> arrayList; private static LinkedList<Integer> linkedList; public static void main(String[] args) throws RunnerException { // 启动基准测试 Options opt = new OptionsBuilder() .include(ArrayOptimizeTest.class.getSimpleName()) // 要导入的测试类 .build(); new Runner(opt).run(); // 执行测试 } @Benchmark public void addArray(Blackhole blackhole) { // 中间删数组表 arrayList = new ArrayList<Integer>(); for (int i = 0; i < maxSize; i++) { arrayList.add(i); } // 为了避免 JIT 忽略未被使用的结果计算 blackhole.consume(arrayList); } @Benchmark public void addLinked(Blackhole blackhole) { // 中间删除链表 linkedList = new LinkedList<Integer>(); for (int i = 0; i < maxSize; i++) { linkedList.add(i); } // 为了避免 JIT 忽略未被使用的结果计算 blackhole.consume(linkedList); } }
以上程序的执行结果为：
接下来，我们将添加的次数调至 1w，测试结果如下：
最后，我们再将添加次数调至 10w，测试结果如下：
从以上结果可以看出在正常情况下，从头部依次开始添加元素时，他们性能差别不大。
总结
本文我们介绍了数组的概念以及它的优缺点，同时还介绍了单向链表、双向链表及循环链表的概念以及链表的优缺点。我们在最后的评测中可以看出，当我们正常从头部依次添加元素时，链表和数组的性能差不不大。但当数据初始化完成之后，我们再进行插入操作时，尤其是从头部插入时，因为数组要移动之后的所有元素，因此性能要比链表低很多；但在查询时性能刚好相反，因为链表要遍历查询，并且 LinkedList 是双向链表，所以在中间查询时性能要比数组查询慢了上万倍（查询 100 个元素），而两头查询（首部和尾部）时，链表也比数组慢了将近 1000 多倍（查询 100 个元素），因此在查询比较多的场景中，我们要尽量使用数组，而在添加和删除操作比较多时，我们应该使用链表结构。
数组和链表的操作时间复杂度，如下表所示：
| 数组 | 链表 | |
| 查询 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
