SegmentFault 最新的文章

中小型前端团队代码规范工程化最佳实践 - ESLint
JDK/Dubbo/Spring 三种 SPI 机制，谁更好？
【2w字干货】ArrayList与LinkedList的区别以及JDK11中的底层实现
面试官一个线程池问题把我问懵逼了。

中小型前端团队代码规范工程化最佳实践 - ESLint

Posted: 12 Apr 2021 07:14 PM PDT

前言

There are a thousand Hamlets in a thousand people's eyes.

一千个程序员，就有一千种代码风格。在前端开发中，有几个至今还在争论的代码风格差异：

单引号还是双引号？
代码行结束是否需要分号？
两个空格还是四个空格？
...

这几个代码风格差异在协同开发中经常会被互相吐槽，甚至不能忍受。

除此之外，由于 JavaScript 的灵活性，往往一段代码能有多种写法，这时候也会导致协同时差异。并且，有一些写法可能会导致不易发现的 bug，或者这些写法的性能不好，开发时也应该避免。

为了解决这类静态代码问题，每个团队都需要一个统一的 JavaScript 代码规范，团队成员都遵守这份代码规范来编写代码。当然，靠人来保障代码规范是不可靠的，需要有对应的工具来保障，ESLint 就是这个工具。

有的读者看到这里，可能会说：Prettier 也可以保证代码风格一致。是的，Prettier 确实可以按照设置的规则对代码进行统一格式化，后面的文章也会有对应的介绍。但是需要明确的一点是，Prettier 只会在格式上对代码进行格式化，一些隐藏的代码质量问题 Prettier 是无法发现的，而 ESLint 可以。

关于 ESLint

关于 ESLint，它的 Slogan 是 Find and fix problems in your JavaScript code。如上文所说，它可以发现并修复你 JavaScript 代码中的问题。来看一下官网上描述 ESLint 具备的三个特性：

Find Problems。ESLint 通过静态代码分析可以快速发现代码中的问题。ESLint 可以运行在大多数文本编辑器中，并且也可以在工作流中接入 ESLint
Fix Automatically。ESLint 发现的很多问题都可以自动修复
Customize。可以定制 ESLint 检查规则

基于以上描述，我们在前端工程化中可以这样使用 ESLint：

基于业界现有的 ESLint 规范和团队代码习惯定制一套统一的 ESLint 代码规则
将统一代码规则封装成 ESLint 规则包接入
将 ESLint 接入脚手架、编辑器以及研发工作流中

快速上手

先简单介绍一下如何使用 ESLint，如果已经有所了解的同学，可以直接跳过这一节。

新建一个包含 package.json 的目录（可以在空目录下执行 npm init -y），新建一个 index.js：

// index.js const name = 'axuebin'

安装 eslint ：

npm install eslint --save-dev

然后执行 ./node_modules/.bin/eslint --init 或者 npx eslint --init 生成一个 ESLint 配置文件 .eslintc.js：

module.exports = {   env: {     es2021: true,   },   extends: 'eslint:recommended',   parserOptions: {     ecmaVersion: 12,   },   rules: {}, };

生成好配置文件之后，就可以执行 ./node_modules/.bin/eslint index.js 或者 npx eslint index.js 命令对文件进行检查。结果如下：

index.js 中的代码命中了 no-unused-vars 这个规则，默认情况下，这个规则是会报 error 的，也就是 ESLint 不允许代码中出现未被使用的变量。这是一个好习惯，有利于代码的维护。

简单配置

我们来尝试配置 ESLint 的检查规则。以分号和引号举例，现在你作为团队代码规范的指定人，希望团队成员开发的代码，都是单引号和带分号的。

打开 .eslintrc.js 配置文件，在 rules 中添加相关配置项：

module.exports = {   env: {     es2021: true,   },   extends: 'eslint:recommended',   parserOptions: {     ecmaVersion: 12,   },   rules: {     semi: ['error', 'always'],     quotes: ['error', 'single'],   }, };

然后我们将 index.js 中的代码改成：

// index.js const name = "axuebin"

执行 eslint 命令之后：

可以看到检查结果如下：

[no-unused-vars] 'name' is assigned a value but never used。定义了 name 变量却未使用。
[quotes] Strings must use singlequote。字符串必须使用单引号。
[semi] Missing semicolon。缺失分号。

老老实实地按照规范修改代码，使用单引号并将加上分号。当然，如果你们希望是双引号和不带分号，修改相应的配置即可。

具体各个规则如何配置可以查看：https://eslint.org/docs/rules

自动修复

执行 eslint xxx --fix 可以自动修复一些代码中的问题，将无法自动修复的问题暴露出来。比如上文中提到的引号和分号的问题，就可以通过 --fix 自动修复，而 no-unused-vars 变量未使用的问题，ESLint 就无法自动修复。

使用配置包

在 init 生成的配置文件中，我们看到包含这一行代码：

module.exports = {   extends: "eslint:recommended" }

这一行代码的意思是，使用 ESLint 的推荐配置。 extends: 'xxx' 就是继承，当前的配置继承于 xxx 的配置，在此基础上进行扩展。

因此，我们也可以使用任意封装好的配置，可以在 NPM 上或者 GItHub 上搜索 eslint-config 关键词获取，本文我们将这类封装好的配置称作 "配置集"。比较常见的配置包有以下几个：

eslint-config-airbnb: Airbnb 公司提供的配置集
eslint-config-prettier: 使用这个配置集，会关闭一些可能与 Prettier 冲突的规则
eslint-config-react: create react app 使用的配置集
eslint-config-vue: vuejs 使用的配置集
...

最佳实践

简单了解完 ESLint 之后，对于 ESLint 的更多使用细节以及原理，在本篇文章就不展开了，感兴趣的朋友可以在官网详细了解。本文重点还是在于如何在团队工程化体系中落地 ESLint，这里提几个最佳实践。

抽象配置集

对于独立开发者以及业务场景比较简单的小型团队而言，使用现成、完备的第三方配置集是非常高效的，可以较低成本低接入 ESLint 代码检查。

但是，对于中大型团队而言，在实际代码规范落地的过程中我们会发现，不可能存在一个能够完全符合团队风格的三方配置包，我们还是会在 extends 三方配置集的基础上，再手动在 rules 配置里加一些自定义的规则。时间长了，有可能 A 应用和 B 应用里的 rules 就不一样了，就很难达到统一的目的。

这时候，就需要一个中心化的方式来管理配置包：根据团队代码风格整理（或者基于现有的三方配置集）发布一个配置集，团队统一使用这个包，就可以做到中心化管理和更新。

除此之外，从技术层面考虑，目前一个前端团队的面对的场景可能比较复杂。比如：

技术选型不一致：框架上 PC 使用 React，H5 使用 Vue；是否使用 TypeScript
跨端场景多：Web 端和小程序端，还有 Node
...

以上问题在真实开发中都是存在的，所以在代码规范的工程化方案落地时，一个单一功能的配置集是不够用的，这时候还需要考虑这个配置集如何抽象。

为了解决以上问题，这里提供一种解决方案的思路：

具体拆解来看，就是有一个类似 eslint-config-standard 的基础规则集（包括代码风格、变量相关、ES6 语法等），在此基础之上集成社区的一些插件（Vue/React）等，封装成统一的一个 NPM Package 发布，消费时根据当前应用类型通过不同路径来 extends 对应的配置集。

这里有一个 Demo，感兴趣的朋友可以看一下：eslint-config-axuebin

开发插件

ESLint 提供了丰富的配置供开发者选择，但是在复杂的业务场景和特定的技术栈下，这些通用规则是不够用的。ESLint 通过插件的形式赋予了扩展性，开发者可以自定义任意的检查规则，比如 eslint-plugin-vue / eslint-plugin-react 就是 Vue / React 框架中使用的扩展插件，官网也提供了相关文档引导开发者开发一个插件。

