性能优化⼿册 本性能优化⼿册会⼀直更新，包含内容：Java性能优化、JVM性能优化、服务器性能优化、数据库性能优化、 前端性能优化等。 请关注微信公众号「Java中⽂社群」关注最新动态。 链表竟然⽐数组慢了 多倍？(动图+性能评测) 阿⾥巴巴为什么不允许⽇志输出时，使⽤字符串拼接？ try-catch放在循环体内执⾏会很慢？性能评测篇 发现了⼀个阿⾥《Java开发⼿册》的bug！ 驳《阿⾥「Java开发⼿册」中的 个bug》？ 阿⾥巴巴为什么让初始化集合时必须指定集合⼤⼩？ String性能提升的⼏个⼩技巧（源码+原理分析） HashMap 的 种遍历⽅式与性能分析！ if快还是switch快？解密switch背后的秘密 ⽤了这⼀招之后 switch 的性能提升了 倍！ 个⼩技巧让你的 if else看起来更优雅 Java应⽤的GC优化 书写⾼质量SQL的 条建议 MySQL性能优化的最佳 +条经验 阿⾥巴巴关于性能的 条规定！ ⼀份超详细的MySQL⾼性能优化实战总结！ Redis 性能优化的 条军规！ Redis的⾃⽩：我为什么在单线程的这条路上越⾛越远？ 1 链表竟然⽐数组慢了 测) 多倍？(动图+性能评 数组和链表是程序中常⽤的两种数据结构，也是⾯试中常考的⾯试题之⼀。然⽽对于很多⼈来说，只是模 糊的记得⼆者的区别，可能还记得不⼀定对，并且每次到了⾯试的时候，都得把这些的概念拿出来背⼀遍 才⾏，未免有些麻烦。⽽本⽂则会从执⾏过程图以及性能评测等⽅⾯⼊⼿，让你更加深⼊的理解和记忆⼆ 者的区别，有了这次深⼊的学习之后，相信会让你记忆深刻。 数组 在开始（性能评测）之前我们先来回顾⼀下，什么是数组？ 数组的定义如下： 数组（Array）是由相同类型的元素（element）的集合所组成的数据结构，分配⼀块连续的内存来存 储。利⽤元素的索引（index）可以计算出该元素对应的存储地址。 最简单的数据结构类型是⼀维数组。例如，索引为 0 到 9 的 32 位整数数组，可作为在存储器地址 2000，2004，2008，...2036 中，存储 10个 变量，因此索引为 i 的元素即在存储器中的 2000+4×i 地址。数组第⼀个元素的存储器地址称为第⼀地址或基础地址。 简单来说，数组就是由⼀块连续的内存组成的数据结构。这个概念中有⼀个关键词“连续”，它反映了数组 的⼀⼤特点，就是它必须是由⼀个连续的内存组成的。 数组的数据结构，如下图所示： 数组添加的过程，如下图所示： 2 数组的优点 数组的“连续”特征决定了它的访问速度很快，因为它是连续存储的，所以这就决定了它的存储位置就是固 定的，因此它的访问速度就很快。⽐如现在有 10 个房间是按照年龄顺序⼊住的，当我们知道第⼀房⼦住的 是 20 岁的⼈之后，那么我们就知道了第⼆个房⼦是 21 岁的⼈，第五个房⼦是 24 岁的⼈......等等。 数组的缺点 祸兮福所倚，福兮祸所伏。数组的连续性既有优点⼜有缺点，优点上⾯已经说了，⽽缺点它对内存的要求 ⽐较⾼，必须要找到⼀块连续的内存才⾏。 数组的另⼀个缺点就是插⼊和删除的效率⽐较慢，假如我们在数组的⾮尾部插⼊或删除⼀个数据，那么就 要移动之后的所有数据，这就会带来⼀定的性能开销，删除的过程如下图所示： 数组还有⼀个缺点，它的⼤⼩固定，不能动态拓展。 链表 链表是和数组互补的⼀种数据结构，它的定义如下： 链表（Linked list）是⼀种常⻅的基础数据结构，是⼀种线性表，但是并不会按线性的顺序存储数据， ⽽是在每⼀个节点⾥存到下⼀个节点的指针（Pointer）。由于不必须按顺序存储，链表在插⼊的时候可 3 以达到 O(1) 的复杂度，⽐另⼀种线性表顺序表快得多，但是查找⼀个节点或者访问特定编号的节点则 需要 O(n) 的时间，⽽顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。 也就说链表是⼀个⽆需连续内存存储的数据结构，链表的元素有两个属性，⼀个是元素的值，另⼀个是指 针，此指针标记了下⼀个元素的地址。 链表的数据结构，如下图所示： 链表添加的过程，如下图所示： 链表删除的过程，如下图所示： 链表分类 链表主要分为以下⼏类： 单向链表 双向链表 循环链表 4 单向链表 单向链表中包含两个域，⼀个信息域和⼀个指针域。这个链接指向列表中的下⼀个节点，⽽最后⼀个节点 则指向⼀个空值，我们上⾯所展示的链表就是单向链表。 双向链表 双向链表也叫双链表，双向链表中不仅有指向后⼀个节点的指针，还有指向前⼀个节点的指针，这样可以 从任何⼀个节点访问前⼀个节点，当然也可以访问后⼀个节点，以⾄整个链表。 双向链表的结构如下图所示： 循环链表 循环链表中第⼀个节点之前就是最后⼀个节点，反之亦然。循环链表的⽆边界使得在这样的链表上设计算 法会⽐普通链表更加容易。 循环链表的结构如下图所示： 为什么会有单、双链表之分？ 有⼈可能会问，既然已经有单向链表了，那为什么还要双向链表呢？双向链表有什么优势呢？ 这个就要从链表的删除说起了，如果单向链表要删除元素的话，不但要找到删除的节点，还要找到删除节 点的上⼀个节点（通常称之为前驱），因为需要变更上⼀个节点中 next 的指针，但⼜因为它是单向链 表，所以在删除的节点中并没有存储上⼀个节点的相关信息，那么我们就需要再查询⼀遍链表以找到上⼀ 个节点，这样就带来了⼀定的性能问题，所以就有了双向链表。 链表优点 链表的优点⼤致可分为以下三个： 5 1. 链表对内存的利⽤率⽐较⾼，⽆需连续的内存空间，即使有内存碎⽚，也不影响链表的创建； 2. 链表的插⼊和删除的速度很快，⽆需像数组⼀样需要移动⼤量的元素； 3. 链表⼤⼩不固定，可以很⽅便的进⾏动态扩展。 链表缺点 链表的主要缺点是不能随机查找，必须从第⼀个开始遍历，查找效率⽐较低，链表查询的时间复杂度是 O(n)。 性能评测 了解了数组和链表的基础知识之后，接下来我们正式进⼊性能评测环节。 在正式开始之前，我们先来明确⼀下测试⽬标，我们需要测试的点其实只有 6 个： 从头部/中间部分/尾部进⾏添加操作的性能测试； 从头部/中间部分/尾部开始查询的性能测试。 因为添加操作和删除操作在执⾏时间层⾯基本是⼀致的，⽐如数组添加需要移动后⾯的元素，删除也同样 是移动后⾯的元素；⽽链表也是如此，添加和删除都是改变⾃身和相连节点的信息，因此我们就把添加和 删除的测试合⼆为⼀，⽤添加操作来进⾏测试。 测试说明： 1. 在 Java 语⾔中，数组的代表为 ArrayList ，⽽链表的代表为 LinkedList ，因此我们就⽤这两 个对象来进⾏测试； 2. 本⽂我们将使⽤ Oracle 官⽅推荐 JMH 框架来进⾏测试，点击查看更多关于 JMH 的内容； 3. 本⽂测试环境是 JDK 1.8、MacMini、Idea 2020.1。 1.头部添加性能测试 1 import org.openjdk.jmh.annotations.*; 2 import org.openjdk.jmh.infra.Blackhole; 3 import org.openjdk.jmh.runner.Runner; 4 import org.openjdk.jmh.runner.RunnerException; 5 import org.openjdk.jmh.runner.options.Options; 6 import org.openjdk.jmh.runner.options.OptionsBuilder; 7 8 import java.util.ArrayList; 9 import java.util.LinkedList; 10 import java.util.concurrent.TimeUnit; 11 6 12 @BenchmarkMode(Mode.AverageTime) // 测试完成时间 13 @OutputTimeUnit(TimeUnit.NANOSECONDS) 14 @Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // 热次数和时间 预 15 @Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS) // 测试次数和时间 16 @Fork(1) // fork 1 个线程 17 @State(Scope.Thread) 18 public class ArrayOptimizeTest { 19 测试循环次数 100; // 操作次数 20 private static final int maxSize = 1000; // 21 private static final int operationSize = 22 23 24 private static ArrayList<Integer> arrayList; 25 private static LinkedList<Integer> linkedList; 26 27 public static void main(String[] args) throws RunnerException { 启动基准测试 28 // 29 Options opt = new OptionsBuilder() 30 .include(ArrayOptimizeTest.class.getSimpleName()) // 要导⼊的测试类 31 .build(); 32 new Runner(opt).run(); // 33 执⾏测试 } 34 35 @Setup 36 public void init() { 启动执⾏事件 37 // 38 arrayList = new ArrayList<Integer>(); 39 linkedList = new LinkedList<Integer>(); 40 for (int i = 0; i < maxSize; i++) { 41 arrayList.add(i); 42 linkedList.add(i); 43 44 } } 45 46 @Benchmark 47 public void addArrayByFirst(Blackhole blackhole) { 48 for (int i = 0; i < +operationSize; i++) { 7 49 arrayList.add(i, i)