场景
Java中使用JMH(Java Microbenchmark Harness 微基准测试框架)进行性能测试和优化：
https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/131723751
上面在使用JMH时测试了Java中数组和链表在进行头部插入时的对比结果。
下面分别对比在头部、中部、尾部分别进行查询和添加/删除时的性能对比，因添加和删除流程类似，
所以只测试添加即可。
Java中数组与链表
数组
数组（Array）是由相同类型的元素（element）的集合所组成的数据结构，分配⼀块连续的内存来存储。
利⽤元素的索引（index）可以计算出该元素对应的存储地址。
数组的“连续”特征决定了它的访问速度很快，因为它是连续存储的，所以这就决定了它的存储位置就是固定的，
因此它的访问速度就很快。
⽽缺点它对内存的要求⽐较⾼，必须要找到⼀块连续的内存才⾏。
数组的另⼀个缺点就是插⼊和删除的效率⽐较慢，假如我们在数组的⾮尾部插⼊或删除⼀个数据，那么就
要移动之后的所有数据，这就会带来⼀定的性能开销数组还有⼀个缺点，它的⼤⼩固定，不能动态拓展。
链表
链表（Linked list）是⼀种常⻅的基础数据结构，是⼀种线性表，但是并不会按线性的顺序存储数据，
⽽是在每⼀个节点⾥存到下⼀个节点的指针（Pointer）。由于不必须按顺序存储，链表在插⼊的时候可
以达到 O(1) 的复杂度，⽐另⼀种线性表顺序表快得多，但是查找⼀个节点或者访问特定编号的节点则
需要 O(n) 的时间，⽽顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。
链表是⼀个⽆需连续内存存储的数据结构，链表的元素有两个属性，⼀个是元素的值，另⼀个是指针，
此指针标记了下⼀个元素的地址。
链表主要分为以下⼏类：
单向链表
单向链表中包含两个域，⼀个信息域和⼀个指针域。这个链接指向列表中的下⼀个节点，⽽最后⼀个节点则指向⼀个空值。
双向链表
双向链表也叫双链表，双向链表中不仅有指向后⼀个节点的指针，还有指向前⼀个节点的指针，这样可以
从任何⼀个节点访问前⼀个节点，当然也可以访问后⼀个节点，以⾄整个链表。
循环链表
循环链表中第⼀个节点之前就是最后⼀个节点，反之亦然。
为什么会有单、双链表之分？
这个就要从链表的删除说起了，如果单向链表要删除元素的话，不但要找到删除的节点，还要找到删除节
点的上⼀个节点（通常称之为前驱），因为需要变更上⼀个节点中 next 的指针，但⼜因为它是单向链表，
所以在删除的节点中并没有存储上⼀个节点的相关信息，那么我们就需要再查询⼀遍链表以找到上⼀个节点，
这样就带来了⼀定的性能问题，所以就有了双向链表。
链表的优点：
1. 链表对内存的利⽤率⽐较⾼，⽆需连续的内存空间，即使有内存碎⽚，也不影响链表的创建；
2. 链表的插⼊和删除的速度很快，⽆需像数组⼀样需要移动⼤量的元素；
3. 链表⼤⼩不固定，可以很⽅便的进⾏动态扩展。
链表缺点
链表的主要缺点是不能随机查找，必须从第⼀个开始遍历，查找效率⽐较低，链表查询的时间复杂度是O(n)。
在 Java 语⾔中，数组的代表为 ArrayList ，⽽链表的代表为 LinkedList ，因此我们就⽤这两个对象来进⾏测试。
注：
博客：
https://blog.csdn.net/badao_liumang_qizhi
实现
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)
@State(Scope.Thread)
//头部添加性能测试
public class ArrayListWithLinkedListTestHeaderAdd {
private static final int maxSize = 10000; //测试循环次数
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(ArrayListWithLinkedListTestHeaderAdd.class.getSimpleName()) //要导入的测试类
.build();
//执行测试
new Runner(opt).run();
}
//@Setup作用于方法上，用于测试前的初始化工作
//启动执行事件
@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);
}
}
//用于回收某些资源
@TearDown
public void finish(){
}
@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);
}
}
测试结果输出如下：
Benchmark Mode Cnt Score Error Units ArrayListWithLinkedListTestHeaderAdd.addArrayByFirst avgt 5 6597432.461 ± 8384921.207 ns/op ArrayListWithLinkedListTestHeaderAdd.addLinkedByFirst avgt 5 111880.375 ± 258245.983 ns/op
可以看到在进行头部插入时LinkedList的平均完成时间比ArrayList平均完成时间快了约60倍
2、测试中部添加
@Benchmark
public void addArrayByMiddle(Blackhole blackhole){
int startIndex = maxSize /2 ;//获取中间值
for (int i = startIndex; i < (startIndex + operationSize); i++) {
arrayList.add(i,i);
}
//为了避免JIT忽略未被使用的结果计算/为了避免死码消除问题
blackhole.consume(arrayList);
}
@Benchmark
public void addLinkedByMiddle(Blackhole blackhole){
int startIndex = maxSize /2 ;//获取中间值
for (int i = startIndex; i < (startIndex + operationSize); i++) {
linkedList.add(i,i);
}
//为了避免JIT忽略未被使用的结果计算/为了避免死码消除问题
blackhole.consume(linkedList);
}
测试结果
Benchmark Mode Cnt Score Error Units
ArrayListWithLinkedListTestMiddleAdd.addArrayByMiddle
avgt 5 6703786.087 ± 9225973.854 ns/op
ArrayListWithLinkedListTestMiddleAdd.addLinkedByMiddle
avgt 5 1064823.250 ± 697306.502 ns/op
可以看到在进行中间插入时LinkedList的平均完成时间比ArrayList平均完成时间快了约7倍
3、测试尾部添加
@Benchmark
public void addArrayByTail(Blackhole blackhole){
int startIndex = maxSize - 1 - operationSize ;
for (int i = startIndex; i < (maxSize - 1); i++) {
arrayList.add(i,i);
}
//为了避免JIT忽略未被使用的结果计算/为了避免死码消除问题
blackhole.consume(arrayList);
}
@Benchmark
public void addLinkedByTail(Blackhole blackhole){
int startIndex = maxSize - 1 - operationSize ;
for (int i = startIndex; i < (maxSize - 1); i++) {
linkedList.add(i,i);
}
//为了避免JIT忽略未被使用的结果计算/为了避免死码消除问题
blackhole.consume(linkedList);
}
测试结果
Benchmark Mode Cnt Score Error Units
ArrayListWithLinkedListTestTailAdd.addArrayByTail avgt
5 6981011.770 ± 10173306.725 ns/op
ArrayListWithLinkedListTestTailAdd.addLinkedByTail avgt
5 2180224.087 ± 913796.230 ns/op
可以看到在进行尾部插入时LinkedList的平均完成时间比ArrayList平均完成时间快了约3倍
4、测试头部查询
@Benchmark
public void searchArrayByFirst(){
for (int i = 0; i < operationSize; i++) {
arrayList.get(i);
}
}
@Benchmark
public void searchLinkedByFirst(){
for (int i = 0; i < operationSize; i++) {
linkedList.get(i);
}
}
测试结果
Benchmark Mode Cnt Score Error Units
ArrayListWithLinkedListTestHeaderSearch.searchArrayByFirst
avgt 5 3.578 ± 0.835 ns/op
ArrayListWithLinkedListTestHeaderSearch.searchLinkedByFirst
avgt 5 4232.832 ± 2019.900 ns/op
5、测试中部查询
@Benchmark
public void searchArrayByMiddle(){
int startIndex = maxSize / 2;
int endIndex = startIndex + operationSize;
for (int i = startIndex; i < endIndex; i++) {
arrayList.get(i);
}
}
@Benchmark
public void searchLinkedByMiddle(){
int startIndex = maxSize / 2;
int endIndex = startIndex + operationSize;
for (int i = startIndex; i < endIndex; i++) {
linkedList.get(i);
}
}
测试结果
Benchmark Mode Cnt Score Error Units
ArrayListWithLinkedListTestMiddleSearch.searchArrayByMiddle
avgt 5 4.969 ± 6.568 ns/op
ArrayListWithLinkedListTestMiddleSearch.searchLinkedByMiddle
avgt 5 1131641.772 ± 313408.389 ns/op
可以看到在进行中部查询时ArrayList的平均完成时间比LinkedList平均完成时间快了约230947倍
6、测试尾部查询
@Benchmark
public void searchArrayByTail(){
for (int i = maxSize - operationSize; i < maxSize; i++) {
arrayList.get(i);
}
}
@Benchmark
public void searchLinkedByTail(){
for (int i = maxSize - operationSize; i < maxSize; i++) {
linkedList.get(i);
}
}
测试结果
Benchmark Mode Cnt Score Error Units
ArrayListWithLinkedListTestTailSearch.searchArrayByTail
avgt 5 5.074 ± 5.384 ns/op
ArrayListWithLinkedListTestTailSearch.searchLinkedByTail
avgt 5 5689.329 ± 563.806 ns/op
可以看到在进行尾部查询时ArrayList的平均完成时间比LinkedList平均完成时间快了约1100倍
7、总结：Java中是否是否链表比数组慢了1000多倍？
可以看到在进行头部查询时ArrayList的平均完成时间比LinkedList平均完成时间快了约1410倍
我们在最后的评测中可以看出，当数据初始化完成之后，我们再进⾏插⼊操作时，尤其是从头部插⼊时，
因为数组要移动之后的所有元素，因此性能要⽐链表低很多；但在查询时性能刚好相反，因为链表要遍历查询，
并且LinkedList 是双向链表，所以在中间查询时性能要⽐数组查询慢了上万倍（查询 100 个元素），
⽽两头查询（⾸部和尾部）时，链表也⽐数组慢了将近 1000 多倍（查询 100 个元素）。