一般来说，我们也不需要开发插件，但我们至少需要了解有这么个东西。在做一些团队代码质量检查的时候，我们可能会有一些特殊的业务逻辑，这时候 ESLint 插件是可以帮助我们做一些事情。

这里就不展开了，主要就是一些 AST 的用法，照着官方文档就可以上手，或者可以参考现有的一些插件写法。

脚手架 / CLI 工具

当有了团队的统一 ESLint 配置集和插件之后，我们会将它们集成到脚手架中，方便新项目集成和开箱即用。但是对于一些老项目，如果需要手动改造还是会有一些麻烦的，这时候就可以借助于 CLI 来完成一键升级。

本文结合上文的 Demo eslint-config-axuebin，设计一个简单的 CLI Demo。由于当前配置也比较简单，所以 CLI 只需要做几件简单的事情即可：

询问用户当前项目的类型（是 JavaScript 还是 TypeScript、是 React 还是 Vue）
根据项目类型写 .eslintrc.js 文件
根据项目类型安装所需依赖（比如 vue 需要 eslint-plugin-vue）
在 package.json 的 scripts 中写入 "lint": "eslint src test --fix"

核心代码如下：

const path = require('path'); const fs = require('fs'); const chalk = require('chalk'); const spawn = require('cross-spawn');  const { askForLanguage, askForFrame } = require('./ask'); const { eslintrcConfig, needDeps } = require('./config');  module.exports = async () => {   const language = await askForLanguage();   const frame = await askForFrame();    let type = language;   if (frame) {     type += `/${frame}`;   }    fs.writeFileSync(     path.join(process.cwd(), '.eslintrc.js'),     `// Documentation\n// https://github.com/axuebin/eslint-config-axuebin\nmodule.exports = ${JSON.stringify(       eslintrcConfig(type),       null,       2     )}`   );    const deps = needDeps.javascript;   if (language === 'typescript') {     deps.concat(needDeps.typescript);   }   if (frame) {     deps.concat(needDeps[frame]);   }    spawn.sync('npm', ['install', ...deps, '--save'], { stdio: 'inherit' }); };

可运行的 CLI Demo 代码见：axb-lint，在项目目录下执行：axblint eslint 即可，如图：

自动化

配置了 ESLint 之后，我们需要让开发者感知到 ESLint 的约束。开发者可以自己运行 eslint 命令来跑代码检查，这不够高效，所以我们需要一些自动化手段来做这个事情。当然在开发时，编辑器也有提供相应的功能可以根据当前工作区下的 ESLint 配置文件来检查当前正在编辑的文件，这个不是我们关心的重点。

一般我们会在有以下几种方式做 ESLint 检查：

开发时：依赖编辑器的能力
手动运行：在终端中手动执行 eslint 命令
pre-commit：在提交 git 前自动执行 eslint 命令
ci：依赖 git 的持续集成，可以将检查结果输出文件上传到服务器

这里提一下 pre-commit 的方案，在每一次本地开发完成提交代码前就做 ESLint 检查，保证云端的代码是统一规范的。

这种方式非常简单，只需要在项目中依赖 husky 和 lint-staged 即可完成。安装好依赖之后，在 package.json 文件加入以下配置即可：

{   "lint-staged": {     "*.{js,jsx,ts,tsx}": "eslint --cache --fix"   },   "husky": {     "hooks": {       "pre-commit": "lint-staged"     }   } }

效果如图所示：

如果代码跑 ESLint 检查抛了 Error 错误，则会中断 commit 流程：

这样就可以确保提交到 GitHub 仓库上的代码是统一规范的。（当然，如果认为将这些配置文件都删了，那也是没办法的）

总结

本文介绍了 ESLint 在中小型前端团队的一些最佳实践的想法，大家可以在此基础上扩展，制订一套完善的 ESLint 工作流，落地到自己团队中。

本文是前端代码规范系列文章的其中一篇，后续还有关于 StyleLint/CommitLint/Prettier 等的文章，并且还有一篇完整的关于前端代码规范工程化实践的文章，敬请期待（~~也有可能就鸽了~~）。

更多原创文章欢迎关注公众号「玩相机的程序员」，或者加我微信 xb9207 交流

JDK/Dubbo/Spring 三种 SPI 机制，谁更好？

Posted: 12 Apr 2021 05:50 PM PDT

先点赞再看，养成好习惯

SPI 全称为 Service Provider Interface，是一种服务发现机制。SPI 的本质是将接口实现类的全限定名配置在文件中，并由服务加载器读取配置文件，加载实现类。这样可以在运行时，动态为接口替换实现类。正因此特性，我们可以很容易的通过 SPI 机制为我们的程序提供拓展功能。

本文主要是特性 & 用法介绍，不涉及源码解析（源码都很简单，相信你一定一看就懂）

SPI 有什么用？

举个栗子，现在我们设计了一款全新的日志框架：super-logger。默认以XML文件作为我们这款日志的配置文件，并设计了一个配置文件解析的接口：

package com.github.kongwu.spisamples;  public interface SuperLoggerConfiguration {     void configure(String configFile); }

然后来一个默认的XML实现：

package com.github.kongwu.spisamples;  public class XMLConfiguration implements SuperLoggerConfiguration{     public void configure(String configFile){         ......     } }

那么我们在初始化，解析配置时，只需要调用这个XMLConfiguration来解析XML配置文件即可。

package com.github.kongwu.spisamples;  public class LoggerFactory {     static {         SuperLoggerConfiguration configuration = new XMLConfiguration();         configuration.configure(configFile);     }          public static getLogger(Class clazz){         ......     } }

这样就完成了一个基础的模型，看起来也没什么问题。不过扩展性不太好，因为如果想定制/扩展/重写解析功能的话，我还得重新定义入口的代码，LoggerFactory 也得重写，不够灵活，侵入性太强了。

比如现在用户/使用方想增加一个 yml 文件的方式，作为日志配置文件，那么只需要新建一个YAMLConfiguration，实现 SuperLoggerConfiguration 就可以。但是……怎么注入呢，怎么让 LoggerFactory中使用新建的这个 YAMLConfiguration ？难不成连 LoggerFactory 也重写了？

如果借助SPI机制的话，这个事情就很简单了，可以很方便的完成这个入口的扩展功能。

下面就先来看看，利用JDK 的 SPI 机制怎么解决上面的扩展性问题。

JDK SPI

JDK 中提供了一个 SPI 的功能，核心类是 java.util.ServiceLoader。其作用就是，可以通过类名获取在"META-INF/services/"下的多个配置实现文件。

为了解决上面的扩展问题，现在我们在META-INF/services/下创建一个com.github.kongwu.spisamples.SuperLoggerConfiguration文件（没有后缀）。文件中只有一行代码，那就是我们默认的com.github.kongwu.spisamples.XMLConfiguration（注意，一个文件里也可以写多个实现，回车分隔）

META-INF/services/com.github.kongwu.spisamples.SuperLoggerConfiguration:  com.github.kongwu.spisamples.XMLConfiguration

然后通过 ServiceLoader 获取我们的 SPI 机制配置的实现类：

ServiceLoader<SuperLoggerConfiguration> serviceLoader = ServiceLoader.load(SuperLoggerConfiguration.class); Iterator<SuperLoggerConfiguration> iterator = serviceLoader.iterator(); SuperLoggerConfiguration configuration;  while(iterator.hasNext()) {     //加载并初始化实现类     configuration = iterator.next(); }  //对最后一个configuration类调用configure方法 configuration.configure(configFile);

最后在调整LoggerFactory中初始化配置的方式为现在的SPI方式：

package com.github.kongwu.spisamples;  public class LoggerFactory {     static {         ServiceLoader<SuperLoggerConfiguration> serviceLoader = ServiceLoader.load(SuperLoggerConfiguration.class);         Iterator<SuperLoggerConfiguration> iterator = serviceLoader.iterator();         SuperLoggerConfiguration configuration;          while(iterator.hasNext()) {             configuration = iterator.next();//加载并初始化实现类         }         configuration.configure(configFile);     }          public static getLogger(Class clazz){         ......     } }

等等，这里为什么是用 iterator ? 而不是get之类的只获取一个实例的方法？

试想一下，如果是一个固定的get方法，那么get到的是一个固定的实例，SPI 还有什么意义呢？

SPI 的目的，就是增强扩展性。将固定的配置提取出来，通过 SPI 机制来配置。那既然如此，一般都会有一个默认的配置，然后通过 SPI 的文件配置不同的实现，这样就会存在一个接口多个实现的问题。要是找到多个实现的话，用哪个实现作为最后的实例呢？

所以这里使用iterator来获取所有的实现类配置。刚才已经在我们这个 super-logger 包里增加了默认的SuperLoggerConfiguration 实现。

为了支持 YAML 配置，现在在使用方/用户的代码里，增加一个YAMLConfiguration的 SPI 配置：

META-INF/services/com.github.kongwu.spisamples.SuperLoggerConfiguration:  com.github.kongwu.spisamples.ext.YAMLConfiguration

此时通过iterator方法，就会获取到默认的XMLConfiguration和我们扩展的这个YAMLConfiguration两个配置实现类了。

在上面那段加载的代码里，我们遍历iterator，遍历到最后，我们**使用最后一个实现配置作为最终的实例。

再等等？最后一个？怎么算最后一个？

使用方/用户自定义的的这个 YAMLConfiguration 一定是最后一个吗？

这个真的不一定，取决于我们运行时的 ClassPath 配置，在前面加载的jar自然在前，最后的jar里的自然当然也在后面。所以如果用户的包在ClassPath中的顺序比super-logger的包更靠后，才会处于最后一个位置；如果用户的包位置在前，那么所谓的最后一个仍然是默认的XMLConfiguration。

举个栗子，如果我们程序的启动脚本为：

java -cp super-logger.jar:a.jar:b.jar:main.jar example.Main

默认的XMLConfiguration SPI配置在super-logger.jar，扩展的YAMLConfiguration SPI配置文件在main.jar，那么iterator获取的最后一个元素一定为YAMLConfiguration。

但这个classpath顺序如果反了呢？main.jar 在前，super-logger.jar 在后

java -cp main.jar:super-logger.jar:a.jar:b.jar example.Main

这样一来，iterator 获取的最后一个元素又变成了默认的XMLConfiguration，我们使用 JDK SPI 没啥意义了，获取的又是第一个，还是默认的XMLConfiguration。

由于这个加载顺序（classpath）是由用户指定的，所以无论我们加载第一个还是最后一个，都有可能会导致加载不到用户自定义的那个配置。

所以这也是JDK SPI机制的一个劣势，无法确认具体加载哪一个实现，也无法加载某个指定的实现，仅靠ClassPath的顺序是一个非常不严谨的方式

Dubbo SPI

Dubbo 就是通过 SPI 机制加载所有的组件。不过，Dubbo 并未使用 Java 原生的 SPI 机制，而是对其进行了增强，使其能够更好的满足需求。在 Dubbo 中，SPI 是一个非常重要的模块。基于 SPI，我们可以很容易的对 Dubbo 进行拓展。如果大家想要学习 Dubbo 的源码，SPI 机制务必弄懂。接下来，我们先来了解一下 Java SPI 与 Dubbo SPI 的用法，然后再来分析 Dubbo SPI 的源码。

Dubbo 中实现了一套新的 SPI 机制，功能更强大，也更复杂一些。相关逻辑被封装在了 ExtensionLoader 类中，通过 ExtensionLoader，我们可以加载指定的实现类。Dubbo SPI 所需的配置文件需放置在 META-INF/dubbo 路径下，配置内容如下（以下demo来自dubbo官方文档）。

optimusPrime = org.apache.spi.OptimusPrime bumblebee = org.apache.spi.Bumblebee

与 Java SPI 实现类配置不同，Dubbo SPI 是通过键值对的方式进行配置，这样我们可以按需加载指定的实现类。另外在使用时还需要在接口上标注 @SPI 注解。下面来演示 Dubbo SPI 的用法：

@SPI public interface Robot {     void sayHello(); }  public class OptimusPrime implements Robot {          @Override     public void sayHello() {         System.out.println("Hello, I am Optimus Prime.");     } }  public class Bumblebee implements Robot {      @Override     public void sayHello() {         System.out.println("Hello, I am Bumblebee.");     } }   public class DubboSPITest {      @Test     public void sayHello() throws Exception {         ExtensionLoader<Robot> extensionLoader =              ExtensionLoader.getExtensionLoader(Robot.class);         Robot optimusPrime = extensionLoader.getExtension("optimusPrime");         optimusPrime.sayHello();         Robot bumblebee = extensionLoader.getExtension("bumblebee");         bumblebee.sayHello();     } }

Dubbo SPI 和 JDK SPI 最大的区别就在于支持"别名"，可以通过某个扩展点的别名来获取固定的扩展点。就像上面的例子中，我可以获取 Robot 多个 SPI 实现中别名为"optimusPrime"的实现，也可以获取别名为"bumblebee"的实现，这个功能非常有用！

通过 @SPI 注解的 value 属性，还可以默认一个"别名"的实现。比如在Dubbo 中，默认的是Dubbo 私有协议：dubbo protocol - dubbo://
**
来看看Dubbo中协议的接口：

@SPI("dubbo") public interface Protocol {     ...... }

在 Protocol 接口上，增加了一个 @SPI 注解，而注解的 value 值为 Dubbo ，通过 SPI 获取实现时就会获取 Protocol SPI 配置中别名为dubbo的那个实现，com.alibaba.dubbo.rpc.Protocol文件如下：

filter=com.alibaba.dubbo.rpc.protocol.ProtocolFilterWrapper listener=com.alibaba.dubbo.rpc.protocol.ProtocolListenerWrapper mock=com.alibaba.dubbo.rpc.support.MockProtocol   dubbo=com.alibaba.dubbo.rpc.protocol.dubbo.DubboProtocol   injvm=com.alibaba.dubbo.rpc.protocol.injvm.InjvmProtocol rmi=com.alibaba.dubbo.rpc.protocol.rmi.RmiProtocol hessian=com.alibaba.dubbo.rpc.protocol.hessian.HessianProtocol com.alibaba.dubbo.rpc.protocol.http.HttpProtocol com.alibaba.dubbo.rpc.protocol.webservice.WebServiceProtocol thrift=com.alibaba.dubbo.rpc.protocol.thrift.ThriftProtocol memcached=com.alibaba.dubbo.rpc.protocol.memcached.MemcachedProtocol redis=com.alibaba.dubbo.rpc.protocol.redis.RedisProtocol rest=com.alibaba.dubbo.rpc.protocol.rest.RestProtocol registry=com.alibaba.dubbo.registry.integration.RegistryProtocol qos=com.alibaba.dubbo.qos.protocol.QosProtocolWrapper

然后只需要通过getDefaultExtension，就可以获取到 @SPI 注解上value对应的那个扩展实现了

Protocol protocol = ExtensionLoader.getExtensionLoader(Protocol.class).getDefaultExtension(); //protocol: DubboProtocol

还有一个 Adaptive 的机制，虽然非常灵活，但……用法并不是很"优雅"，这里就不介绍了

Dubbo 的 SPI 中还有一个"加载优先级"，优先加载内置（internal）的，然后加载外部的（external），按优先级顺序加载，如果遇到重复就跳过不会加载了。

所以如果想靠classpath加载顺序去覆盖内置的扩展，也是个不太理智的做法，原因同上 - 加载顺序不严谨

Spring SPI

Spring 的 SPI 配置文件是一个固定的文件 - META-INF/spring.factories，功能上和 JDK 的类似，每个接口可以有多个扩展实现，使用起来非常简单：

//获取所有factories文件中配置的LoggingSystemFactory List<LoggingSystemFactory>> factories =      SpringFactoriesLoader.loadFactories(LoggingSystemFactory.class, classLoader);

下面是一段 Spring Boot 中 spring.factories 的配置

# Logging Systems org.springframework.boot.logging.LoggingSystemFactory=\ org.springframework.boot.logging.logback.LogbackLoggingSystem.Factory,\ org.springframework.boot.logging.log4j2.Log4J2LoggingSystem.Factory,\ org.springframework.boot.logging.java.JavaLoggingSystem.Factory  # PropertySource Loaders org.springframework.boot.env.PropertySourceLoader=\ org.springframework.boot.env.PropertiesPropertySourceLoader,\ org.springframework.boot.env.YamlPropertySourceLoader  # ConfigData Location Resolvers org.springframework.boot.context.config.ConfigDataLocationResolver=\ org.springframework.boot.context.config.ConfigTreeConfigDataLocationResolver,\ org.springframework.boot.context.config.StandardConfigDataLocationResolver  ......

Spring SPI 中，将所有的配置放到一个固定的文件中，省去了配置一大堆文件的麻烦。至于多个接口的扩展配置，是用一个文件好，还是每个单独一个文件好这个，这个问题就见仁见智了（个人喜欢 Spring 这种，干净利落）。

Spring的SPI 虽然属于spring-framework(core)，但是目前主要用在spring boot中……

和前面两种 SPI 机制一样，Spring 也是支持 ClassPath 中存在多个 spring.factories 文件的，加载时会按照 classpath 的顺序依次加载这些 spring.factories 文件，添加到一个 ArrayList 中。由于没有别名，所以也没有去重的概念，有多少就添加多少。

但由于 Spring 的 SPI 主要用在 Spring Boot 中，而 Spring Boot 中的 ClassLoader 会优先加载项目中的文件，而不是依赖包中的文件。所以如果在你的项目中定义个spring.factories文件，那么你项目中的文件会被第一个加载，得到的Factories中，项目中spring.factories里配置的那个实现类也会排在第一个

如果我们要扩展某个接口的话，只需要在你的项目（spring boot）里新建一个META-INF/spring.factories文件，只添加你要的那个配置，不要完整的复制一遍 Spring Boot 的 spring.factories 文件然后修改
**
比如我只想添加一个新的 LoggingSystemFactory 实现，那么我只需要新建一个META-INF/spring.factories文件，而不是完整的复制+修改：

org.springframework.boot.logging.LoggingSystemFactory=\ com.example.log4j2demo.Log4J2LoggingSystem.Factory

对比

	JDK SPI	DUBBO SPI	Spring SPI
文件方式	每个扩展点单独一个文件	每个扩展点单独一个文件	所有的扩展点在一个文件
获取某个固定的实现	不支持，只能按顺序获取所有实现	有"别名"的概念，可以通过名称获取扩展点的某个固定实现，配合Dubbo SPI的注解很方便	不支持，只能按顺序获取所有实现。但由于Spring Boot ClassLoader会优先加载用户代码中的文件，所以可以保证用户自定义的spring.factoires文件在第一个，通过获取第一个factory的方式就可以固定获取自定义的扩展
其他	无	支持Dubbo内部的依赖注入，通过目录来区分Dubbo 内置SPI和外部SPI，优先加载内部，保证内部的优先级最高	无
文档完整度	文章 & 三方资料足够丰富	文档 & 三方资料足够丰富	文档不够丰富，但由于功能少，使用非常简单
IDE支持	无	无	IDEA 完美支持，有语法提示

三种 SPI 机制对比之下，JDK 内置的机制是最弱鸡的，但是由于是 JDK 内置，所以还是有一定应用场景，毕竟不用额外的依赖；Dubbo 的功能最丰富，但机制有点复杂了，而且只能配合 Dubbo 使用，不能完全算是一个独立的模块；Spring 的功能和JDK的相差无几，最大的区别是所有扩展点写在一个 spring.factories 文件中，也算是一个改进，并且 IDEA 完美支持语法提示。

各位看官们大佬们，你们觉得 JDK/Dubbo/Spring 三种 SPI 的机制，哪个更好呢？欢迎评论区留言

参考

原创不易，未经授权禁止转载。如果我的文章对您有帮助，请点赞/收藏/关注鼓励支持一下吧❤❤❤❤❤❤

【2w字干货】ArrayList与LinkedList的区别以及JDK11中的底层实现

Posted: 12 Apr 2021 01:10 AM PDT

1 概述

本文主要讲述了ArrayList与LinkedList的相同以及不同之处，以及两者的底层实现（环境OpenJDK 11.0.10）。

2 两者区别

在详细介绍两者的底层实现之前，先来简单看一下两者的异同。

2.1 相同点

两者都实现了List接口，都继承了AbstractList（LinkedList间接继承，ArrayList直接继承）
都是线程不安全的
都具有增删查改方法

2.2 不同点

底层数据结构不同：ArrayList基于Object[]数组，LinkedList基于LinkedList.Node双向链表
随机访问效率不同：ArrayList随机访问能做到O(1)，因为可以直接通过下标找到元素，而LinkedList需要从头指针开始遍历，时间O(n)
初始化操作不同：ArrayList初始化时需要指定一个初始化容量（默认为10），而LinkedList不需要
扩容：ArrayList当长度不足以容纳新元素的时候，会进行扩容，而LinkedList不会

3 `ArrayList`底层

3.1 基本结构

底层使用Object[]数组实现，成员变量如下：

private static final long serialVersionUID = 8683452581122892189L; private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = new Object[0]; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0]; transient Object[] elementData; private int size; private static final int MAX_ARRAY_SIZE = 2147483639;

默认的初始化容量为10，接下来是两个空数组，供默认构造方法以及带初始化容量的构造方法使用：

public ArrayList(int initialCapacity) {     if (initialCapacity > 0) {         this.elementData = new Object[initialCapacity];     } else {         if (initialCapacity != 0) {             throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);         }          this.elementData = EMPTY_ELEMENTDATA;     } }  public ArrayList() {     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

下面再来看一些重要方法，包括：

add()
remove()
indexOf()/lastIndexOf()/contains()

3.2 `add()`

add()方法有四个：

add(E e)
add(int index,E e)
addAll(Collection<? extends E> c)
addAll(int index, Collection<? extends E> c

3.2.1 单一元素`add()`

先来看一下add(E e)以及add(int index,E eelment)：

private void add(E e, Object[] elementData, int s) {     if (s == elementData.length) {         elementData = this.grow();     }      elementData[s] = e;     this.size = s + 1; }  public boolean add(E e) {     ++this.modCount;     this.add(e, this.elementData, this.size);     return true; }  public void add(int index, E element) {     this.rangeCheckForAdd(index);     ++this.modCount;     int s;     Object[] elementData;     if ((s = this.size) == (elementData = this.elementData).length) {         elementData = this.grow();     }      System.arraycopy(elementData, index, elementData, index + 1, s - index);     elementData[index] = element;     this.size = s + 1; }

add(E e)实际调用的是一个私有方法，判断是否需要扩容之后，直接添加到末尾。而add(int index,E element)会首先检查下标是否合法，合法的话，再判断是否需要扩容，之后调用System.arraycopy对数组进行复制，最后进行赋值并将长度加1。

关于System.arraycopy，官方文档如下：

在这里插入图片描述

一共有5个参数：

第一个参数：原数组
第二个参数：原数组需要开始复制的位置
第三个参数：目标数组
第四个参数：复制到目标数组的开始位置
第五个参数：需要复制的数目

也就是说：

System.arraycopy(elementData, index, elementData, index + 1, s - index);

的作用是将原数组在index后面的元素"往后挪"，空出一个位置让index进行插入。

3.2.2 `addAll()`

下面来看一下两个addAll()：

public boolean addAll(Collection<? extends E> c) {     Object[] a = c.toArray();     ++this.modCount;     int numNew = a.length;     if (numNew == 0) {         return false;     } else {         Object[] elementData;         int s;         if (numNew > (elementData = this.elementData).length - (s = this.size)) {             elementData = this.grow(s + numNew);         }          System.arraycopy(a, 0, elementData, s, numNew);         this.size = s + numNew;         return true;     } }  public boolean addAll(int index, Collection<? extends E> c) {     this.rangeCheckForAdd(index);     Object[] a = c.toArray();     ++this.modCount;     int numNew = a.length;     if (numNew == 0) {         return false;     } else {         Object[] elementData;         int s;         if (numNew > (elementData = this.elementData).length - (s = this.size)) {             elementData = this.grow(s + numNew);         }          int numMoved = s - index;         if (numMoved > 0) {             System.arraycopy(elementData, index, elementData, index + numNew, numMoved);         }          System.arraycopy(a, 0, elementData, index, numNew);         this.size = s + numNew;         return true;     } }

在第一个addAll中，首先判断是否需要扩容，接着也是直接调用目标集合添加到尾部。而在第二个addAll中，由于多了一个下标参数，处理步骤稍微多了一点：

首先判断下标是否合法
接着判断是否需要扩容
再计算是否需要把原来的数组元素"往后挪"，也就是if里面的System.arraycopy
最后把目标数组复制到指定的index位置

3.2.3 扩容

上面的add()方法都涉及到了扩容，也就是grow方法，下面来看一下：

private Object[] grow(int minCapacity) {     return this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity)); }  private Object[] grow() {     return this.grow(this.size + 1); }  private int newCapacity(int minCapacity) {     int oldCapacity = this.elementData.length;     int newCapacity = oldCapacity + (oldCapacity >> 1);     if (newCapacity - minCapacity <= 0) {         if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {             return Math.max(10, minCapacity);         } else if (minCapacity < 0) {             throw new OutOfMemoryError();         } else {             return minCapacity;         }     } else {         return newCapacity - 2147483639 <= 0 ? newCapacity : hugeCapacity(minCapacity);     } }  private static int hugeCapacity(int minCapacity) {     if (minCapacity < 0) {         throw new OutOfMemoryError();     } else {         return minCapacity > 2147483639 ? 2147483647 : 2147483639;     } }

grow()首先通过newCapacity计算需要扩容的容量，接着调用Arrays.copyOf将旧元素复制过去，并将返回值覆盖到原来的数组。而在newCapacity中，有两个变量：

newCapacity：新的容量，默认是旧容量的1.5倍，也就是默认扩容1.5倍
minCapacity：最低需要的容量

如果最低容量大于等于新容量，则是如下情况之一：

通过默认构造初始化的数组：返回minCapacity与10的最大值
溢出：直接抛OOM
否则返回最小容量值

如果不是，则判断新容量是否达到最大值（这里有点好奇为什么不用MAX_ARRAY_SIZE，猜测是反编译的问题），如果没有到达最大值，则返回新容量，如果到达了最大值，调用hugeCapacity。

hugeCapacity同样会首先判断最小容量是否小于0，小于则抛OOM，否则将其与最大值（MAX_ARRAY_SIZE）判断，如果大于返回Integer.MAX_VALUE，否则返回MAX_ARRAY_SIZE。

3.3 `remove()`

remove()包含四个方法：

remove(int index)
remove(Object o)
removeAll()
removeIf()

3.3.1 单一元素`remove()`

也就是remove(int index)以及remove(Object o)：

public E remove(int index) {     Objects.checkIndex(index, this.size);     Object[] es = this.elementData;     E oldValue = es[index];     this.fastRemove(es, index);     return oldValue; }  public boolean remove(Object o) {     Object[] es = this.elementData;     int size = this.size;     int i = 0;     if (o == null) {         while(true) {             if (i >= size) {                 return false;             }              if (es[i] == null) {                 break;             }              ++i;         }     } else {         while(true) {             if (i >= size) {                 return false;             }              if (o.equals(es[i])) {                 break;             }              ++i;         }     }      this.fastRemove(es, i);     return true; }

其中remove(int index)的逻辑比较简单，先检查下标合法性，然后保存需要remove的值，并调用fastRemove()进行移除，而在remove(Object o)中，直接对数组进行遍历，并判断是否存在对应的元素，如果不存在直接返回false，如果存在，调用fastRemove()，并返回true。

下面看一下fastRemove()：

private void fastRemove(Object[] es, int i) {     ++this.modCount;     int newSize;     if ((newSize = this.size - 1) > i) {         System.arraycopy(es, i + 1, es, i, newSize - i);     }      es[this.size = newSize] = null; }

首先修改次数加1，然后将数组长度减1，并判断新长度是否是最后一个，如果是最后一个则不需要移动，如果不是，调用System.arraycopy将数组向前"挪"1位，最后将末尾多出来的一个值置为null。

3.3.2 `removeAll()`

public boolean removeAll(Collection<?> c) {     return this.batchRemove(c, false, 0, this.size); }  boolean batchRemove(Collection<?> c, boolean complement, int from, int end) {     Objects.requireNonNull(c);     Object[] es = this.elementData;      for(int r = from; r != end; ++r) {         if (c.contains(es[r]) != complement) {             int w = r++;              try {                 for(; r < end; ++r) {                     Object e;                     if (c.contains(e = es[r]) == complement) {                         es[w++] = e;                     }                 }             } catch (Throwable var12) {                 System.arraycopy(es, r, es, w, end - r);                 w += end - r;                 throw var12;             } finally {                 this.modCount += end - w;                 this.shiftTailOverGap(es, w, end);             }              return true;         }     }      return false; }

removeAll实际上调用的是batchRemove()，在batchRemove()中，有四个参数，含义如下：

Collection<?> c：目标集合
boolean complement：如果取值true，表示保留数组中包含在目标集合c中的元素，如果为false，表示删除数组中包含在目标集合c中的元素
from/end：区间范围，左闭右开

所以传递的(c,false,0,this.size)表示删除数组里面在目标集合c中的元素。下面简单说一下执行步骤：

首先进行判空操作
接着找到第一符合要求的元素（这里是找到第一个需要删除的元素）
找到后从该元素开始继续向后查找，同时记录删除后的数组中最后一个元素的下标w
try/catch是一种保护性行为，因为contains()在AbstractCollection的实现中，会使用Iterator，这里catch异常后仍然调用System.arraycopy，使得已经处理的元素"挪到"前面
最后会增加修改的次数，并调用shiftTailOverGap，该方法在后面会详解

3.3.3 `removeIf()`

public boolean removeIf(Predicate<? super E> filter) {     return this.removeIf(filter, 0, this.size); }  boolean removeIf(Predicate<? super E> filter, int i, int end) {     Objects.requireNonNull(filter);     int expectedModCount = this.modCount;      Object[] es;     for(es = this.elementData; i < end && !filter.test(elementAt(es, i)); ++i) {     }      if (i < end) {         int beg = i;         long[] deathRow = nBits(end - i);         deathRow[0] = 1L;         ++i;          for(; i < end; ++i) {             if (filter.test(elementAt(es, i))) {                 setBit(deathRow, i - beg);             }         }          if (this.modCount != expectedModCount) {             throw new ConcurrentModificationException();         } else {             ++this.modCount;             int w = beg;              for(i = beg; i < end; ++i) {                 if (isClear(deathRow, i - beg)) {                     es[w++] = es[i];                 }             }              this.shiftTailOverGap(es, w, end);             return true;         }     } else if (this.modCount != expectedModCount) {         throw new ConcurrentModificationException();     } else {         return false;     } }

在removeIf中，删除符合条件的元素，首先会进行判空操作，然后找到第一个符合条件的元素下标，如果找不到（i>=end），判断是否有并发操作问题，没有的话返回false，如果i<end，也就是正式进入删除流程：

记录开始下标beg
deathRow是一个标记数组，长度为(end-i-1)>>6 + 1，从beg开始如果遇到符合条件的元素就对下标进行标记（调用setBit）
标记后进行删除，所谓的删除其实就是把后面不符合条件的元素逐个移动到beg之后的位置上
调用shiftTailOverGap处理末尾的元素
返回true，表示存在符合条件的元素并进行了删除操作

3.3.4 `shiftTailOverGap()`

上面的removeAll()以及removeIf()都涉及到了shiftTailOverGap()，下面来看一下实现：

private void shiftTailOverGap(Object[] es, int lo, int hi) {     System.arraycopy(es, hi, es, lo, this.size - hi);     int to = this.size;      for(int i = this.size -= hi - lo; i < to; ++i) {         es[i] = null;     }  }

该方法将es数组中的元素向前移动hi-lo位，并将移动之后的在末尾多出来的那部分元素置为null。

3.4 `indexOf()`系列

包括：

indexOf()
lastIndexOf()
contains()

3.4.1 `indexOf`

public int indexOf(Object o) {     return this.indexOfRange(o, 0, this.size); }  int indexOfRange(Object o, int start, int end) {     Object[] es = this.elementData;     int i;     if (o == null) {         for(i = start; i < end; ++i) {             if (es[i] == null) {                 return i;             }         }     } else {         for(i = start; i < end; ++i) {             if (o.equals(es[i])) {                 return i;             }         }     }      return -1; }

indexOf()实际上是一个包装好的方法，会调用内部的indexOfRange()进行查找，逻辑很简单，首先判断需要查找的值是否为空，如果不为空，使用equals()判断，否则使用==判断，找到就返回下标，否则返回-1。

3.4.2 `contains()`

contains()实际上是indexOf()的包装：

public boolean contains(Object o) {     return this.indexOf(o) >= 0; }

调用indexOf()方法，根据返回的下标判断是否大于等于0，如果是则返回存在，否则返回不存在。

3.4.3 `lastIndexOf()`

lastIndexOf()实现与indexOf()类似，只不过是从尾部开始遍历，内部调用的是lastIndexOfRange()：

public int lastIndexOf(Object o) {     return this.lastIndexOfRange(o, 0, this.size); }  int lastIndexOfRange(Object o, int start, int end) {     Object[] es = this.elementData;     int i;     if (o == null) {         for(i = end - 1; i >= start; --i) {             if (es[i] == null) {                 return i;             }         }     } else {         for(i = end - 1; i >= start; --i) {             if (o.equals(es[i])) {                 return i;             }         }     }      return -1; }

4 `LinkedList`底层

4.1 基本结构

首先来看一下里面的成员变量：

transient int size; transient LinkedList.Node<E> first; transient LinkedList.Node<E> last; private static final long serialVersionUID = 876323262645176354L;

一个表示长度，一个头指针和一个尾指针。

其中LinkedList.Node实现如下：

private static class Node<E> {     E item;     LinkedList.Node<E> next;     LinkedList.Node<E> prev;      Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {         this.item = element;         this.next = next;         this.prev = prev;     } }

可以看到LinkedList实际是基于双链表实现的。

下面再来看一些重要方法，包括：

add()
remove()
get()

4.2 `add()`

add()方法包括6个：

add(E e)
add(int index,E e)
addFirst(E e)
addLast(E e)
addAll(Collection<? extends E> c)
addAll(int index, Collection<? extends E> c)

4.2.1 `linkFirst`/`linkLast`/`linkBefore`实现的`add()`

先看一下比较简单的四个add()：

public void addFirst(E e) {     this.linkFirst(e); }  public void addLast(E e) {     this.linkLast(e); }  public boolean add(E e) {     this.linkLast(e);     return true; }  public void add(int index, E element) {     this.checkPositionIndex(index);     if (index == this.size) {         this.linkLast(element);     } else {         this.linkBefore(element, this.node(index));     } }

可以看到，上面的四个add()不进行任何的添加元素操作，add()只是添加元素的封装，真正实现add操作的是linkLast()、linkFirst()和linkBefore()，这些方法顾名思义就是把元素链接到链表的末尾或者头部，或者链表某个节点的前面：

void linkLast(E e) {     LinkedList.Node<E> l = this.last;     LinkedList.Node<E> newNode = new LinkedList.Node(l, e, (LinkedList.Node)null);     this.last = newNode;     if (l == null) {         this.first = newNode;     } else {         l.next = newNode;     }      ++this.size;     ++this.modCount; }  private void linkFirst(E e) {     LinkedList.Node<E> f = this.first;     LinkedList.Node<E> newNode = new LinkedList.Node((LinkedList.Node)null, e, f);     this.first = newNode;     if (f == null) {         this.last = newNode;     } else {         f.prev = newNode;     }      ++this.size;     ++this.modCount; }  void linkBefore(E e, LinkedList.Node<E> succ) {     LinkedList.Node<E> pred = succ.prev;     LinkedList.Node<E> newNode = new LinkedList.Node(pred, e, succ);     succ.prev = newNode;     if (pred == null) {         this.first = newNode;     } else {         pred.next = newNode;     }      ++this.size;     ++this.modCount; }

实现大体相同，一个是添加到尾部，一个是添加头部，一个是插入到前面。另外，三者在方法的最后都有如下操作：

++this.size; ++this.modCount;

第一个表示节点的个数加1，而第二个，则表示对链表的修改次数加1。

比如，在unlinkLast方法的最后，有如下代码：

--this.size; ++this.modCount;

unlinkLast操作就是移除最后一个节点，节点个数减1的同时，对链表的修改次数加1。

另一方面，通常来说链表插入操作需要找到链表的位置，但是在三个link方法里面，都看不到for循环找到插入位置的代码，这是为什么呢？

由于保存了头尾指针，linkFirst()以及linkLast()并不需要遍历找到插入的位置，但是对于linkBefore()来说，需要找到插入的位置，不过linkBefore()并没有类似"插入位置/插入下标"之类的参数，而是只有一个元素值以及一个后继节点。换句话说，这个后继节点就是通过循环得到的插入位置，比如，调用的代码如下：

this.linkBefore(element, this.node(index));

可以看到在this.node()中，传入了一个下标，并返回了一个后继节点，也就是遍历操作在该方法完成：

LinkedList.Node<E> node(int index) {     LinkedList.Node x;     int i;     if (index < this.size >> 1) {         x = this.first;          for(i = 0; i < index; ++i) {             x = x.next;         }          return x;     } else {         x = this.last;          for(i = this.size - 1; i > index; --i) {             x = x.prev;         }          return x;     } }

这里首先通过判断下标是位于"哪一边"，如果靠近头部，从头指针开始往后遍历，如果靠近尾部，从尾指针开始向后遍历。

4.2.2 遍历实现的`addAll()`

public boolean addAll(Collection<? extends E> c) {     return this.addAll(this.size, c); }  public boolean addAll(int index, Collection<? extends E> c) {     this.checkPositionIndex(index);     Object[] a = c.toArray();     int numNew = a.length;     if (numNew == 0) {         return false;     } else {         LinkedList.Node pred;         LinkedList.Node succ;         if (index == this.size) {             succ = null;             pred = this.last;         } else {             succ = this.node(index);             pred = succ.prev;         }          Object[] var7 = a;         int var8 = a.length;          for(int var9 = 0; var9 < var8; ++var9) {             Object o = var7[var9];             LinkedList.Node<E> newNode = new LinkedList.Node(pred, o, (LinkedList.Node)null);             if (pred == null) {                 this.first = newNode;             } else {                 pred.next = newNode;             }              pred = newNode;         }          if (succ == null) {             this.last = pred;         } else {             pred.next = succ;             succ.prev = pred;         }          this.size += numNew;         ++this.modCount;         return true;     } }

首先可以看到两个addAll实际上调用的是同一个方法，步骤简述如下：

首先通过checkPositionIndex判断下标是否合法
接着把目标集合转为Object[]数组
进行一些特判处理，判断index的范围是插入中间，还是在末尾插入
for循环遍历目标数组，并插入到链表中
修改节点长度，并返回

4.3 `remove()`

与add()类似，remove包括：

remove()
remove(int index)
remove(Object o)
removeFirst()
removeLast()
removeFirstOccurrence(Object o)
removeLastOccurrence(Object o)

当然其实还有两个removeAll与removeIf，但实际上是父类的方法，这里就不分析了。

4.3.1 `unlinkFirst()`/`unlinkLast()`实现的`remove()`

remove()、removeFirst()、removeLast()实际上是通过调用unlinkFirst()/unlinkLast()进行删除的，其中remove()只是removeFirst()的一个别名：

public E remove() {     return this.removeFirst(); }  public E removeFirst() {     LinkedList.Node<E> f = this.first;     if (f == null) {         throw new NoSuchElementException();     } else {         return this.unlinkFirst(f);     } }  public E removeLast() {     LinkedList.Node<E> l = this.last;     if (l == null) {         throw new NoSuchElementException();     } else {         return this.unlinkLast(l);     } }

逻辑很简单，判空之后，调用unlinkFirst()/unlinkLast()：

private E unlinkFirst(LinkedList.Node<E> f) {     E element = f.item;     LinkedList.Node<E> next = f.next;     f.item = null;     f.next = null;     this.first = next;     if (next == null) {         this.last = null;     } else {         next.prev = null;     }      --this.size;     ++this.modCount;     return element; }  private E unlinkLast(LinkedList.Node<E> l) {     E element = l.item;     LinkedList.Node<E> prev = l.prev;     l.item = null;     l.prev = null;     this.last = prev;     if (prev == null) {         this.first = null;     } else {         prev.next = null;     }      --this.size;     ++this.modCount;     return element; }

而在这两个unlink中，由于已经保存了头指针和尾指针的位置，因此两者可以直接在O(1)内进行移除操作，最后将节点长度减1，修改次数加1，并返回旧元素。

4.3.2 `unlink()`实现的`remove()`

再来看一下remove(int index)、remove(Object o)、removeFirstOccurrence(Object o)、removeLastOccurrence(Object o)：

public E remove(int index) {     this.checkElementIndex(index);     return this.unlink(this.node(index)); }  public boolean remove(Object o) {     LinkedList.Node x;     if (o == null) {         for(x = this.first; x != null; x = x.next) {             if (x.item == null) {                 this.unlink(x);                 return true;             }         }     } else {         for(x = this.first; x != null; x = x.next) {             if (o.equals(x.item)) {                 this.unlink(x);                 return true;             }         }     }      return false; }  public boolean removeFirstOccurrence(Object o) {     return this.remove(o); }  public boolean removeLastOccurrence(Object o) {     LinkedList.Node x;     if (o == null) {         for(x = this.last; x != null; x = x.prev) {             if (x.item == null) {                 this.unlink(x);                 return true;             }         }     } else {         for(x = this.last; x != null; x = x.prev) {             if (o.equals(x.item)) {                 this.unlink(x);                 return true;             }         }     }      return false; }

这几个方法实际上都是调用unlink去移除元素，其中removeFirstOccurrence(Object o)等价于remove(Object o)，先说一下remove(int index)，该方法逻辑比较简单，先检查下标合法性，再通过下标找到节点并进行unlnk。

而在remove(Object o)中，需要首先对元素的值是否为null进行判断，两个循环实际上效果等价，会移除遇到的第一个与目标值相同的元素。在removeLastOccurrence(Object o)中，代码大体一致，只是remove(Object o)从头指针开始遍历，而removeLastOccurrence(Object o)从尾指针开始遍历。

可以看到，这几个remove方法实际上是找到要删除的节点，最后调用unlink()进行删除，下面看一下unlink()：

E unlink(LinkedList.Node<E> x) {     E element = x.item;     LinkedList.Node<E> next = x.next;     LinkedList.Node<E> prev = x.prev;     if (prev == null) {         this.first = next;     } else {         prev.next = next;         x.prev = null;     }      if (next == null) {         this.last = prev;     } else {         next.prev = prev;         x.next = null;     }      x.item = null;     --this.size;     ++this.modCount;     return element; }

实现逻辑与unlinkFirst()/unlinkLast()类似，在O(1)内进行删除，里面只是一些比较简单的特判操作，最后将节点长度减1，并将修改次数加1，最后返回旧值。

4.4 `get()`

get方法比较简单，对外提供了三个：

get(int index)
getFirst()
getLast()

其中getFirst()以及getLast()由于保存了头尾指针，特判后，直接O(1)返回：

public E getFirst() {     LinkedList.Node<E> f = this.first;     if (f == null) {         throw new NoSuchElementException();     } else {         return f.item;     } }  public E getLast() {     LinkedList.Node<E> l = this.last;     if (l == null) {         throw new NoSuchElementException();     } else {         return l.item;     } }

而get(int index)毫无疑问需要O(n)时间：

public E get(int index) {     this.checkElementIndex(index);     return this.node(index).item; }

get(int index)判断下标后，实际上进行操作的是this.node()，由于该方法是通过下标找到对应的节点，源码前面也写上了，这里就不分析了，需要O(n)的时间。

5 总结

ArrayList基于Object[]实现，LinkedList基于双链表实现
ArrayList随机访问效率要高于LinkedList
LinkedList提供了比ArrayList更多的插入方法，而且头尾插入效率要高于ArrayList
两者的删除元素方法并不完全相同，ArrayList提供了独有的removeIf()，而LinkedList提供了独有的removeFirstOccurrence()以及removeLastOccurrence()
ArrayList的get()方法始终为O(1)，而LinkedList只有getFirst()/getLast()为O(1)
ArrayList中的两个核心方法是grow()以及System.arraycopy，前者是扩容方法，默认为1.5倍扩容，后者是复制数组方法，是一个native方法，插入、删除等等操作都需要使用
LinkedList中很多方法需要对头尾进行特判，创建比ArrayList简单，无须初始化，不涉及扩容问题

6 附录：关于插入与删除的一个实验

关于插入与删除，通常认为LinkedList的效率要比ArrayList高，但实际上并不是这样，下面是一个测试插入与删除时间的小实验。

先上 Demo

基于我前面说的这个场景，码出代码如下：

public class ThreadTest {      @Test     public void test() throws InterruptedException {          ThreadPoolExecutor executorService = new ThreadPoolExecutor(2, 3, 30, TimeUnit.SECONDS,                 new LinkedBlockingQueue<>(2), new DefaultThreadFactory("test"),                 new ThreadPoolExecutor.DiscardPolicy());                          //每隔两秒打印线程池的信息         ScheduledExecutorService scheduledExecutorService = Executors.newScheduledThreadPool(1);         scheduledExecutorService.scheduleAtFixedRate(() -> {             System.out.println("=====================================thread-pool-info:" + new Date() + "=====================================");             System.out.println("CorePoolSize:" + executorService.getCorePoolSize());             System.out.println("PoolSize:" + executorService.getPoolSize());             System.out.println("ActiveCount:" + executorService.getActiveCount());             System.out.println("KeepAliveTime:" + executorService.getKeepAliveTime(TimeUnit.SECONDS));             System.out.println("QueueSize:" + executorService.getQueue().size());         }, 0, 2, TimeUnit.SECONDS);          try {             //同时提交5个任务,模拟达到最大线程数             for (int i = 0; i < 5; i++) {                 executorService.execute(new Task());             }         } catch (Exception e) {             e.printStackTrace();         }         //休眠10秒，打印日志，观察线程池状态         Thread.sleep(10000);          //每隔3秒提交一个任务         while (true) {             Thread.sleep(3000);             executorService.submit(new Task());         }     }      static class Task implements Runnable {         @Override         public void run(){             try {                 Thread.sleep(1000);             } catch (InterruptedException e) {                 e.printStackTrace();             }             System.out.println(Thread.currentThread() + "-执行任务");         }     } }

这份代码也是提问的哥们给我的，我做了微调，你直接粘出去就能跑起来。

show me code，no bb。这才是相互探讨的正确姿势。

这个程序的运行结果是这样的：

一共五个任务，线程池的运行情况是什么样的呢？

先看标号为 ① 的地方：

三个线程都在执行任务，然后 2 号线程和 1 号线程率先完成了任务，接着把队列里面的两个任务拿出来执行（标号为 ② 的地方）。

按照程序，接下来，每隔 3 秒就有一个耗时 1 秒的任务过来。而此时线程池里面的三个活跃线程都是空闲状态。

那么问题就来了：

该选择哪个线程来执行这个任务呢？是随机选一个吗？

虽然接下来的程序还没有执行，但是基于前面的截图，我现在就可以告诉你，接下来的任务，线程执行顺序为：

Thread[test-1-3,5,main]-执行任务
Thread[test-1-2,5,main]-执行任务
Thread[test-1-1,5,main]-执行任务
Thread[test-1-3,5,main]-执行任务
Thread[test-1-2,5,main]-执行任务
Thread[test-1-1,5,main]-执行任务
......

即虽然线程都是空闲的，但是当任务来的时候不是随机调用的，而是轮询。

由于是轮询，每三秒执行一次，所以非核心线程的空闲时间最多也就是 9 秒，不会超过 30 秒，所以一直不会被回收。

基于这个 Demo，我们就从表象上回答了，为什么活跃线程数一直为 3。

为什么是轮询？

我们通过 Demo 验证了上面场景中，线程执行顺序为轮询。

那么为什么呢？

这只是通过日志得出的表象呀，内部原理呢？对应的代码呢？

这一小节带大家看一下到底是怎么回事。

首先我看到这个表象的时候我就猜测：这三个线程肯定是在某个地方被某个队列存起来了，基于此，才能实现轮询调用。

所以，我一直在找这个队列，一直没有找到对应的代码，我还有点着急了。想着不会是在操作系统层面控制的吧？

后来我冷静下来，觉得不太可能。于是电光火石之间，我想到了，要不先 Dump 一下线程，看看它们都在干啥：

Dump 之后，这玩意我眼熟啊，AQS 的等待队列啊。

根据堆栈信息，我们可以定位到这里的源码：

java.util.concurrent.locks.AbstractQueuedSynchronizer.ConditionObject#awaitNanos

看到这里的时候，我才一下恍然大悟了起来。

害，是自己想的太多了。

说穿了，这其实就是个生产者-消费者的问题啊。

三个线程就是三个消费者，现在没有任务需要处理，它们就等着生产者生产任务，然后通知它们准备消费。

由于本文只是带着你去找答案在源码的什么地方，不对源码进行解读。

所以我默认你是对 AQS 是有一定的了解的。

可以看到 addConditionWaiter 方法其实就是在操作我们要找的那个队列。学名叫做等待队列。

Debug 一下，看看队列里面的情况：

巧了嘛，这不是。顺序刚好是：

Thread[test-1-3,5,main]
Thread[test-1-2,5,main]
Thread[test-1-1,5,main]

消费者这边我们大概摸清楚了，接着去看看生产者。

java.util.concurrent.ThreadPoolExecutor#execute

线程池是在这里把任务放到队列里面去的。

而这个方法里面的源码是这样的：

其中signalNotEmpty() 最终会走到 doSignal 方法，而该方法里面会调用 transferForSignal 方法。

这个方法里面会调用 LockSupport.unpark(node.thred) 方法，唤醒线程：

而唤醒的顺序，就是等待队列里面的顺序：

所以，现在你知道当一个任务来了之后，这个任务该由线程池里面的哪个线程执行，这个不是随机的，也不是随便来的。

是讲究一个顺序的。

什么顺序呢？

Condition 里面的等待队列里面的顺序。

什么，你不太懂 Condition？

那还不赶紧去学？等着我给你讲呢？

本来我是想写一下的，后来发现《Java并发编程的艺术》一书中的 5.6.2 小节已经写的挺清楚了，图文并茂。这部分内容其实也是面试的时候的高频考点，所以自己去看看就好了。

先欠着，欠着。

非核心线程怎么回收？

还是上面的例子，假设非核心线程就空闲了超过 30 秒，那么它是怎么被回收的呢？

这个也是一个比较热门的面试题。

这题没有什么高深的地方，答案就藏在源码的这个地方：

java.util.concurrent.ThreadPoolExecutor#getTask

当 timed 参数为 true 的时候，会执行 workQueue.poll(keepAliveTime,TimeUnit.NANOSECONDS) 方法。

而 timed 什么时候为 true 呢？

boolean timed = allowCoreThreadTimeOut || wc > corePoolSize;

allowCoreThreadTimeOut 默认为 false。

所以，就是看 wc > corePoolSize 条件，wc 是活跃线程数。此时活跃线程数为 3 ，大于核心线程数 2。

因此 timed 为 true。

也就是说，当前 workQueue 为空的时候，现在三个线程都阻塞 workQueue.poll 方法中。

而当指定时间后，workQueue 还是为空，则返回为 null。

于是在 1077 行把 timeOut 修改为 true。

进入一下次循环，返回 null。

最终会执行到这个方法：

java.util.concurrent.ThreadPoolExecutor#processWorkerExit

而这个方法里面会执行 remove 的操作。

于是线程就被回收了。

所以当超过指定时间后，线程会被回收。

那么被回收的这个线程是核心线程还是非核心线程呢？

不知道。

因为在线程池里面，核心线程和非核心线程仅仅是一个概念而已，其实拿着一个线程，我们并不能知道它是核心线程还是非核心线程。

这个地方就是一个证明，因为当工作线程多余核心线程数之后，所有的线程都在 poll，也就是说所有的线程都有可能被回收：

另外一个强有力的证明就是 addWorker 这里：

core 参数仅仅是控制取 corePoolSize 还是 maximumPoolSize。

所以，这个问题你说怎么回答：

JDK 区分的方式就是不区分。

那么我们可以知道吗？

可以，比如通过观察日志，前面的案例中，我就知道这两个是核心线程，因为它们最先创建：

Thread[test-1-1,5,main]-执行任务
Thread[test-1-2,5,main]-执行任务

在程序里面怎么知道呢？

目前是不知道的，但是这个需求，加钱就可以实现。

自己扩展一下线程池嘛，给线程池里面的线程打个标还不是一件很简单的事情吗？

只是你想想，你区分这玩意干啥，有没有可落地的需求？

毕竟，脱离需求谈实现。都是耍流氓。

最后说一句

才疏学浅，难免会有纰漏，如果你发现了错误的地方，可以在后台提出来，我对其加以修改。

感谢您的阅读，我坚持原创，十分欢迎并感谢您的关注。

Tuesday, April 13, 2021