一、前言

学习目标：

• 掌握 原码 反码 补码 基本运算以及转换


• 熟练应用 与 或 非 同或 异或 应用


• 对于 移位运算 在题目中熟练应用，后面会出位运算的题目

二、概述

计算机最主要的功能是处理数值、文字、声音、图形图像等信息。

在计算机内部，各种信息都必须经过数字化编码后才能被传送、存储和处理，所有的数据以二进制的形式存储在设备中，即 0、1 这两种状态。

计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算，例如下面的计算：

int a=74;

int b=58;

int c=a+b;



a  74 ：  1 0 0 1 0 1 0

b  58 :     1 1 1 0 1 0

c 132 : 1 0 0 0 0 1 0 0

十进制数字转换成底层的二进制数字之后，二进制逐位相加，满2进1。

三、原码 反码 补码

1.原码

在计算机的运算中，计算机只能做加法，减法、乘除都没法计算。原码是最简单的机器数表示法，用最高位表示符号位，其他位存放该数的二进制的绝对值。

首位的0表示正数、1表示负数。

特点：

• 表示直观易懂，正负数区分清晰


• 加减法运算复杂，要先判断符号是正号还是负号、相同还是相反

2.反码

正数的反码还是等于原码，负数的反码就是它的原码除符号位外，按位取反。

特点：

• 反码的表示范围与原码的表示范围相同


• 反码表示在计算机中往往作为数码变换的中间环节

3.补码

正数的补码等于它的原码，负数的补码等于反码+1。

特点：

• 在计算机运算时，都是以补码的方式运算的，下面的位运算也是补码形式计算

四、基本运算

1.与

符号：&

运算规则：两个二进制位都为1时才为1，否则为0

示例：1001&1111=1001

2.或

符号：|

运算规则：两个二进制位都为0时才为0，否则为1

示例：1001&1100=1101

3.非

符号：~

运算规则：0变成1，1变成0

示例：~1001 = 0110

4.同或

符号：~

运算规则：数字相同时为1，相反为0

示例：1001~1100=1010

5.异或

符号：^

运算规则：两个二进制位相反为1，相同为0

示例：1001^0111=1110

五、移位运算

1.左移

符号：<<

运算规则：符号位不变，低位补0

示例：

a<<b 代表十进制数字a向左移动b个进位

/* 左移：

 * 左移1位，相当于原数值 * 2

 * 左移2位，相当于原数值 * 4

 * 左移n位，相当于原数值 * 2^n

 */

计算 10 << 1

10的补码：0000 1010

-----------------------

结果补码：0001 0100 ==> 正数，即 10*2=20



计算 10 << 2

10的补码：0000 1010

-----------------------

结果补码：0010 1000 ==> 正数，即 10*2^2=40



计算 10 << 3

10的补码：0000 1010

-----------------------

结果补码：0101 0000 ==> 正数，即 10*2^3=80



计算 12 << 1

12的补码：0000 1100

-----------------------

结果补码：0001 1000 ==> 正数，即 12*2=24

2.右移

符号：>>

运算规则：低位溢出，符号位不变，并用符号位补溢出的高位

示例：

a>>b 代表十进制数字a向右移动b个进位

/* 右移：

 * 右移1位，相当于原数值 / 2

 * 右移2位，相当于原数值 / 4

 * 右移3位，相当于原数值 / 2^n

 * 结果没有小数(向下取整)

 */

计算 80 >> 1

80的补码：0101 0000

-----------------------

结果补码：0010 1000 ==> 正数，即 80/2=40



计算 80 >> 2

80的补码：0101 0000

-----------------------

结果补码：0001 01000 ==> 正数，即 80/2^2=20



计算 80 >> 3

80的补码：0101 0000

-----------------------

结果补码：0000 1010 ==> 正数，即 80/2^3=10



计算 24 >> 1

12的补码：0001 1000

-----------------------

结果补码：0000 1100 ==> 正数，即 24/2=12

前言

前段时间，学习到了Flutter动画，正愁不知道写个项目练习巩固，突然有一天产品在群里发了一个链接【ios中的动画标签】(下面有例图)，我心里直呼"好家伙"，要是产品都要求做成这样，产品经理和程序员又又又又又又得打起来! 还好只是让我们参考，刚好可以拿来练习。

GitHub地址：github.com/longer96/fl…

我们每天都会看到底部导航菜单，它们在应用程序内引导用户，允许他们在不同的tag之间快速切换。但是谁说切换标签就应该很无聊？
让我们一起探索标签栏中有趣的动画。虽然你在应用程序中可能不会使用到，但看看它的实现可能会给你提供一些灵感、设计参考。

如果恰好能给你带来一点点帮助，那是再好不过啦~ 路过的帅逼帮忙点个 star

先上几张花里胡哨的底部菜单 参考图

效果分析

咳咳，有的动效确实挺难的，需要设计师的鼎力支持，我只好选软的柿子捏

首先我们观察，它是由文字和指示器组成的。点击之后指示器切换，文字缩放。

• 每个tag 均分了屏幕宽度


• 点击之后，指示器从之前的tag中部位置拉长到选中tag的中部位置


• 指示器到达选中tag之后，长度立马向选中tag位置收缩

稍微复杂一点的是指示器的动画，看上去有3个变量：左边距、右边距、指示器宽度。
但变量越多，越不方便控制，细心想一下 我们发现其实只需要控制： 左、右边距就可以了，指示器宽度设置成自适应（或者只控制左边距和指示器宽度）

实现效果

其实很多类似底部菜单都可以如法炮制，指示器位于tag后面，根据不同的条件调整位置和尺寸。

实现一款底部菜单

常见的还有另一种展开类似的菜单，比如这样

咱们还是先简单分析一下

• 由一个按钮、多个tag按钮组成


• 点击之后，tag呈扇状展开或收缩

看上去只有2步，还是很简单的嘛

第一步：我们用帧布局叠放按钮和tag

Stack(

    children: [

      // tag菜单



      // 菜单/关闭 按钮

    ]

  )

第二步：管理好tag的位置
简单介绍一下Flow，Flutter中Flow是一个对子组件尺寸以及位置调整非常高效的控件。

Flow用转换矩阵在对子组件进行位置调整的时候进行了优化：在Flow定位过后，如果子组件的尺寸或者位置发生了变化，在FlowDelegate中的paintChildren()方法中调用context.paintChild 进行重绘，而context.paintChild在重绘时使用了转换矩阵，并没有实际调整组件位置。

使用起来也很简单，只需要实现FlowDelegate的paintChildren()方法，就可以自定义布局策略。所以我们需要计算好每一个tag的轨迹位置。

经过你的细心观察，你发现tag的轨迹呈半圆状展开，对 没错 就是需要翻出三角函数

经过你的又一次细心观察，你发现有5个tag，半圆实际可以放7个，但是为了有更好的显示效果，可以将需要展示的tag放在中间位置（过滤掉第一个和最后一个）

所以我们可以列出简单的计算

final total = context.childCount + 1;



for (int i = 0; i < childCount; i++) {

  x = cos(pi * (total - i - 1) / total) * Radius;

  y = sin(pi * (total - i - 1) / total) * Radius;

}

你发现太规整的圆其实并不是那么好看，优化一下

• 将x轴半径设置为 父级约束宽度的一半


• 将Y轴半径设置为 父级约束高度


• 给动画加上曲线，让tag有类似回弹效果


• 注意y轴得转换为负数，因为我们的坐标点位于下方

微调一下，好啦 恭喜你!
3句代码，让产品经理给你点了18杯茶

class FlowAnimatedCircle extends FlowDelegate {

  final Animation<double> animation;



  /// icon 尺寸

  final double iconSize = 48.0;



  /// 菜单左右边距

  final paddingHorizontal = 8.0;



  FlowAnimatedCircle(this.animation) : super(repaint: animation);



  @override

  void paintChildren(FlowPaintingContext context) {

    // 进度等于0，也就是收起来的时候不绘制

    final progress = animation.value;

    if (progress == 0) return;



    final xRadius = context.size.width / 2 - paddingHorizontal;

    final yRadius = context.size.height - iconSize;



    // 开始(0,0)在父组件的中心

    double x = 0;

    double y = 0;



    final total = context.childCount + 1;



    for (int i = 0; i < context.childCount; i++) {

      x = progress * cos(pi * (total - i - 1) / total) * xRadius;

      y = progress * sin(pi * (total - i - 1) / total) * yRadius;



      // 使用Matrix定位每个子组件

      context.paintChild(

        i,

        transform: Matrix4.translationValues(

            x, -y + (context.size.height / 2) - (iconSize / 2), 0),

      );

    }

  }



  @override

  bool shouldRepaint(FlowAnimatedCircle oldDelegate) => false;

}

只要理解到了上面的实现，下面这3种也能很轻松完成

最后

收集、参考实现了几个底部导航，当然可能很多地方需要优化，大家不要喷我哦

• 有很棒的底部菜单希望推荐


• 需要使用的，建议大家clone下来，直接引入，具体需求(如未读消息)自己添加


• 欢迎Fork & pr贡献您的代码，大家共同学习❤


• Android 体验下载 d.cc53.cn/sn6c


• Web在线体验 footer.eeaarr.cn

相信绝大多数朋友做 PPT（幻灯片 / Slides / Deck 等各种称呼了）都是用的 PowerPoint 或者 KeyNote 吧？功能是比较强大，但你有没有遇到过这样的痛点：

• 各种标题、段落的格式不统一，比如字体大小、行间距等等各个页面不太一样，然后得用格式刷来挨个刷一下。


• 想给 PPT 做版本控制，然后就保存了各种复制版本，比如“一版”、“二版”、“终版”、“最终版”、“最终不改版”、“最终稳定不改版”等等，想必大家都见过类似这样的场景吧。


• 想插入代码，但是插入之后发现格式全乱了或者高亮全没了，然后不得不截图插入进去。


• 想插入个公式，然后发现 PPT、Keynote 对 Latex 兼容不太好或者配置稍微麻烦，就只能自己重新敲一遍或者贴截图。


• 想插入一个酷炫的交互组件，比如嵌入一个微博的网页页面实时访问、插入一个可以交互的组件、插入一个音乐播放器组件，原生的 PPT 功能几乎都不支持，这全得依赖于 PowerPoint 或者 KeyNote 来支持才行。

如果你遇到这些痛点，那请你一定要看下去。如果你没有遇到，那也请你看下去吧（拜托。

好，说回正题，我列举了那么多痛点，那这些痛点咋解决呢？

能！甚至解决方案更加轻量级，那就是用 Markdown 来做 PPT！

你试过用 Markdown 写 PPT 吗？没有吧，试试吧，试过之后你就发现上面的功能简直易如反掌。

具体怎么实现呢？

接下来，就有请今天的主角登场了！它就是 Slidev。

什么是 Slidev？

简而言之，Slidev 就是可以让我们用 Markdown 写 PPT 的工具库，基于 Node.js、Vue.js 开发。

利用它我们可以简单地把 Markdown 转化成 PPT，而且它可以支持各种好看的主题、代码高亮、公式、流程图、自定义的网页交互组件，还可以方便地导出成 pdf 或者直接部署成一个网页使用。

官方主页：sli.dev/

GitHub：github.com/slidevjs/sl…

安装和启动

下面我们就来了解下它的基本使用啦。

首先我们需要先安装好 Node.js，推荐 14.x 及以上版本，安装方法见 setup.scrape.center/nodejs。

接着，我们就可以使用 npm 这个命令了。

然后我们可以初始化一个仓库，运行命令如下：

npm init slidev@latest

这个命令就是初始化一个 Slidev 的仓库，运行之后它会让我们输入和选择一些选项，如图所示：

比如上图就是先输入项目文件夹的名称，比如这里我取名叫做 slidevtest。

总之一些选项完成之后，Slidev 会在本地 3000 端口上启动，如图所示：

接着，我们就可以打开浏览器 http://localhost:3000 来查看一个 HelloWorld 版本的 PPT 了，如图所示：

我们可以点击空格进行翻页，第二页展示了一张常规的 PPT 的样式，包括标题、正文、列表等，如图所示：

那这一页的 Markdown 是什么样的呢？其实就是非常常规的 Markdown 文章的写法，内容如下：

# What is Slidev?



Slidev is a slides maker and presenter designed for developers, consist of the following features



- 📝 **Text-based** - focus on the content with Markdown, and then style them later

- 🎨 **Themable** - theme can be shared and used with npm packages

- 🧑‍💻 **Developer Friendly** - code highlighting, live coding with autocompletion

- 🤹 **Interactive** - embedding Vue components to enhance your expressions

- 🎥 **Recording** - built-in recording and camera view

- 📤 **Portable** - export into PDF, PNGs, or even a hostable SPA

- 🛠 **Hackable** - anything possible on a webpage



<br>

<br>



Read more about [Why Slidev?](https://sli.dev/guide/why)

是不是？我们只需要用同样格式的 Markdown 语法就可以轻松将其转化为 PPT 了。

快捷键操作

再下一页介绍了各种快捷键的操作，这个就很常规了，比如点击空格、上下左右键来进行页面切换，如图所示：

更多快捷键的操作可以看这里的说明：sli.dev/guide/navig…，一些简单的快捷键列举如下：

• f：切换全屏


• right / space：下一动画或幻灯片


• left：上一动画或幻灯片


• up：上一张幻灯片


• down：下一张幻灯片


• o：切换幻灯片总览


• d：切换暗黑模式


• g：显示“前往...”

代码高亮

接下来就是代码环节了，因为 Markdown 对代码编写非常友好，所以展示自然也不是问题了，比如代码高亮、代码对齐等都是常规操作，如图所示：

那左边的代码定义就直接这么写就行了：

# Code



Use code snippets and get the highlighting directly![^1]



```ts {all|2|1-6|9|all}

interface User {

  id: number

  firstName: string

  lastName: string

  role: string

}



function updateUser(id: number, update: User) {

  const user = getUser(id)

  const newUser = {...user, ...update}  

  saveUser(id, newUser)

}

```

由于是 Markdown，所以我们可以指定是什么语言，比如 TypeScript、Python 等等。

网页组件

接下来就是非常酷炫的环节了，我们还可以自定义一些网页组件，然后展示出来。

比如我们看下面的一张图。左边就呈现了一个数字计数器，点击左侧数字就会减 1，点击右侧数字就会加 1；另外图的右侧还嵌入了一个组件，这里显示了一个推特的消息，通过一个卡片的形式呈现了出来，不仅仅可以看内容，甚至我们还可以点击下方的喜欢、回复、复制等按钮来进行一些交互。

这些功能在网页里面并不稀奇，但是如果能做到 PPT 里面，那感觉就挺酷的。

那这一页怎么做到的呢？这个其实是引入了一些基于 Vue.js 的组件，本节对应的 Markdown 代码如下：

# Components



<div grid="~ cols-2 gap-4">

<div>



You can use Vue components directly inside your slides.



We have provided a few built-in components like `<Tweet/>` and `<Youtube/>` that you can use directly. And adding your custom components is also super easy.



```html

<Counter :count="10" />

```



<!-- ./components/Counter.vue -->

<Counter :count="10" m="t-4" />



Check out [the guides](https://sli.dev/builtin/components.html) for more.



</div>

<div>



```html

<Tweet id="1390115482657726468" />

```



<Tweet id="1390115482657726468" scale="0.65" />



</div>

</div>

这里我们可以看到，这里引入了 Counter、Tweet 组件，而这个 Counter 就是 Vue.js 的组件，代码如下：

<script setup lang="ts">

import { ref } from 'vue'



const props = defineProps({

  count: {

    default: 0,

  },

})



const counter = ref(props.count)

</script>



<template>

  <div flex="~" w="min" border="~ gray-400 opacity-50 rounded-md">

    <button

      border="r gray-400 opacity-50"

      p="2"

      font="mono"

      outline="!none"

      hover:bg="gray-400 opacity-20"

      @click="counter -= 1"

    >

      -

    </button>

    <span m="auto" p="2">{{ counter }}</span>

    <button

      border="l gray-400 opacity-50"

      p="2"

      font="mono"

      outline="!none"

      hover:bg="gray-400 opacity-20"

      @click="counter += 1"

    >

      +

    </button>

  </div>

</template>

这就是一个标准的基于 Vue.js 3.x 的组件，都是标准的 Vue.js 语法，所以如果我们要添加想要的组件，直接自己写就行了，什么都能实现，只要网页能支持的，统统都能写！

主题定义

当然，一些主题定制也是非常方便的，我们可以在 Markdown 文件直接更改一些配置就好了，比如就把 theme 换个名字，整个主题样式就变了，看如下的对比图：

上面就是一些内置主题，当然我们也可以去官方文档查看一些别人已经写好的主题，见：sli.dev/themes/gall…。

另外我们自己写主题也是可以的，所有的主题样式都可以通过 CSS 等配置好，想要什么就可以有什么，见：sli.dev/themes/writ…

公式和图表

接下来就是一个非常强大实用的功能，公式和图表，支持 Latex、流程图，如图所示：

比如上面的 Latex 的源代码就是这样的：

Inline $\sqrt{3x-1}+(1+x)^2$



Block

$$

\begin{array}{c}



\nabla \times \vec{\mathbf{B}} -\, \frac1c\, \frac{\partial\vec{\mathbf{E}}}{\partial t} &

= \frac{4\pi}{c}\vec{\mathbf{j}}    \nabla \cdot \vec{\mathbf{E}} & = 4 \pi \rho \\



\nabla \times \vec{\mathbf{E}}\, +\, \frac1c\, \frac{\partial\vec{\mathbf{B}}}{\partial t} & = \vec{\mathbf{0}} \\



\nabla \cdot \vec{\mathbf{B}} & = 0



\end{array}

$$

其语法也是和 Latex 一样的。

其背后是怎么实现的呢？其实是因为 Slidev 默认集成了 Katex 这个库，见：katex.org/，有了 Katex 的加持，所有公式的显示都不是事。

页面分隔

有的朋友就好奇了，既然是用 Markdown 写 PPT，那么每一页之间是怎么分割的呢？

其实很简单，最常规的，用三条横线分割就好了，比如：

---

layout: cover

---



# 第 1 页



This is the cover page.



---



# 第 2 页



The second page

当然，除了使用三横线，我们还可以使用更丰富的定义模式，可以给每一页制定一些具体信息，就是使用两层三横线。

比如这样：

---

theme: seriph

layout: cover

background: 'https://source.unsplash.com/1600x900/?nature,water'

---

上面这样的配置可以替代三横线，是另一种可以用作页面分隔的写法，借助这种写法我们可以定义更多页面的具体信息。

备注

当然我们肯定也想给 PPT 添加备注，这个也非常简单，通过注释的形式写到 Markdown 源文件就好了：

---

layout: cover

---



# 第 1 页



This is the cover page.



<!-- 这是一条备注 -->

这里可以看到其实就是用了注释的特定语法。

演讲者头像

当然还有很多酷炫的功能，比如说，我们在讲 PPT 的时候，可能想同时自己也出镜，Slidev 也可以支持。

因为开的是网页，而网页又有捕捉摄像头的功能，所以最终效果可以是这样子：

是的没错！右下角就是演讲者的个人头像，它被嵌入到了 PPT 中！是不是非常酷！

演讲录制

当然，Slidev 还支持演讲录制功能，因为它背后集成了 WebRTC 和 RecordRTC 的 API，一些录制配置如下所示：

所以，演讲过程的录制完全不是问题。

具体的操作可以查看：sli.dev/guide/recor…。

部署

当然用 Slidev 写的 PPT 还可以支持部署，因为这毕竟就是一个网页。

而且部署非常简单和轻量级，因为这就是一些纯静态的 HTML、JavaScript 文件，我们可以轻松把它部署到 GitHub Pages、Netlify 等站点上。

试想这么一个场景：别人在演讲之前还在各种拷贝 PPT，而你打开了一个浏览器直接输入了一个网址，PPT 就出来了，众人惊叹，就问你装不装逼？

具体的部署操作可以查看：sli.dev/guide/hosti…

让我们看几个别人已经部署好的 PPT，直接网页打开就行了：

• demo.sli.dev/composable-…


• masukin.link/talks/simpl…

就是这么简单方便。

版本控制

什么？你想实现版本控制，那再简单不过了。

Markdown 嘛，配合下专业版本管理工具 Git，版本控制再也不是难题。

总结

以上就是对 Slidev 的简单介绍，确实不得不说有些功能真的非常实用，而且我本身特别喜欢 Markdown 和网页开发，所以这个简直对我来说太方便了。

Flutter 保证数据操作原子性

Flutter 是单线程架构，按道理理说，Flutter 不会出现 Java 的多线程相关的问题。

但在我使用 Flutter 过程中，却发现 Flutter 依然会存在数据操作原子性的问题。

其实 Flutter 中存在多线程的（Isolate 隔离池），只是 Flutter 中的多线程更像 Java 中的多进程，因为 Flutter 中线程不能像 Java 一样，可以两个线程去操作同一个对象。

我们一般将计算任务放在 Flutter 单独的线程中，例如一大段 Json 数据的解析，可以将解析计算放在单独的线程中，然后将解析完后的 Map<String, dynamic> 返回到主线程来用。

Flutter单例模式

在 Java 中，我们一般喜欢用单例模式来理解 Java 多线程问题。这里我们也以单例来举例，我们先来一个正常的：

class FlutterSingleton {

  static FlutterSingleton? _instance;



  /// 将构造方法声明成私有的

  FlutterSingleton._();



  static FlutterSingleton getInstance() {

    if (_instance == null) {

      _instance = FlutterSingleton._();

    }

    return _instance!;

  }

}

由于 Flutter 是单线程架构的, 所以上述代码是没有问题的。

问题示例

但是, 和 Java 不同的是, Flutter 中存在异步方法。

做 App 开发肯定会涉及到数据持久化，Android 开发应该都熟悉 SharedPreferences，Flutter 中也存在 SharedPreferences 库，我们就以此来举例。同样实现单例模式，只是这次无可避免的需要使用 Flutter 中的异步：

class SPSingleton {

  static SPSingleton? _instance;



  String? data;



  /// 将构造方法声明成私有的

  SPSingleton._fromMap(Map<String, dynamic> map) : data = map['data'];



  static Future<SPSingleton> _fromSharedPreferences() async {

    // 模拟从 SharedPreferences 中读取数据, 并以此来初始化当前对象

    Map<String, String> map = {'data': 'mockData'};

    await Future.delayed(Duration(milliseconds: 10));

    return SPSingleton._fromMap(map);

  }



  static Future<SPSingleton> getInstance() async {

    if (_instance == null) {

      _instance = await SPSingleton._fromSharedPreferences();

    }

    return _instance!;

  }

}



void main() async {

  SPSingleton.getInstance().then((value) {

    print('instance1.hashcode = ${value.hashCode}');

  });

  SPSingleton.getInstance().then((value) {

    print('instance2.hashcode = ${value.hashCode}');

  });

}

运行上面的代码，打印日志如下：

instance1.hashcode = 428834223

instance2.hashcode = 324692380

可以发现，我们两次调用 SPSingleton.getInstance() 方法，分别创建了两个对象，说明上面的单例模式实现有问题。

我们来分析一下 getInstance() 方法：

static Future<SPSingleton> getInstance() async {

  if (_instance == null) { // 1

    _instance = await SPSingleton._fromSharedPreferences(); //2

  }

  return _instance!;

}

当第一次调用 getInstance() 方法时，代码在运行到 1 处时，发现 _instance 为 null, 就会进入 if 语句里面执行 2 处, 并因为 await 关键字挂起, 并交出代码的执行权, 直到被 await 的 Future 执行完毕，最后将创建的 SPSingleton 对象赋值给 _instance 并返回。

当第二次调用 getInstance() 方法时，代码在运行到 1 处时，可能会发现 _instance 还是为 null (因为 await SPSingleton._fromSharedPreferences() 需要 10ms 才能返回结果), 然后和第一次调用 getInstance() 方法类似, 创建新的 SPSingleton 对象赋值给 _instance。

最后导致两次调用 getInstance() 方法, 分别创建了两个对象。

解决办法

问题原因知道了，那么该怎样解决这个问题呢？

究其本质，就是 getInstance() 方法的执行不具有原子性，即：在一次 getInstance() 方法执行结束前，不能执行下一次 getInstance() 方法。

幸运的是, 我们可以借助 Completer 来将异步操作原子化，下面是借助 Completer 改造后的代码：

import 'dart:async';



class SPSingleton {

  static SPSingleton? _instance;

  static Completer<bool>? _monitor;



  String? data;



  /// 将构造方法声明成私有的

  SPSingleton._fromMap(Map<String, dynamic> map) : data = map['data'];



  static Future<SPSingleton> _fromSharedPreferences() async {

    // 模拟从 SharedPreferences 中读取数据, 并以此来初始化当前对象

    Map<String, String> map = {'data': 'mockData'};

    await Future.delayed(Duration(milliseconds: 10));

    return SPSingleton._fromMap(map);

  }



  static Future<SPSingleton> getInstance() async {

    if (_instance == null) {

      if (_monitor == null) {

        _monitor = Completer<bool>();

        _instance = await SPSingleton._fromSharedPreferences();

        _monitor!.complete(true);

      } else {

        // Flutter 的 Future 支持被多次 await

        await _monitor!.future;

        _monitor = null;

      }

    }

    return _instance!;

  }

}



void main() async {

  SPSingleton.getInstance().then((value) {

    print('instance1.hashcode = ${value.hashCode}');

  });

  SPSingleton.getInstance().then((value) {

    print('instance2.hashcode = ${value.hashCode}');

  });

}

我们再次分析一下 getInstance() 方法:

static Future<SPSingleton> getInstance() async {

  if (_instance == null) { // 1

    if (_monitor == null) { // 2

      _monitor = Completer<bool>(); // 3

      _instance = await SPSingleton._fromSharedPreferences(); // 4

      _monitor!.complete(true); // 5

    } else {

      // Flutter 的 Future 支持被多次 await

      await _monitor!.future; //6

      _monitor = null;

    }

  }

  return _instance!; // 7

}

当第一次调用 getInstance() 方法时, 1 处和 2 处都会判定为 true, 然后进入执行到 3 处创建一个的 Completer 对象, 然后在 4 的 await 处挂起, 并交出代码的执行权, 直到被 await 的 Future 执行完毕。

此时第二次调用的 getInstance() 方法开始执行，1 处同样会判定为 true, 但是到 2 处时会判定为 false, 从而进入到 else, 并因为 6 处的 await 挂起, 并交出代码的执行权;

此时, 第一次调用 getInstance() 时的 4 处执行完毕, 并执行到 5, 并通过 Completer 通知第二次调用的 getInstance() 方法可以等待获取代码执行权了。

最后，两次调用 getInstance() 方法都会返回同一个 SPSingleton 对象，以下是打印日志：

instance1.hashcode = 786567983

instance2.hashcode = 786567983

由于 Flutter 的 Future 是支持多次 await 的, 所以即便是连续 n 次调用 getInstance() 方法, 从第 2 到 n 次调用会 await 同一个 Completer.future, 最后也能返回同一个对象。

Flutter任务队列

虽然我们经常拿单例模式来解释说明 Java 多线程问题，可这并不代表着 Java 只有在单例模式时才有多线程问题。

同样的，也并不代表着 Flutter 只有在单例模式下才有原子操作问题。

问题示例

我们同样以数据持久化来举例，只是这次我们以数据库操作来举例。

我们在操作数据库时，经常会有这样的需求：如果数据库表中存在这条数据，就更新这条数据，否则就插入这条数据。

为了实现这样的需求，我们可能会先从数据库表中查询数据，查询到了就更新，没查询到就插入，代码如下：

class Item {

  int id;

  String data;

  Item({

    required this.id,

    required this.data,

  });

}



class DBTest {

  DBTest._();

  static DBTest instance = DBTest._();

  bool _existsData = false;

  Future<void> insert(String data) async {

    // 模拟数据库插入操作,10毫秒过后,数据库中才有数据

    await Future.delayed(Duration(milliseconds: 10));

    _existsData = true;

    print('执行了插入');

  }



  Future<void> update(String data) async {

    // 模拟数据库更新操作

    await Future.delayed(Duration(milliseconds: 10));

    print('执行了更新');

  }



  Future<Item?> selected(int id) async {

    // 模拟数据库查询操作

    await Future.delayed(Duration(milliseconds: 10));

    if (_existsData) {

      // 数据库中有数据才返回

      return Item(id: 1, data: 'mockData');

    } else {

      // 数据库没有数据时,返回null

      return null;

    }

  }



  /// 先从数据库表中查询数据，查询到了就更新，没查询到就插入

  Future<void> insertOrUpdate(int id, String data) async {

    Item? item = await selected(id);

    if (item == null) {

      await insert(data);

    } else {

      await update(data);

    }

  }

}



void main() async {

  DBTest.instance.insertOrUpdate(1, 'data');

  DBTest.instance.insertOrUpdate(1, 'data');

}

我们期望的输出日志为:

执行了插入

执行了更新

但不幸的是, 输出的日志为:

执行了插入

执行了插入

原因也是异步方法操作数据, 不是原子操作, 导致逻辑异常。

也许我们也可以效仿单例模式的实现，利用 Completer 将 insertOrUpdate() 方法原子化。

但对于数据库操作是不合适的，因为我们可能还有其它需求，比如说：调用插入数据的方法，然后立即从数据库中查询这条数据，发现找不到。

如果强行使用 Completer，那么到最后，可能这个类中会出现一大堆的 Completer ，代码难以维护。

解决办法

其实我们想要的效果是，当有异步方法在操作数据库时，别的操作数据的异步方法应该阻塞住，也就是同一时间只能有一个方法来操作数据库。我们其实可以使用任务队列来实现数据库操作的需求。

我这里利用 Completer 实现了一个任务队列:

import 'dart:async';

import 'dart:collection';



/// TaskQueue 不支持 submit await submit, 以下代码就存在问题

///

/// TaskQueue taskQueue = TaskQueue();

/// Future<void> task1(String arg)async{

///   await Future.delayed(Duration(milliseconds: 100));

/// }

/// Future<void> task2(String arg)async{

///   在这里submit时, 任务会被添加到队尾, 且当前方法任务不会结束

///   添加到队尾的任务必须等到当前方法任务执行完毕后, 才能继续执行

///   而队尾的任务必须等当前任务执行完毕后, 才能执行

///   这就导致相互等待, 使任务无法进行下去

///   解决办法是, 移除当前的 await, 让当前任务结束

///   await taskQueue.submit(task1, arg);

/// }

///

/// taskQueue.submit(task2, arg);

///

/// 总结:

/// 被 submit 的方法的内部如果调用 submit 方法, 此方法不能 await, 否则任务队列会被阻塞住

///

/// 如何避免此操作, 可以借鉴以下思想:

/// 以数据库操作举例, 有个save方法的逻辑是插入或者更新(先查询数据库select,再进行下一步操作);

/// sava方法内部submit,并且select也submit, 就容易出现submit await submit的情况

///

/// 我们可以这样操作,假设当前类为 DBHelper:

/// 将数据库的增,删,查,改操作封装成私有的 async 方法, 且私有方法不能使用submit

/// DBHelper的公有方法, 可以调用自己的私有 async 方法, 但不能调用自己的公有方法, 公有方法可以使用submit

/// 这样就不会存在submit await submit的情况了

class TaskQueue {

  /// 提交任务

  Future<O> submit<A, O>(Function fun, A? arg) async {

    if (!_isEnable) {

      throw Exception('current TaskQueue is recycled.');

    }

    Completer<O> result = new Completer<O>();



    if (!_isStartLoop) {

      _isStartLoop = true;

      _startLoop();

    }



    _queue.addLast(_Runnable<A, O>(

      fun: fun,

      arg: arg,

      completer: result,

    ));

    if (!(_emptyMonitor?.isCompleted ?? true)) {

      _emptyMonitor?.complete();

    }



    return result.future;

  }



  /// 回收 TaskQueue

  void recycle() {

    _isEnable = false;

    if (!(_emptyMonitor?.isCompleted ?? true)) {

      _emptyMonitor?.complete();

    }

    _queue.clear();

  }



  Queue<_Runnable> _queue = Queue<_Runnable>();

  Completer? _emptyMonitor;

  bool _isStartLoop = false;

  bool _isEnable = true;



  Future<void> _startLoop() async {

    while (_isEnable) {

      if (_queue.isEmpty) {

        _emptyMonitor = new Completer();

        await _emptyMonitor!.future;

        _emptyMonitor = null;

      }



      if (!_isEnable) {

        // 当前TaskQueue不可用时, 跳出循环

        return;

      }



      _Runnable runnable = _queue.removeFirst();

      try {

        dynamic result = await runnable.fun(runnable.arg);

        runnable.completer.complete(result);

      } catch (e) {

        runnable.completer.completeError(e);

      }

    }

  }

}



class _Runnable<A, O> {

  final Completer<O> completer;

  final Function fun;

  final A? arg;



  _Runnable({

    required this.completer,

    required this.fun,

    this.arg,

  });

}

由于 Flutter 中的 future 不支持暂停操作, 一旦开始执行, 就只能等待执行完。

所以这里的任务队列实现是基于方法的延迟调用来实现的。

TaskQueue 的用法示例如下:

void main() async {

  Future<void> test1(String data) async {

    await Future.delayed(Duration(milliseconds: 20));

    print('执行了test1');

  }



  Future<String> test2(Map<String, dynamic> args) async {

    await Future.delayed(Duration(milliseconds: 10));

    print('执行了test2');

    return 'mockResult';

  }



  TaskQueue taskQueue = TaskQueue();

  taskQueue.submit(test1, '1');

  taskQueue.submit(test2, {

    'data1': 1,

    'data2': '2',

  }).then((value) {

    print('test2返回结果:${value}');

  });



  await Future.delayed(Duration(milliseconds: 200));

  taskQueue.recycle();

}

/*

执行输出结果如下:



执行了test1

执行了test2

test2返回结果:mockResult

*/

值得注意的是: 这里的 TaskQueue 不支持 submit await submit, 原因及示例代码已在注释中说明，这里不再赘述。

为了避免出现 submit await submit 的情况，我代码注释中也做出了建议（假设当前类为 DBHelper）：

• 
  

  将数据库的增、删、查、改操作封装成私有的异步方法, 且私有异步方法不能使用 submit；

  
  


• 
  

  DBHelper 的公有方法, 可以调用自己的私有异步方法, 但不能调用自己的公有异步方法, 公有异步方法可以使用 submit；

  
  

这样就不会出现 submit await submit 的情况了。

于是，上述的数据库操作示例代码就变成了以下的样子：

class Item {

  int id;

  String data;

  Item({

    required this.id,

    required this.data,

  });

}



class DBTest {

  DBTest._();

  static DBTest instance = DBTest._();

  TaskQueue _taskQueue = TaskQueue();

  bool _existsData = false;

  Future<void> _insert(String data) async {

    // 模拟数据库插入操作,10毫秒过后,数据库才有数据

    await Future.delayed(Duration(milliseconds: 10));

    _existsData = true;

    print('执行了插入');

  }



  Future<void> insert(String data) async {

    await _taskQueue.submit(_insert, data);

  }



  Future<void> _update(String data) async {

    // 模拟数据库更新操作

    await Future.delayed(Duration(milliseconds: 10));

    print('执行了更新');

  }



  Future<void> update(String data) async {

    await _taskQueue.submit(_update, data);

  }



  Future<Item?> _selected(int id) async {

    // 模拟数据库查询操作

    await Future.delayed(Duration(milliseconds: 10));

    if (_existsData) {

      // 数据库中有数据才返回

      return Item(id: 1, data: 'mockData');

    } else {

      // 数据库没有数据时,返回null

      return null;

    }

  }



  Future<Item?> selected(int id) async {

    return await _taskQueue.submit(_selected, id);

  }



  /// 先从数据库表中查询数据，查询到了就更新，没查询到就插入

  Future<void> _insertOrUpdate(Map<String, dynamic> args) async {

    int id = args['id'];

    String data = args['data'];

    Item? item = await _selected(id);

    if (item == null) {

      await _insert(data);

    } else {

      await _update(data);

    }

  }



  Future<Item?> insertOrUpdate(int id, String data) async {

    return await _taskQueue.submit(_insertOrUpdate, {

      'id': id,

      'data': data,

    });

  }

}



void main() async {

  DBTest.instance.insertOrUpdate(1, 'data');

  DBTest.instance.insertOrUpdate(1, 'data');

}

输出日志也变成了我们期望的样子:

执行了插入

执行了更新

总结

• 
  

  Flutter 异步方法修改数据时, 一定要注意数据操作的原子性, 不能因为 Flutter 是单线程架构，就忽略多个异步方法竞争导致数据异常的问题。

  
  


• 
  

  Flutter 保证数据操作的原子性，也有可行办法，当逻辑比较简单时，可直接使用 Completer，当逻辑比较复杂时，可以考虑使用任务队列。

  
  

另外，本文中的任务队列实现有很大的缺陷，不支持 submit await submit，否则整个任务队列会被阻塞住。

如果诸位有其它的任务队列实现方式，或者保证数据操作原子性的方法，欢迎留言。

背景

在上篇文章，我们系统地学习了where 1=1 相关的知识点，大家可以回看《不要再用where 1=1了！有更好的写法！》这篇文章。文章中涉及到了Mybatis的替代方案，有好学的朋友在评论区有朋友问了基于Mybatis写法的问题。

于是，就有了这篇文章。本篇文章会将Mybatis中where标签的基本使用形式、小技巧以及容易踩到的坑进行总结梳理，方便大家更好地实践运用d

原始的手动拼接

在不使用Mybatis的where标签时，我们通常是根据查询条件进行手动拼接，也就是用到了上面提到的where 1=1的方式，示例如下：

  <select id="selectSelective" resultType="com.secbro.entity.User">

    select * from t_user

    where 1=1

    <if test="username != null and username != ''">

     and username = #{username}

    </if>

    <if test="idNo != null and idNo != ''">

      and id_no = #{idNo}

    </if>

  </select>

这种方式主要就是为了避免语句拼接错误，出现类似如下的错误SQL：

select * from t_user where and username = 'Tom' and id = '1001';

select * from t_user where and id = '1001';

当添加上1=1时，SQL语句便是正确的了：

select * from t_user where 1=1 and username = 'Tom' and id = '1001';

select * from t_user where 1=1 and id = '1001';

这个我们之前已经提到过，多少对MySQL数据库的有一定的压力。因为1=1条件的优化过滤是需要MySQL做的。如果能够将这部分放到应用程序来做，就减少了MySQL的压力。毕竟，应用程序是可以轻易地横向扩展的。

Mybatis where标签的使用

为了能达到MySQL性能的调优，我们可以基于Mybatis的where标签来进行实现。where标签是顶层的遍历标签，需要配合if标签使用，单独使用无意义。通常有下面两种实现形式。

方式一：

  <select id="selectSelective" resultType="com.secbro.entity.User">

    select * from t_user

    <where>

      <if test="username != null and username != ''">

        username = #{username}

      </if>

      <if test="idNo != null and idNo != ''">

        and id_no = #{idNo}

      </if>

    </where>

  </select>

方式二：

  <select id="selectSelective" resultType="com.secbro.entity.User">

    select * from t_user

    <where>

      <if test="username != null and username != ''">

        and username = #{username}

      </if>

      <if test="idNo != null and idNo != ''">

        and id_no = #{idNo}

      </if>

    </where>

  </select>

仔细观察会发现，这两种方式的区别在于第一if条件中的SQL语句是否有and。

这里就涉及到where标签的两个特性：

• 第一，只有if标签有内容的情况下才会插入where子句；


• 第二，若子句的开通为 “AND” 或 “OR”，where标签会将它替换去除；

所以说，上面的两种写法都是可以了，Mybatis的where标签会替我们做一些事情。

但需要注意的是：where标签只会 智能的去除（忽略）首个满足条件语句的前缀。所以建议在使用where标签时，每个语句都最好写上 and 前缀或者 or 前缀，否则像以下写法就会出现问题：

  <select id="selectSelective" resultType="com.secbro.entity.User">

    select * from t_user

    <where>

      <if test="username != null and username != ''">

        username = #{username}

      </if>

      <if test="idNo != null and idNo != ''">

        id_no = #{idNo}

      </if>

    </where>

  </select>

生成的SQL语句如下：

select * from t_user      WHERE username = ?  id_no = ?

很显然，语法是错误的。

因此，在使用where标签时，建议将所有条件都添加上and或or；

进阶：自定义trim标签

上面使用where标签可以达到拼接条件语句时，自动去掉首个条件的and或or，那么如果是其他自定义的关键字是否也能去掉呢？

此时，where标签就无能为力了，该trim标签上场了，它也可以实现where标签的功能。

  <select id="selectSelective" resultType="com.secbro.entity.User">

    select * from t_user

    <trim prefix="where" prefixOverrides="and | or ">

      <if test="username != null and username != ''">

        and username = #{username}

      </if>

      <if test="idNo != null and idNo != ''">

        and id_no = #{idNo}

      </if>

    </trim>

  </select>

将上面基于where标签的写改写为trim标签，发现执行效果完全一样。而且trim标签具有了更加灵活的自定义性。

where语句的坑

另外，在使用where语句或其他语句时一定要注意一个地方，那就是：注释的使用。

先来看例子：

  <select id="selectSelective" resultType="com.secbro.entity.User">

    select * from t_user

    <where>

      <if test="username != null and username != ''">

        and username = #{username}

      </if>

      <if test="idNo != null and idNo != ''">

        /* and id_no = #{idNo}*/

        and id_no = #{idNo}

      </if>

    </where>

  </select>

上述SQL语句中添加了 /**/的注释，生成的SQL语句为：

select * from t_user WHERE username = ? /* and id_no = ?*/ and id_no = ? 

执行时，直接报错。

还有一个示例：

  <select id="selectSelective" resultType="com.secbro.entity.User">

    select * from t_user

    <where>

      <if test="username != null and username != ''">

        -- and username = #{username}

        and username = #{username}

      </if>

      <if test="idNo != null and idNo != ''">

        and id_no = #{idNo}

      </if>

    </where>

  </select>

生成的SQL语句为：

select * from t_user WHERE -- and username = ? and username = ? and id_no = ? 

同样会导致报错。

这是因为我们使用 XML 方式配置 SQL 时，如果在 where 标签之后添加了注释，那么当有子元素满足条件时，除了 < !-- --> 注释会被 where 忽略解析以外，其它注释例如 // 或 /**/ 或 -- 等都会被 where 当成首个子句元素处理，导致后续真正的首个 AND 子句元素或 OR 子句元素没能被成功替换掉前缀，从而引起语法错误。

同时，个人在实践中也经常发现因为在XML中使用注释不当导致SQL语法错误或执行出错误的结果。强烈建议，非必要，不要在XML中注释掉SQL，可以通过版本管理工具来追溯历史记录和修改。

小结

本文基于Mybatis中where标签的使用，展开讲了它的使用方式、特性以及拓展到trim标签的替代作用，同时，也提到了在使用时可能会出现的坑。内容虽然简单，但如果能够很好地实践、避免踩坑也是能力的体现。

泪目，想不到我用了这么久的Java编程语言，竟然使用的是值传递。本篇文章我们将带大家搞清楚Java值传递的特性。

前言

是不是有人会这样认为Java在传递参数时，参数如果是普通类型，那就是值传递，如果是对象，那就是引用传递。

如果是这样认为那就大错特错了。

下面我们一起看一下Java的值传递特性。

Java 真的是值传递

检验是值传递最好的方法就是交换方法，我们在交换方法中将两个对象的引用互换，再看一下原来的值会不会被影响。

我们可以看如下例子:

• 首先创建两个用户一个张三，一个李四。
• 然后我们调用身份互换方法swap
• 在身份互换方法中确认两人是否身份互换成功（可以看到结果是成功的）
• 如果是引用传递的话我们创建的两个用户已经完成了身份互换
• 但实际结果是两个用户

package com.zhj.interview;



public class Test15 {



    public static void main(String[] args) {

        User ZhangSan = new User("张三");

        User LiSi = new User("李四");

        System.out.println("开始交换---------------------------------");

        swap(ZhangSan, LiSi);

        System.out.println("交换结束---------------------------------");

        System.out.println("交换后ZhangSan的名字：" + ZhangSan.name);

        System.out.println("交换后LiSi的名字：" + LiSi.name);

    }



    private static void swap(User ZhangSan, User LiSi){

        User user;

        user = ZhangSan;

        ZhangSan = LiSi;

        LiSi = user;

        System.out.println("交换后ZhangSan的名字：" + ZhangSan.name);

        System.out.println("交换后LiSi的名字：" + LiSi.name);

    }

}

class User{

    String name;

    User(String name) {

        this.name = name;

    }

}

运行结果：

开始交换---------------------------------

交换后ZhangSan的名字：李四

交换后LiSi的名字：张三

交换结束---------------------------------

交换后ZhangSan的名字：张三

交换后LiSi的名字：李四

如下图所示，值传递的意思是将引用进行值传递，希望下图能对大家理解上有所帮助。

造成错觉的原因

造成我们认为Java在传递参数时，参数如果是普通类型，那就是值传递，如果是对象，那就是引用传递的原因就是，我们将传入的对象修改后，开始创建的对象内容也会改变。

最好的理解方式就是：

我们传入的参数只是钥匙，值传递就是配两把钥匙给方法，引用传递就是把自己的钥匙给方法；

如果把自己的钥匙给方法，方法内交换了钥匙之后，我们自己的钥匙也就被掉包了（引用传递）；

如果是额外配两把钥匙给对方，方法内交换的钥匙是新配的钥匙，不会影响我们自己的钥匙（值传递）；

需要注意的是，无论是使用自己的钥匙，还是后配的钥匙，打开房门，修改房屋内结构，这个变化是不受影响钥匙影响的，因为改变的不是钥匙。

在JVM中对象引用与对象信息的体现，如下图所示。

一. 前言

太极生两仪,两仪生四相，四相生八卦,八卦定吉凶

中国的八卦与西方的二进制其实原理上有极其相似的一面. 但是演化和推算方面, 八卦更胜一筹.

阴: 0, 阳: 1;

老阴: 00, 少阳: 10, 少阴: 01, 老阳: 11;

坤: 000, 艮: 100, 坎: 010,巽 :110, ,震: 001, 离:101, 兑: 011, 乾: 111;

二.正文.

计算机就是一个二进制的逻辑机器

计算机三大件:主板,CPU,内存; 而最主要的就是cpu, cpu的主要组成就是可以理解为晶体管, 晶体管也就相当于是个开关, 即打电报中的.和_. 这种二进制的简单也造就了计算机快的特性.

**计算机只会二进制, 那怎样才能让计算机有用呢? **

那就是约定大于配置

先是字符集

• ASCII字符集


• ISO 8859-1字符集


• GB2312字符集


• GBK字符集


• utf8字符集

数字, 以int为例子:

二进制在源码的巧妙使用(我们以java示例)

很多源码中使用了二进制来区分各个状态, 而且状态可以组合的形式.
主要使用的是& 和 |的计算来实现的.

0&0 = 0;           0|0 = 0;

0&1 = 0;           0|1 = 1;   

1&0 = 0;           1|0 = 1;   

1&1 = 1;           1|1 = 1;

例如:

Streams

public int characteristics() {

    // 既包含所有的特性

    return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED |

           Spliterator.IMMUTABLE | Spliterator.NONNULL |

           Spliterator.DISTINCT | Spliterator.SORTED;

}



public int characteristics() {

    if (beforeSplit) {

        // 两个共同都有的特性: aSpliterator.characteristics() & bSpliterator.characteristics()

        return aSpliterator.characteristics() & bSpliterator.characteristics()

               & ~(Spliterator.DISTINCT | Spliterator.SORTED

                   | (unsized ? Spliterator.SIZED | Spliterator.SUBSIZED : 0));

    }

    else {

        return bSpliterator.characteristics();

    }

}

public interface Spliterator<T> {

    public static final int ORDERED    = 0x00000010;



    public static final int DISTINCT   = 0x00000001;



    public static final int SORTED     = 0x00000004;



    public static final int SIZED      = 0x00000040;



    public static final int NONNULL    = 0x00000100;



    public static final int IMMUTABLE  = 0x00000400;



    public static final int CONCURRENT = 0x00001000;



    public static final int SUBSIZED = 0x00004000;

}

二进制在一些记录中的头信息巧妙使用

mysql中 COMPACT行格式 中一条记录.

JVM中一个对象的二进制的巧妙使用

二进制解决一些有趣的问题

有1000桶酒，其中1桶有毒。而一旦吃了，毒性会在1周后发作。现在我们用小老鼠做实验，要在1周后找出那桶毒酒，问最少需要多少老鼠。

这个问题其实大家都见到过. 解题思路也巧妙地使用了二进制来完成.

• 
  

  把10只老鼠依次排队为：0 - 9，关在笼子里

  
  


• 
  

  把1000瓶药依次编号，并换算成二进制，如 8 = 1000，根据二进制中出现1的位数对相应位置小鼠喝药。 因为我们选择的是10只

  
  

  小鼠，2^10 = 1024 > 1000,能够保证所有的编号的酒都能被喂小鼠而不会遗漏被转为二进制的1的位.

  
  


• 
  

  长时间的等待，等待小鼠的死亡

  
  


• 
  

  把死亡小鼠的依次记录，然后10位的二进制中, 死亡老鼠编号对应10位中的二进制数为1, 没死的老鼠编号对应10为中的二进制数为0, 即知毒药的编号.

首先我们需要去了解一下, 二叉搜索树的性质:

1. 对于 BST的每一个节点 node，左子树节点的值都比 node的值要小,右子树的值都要比node的值大。
2. 对于BST的每一个节点node， 它的左侧和右侧都是 BST

这里需要说明一下的是,从刷算法的角度来讲,还有一个重要的性质: BST的中序遍历的结果是有序的(升序)。

那么我们开始吧, 最近一直拖更，很不好意思.

230. 二叉搜索树中第K个小的元素

思路梳理 如果这么理解, 产生一个升序的序列(数组)，那么我们可以根据第k个小的元素 1,2,3,4,5这里第1个小的元素在哪里？那不就是1嘛.刚好借助于BST中序遍历的结果。是不是就很巧了呢。

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {TreeNode} root

 * @param {number} k

 * @return {number}

 */

// BST 的两个性质 左边的比右边的大

// 中序遍历的结果是 升序的 



var kthSmallest = function(root, k) {

    // 返回结果 记录结果

    let res = 0;

    // 记录升序之后的排名

    let count = 0;

    function traverse(root, k) {

        // base case

        if (root === null) return

        

        traverse(root.left, k)

        //中序

        count++;

        if (count === k) {

           res = root.val;

           return res;

        }

        traverse(root.right, k)

    }

    

    //定义函数

    traverse(root, k)

    return res;

}

538. 把二叉搜索树转换为累加树

思路梳理

其实这道题需要需要一个反过来的想法, BST的中序遍历的结果是升序的, 如果我们稍微作为一下修改呢？

function traverse(root) {

    

    traverse(root.right)

    // 中序遍历的结果是不是就成了 逆序(降序)的方式排列呢

    // 这里做累加的结果

    traverse(root.left)

}

traverse(root)

通过逆向的思考方式, 我从 8开始，也就是右子树开始依次去右中左的方式去遍历和累加和，是不是会更好一点呢，你可以思考一下,仔细去看一下那颗实例树:

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {TreeNode} root

 * @return {TreeNode}

 */

 

 var convertBST = function(root) {

     // 升序变为降序

     // sum 记录累加和

     let sum = 0;

     

     function traverse(root) {

         // base case

         if (root === null) return

         

         traverse(root.right)

         // 维护累加值

         sum += root.val;

         root.val = sum;

         traverse(root.left)

     }

     traverse(root)

     return root;

 }

1038. 从搜索树到更大的和树

思路梳理

这道题和上题完全一样的思路和写法这里就不做赘述了

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {TreeNode} root

 * @return {TreeNode}

 */

var bstToGst = function(root) {

    // 升序变降序

    // 记录累加和

    let sum = 0;

    

    function traverse(root) {

        if (root === null) return;

        

        traverse(root.right)

        // 累加和

        sum += root.val;

        root.val = sum;

        traverse(root.left)

    }

    traverse(root)

    return root;

}

654. 最大二叉树

思路梳理

其实对于构建一颗二叉树最关键的是把root也就是把根节点找出来就好了。 那么我们就需要去遍历去找出数组中最大的值maxVal，把根节点root找出来了。 那么就可以把 maxVal左边和右边的数组进行递归，作为root的左右子树

// 伪代码

var constructMaximumBinaryTree = function([3,2,1,6,0,5]) {

    // 找出数组中的最大值

    let root = TreeNode(6)

    

    let root.left = constructMaximumBinaryTree([3,2,1])

    let root.right = constructMaximumBinaryTree([0,5])

    return root;

}

这里我们需要的注意的是如何去构建一个递归函数: 参数是如何要求的？ 因为需要 分离左子树和右子树 我们需要不断的确认子树的开始和结束的位置

function build (nums, start, end) {

    // base case

    if (left > right) return;

    

    let maxValue = -1, index = -1; // index 是最大值的索引值是重要的分离条件

    // find

    for (let i = start; i < end; i++) {

        if (nums[i] > maxValue) {

           maxValue = nums[i];

           index = i;

        }

    }

    // 此时去构建树 root;

    let root = new TreeNode(maxValue);

    

    root.left = build(nums, start, index - 1)

    root.right = build(nums, index + 1, end)

    // 别忘了返回 

    return root;

}

这里其实我们已经写出来的本题的核心代码了,需要我们自己耐心的组合一下就好了啊

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {number[]} nums

 * @return {TreeNode}

 */

var constructMaximumBinaryTree = function(nums) {

    let root = build(nums, 0, nums.length-1)

    return root;

}



function build(nums, start, end) {

     // base case 

     if (left > right) return;

     

     let maxVal = -1, index = -1;

     for (let i = start; i < end; i++) {

         if (nums[i] > maxVal) {

            maxVal = nums[i]

            index = i;

         }

     }

     

     // 制作树

     let root = new TreeNode(maxVal)

     

     root.left = build(nums, start, index - 1)

     root.right = build(nums, index + 1, end)

     return root;

}

98. 验证二叉搜索树

思路分析

BST类似的代码逻辑就是利用 左小右大的特性

function BST(root, target) {

    if (root.val === target) {

       // 找到目标做点什么呢

    }

    if (root.val < target) {

       // 右 比 root 大

       BST(root.right, target)

    }

    if (root.val > target) {

       // 左 比 root 小

       BST(root.left, target)

    }

}

那么对于我们去验证一棵树是不是合法的是需要注意一些事情的：

1. 对于每一个节点 root代码值都需要去检查它的左右孩子节点是否都是符合左小右大的原则
2. 从 BST的定义出发的话, root的整个左子树都要小于 root.val, 整个右子树都要大于 root.val

但是就会产生一个问题,就是对于某个节点,它只能管得了自己的左右子节点,如何去把约束关系传递给左右子树呢？

left.val < root.val < right.val

是不是可以借助于这种关系去约束他们呢？

主函数的定义

function isValidBST(root, null, null)

对于左子树来说 每一个左子树的 val 都需要满足于 min.val < val < root.val

isValidBST(root.left, min, root) 

那么同样的对于 每一个右子树的 val 都需要满足于 root.val < val < max.val

isValidBST(root.right, root, max)

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {TreeNode} root

 * @return {boolean}

 */

var isValidBST = function(root) {

    return isValid(root, null, null)

}



function isValid(root, min, max) {

    // 怎么就合法了呢？ 找完还一直没报false 不就是满足条件的吗

    if (root === null) return true;

    // 比最小的还小 不合法

    if (min !== null && root.val <= min.val) return false;

    // 比最大的还大。不合法

    if (max !== null && root.val >= max.val) return false;

    

    return isvalid(root.left, min, root) && isValid(root.right, root, max)

}

700. 二叉搜索树中的搜索

思路分析

其实，你看像不像我们上面提到的二叉树的思维模版呢？ 题目要求是 找到对应的val的节点, 并返回以该节点为根的子树 其实就是可以理解为 返回当前节点就好了 会带有以 该节点为根的一颗子树的。

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {TreeNode} root

 * @param {number} val

 * @return {TreeNode}

 */

 

 var searchBST = function(root, val) {

     // base case 

     if (root === null) return null;

     

     if (root.val === val) {

        return root;

     }

     

     if (root.val < val) {

       searchBST(root.right)

     }

     if (root.val > val) {

       searchBST(root.left)

     }



 }

701. 二叉搜索树中的插入操作

思路分析

这里 需要注意的一点就是你你怎么样才能插入呢？如果是 target === val说明不是空位置, 那就插不进去啊, 所以我们要插入的位置肯定是一个空位置, 你如果认真分析过 这个过程 你对 base case 有没有一个全新的认识呢？ 就是这里

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {TreeNode} root

 * @param {number} val

 * @return {TreeNode}

 */

var insertIntoBST = function(root, val) {

    // base case

    if (root === null) // 插入

    return new TreeNode(val)

    

    // if (root === val) 不需要了

    if (root.val < val) {

        insertIntoBST(root.right)

    }

    if (root.val > val) {

        insertIntoBST(root.left)

    }

}

450. 删除二叉搜索树中的节点

思路分析

先上一个基本的模版：

var deleteNode = function(root, key) {

    // 基本的摹本

    if (root === null) return null;

    

    if (root.val === key) {

       // 删除操作

    }

    

    if (root.val < key) {

       deleteNode(root.right, val)

    }

    if (root.val > key) {

       deleteNode(root.left, val)

    }

}

当 root.val === key的时候 需要我们去执行一个删除的逻辑了

case1: 没有子孩子

if (root.left === null && root.right) reture null;

case2: 只有一个非空节点的情况,那么需要这个非空的节点接替自己的位置

if (root.left === null) return root.right;

if (root.right === null) return root.left;

case3: 如果有两个节点就麻烦了,我们就需要把 左子树中最大的或者是右子树中最小的元素来接替自己， 我们采用第二种方式

if (root.left !== null && root.right !== null) {

    // 找到右子树中的最小的节点

    let minNode = getMin(root.right)

    // 把当前的值 替换为最小的值

    root.val = minNode;

    // 我们还需要把右子树中最小的值 删除掉

    root.right = deleteNode(root.right, minNode.val)

}

获取右子树中最小的元素

// 其实这里的最小的就是 左子树

function getMin(node) {

    while (node.left !== null)  继续找下面的左子树

    node = node.left;

    return node;  // 没有发现和前端的原型链好像啊

}

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {TreeNode} root

 * @param {number} key

 * @return {TreeNode}

 */

var deleteNode = function(root, key) {

    // 基本的摹本

    if (root === null) return null;

    

    if (root.val === key) {

       // 删除操作

       // case1, 2

       if (root.left === null) return root.right;

       if (root.right === null) return root.left;

       // case 3

       let minNode = getMin(root.right);

       root.val = minNode.val; // 一加

       root.right = deleteNode(root.right, minNode); // 一减

    }

    

    if (root.val < key) {

       deleteNode(root.right, val)

    }

    if (root.val > key) {

       deleteNode(root.left, val)

    }

    

    function getMin(node) {

        while(node.left !== null) node = node.left;

        return node;

    }

}

嗯，当然

不能

进入正题，Kotlin中，高阶函数的身影无处不在，听上去高端大气上档次的高阶函数，简化一点讲，其实就是Lambda + 函数。

如果，Lambda学不好，就会导致高阶函数学不好，就会导致协程等等一系列的Kotlin核心学不好，Kotlin自然就一知半解了。所以，下面，一起来学习吧。

开始一个稍微复杂一点的实现

需求如下：传入一个参数，打印该参数，并且返回该参数

分析

乍看需求，这还不简单，一个print加一个return不就完事了，但是如果用Lambda，该怎么写呢？

val myPrint = { str: String ->

    print("str is $str")

    str

}

• 这里划第一个重点，Lambda的最后一行作为返回值输出。此时，如果直接打印myPrint，是可以直接输出的

fun main() {

    println(myPrint("this is kotlin"))

}

结果和预想一致。如果对这种函数的写法结构有什么疑惑的，可以查看juejin.cn/post/701173…

String.()

一脸懵逼，这是啥玩意？（此处应有表情 尼克杨问号脸）

先写个例子看看

val testStr : String.() -> Unit = {

    print(this)

}

• 官方一点解释，在.和()之间没有函数名，所以这是给String增加了一个匿名的扩展函数，这个函数的功能是打印String。在括号内，也就是Lambda体中，会持有String本身，也就是this。怎么调用呢？如下：

fun main() {

    "hello kotlin".testStr()

}

// 执行结果：hello kotlin

• 此外这里还有一个重点：扩展函数是可以全局调用的


• 扩展函数有啥用？举个例子，如果对Glide提供的方法不满意，可以直接扩展一个Glide.xxx函数供自己调用，在xxx函数内部，可以取到this，也就是Glide本身。


• 有兴趣可以看一下Compose的源码，原来扩展函数还可以这么用

终极形态

先看代码

val addInt : Int.(Int) -> String = {

    "两数相加的结果是${this + it}"

}

用已有的知识分析一下：

• Int.():匿名的扩展函数


• this：当前的Int，也就是调用这个扩展函数的对象


• "两数相加的结果是${this + it}" ： Lambda的最后一行，也就返回值

如何调用

一般有如下两种调用方式：

fun main() {

    println(addInt(1,2))

    println(1.addInt(2)) 

}

• 第二种更加符合规范，之所以可以有第一种写法，是因为this会默认作为第一个参数


• 此处可以记住一个知识点，扩展了某一个函数，扩展函数内部的this就是被扩展的函数本身

Kotlin函数返回值那些事

在Kotlin函数中，如果不指定函数的返回值类型，则默认为Unit

fun output() {println("helle kotlin")}

• 上述函数的返回值为Unit类型

当函数体中出现return的时候，则需要手动为函数指定类型

fun output2() : Int {

    return 0

}

• 返回Int类型的0，需要手动指定函数的返回值类型，否则报错

如果是以下的函数，那么返回值为？

fun output3() = {}

• 此处的返回值为() -> Unit，可省略，写全了，就是如下的样子：

fun output3() : () -> Unit = {}

• 此处函数返回函数，已经是高阶函数的范畴了

如果函数接着套一个函数呢，比如

fun output4() = run { println("hello kotlin") }

• 虽说run是一个函数，但是此处的返回值就不是() -> Unit


• 此处的返回就是run的返回值，但是run是什么？

@kotlin.internal.InlineOnly

public inline fun <R> run(block: () -> R): R {

    contract {

        callsInPlace(block, InvocationKind.EXACTLY_ONCE)

    }

    return block()

}

• run的作用就是执行内部的函数，在这里就是println方法。


• run的返回自是R，也就是泛型，具体一点就是println的返回值，这里println的返回值是Unit，所以可以得出上面的output4的返回值就是Unit。


• 这里如果不是很懂的话，可以看一个简单一点的例子

fun output5() = run {true}

• 此处，函数的返回值就是true的类型，Boolen

函数中套一个函数怎么传参呢

刚刚的例子中，知道了怎么写一个函数中套函数，那么其中嵌套得函数怎么传参呢

fun output6() = {a: Int ->  println("this is $a")}

• a为参数，函数是println，所以output6的返回值类型为(Int) -> Unit


• 如果需要调用的话，需要这么写：

output6()(1)

最后一个重点：在写Lambda的时候，记住换行

几种函数写法的区别

fun a()

常见的函数

val a = {}

a是一个变量，只不过是一个接受了匿名函数的变量，可以执行这个函数，和第一种现象一致。

这里的a还可以赋值给另一个变量 val a2 = a，但是函数本身不能直接赋给一个变量，可以使用::，让函数本身变成函数的引用

--end---

列表流畅度优化

这是一个通用的流畅度优化方案，通过分帧渲染优化由构建导致的卡顿，例如页面切换或者复杂列表快速滚动的场景。

代码中 example 运行在 VIVO X23（骁龙 660），在相同的滚动操作下优化前后 200 帧采集数据指标对比（录屏在文章最后）：

优化前	优化后

监控工具来自：fps_monitor，指标详细信息：页面流畅度不再是谜！调试神器开箱即用，Flutter FPS检测工具

• 流畅：一帧耗时低于 18ms
• 良好：一帧耗时在 18ms-33ms 之间
• 轻微卡顿：一帧耗时在 33ms-67ms 之间
• 卡顿：一帧耗时大于 66.7ms

采用分帧优化后，卡顿次数从 平均 33.3 帧出现了一帧，降低到 200 帧中仅出现了一帧，峰值也从 188ms 降低到 90ms。卡顿现象大幅减轻，流畅帧占比显著提升，整体表现更流畅。下方是详细数据。

页面切换流畅度提升

在打开一个页面或者 Tab 切换时，系统会渲染整个页面并结合动画完成页面切换。对于复杂页面，同样会出现卡顿掉帧。借助分帧组件，将页面的构建逐帧拆解，通过 DevTools 中的性能工具查看。切换过程的峰值由 112.5ms 降低到 30.2 ms，整体切换过程更加流畅。

实际优化合集：Keframe 流畅度优化实践合集

如何使用？

项目依赖：

在 pubspec.yaml 中添加 keframe 依赖

dependencies:

  keframe: version

组件仅区分非空安全与空安全版本

非空安全使用： 1.0.2

空安全版本使用： 2.0.2

github 地址：github.com/LianjiaTech…

pub 查看：pub.dev/packages/ke…

Dont forget star ~

快速上手：

如下图所示

假如现在页面由 A、B、C、D 四部分组成，每部分耗时 10ms，在页面时构建为 40ms。使用分帧组件 FrameSeparateWidget 嵌套每一个部分。页面构建时会在第一帧渲染简单的占位，在后续四帧内分别渲染 A、B、C、D。

对于列表，在每一个 item 中嵌套 FrameSeparateWidget，并将 ListView 嵌套在 SizeCacheWidget 内即可。

构造函数说明

FrameSeparateWidget ：分帧组件，将嵌套的 widget 单独一帧渲染

SizeCacheWidget：缓存子节点中，分帧组件嵌套的实际 widget 的尺寸信息

方案设计与分析：

卡顿的本质，就是 单帧的绘制时间过长。基于此自然衍生出两种思路解决：

1、减少一帧的绘制耗时，因为导致耗时过长的原因有很多，比如不合理的刷新，或者绘制时间过长，都有可能，需要具体问题具体分析，后面我会分享一些我的优化经验。

2、在不对耗时优化下，将一帧的任务拆分到多帧内，保证每一帧都不超时。这也是本组件的设计思路，分帧渲染。

如下图所示:

原理并不复杂，问题在于如何在 Flutter 中实践这一机制。

因为涉及到帧与系统的调度，自然联想到看 SchedulerBinding 中有无现成的 API。

发现了 scheduleTask 方法，这是系统提供的一个执行任务的方法，但这个方法存在两个问题：

• 1、其中的渲染任务是优先级进行堆排序，而堆排序是不稳定排序，这会导致任务的执行顺序并非 FIFO。从效果上来看，就是列表不会按照顺序渲染，而是会出现跳动渲染的情况

• 2、这个方法本身存在调度问题，我已经提交 issue 与 pr，不过一直卡在单元测试上，如果感兴趣可以以在这里交流谈论。

fix: Tasks scheduled through 'SchedulerBinding.instance.scheduleTask'… #82781

最终，参考这个设计结合 endOfFrame 方法的使用，完成了分帧队列。整个渲染流程变为下图所示：

对于列表构建场景来说，假设屏幕上能显示五个 item。首先在第一帧的时候，列表会渲染 5 个占位的 Widget，同时添加 5 个高优先级任务到队列中，这里的任务可以是简单的将占位 Widget 和实际 item进行替换，也可通过渐变等动画提升体验。在后续的五帧中占位 Widget 依次被替换成实际的列表 item。

在 ListView流畅度翻倍！！Flutter卡顿分析和通用优化方案 这篇文章中有更加详细的分析。

一些展示效果（Example 说明请查看 Github）

卡顿的页面往往都是由多个复杂 widget 同时渲染导致。通过为复杂的 widget 嵌套分帧组件 FrameSeparateWidget。渲染时，分帧组件会在第一帧同时渲染多个 palceHolder，之后连续的多帧内依次渲染复杂子项，以此提升页面流畅度。

例如 example 中的优化前示例：

ListView.builder(

              itemCount: childCount,

              itemBuilder: (c, i) => CellWidget(

                color: i % 2 == 0 ? Colors.red : Colors.blue,

                index: i,

              ),

            )

其中 CellWidget 高度为 60，内部嵌套了三个 TextField 的组件（整体构建耗时在 9ms 左右）。

优化仅需为每一个 item 嵌套分帧组件，并为其设置 placeHolder（placeHolder 尽量简单，样式与实际 item 接近即可）。

在列表情况下，给 ListView 嵌套 SizeCacheWidget，同时建议将预加载范围 cacheExtent 设置大一点，例如 500（该属性默认为 250），提升慢速滑动时候的体验。

此外，也可以给 item 嵌套透明度/位移等动画，优化视觉上的效果。

效果如下图：

分帧的成本

当然分帧方案也非十全十美，在我看来主要有两点成本：

1、额外的构建开销：整个构建过程的构建消耗由「n * widget消耗 」变成了「n *（ widget + 占位）消耗 + 系统调度 n 帧消耗」。可以看出，额外的开销主要由占位的复杂度决定。如果占位只是简单的 Container，测试后发现整体构建耗时大概提升在 15 % 左右。这种额外开销对于当下的移动设备而言，成本几乎可以不计。

2、视觉上的变化：如同上面的演示，组件会将 item 分帧渲染，页面在视觉上出现占位变成实际 widget 的过程。但其实由于列表存在缓存区域（建议将缓存区调大），在高端机或正常滑动情况下用户并无感知。而在中低端设备上快速滑动能感觉到切换的过程，但比严重顿挫要好。

优化前后对比演示

注：gif 帧率只有20

优化前	优化后

最后：一点点思考

列表优化篇到此告一段落，在整个开源实践过程中，有两点感触较深：

「点」与「面」的关系

我们在思考技术方案的时候可以由「点」到「面」，站在一个较高视野去想问题的本质。

而在执行的时候则需要由「面」到「点」的进行逐级拆分，抓住问题的关键节点，并且拟定进度计划，逐步破解。

很多时候，这种向上和向下的逻辑思维才是我们的核心竞争力。

以不变应万变

对于未知的东西，我们往往会过度的将它想复杂。在一开始分析列表构建原理的时候，我也苦于无从下手，走了很多弯路。但其实对于 Flutter 这套 「UI」 框架而言，核心仍然在于三棵树的构建机制。

在这套体系内，抓住不变的东西，无论是生命周期、路由等等问题都可以从里面找到答案。我之前也有过总结：Flutter 核心渲染机制 与 Flutter路由设计与源码解析 。

前言

大家好，我是林三心，用最通俗的话讲最难的知识点是我的座右铭，基础是进阶的前提是我的初心，今天跟大家来唠唠嗑，如果后端真的返回给前端10万条数据，咱们前端要怎么优雅地展示出来呢？（哈哈假设后端真的能传10万条数据到前端）

前置工作

先把前置工作给做好，后面才能进行测试

后端搭建

新建一个server.js文件，简单起个服务，并返回给前端10w条数据，并通过nodemon server.js开启服务

没有安装nodemon的同学可以先全局安装npm i nodemon -g

// server.js



const http = require('http')

const port = 8000;



http.createServer(function (req, res) {

  // 开启Cors

  res.writeHead(200, {

    //设置允许跨域的域名，也可设置*允许所有域名

    'Access-Control-Allow-Origin': '*',

    //跨域允许的请求方法，也可设置*允许所有方法

    "Access-Control-Allow-Methods": "DELETE,PUT,POST,GET,OPTIONS",

    //允许的header类型

    'Access-Control-Allow-Headers': 'Content-Type'

  })

  let list = []

  let num = 0



  // 生成10万条数据的list

  for (let i = 0; i < 100000; i++) {

    num++

    list.push({

      src: 'https://p3-passport.byteacctimg.com/img/user-avatar/d71c38d1682c543b33f8d716b3b734ca~300x300.image',

      text: `我是${num}号嘉宾林三心`,

      tid: num

    })

  }

  res.end(JSON.stringify(list));

}).listen(port, function () {

  console.log('server is listening on port ' + port);

})

复制代码

前端页面

先新建一个index.html

// index.html



// 样式

<style>

    * {

      padding: 0;

      margin: 0;

    }

    #container {

      height: 100vh;

      overflow: auto;

    }

    .sunshine {

      display: flex;

      padding: 10px;

    }

    img {

      width: 150px;

      height: 150px;

    }

  </style>



// html部分

<body>

  <div id="container">

  </div>

  <script src="./index.js"></script>

</body>

复制代码

然后新建一个index.js文件，封装一个AJAX函数，用来请求这10w条数据

// index.js



// 请求函数

const getList = () => {

    return new Promise((resolve, reject) => {

        //步骤一:创建异步对象

        var ajax = new XMLHttpRequest();

        //步骤二:设置请求的url参数,参数一是请求的类型,参数二是请求的url,可以带参数

        ajax.open('get', 'http://127.0.0.1:8000');

        //步骤三:发送请求

        ajax.send();

        //步骤四:注册事件 onreadystatechange 状态改变就会调用

        ajax.onreadystatechange = function () {

            if (ajax.readyState == 4 && ajax.status == 200) {

                //步骤五 如果能够进到这个判断 说明 数据 完美的回来了,并且请求的页面是存在的

                resolve(JSON.parse(ajax.responseText))

            }

        }

    })

}



// 获取container对象

const container = document.getElementById('container')

复制代码

直接渲染

最直接的方式就是直接渲染出来，但是这样的做法肯定是不可取的，因为一次性渲染出10w个节点，是非常耗时间的，咱们可以来看一下耗时，差不多要消耗12秒，非常消耗时间

const renderList = async () => {

    console.time('列表时间')

    const list = await getList()

    list.forEach(item => {

        const div = document.createElement('div')

        div.className = 'sunshine'

        div.innerHTML = `<img src="${item.src}" /><span>${item.text}</span>`

        container.appendChild(div)

    })

    console.timeEnd('列表时间')

}

renderList()

复制代码

setTimeout分页渲染

这个方法就是，把10w按照每页数量limit分成总共Math.ceil(total / limit)页，然后利用setTimeout，每次渲染1页数据，这样的话，渲染出首页数据的时间大大缩减了

const renderList = async () => {

    console.time('列表时间')

    const list = await getList()

    console.log(list)

    const total = list.length

    const page = 0

    const limit = 200

    const totalPage = Math.ceil(total / limit)



    const render = (page) => {

        if (page >= totalPage) return

        setTimeout(() => {

            for (let i = page * limit; i < page * limit + limit; i++) {

                const item = list[i]

                const div = document.createElement('div')

                div.className = 'sunshine'

                div.innerHTML = `<img src="${item.src}" /><span>${item.text}</span>`

                container.appendChild(div)

            }

            render(page + 1)

        }, 0)

    }

    render(page)

    console.timeEnd('列表时间')

}

复制代码

requestAnimationFrame

使用requestAnimationFrame代替setTimeout，减少了重排的次数，极大提高了性能，建议大家在渲染方面多使用requestAnimationFrame

const renderList = async () => {

    console.time('列表时间')

    const list = await getList()

    console.log(list)

    const total = list.length

    const page = 0

    const limit = 200

    const totalPage = Math.ceil(total / limit)



    const render = (page) => {

        if (page >= totalPage) return

        // 使用requestAnimationFrame代替setTimeout

        requestAnimationFrame(() => {

            for (let i = page * limit; i < page * limit + limit; i++) {

                const item = list[i]

                const div = document.createElement('div')

                div.className = 'sunshine'

                div.innerHTML = `<img src="${item.src}" /><span>${item.text}</span>`

                container.appendChild(div)

            }

            render(page + 1)

        })

    }

    render(page)

    console.timeEnd('列表时间')

}

复制代码

文档碎片 + requestAnimationFrame

文档碎片的好处

• 1、之前都是每次创建一个div标签就appendChild一次，但是有了文档碎片可以先把1页的div标签先放进文档碎片中，然后一次性appendChild到container中，这样减少了appendChild的次数，极大提高了性能


• 2、页面只会渲染文档碎片包裹着的元素，而不会渲染文档碎片

const renderList = async () => {

    console.time('列表时间')

    const list = await getList()

    console.log(list)

    const total = list.length

    const page = 0

    const limit = 200

    const totalPage = Math.ceil(total / limit)



    const render = (page) => {

        if (page >= totalPage) return

        requestAnimationFrame(() => {

            // 创建一个文档碎片

            const fragment = document.createDocumentFragment()

            for (let i = page * limit; i < page * limit + limit; i++) {

                const item = list[i]

                const div = document.createElement('div')

                div.className = 'sunshine'

                div.innerHTML = `<img src="${item.src}" /><span>${item.text}</span>`

                // 先塞进文档碎片

                fragment.appendChild(div)

            }

            // 一次性appendChild

            container.appendChild(fragment)

            render(page + 1)

        })

    }

    render(page)

    console.timeEnd('列表时间')

}

复制代码

懒加载

为了比较通俗的讲解，咱们启动一个vue前端项目，后端服务还是开着

其实实现原理很简单，咱们通过一张图来展示，就是在列表尾部放一个空节点blank，然后先渲染第1页数据，向上滚动，等到blank出现在视图中，就说明到底了，这时候再加载第二页，往后以此类推。

至于怎么判断blank出现在视图上，可以使用getBoundingClientRect方法获取top属性

IntersectionObserver 性能更好，但是我这里就拿getBoundingClientRect来举例

<script setup lang="ts">

import { onMounted, ref, computed } from 'vue'

const getList = () => {

  // 跟上面一样的代码

}



const container = ref<HTMLElement>() // container节点

const blank = ref<HTMLElement>() // blank节点

const list = ref<any>([]) // 列表

const page = ref(1) // 当前页数

const limit = 200 // 一页展示

// 最大页数

const maxPage = computed(() => Math.ceil(list.value.length / limit))

// 真实展示的列表

const showList = computed(() => list.value.slice(0, page.value * limit))

const handleScroll = () => {

  // 当前页数与最大页数的比较

  if (page.value > maxPage.value) return

  const clientHeight = container.value?.clientHeight

  const blankTop = blank.value?.getBoundingClientRect().top

  if (clientHeight === blankTop) {

    // blank出现在视图，则当前页数加1

    page.value++

  }

}



onMounted(async () => {

  const res = await getList()

  list.value = res

})

</script>



<template>

  <div id="container" @scroll="handleScroll" ref="container">

    <div class="sunshine" v-for="(item) in showList" :key="item.tid">

      <img :src="item.src" />

      <span>{{ item.text }}</span>

    </div>

    <div ref="blank"></div>

  </div>

</template>

复制代码

应用程序中的图表提供了数据的图形显示或图画表示，跨越了行业和应用程序。像Mint这样的移动应用程序使用饼状图来监测消费习惯，像Strava这样的健身应用程序使用线状图和条状图来分析步幅、心率和海拔高度。

在构建Flutter应用程序时，开发者可以使用由谷歌维护的官方charts_flutter 库来创建这些类型的图表。

在本教程中，我们将学习如何使用charts_flutter 创建一些最常见的图表--线形图、饼图和条形图。

我们将用这些图表来显示一个虚构的Flutter图表开发者社区五年来的增长情况。虽然本教程中的数据是捏造的，但本教程可以很容易地利用真实数据。

前提条件

要学习本教程，您必须具备以下条件。

• 安装了Flutter
• 安装了Android Studio或Xcode
• 对Flutter有一定的了解

创建并设置一个Flutter项目charts_flutter

要创建一个新的Flutter项目，运行以下命令。

flutter create projectName

接下来，在您的代码编辑器中打开这个新项目。如上所述，我们将使用[chart_flutter](https://pub.dev/packages/charts_flutter) ，Flutter的官方库。

要将chart_flutter 导入您的项目，请打开pubspec.yaml 文件并将其添加到依赖项下。

dependencies:

  flutter:

    sdk: flutter



  charts_flutter: ^0.11.0

构建应用程序的脚手架

现在我们有了新的Flutter应用程序所附带的基本代码：一个记录按钮被按下多少次的计数器。

由于我们的条形图应用程序中不需要这个，继续删除在main.dart 页面中发现的代码。删除所有的内容，除了下面的内容。

import ‘package:flutter/material.dart’;

void main() => runApp(MyApp());

class MyApp extends StatelessWidget {

@override

Widget build(BuildContext context) {

            //TODO: implement build

            Return MaterialApp(

            );

     }

}

现在，在我们的构建部件中返回MaterialApp 类，以便我们可以使用Material Design。

创建一个主页

要为我们的应用程序创建一个主页，请导航到lib 文件夹，并创建一个名为home.dart 的新页面。

import 'package:flutter/material.dart';



class HomePage extends StatelessWidget {

  @override

  Widget build(BuildContext context) {

    return Scaffold(

      body: Center(

        child: ,

      ),

    );

  }

}

通过import 'package:flutter/material.dart' ，我们就可以导入Material Design。

然后，HomePage 类扩展了statelessWidget ，因为在这个页面上没有状态变化。

在BuildContext widget里面，我们返回Scaffold 类，给我们一个基本的Material Design布局结构。我们的条形图将放在子参数的位置，我们将把它放在屏幕主体的中心。

所有这些现在都成为我们应用程序的支架。

随着主页的完成，我们可以在我们的main.dart 文件中指定HomePage ，因为main.dart 将我们应用程序中的所有功能集中在一起。

class MyApp extends StatelessWidget {

  @override

  Widget build(BuildContext context) {

    return MaterialApp(

      debugShowCheckedModeBanner: false,

      home: HomePage(), //This is where we specify our homepage

    );

  }

}

有了这段代码，main.dart 就知道每当应用加载时首先显示哪一页。

请注意，将debugShowCheckedModeBanner 设置为false ，就可以从我们的应用程序中删除调试标记。

创建一个Flutter图表应用程序

系列和模型

在我们创建图表应用之前，让我们熟悉一下Flutter图表常用的两个术语：系列和模型。

系列是一组（或系列）的信息，我们可以用它来绘制我们的图表。一个模型是我们的信息的格式，它规定了使用该模型的每个数据项必须具有的属性。

创建一个条形图

为柱状图数据创建一个模型

首先，我们将创建一个柱状图，以显示在过去五年中新增的虚构Flutter图表开发者的数量。换句话说，我们要跟踪虚构的Flutter图表社区的增长情况。

我们的模型，定义了我们的数据格式，包括我们要看的年份，那一年加入Flutter图表社区的开发者数量，以及相应条形图的颜色。

在lib 文件夹中，创建一个名为developer_series.dart 的文件。下面，实现我们模型的代码。

import 'package:charts_flutter/flutter.dart' as charts;

import 'package:flutter/foundation.dart';



class DeveloperSeries {

  final int year;

  final int developers;

  final charts.Color barColor;



  DeveloperSeries(

    {

      @required this.year,

      @required this.developers,

      @required this.barColor

    }

  );

}

我们将模型命名为DeveloperSeries ，并指定了每个系列项目必须具备的属性（year,developers, 和barColor ）。

为了防止在创建一个类的对象时，该类的参数为空，我们使用了@required 注释，如上面的代码块中所示。

要使用@required 关键字，我们必须导入foundation.dart 包。

为柱状图创建数据

现在我们有了一个条形图数据的模型，让我们继续实际创建一些数据。在主页上，通过添加以下内容为柱状图生成数据。

 import 'package:flutter/material.dart';

import 'package:charts_flutter/flutter.dart' as charts;

import 'package:;lib/developer_series.dart';



class HomePage extends StatelessWidget {

  final List<DeveloperSeries> data = [



    DeveloperSeries(

      year: "2017",

      developers: 40000,

      barColor: charts.ColorUtil.fromDartColor(Colors.green),

    ),

    DeveloperSeries(

      year: "2018",

      developers: 5000,

      barColor: charts.ColorUtil.fromDartColor(Colors.green),

    ),

    DeveloperSeries(

      year: "2019",

      developers: 40000,

      barColor: charts.ColorUtil.fromDartColor(Colors.green),

    ),

    DeveloperSeries(

      year: "2020",

      developers: 35000,

      barColor: charts.ColorUtil.fromDartColor(Colors.green),

    ),

    DeveloperSeries(

      year: "2021",

      developers: 45000,

      barColor: charts.ColorUtil.fromDartColor(Colors.green),

    ),

  ];



  @override

  Widget build(BuildContext context) {

    return Scaffold(

      body: Center(

        child: ,

      ),

    );

  }

}

这是一个名为data 的简单列表。列表中的每一个项目都是按照DeveloperSeries 的模型制作的，也就是说每一个项目都有一个年份(year)、开发者的数量(developers)和条形图的颜色(barColor)的属性。

请注意，上面的数据是真实的，所以请随意操作这些数字和颜色。

构建柱状图

我们已经成功地为我们的柱状图创建了数据。现在，让我们来创建条形图本身。为了使我们的项目有条理，我们将把柱状图的代码放在一个单独的文件中。

在lib ，创建一个developer_chart.dart 文件。

import 'package:flutter/material.dart';

import 'package:charts_flutter/flutter.dart' as charts;

import 'package:lib/developer_series.dart';



class DeveloperChart extends StatelessWidget {

  final List<DeveloperSeries> data;



  DeveloperChart({@required this.data});

  @override

  Widget build(BuildContext context) {

    List<charts.Series<DeveloperSeries, String>> series = [

      charts.Series(

        id: "developers",

        data: data,

        domainFn: (DeveloperSeries series, _) => series.year,

        measureFn: (DeveloperSeries series, _) => series.developers,

        colorFn: (DeveloperSeries series, _) => series.barColor

      )

    ];



    Return charts.Barchart(series, animate: true);

  }



}

通过final List<DeveloperSeries> data ，我们定义了一个名为data 的列表，它是我们之前创建的DeveloperSeries 模型形式的数据项的List 。

列表中的每一个数据项都带有相应的年份、开发人员的数量和条形颜色。

类中的DeveloperChart 构造函数确保在使用条形图类的任何地方，它所需要的数据总是被提供；这是用@required 关键字完成的。

实际的柱状图是在我们的构建部件中创建的。如你所知，所有的柱状图都有几组数据相互对照（在我们的例子中，过去五年和Flutter图表社区获得的开发者数量）。

这些数据组在一起，被称为系列。系列告诉我们Flutter要把哪一组数据放在我们条形图的水平面，哪一组放在垂直面。

然后，我们先前创建的数据列表插入到我们的系列中，并由Flutter适当地使用。

通过List<charts.Series<DeveloperSeries, String>> series ，我们创建了一个名为series 的列表。这个列表的类型为charts.Series ；charts 将Flutter导入我们的项目，Series 函数为Flutter中的柱状图创建系列。

我们刚刚创建的系列是以我们的DeveloperSeries 模型为模型。

我们将在系列中指定的参数包括：id,data,domainFn,measureFn, 和colorFN 。

• id 标识了图表
• data 指向要在柱状图上绘制的项目列表
• domainFn 指向柱状图水平方向上的数值。
• measureFn 指向垂直方向上的数值的数量
• colorFN 指的是条形图的颜色

通过domainFn,measureFn, 和colorFN 函数，我们创建了以Subscriber 系列为参数的函数，创建了它的实例，然后使用这些实例来访问它的不同属性。

developer_chart.dart 文件中的下划线标志着第二个参数是不需要的。

在将我们的系列指向它所需要的所有数据后，我们再使用Flutter的BarChart 函数来创建我们的柱状图。

我们还可以通过简单地将animate 设置为true 来添加一个动画，以获得视觉上的吸引力，这将使图表呈现出一个漂亮的动画。

将柱状图添加到主页上

现在，我们可以将新创建的柱状图添加到我们的主页上并显示。

import 'package:flutter/material.dart';

import 'package:charts_flutter/flutter.dart' as charts;

import 'package:lib/developer_series.dart';

import 'package:lib/developer_chart.dart';



class HomePage extends StatelessWidget {

  // ...



  @override

  Widget build(BuildContext context) {

    return Scaffold(

      body: Center(

        child: DeveloperChart(

          data: data,

        )

      ),

    );

  }

}

在这里，我们只需在我们的页面主体内调用DeveloperChart 类，并将其指向我们要使用的数据。

为了确保我们的图表能够很好地在屏幕上显示，我们将把它放在一个Card ，在它周围包裹一个容器，并给它设置一个高度和一些填充。

…



class DeveloperChart extends StatelessWidget {

  final List<DeveloperSeries> data;



  DeveloperChart({@required this.data});

  @override

  Widget build(BuildContext context) {

    List<charts.Series<DeveloperSeries, String>> series = [

      charts.Series(

        id: "developers",

        data: data,

        domainFn: (DeveloperSeries series, _) => series.year,

        measureFn: (DeveloperSeries series, _) => series.developers,

        colorFn: (DeveloperSeries series, _) => series.barColor

      )

    ];



    return Container(

      height: 300,

      padding: EdgeInsets.all(25),

      child: Card(

        child: Padding(

          padding: const EdgeInsets.all(9.0),

          child: Column(

            children: <Widget>[

              Text(

                "Yearly Growth in the Flutter Community",

                style: Theme.of(context).textTheme.body2,

              ),

              Expanded(

                child: charts.BarChart(series, animate: true),

              )

            ],

          ),

        ),

      ),

    );

  }



}

通过使用expanded widget，我们将我们的柱状图很好地扩展到Card 。上面的Text widget给了我们的柱状图一个标题，让人们知道它是关于什么的。

而且，通过Theme.of(context).textTheme.body2 ，我们将Material Design默认的正文样式应用于我们的标题。

通过padding: const EdgeInsets.all(9.0) ，我们给容纳我们的条形图的卡片在所有边上加了9px的填充。最后，我们将Card 包裹在一个容器中，并给这个容器一个300px的高度和25px的边距。

现在，我们的条形图应该能很好地呈现在我们的屏幕上。

创建饼状图

我们也可以使用charts_flutter 包来创建饼图。事实上，我们上面遵循的程序和我们编写的代码可以创建饼图。

要将我们创建的条形图改为饼图，只需将charts.BarChart(series, animate: true) 改为child:( charts.PieChart(series, animate: true) 。

然后我们就可以在饼图上添加标签。

Expanded(

          child: charts.PieChart(series,

           defaultRenderer: charts.ArcRendererConfig(

            arcRendererDecorators: [

                     charts.ArcLabelDecorator(

                        labelPosition: charts.ArcLabelPosition.inside)

          ])

           animate: true),

)

ArcRendererConfig 函数可以配置饼图的外观，我们可以使用ArcLabelDecorator 函数为饼图添加标签。

labelPosition 指定将标签放在哪里，是放在里面还是外面；在这种情况下，我们指定标签应该放在外面。

创建折线图

我们可以用创建其他两个图表的同样方法来创建一个折线图。我们只需对我们的数据配置做一个小小的调整。

在我们的系列列表中，List<charts.Series<DeveloperSeries, String>> 变成List<charts.Series<DeveloperSeries, num>> ，因为折线图只对数字起作用。

List<charts.Series<DeveloperSeries, num>> series = [

      charts.Series(

        id: "developers",

        data: data,

        domainFn: (DeveloperSeries series, _) => series.year,

        measureFn: (DeveloperSeries series, _) => series.developers,

        colorFn: (DeveloperSeries series, _) => series.barColor

      )

    ];

现在我们可以把charts.PieChart 改为charts.Linechart ，从而得到我们的折线图。默认情况下，折线图是从原点零开始的。但是我们所关注的年份是从2016年到2021年。因此，这里是如何使我们的折线图跨越这个范围的。

Expanded(

          child: charts.LineChart(series,

           domainAxis: const charts.NumericAxisSpec(

                 tickProviderSpec:

                 charts.BasicNumericTickProviderSpec(zeroBound: false),

                 viewport: charts.NumericExtents(2016.0, 2022.0),

           ),

           animate: true),

)

NumericAxisSpec 函数为图表中的轴设置规格。通过BasicNumericTickProviderSpec 函数，我们将zeroBound 设置为false ，这样我们的图表就不会从原点零开始。

最后，通过NumericExtents 函数，我们设置了我们希望我们的坐标轴所跨越的范围。

总结

本教程的目的是向Flutter开发者展示如何在其应用程序中实现不同的图表。使用谷歌创建的强大的charts_flutter 包，我们能够实现一个柱状图、一个饼状图和一个线形图。

Java并发-ThreadLocal

ThreadLocal简介：

多线程访问同一个共享变量的时候容易出现并发问题，特别是多个线程对一个变量进行写入的时候，为了保证线程安全，一般使用者在访问共享变量的时候需要进行额外的同步措施才能保证线程安全性。

而ThreadLocal是除了加锁这种同步方式之外的另一种保证一种规避多线程访问出现线程不安全的方法，线程并发的安全问题在于多个线程同时操作同一个变量的时候，不加以额外限制会存在线程争着写入导致数据写入不符合预期，如果我们在创建一个变量后，每个线程对其进行访问的时候访问的都是线程自己的变量这样就不会存在线程不安全问题。

ThreadLocal的典型适用场景：

典型场景1：

每一个线程需要有一个独享的对象（通常是工具类，典型比如SimpleDateFormat，Random）。

以代码为例，通过SimpleDateFormat实现时间戳转换为格式化时间串的功能：

public static void main(String[] args) {

    ExecutorService threadPool = Executors.newFixedThreadPool(10);

    for (int i = 0; i < 1000; i++) {

        int finalI = i;

        threadPool.execute(new Runnable() {

            @Override

            public void run() {

                String result = toDate(1000L + finalI);

            }

        });

    }

    threadPool.shutdown();

}



public static String toDate(long seconds){

    Date currentDate = new Date(seconds *1000);

    SimpleDateFormat formator = new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");

    return formator.format(currentDate);

}

上面的代码其实是没有线程安全问题的，但是存在的不足是我们调用了1000次，创建了1000次SimpleDateFormat对象，为了结局这个问题，我们可以把SimpleDateFormat对象从toDate中抽离出来，成为一个全局的变量：

static SimpleDateFormat formator = new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");



public static String toDate(long seconds){

	Date currentDate = new Date(seconds *1000);

	return formator.format(currentDate);

}

// output:

1970-01-01 08:33:06

1970-01-01 08:33:07

1970-01-01 08:32:47

1970-01-01 08:32:47

1970-01-01 08:33:10

1970-01-01 08:33:11

很容易发现，全局唯一的formator对象，因为没有加锁，是有线程安全问题的，那么我们可以通过加锁修复：

public static String toDate(long seconds){

    Date currentDate = new Date(seconds *1000);

    synchronized (formator){

        return formator.format(currentDate);

    }

}

虽然修复了线程安全问题，但是随之而来的，synchronized关键字导致各个线程需要频繁的申请锁资源，等待锁资源释放，释放锁资源，这并不划算，而利用ThreadLocal这个工具类，可以很方便的解决问题：

ThreadLocal改造如下：

class FormatorThreadLocalGetter {

  public static ThreadLocal<SimpleDateFormat> formator = new ThreadLocal<>() {

    @Override

    protected SimpleDateFormat initialValue() {

      return new SSimpleDateFormat("yyyy-MM-dd hh:mm:ss");

    }

  };



  // or use Lambda

  public static ThreadLocal<SimpleDateFormat> formator2 = ThreadLocal.withInitial(() -> new SimpleDateFormat("yyyy-MM-dd hh:mm:ss"));

}

public class ThreadLocalTest {

  // 这里我们使用COW容器记录下每一个SimpleDateFormator的hashcode

  static CopyOnWriteArraySet<String> hashSet = new CopyOnWriteArraySet<String>();



  public static void main(String[] args) throws InterruptedException {

    ExecutorService threadPool = Executors.newFixedThreadPool(10);

    for (int i = 0; i < 1000; i++) {

      int finalI = i;

      threadPool.execute(new Runnable() {

        @Override

        public void run() {

          System.out.println(Thread.currentThread().getName());

          System.out.println(toDate(1000L + finalI));

        }

      });

    }

    threadPool.shutdown();

    Thread.sleep(5000);

    // 延迟5s，确保所有的输出都执行完毕，然后看看我们创建了多少个formator对象。

    System.out.println(hashSet.size());

    hashSet.forEach(new Consumer<String>() {

      @Override

      public void accept(String s) {

        System.out.println(s);

      }

    });

  }



  public static String toDate(long seconds) {

    Date currentDate = new Date(seconds * 1000);

    SimpleDateFormat formator = FormatorThreadLocalGetter.formator.get();

    // 将当前线程的formator的hashcode记录下来，看看最终有多少个hashCode

    hashSet.add(String.valueOf(formator.hashCode()));

    // 通过ThreadLocal去get一个formator。

    return FormatorThreadLocalGetter.formator.get().format(currentDate);

  }

}



// 这里我们需要override一下hashCode函数，因为默认的hashCode生成规则是

// 调用构造函数入参pattern这个String对象的hashCode，因为所有的formator

// 的pattern都一样，不重写一下会发现hashCode都一样。

class SSimpleDateFormat extends SimpleDateFormat {

  private int hashCode = 0;

  SSimpleDateFormat(String pattern) {

    super(pattern);

  }



  @Override

  public int hashCode() {

    if (hashCode > 0) {

      return hashCode;

    }

    hashCode = UUID.randomUUID().hashCode();

    return hashCode;

  }

}

// output:

1970-01-01 08:33:15

1970-01-01 08:33:10

1970-01-01 08:33:18

23 // 一千次任务总共创建了23个formator对象

-674481611

-424833271

-2124230669

411606156

-1600493931

900910308

540382160

-1054803206

...

因为线程池执行1000次任务并不是只创建了10个线程，其中仍然包括线程的销毁和新建，因此通常而言是不止10个formator对象被创建，符合预期。

典型场景2：

每个线程内需要有保存自己线程内部全局变量的地方，可以让不同的方法直接使用，避免参数传递麻烦，同时规避线程不安全行为。

典型场景2其实对于客户端来说比较少见，但是可以作为ThreadLocal的另外用法的演示，在使用场景1中，我们用到的是在ThreadLocal对象构造的时候主动去初始化我们希望通过它去保存的线程独有对象。

下面的场景是用来演示主动给ThreadLocal赋值：

举个例子如下图所示，每一个请求都是在一个thread中被处理的，然后通过层层Handler去传递和处理user信息。

这些信息在同一个线程内都是相同的，但是不同的线程使用的业务内容user是不同的，这个时候我们不能简单通过一个全局的变量去存储，因为这个全局变量是线程间都可见的，为此，我们可以声明一个map结构，去保存每一个线程所独有的user信息，key是这个线程，value是我们要保存的内容，为了线程安全，我们可以采取两种方式：

1. 给map的操作加锁（synchronized等）。


2. 借助线程安全的map数据结构来实现这个map，比如ConcurrentHashMap。

但是无论加锁还是CHM去实现，都免不得会面临线程同步互斥的压力，而这个场景下，ThreadLocal就是一个非常好的解决方式，无需同步互斥机制，在不影响性能的前提下，user参数也不需要通过函数入参的方式去层层传递，就可以达到保存当前线程（request）对应的用户信息的目的。

简单实现如下：

class UserContextHolder{

  public static ThreadLocal<User> holder = new ThreadLocal<>();

}



class Handler1{

  public void handle(){

    User user = new User();

    user.name = "UserInfo" + user.hashCode();

    // handler1通过set方法给当前线程的ThreadLoca<User>赋值

    UserContextHolder.holder.set(user);

  }

}



class Handler2{

  public void handle(){

    // handler2通过get方法获取到当前线程对应的user信息。

    System.out.println("UserInfo:" + UserContextHolder.holder.get());

  }

}

通过上面的例子，我们可以总结出ThreadLocal几个好处：

1. 线程安全的存储方式，因为每一个线程都会有自己独有的一份数据，不存在并发安全性。


2. 不需要加锁，执行效率肯定是比加锁同步的方式更高的。


3. 可以更高效利用内存，节省内存开销，见场景1，几遍有1000个任务，相比于原始的创建1000个SimpleDateFormator对象或者加锁，显然ThreadLocal是更好的方案。


4. 从场景2，我们也能看出，在某些场景下，可以简化我们传参的繁琐流程，降低代码的耦合程度。

ThreadLocal原理分析：

理解ThreadLocal需要先知道Thread，ThreadLocal，ThreadLocalMap三者之间的关系，如下图所示：

每一个Thread对象内部都有一个ThreadLocalMap变量，这个Map是一个散列表的数据结构，而Map的Entry的key是ThreadLocal对象，Value就是ThreadLocal对象要保存的Value对象。

ThreadLocalMap本身是一个数组结构的散列表，并非传统定义的Map结构，ThreadLocalMap在遇到hash冲突的时候，采用的是线性探测法去解决冲突 ，数组存放的Entry是ThreadLocal和Value对象。

static class Entry extends WeakReference<ThreadLocal<?>> {

    /** The value associated with this ThreadLocal. */

    Object value;



    Entry(ThreadLocal<?> k, Object v) {

        super(k);

        value = v;

    }

}

**尤其需要注意，ThreadLocal工作机制的核心是线程持有的ThreadLocalMap这个数据结构，而不是ThreadLocal自身。**有点绕，可以看下文的分析。

核心API解析：

initialValue:

该方法会返回当前线程对应的数据的初始值，并且这是一个延迟初始化的方法，不会在ThreadLocal对象构造的时候调用，而是在线程调用ThreadLocal#get方法的时候调用到。

get:

得到这个线程对应的Value值，如果首次调用，会通过initialize这个方法初始化。

set:

为这个线程设置一个新的Value。

remove:

删除这个线程设置的Value，后续再get，就会再次initialValue。

源码如下：

public T get() {

    Thread t = Thread.currentThread();

    ThreadLocalMap map = getMap(t);

    // JDK源码中上面两行代码其实等价于：

    // ThreadLocalMap map = t.threadLocals

    if (map != null) {

        // 获取到当前线程的ThreadLocalMap中存放的Entry

        // Entry的key其实就是this（ThreadLocal本身）

        ThreadLocalMap.Entry e = map.getEntry(this);

        if (e != null) {

            @SuppressWarnings("unchecked")

            T result = (T)e.value;

            // 返回ThreadLocal存放的对象本身。

            return result;

        }

    }

    // 如果上面没有找到，那么就会初始化

    return setInitialValue();

}

setInitialValue实现如下：

private T setInitialValue() {

    // 调用initialValue初始化ThreadLocal要保存的对象。

    T value = initialValue();

    Thread t = Thread.currentThread();

    // 拿到当前线程的ThreadLocalMap

    ThreadLocalMap map = getMap(t);

    // Thread#ThreadLocalMap的初始值是null

    if (map != null) {

        // 如果map有了，set存

        map.set(this, value);

    } else {

        // 否则就给当前Thread的threadLocals(即ThreadLocalMap)赋值并存入

        // 上面创建的Value。

        createMap(t, value);

    }

    if (this instanceof TerminatingThreadLocal) {

        TerminatingThreadLocal.register((TerminatingThreadLocal<?>) this);

    }

    // 将Value返回，作为get的返回值。

    return value;

}

再来看下set操作实现，其实就是做一件事，如果线程已经有了ThreadLocalMap，那么就直接存Value，如果线程没有ThreadLocalMap，就创建Map并且存Value。

    public void set(T value) {

        Thread t = Thread.currentThread();

        ThreadLocalMap map = getMap(t);

        if (map != null) {

            map.set(this, value);

        } else {

            createMap(t, value);

        }

    }

在这里我们也可以看到如果是通过initialValue将Value的初始值写入，那么就会调用setInitialValue，如果是通过set写入初始值，那么不会调用到setInitialValue。

同时，需要注意，initialValue通常是只会调用一次的，同一个线程重复get并不会触发多次init操作，但是如果通过remove这个API，主动移除Value，后续再get，还是会触发到initialValue这个方法的。

public void remove() {

    ThreadLocalMap m = getMap(Thread.currentThread());

    if (m != null) {

        m.remove(this);

    }

}

如果我们不主动重写initialValue这个方法，默认是返回null的，一般使用匿名内部类的方法来重写initialValue方法，这样方便在后续的使用中，可以直接使用，但是要注意，initialValue除非主动remove，否则是只会调用一次的，即仍然需要做空值确认。

ThreadLocal内存泄露：

ThreadLocal被讨论的最多的就是它可能导致内存泄露的问题。

我们看下ThreadLocalMap#Entry的定义：

static class Entry extends WeakReference<ThreadLocal<?>> {

    Object value;

    Entry(ThreadLocal<?> k, Object v) {

        super(k);

        value = v;

    }

}

ThreadLocalMap对Entry的引用是强引用，Entry对ThreadLocal的引用是弱引用，但是对Value的引用是强引用，这就可能会导致内存泄露。

正常情况下，当线程终止的时候，会将threadLocals置空，这看起来没有问题。

but：

如果线程不能终止，或者线程的存活时间比较久，那么Value对象将始终得不到回收，而如果Value对象再持有其它对象，比如Android当中的Activity，就会导致Activity的内存泄露，（Activity被销毁了，但是因为Value绑定的Thread还在运行状态，将导致Activity对象无法被GC回收）。

这个时候引用链就变成了如下：

Thread->ThreadLocalMap->Entry(key是null,Value不为空)->Value->Activity。

当然JDK其实已经考虑了这个问题，ThreadLocalMap在set，remove，rehash等方法中，都会主动扫描key为null的Entry，然后把对应的Value设置为null，这样原来Value对应的对象就可以被回收。

以resize为例：

private void resize() {

    Entry[] oldTab = table;

    int oldLen = oldTab.length;

    int newLen = oldLen * 2;

    Entry[] newTab = new Entry[newLen];

    int count = 0;



    for (Entry e : oldTab) {

        if (e != null) {

            ThreadLocal<?> k = e.get();

            // 遍历到key为null的时候就将value也设置为null。

            if (k == null) {

                e.value = null; // Help the GC

            } else {

                int h = k.threadLocalHashCode & (newLen - 1);

                while (newTab[h] != null)

                    h = nextIndex(h, newLen);

                newTab[h] = e;

                count++;

            }

        }

    }



    setThreshold(newLen);

    size = count;

    table = newTab;

}

但是但是，还是有问题：

如果Thread一直在运行，但是其所持有的ThreadLocalMap又没被用到了，此事上面那些set，remove，rehash方法都不会被调用，那还是存在内存泄露的问题......

按照阿里Java规范，ThreadLocal的最佳实践需要在ThreadLocal用完之后，主动去remove，回到典型场景2的代码，我们需要在Handler2的末尾，执行ThreadLoca.remove操作，或者在Handler链路过程中，如果逻辑无法运行到Handler2末尾，相应的异常处也需要处理remove。

装箱拆箱的NPE问题：

如果使用ThreadLocal去保存基本数据类型，需要注意空指针异常，因为ThreadLocal保存的只能是封箱之后的Object类型，在做拆箱操作的时候需要兼容空指针，如下代码所示：

public class ThreadLocalNPE {

  static ThreadLocal<Integer> intHolder = new ThreadLocal<>();

  static int getV(){

    return intHolder.get();

  }

  public static void main(String[] args) {

    getV();// 抛异常

  }

}

原因是我们在get之前没有主动set去赋值，getV中intHolder.get先拿到一个Integer的null值，null值转换为基本数据类型，当然报错，将getV的返回值修改为Integer即可。

ThreadPoolExecutor中知识点很多，本文只是从7个构造参数入手，看看其运转的核心思路。重点不是扣代码，是体会设计思想哈！
欢迎纠错和沟通。

ThreadPoolExecutor

以下是构造ThreadPoolExecutor的7大参数。

public ThreadPoolExecutor(int corePoolSize,

                          int maximumPoolSize,

                          long keepAliveTime,

                          TimeUnit unit,

                          BlockingQueue<Runnable> workQueue,

                          ThreadFactory threadFactory,

                          RejectedExecutionHandler handler) {

corePoolSize 和 maximumPoolSize 以及 workQueue（BlockingQueue）共同决定了线程池中线程的数量。
下面几条是我总结的观点：

1. 核心线程数小于等corePoolSize。


2. 普通线程在workQueue满了后才会创建。


3. 普通线程在任务结束后存活时长为：keepAliveTime*unit。


4. 任务总数如果超过了workQueue的容量+普通线程数，会触发 RejectedExecutionHandler。


5. 最好自定义ThreadFactory来创建线程，方便标识线程名等。


6. ThreadPoolExecutor提供了hook的方法beforeExecute()、afterExecute()


7. shutdown()不会立即停止线程池中的未完成的任务，shutdownNow()会。

这里有个设计上的亮点：它使用了一个AtomicInteger类型的ctl来同时记录线程池状态和线程池中线程数。ctl中高3位记录状态，低29位代表线程数量。
这种方法值得学习，除了节省变量，也减少了线程池状态和当前线程数量同步问题。

@ReachabilitySensitive

private final AtomicInteger ctl = new AtomicInteger(ctlOf(RUNNING, 0));

private static final int COUNT_BITS = Integer.SIZE - 3;

private static final int CAPACITY   = (1 << COUNT_BITS) - 1;



// runState is stored in the high-order bits

private static final int RUNNING    = -1 << COUNT_BITS;

private static final int SHUTDOWN   =  0 << COUNT_BITS;

private static final int STOP       =  1 << COUNT_BITS;

private static final int TIDYING    =  2 << COUNT_BITS;

private static final int TERMINATED =  3 << COUNT_BITS;



// Packing and unpacking ctl

private static int runStateOf(int c)     { return c & ~CAPACITY; }

private static int workerCountOf(int c)  { return c & CAPACITY; }

private static int ctlOf(int rs, int wc) { return rs | wc; }

核心代码区域execute()：

public void execute(Runnable command) {

    if (command == null)

        throw new NullPointerException();

   

    int c = ctl.get();

    if (workerCountOf(c) < corePoolSize) {

        //如果当前worker数量小于corePoolSize则创建新的核心Worker

        if (addWorker(command, true))

            return;

        c = ctl.get();

    }

    //线程池正在运行且可以正常添加任务(即workQueue还没有满)，此时等待任务执行即可。注意此处已经将新的Runnable存储到了workQueue里了。

    if (isRunning(c) && workQueue.offer(command)) {

        int recheck = ctl.get();

        if (! isRunning(recheck) && remove(command))

        //二次确认，此时线程池不属于运行状态，且刚添加进去的任务还没有执行，则reject

            reject(command);

        else if (workerCountOf(recheck) == 0)

        //线程池showdown中，后续应该什么都不会做直接return

            addWorker(null, false);

    }

    //workerQueue中满了，创建非核心worker，如果不成功则reject

    else if (!addWorker(command, false))

        reject(command);

}

看下addWorker()到底干了啥

private boolean addWorker(Runnable firstTask, boolean core) {

   

   retry:

    for (;;) {

        int c = ctl.get();

        int rs = runStateOf(c);

        //如果当前线程池停止了，或者 当前task为空且workQueue中没有任务了。这些情况可以直接退出该方法。

        // Check if queue empty only if necessary.

        if (rs >= SHUTDOWN &&

            ! (rs == SHUTDOWN &&

               firstTask == null &&

               ! workQueue.isEmpty()))

            return false;



        for (;;) {

            int wc = workerCountOf(c);

            if (wc >= CAPACITY ||

                wc >= (core ? corePoolSize : maximumPoolSize))

                return false;

            if (compareAndIncrementWorkerCount(c))

                break retry;

            c = ctl.get();  // Re-read ctl

            if (runStateOf(c) != rs)

                continue retry;

            // else CAS failed due to workerCount change; retry inner loop

        }

    }



    boolean workerStarted = false;

    boolean workerAdded = false;

    Worker w = null;

    try {

        w = new Worker(firstTask);

        final Thread t = w.thread;

        if (t != null) {

            final ReentrantLock mainLock = this.mainLock;

            mainLock.lock();

            try {

                // Recheck while holding lock.

                // Back out on ThreadFactory failure or if

                // shut down before lock acquired.

                int rs = runStateOf(ctl.get());



                if (rs < SHUTDOWN ||

                    (rs == SHUTDOWN && firstTask == null)) {

                    if (t.isAlive()) // precheck that t is startable

                        throw new IllegalThreadStateException();

                    workers.add(w);

                    int s = workers.size();

                    if (s > largestPoolSize)

                        largestPoolSize = s;

                    workerAdded = true;

                }

            } finally {

                mainLock.unlock();

            }

            if (workerAdded) {

                t.start();

                workerStarted = true;

            }

        }

    } finally {

        if (! workerStarted)

            addWorkerFailed(w);

    }

    return workerStarted;

}

上面代码，除了线程池状态校验以及保证代码的异步安全，核心就是：

 w = new Worker(firstTask);

 final Thread t = w.thread;

 t.start()；

创建一个Worker并启动其中的线程。

Worker

Worker是什么？Worker是ThreadPoolExecutor的内部类，ThreadPoolExecutor中把excute()传递进来的Runnable认为是一个Work，那么执行Work的就是Worker了。

private final class Worker

    extends AbstractQueuedSynchronizer

    implements Runnable

{



    /** Thread this worker is running in.  Null if factory fails. */

    final Thread thread;

    /** Initial task to run.  Possibly null. */

    Runnable firstTask;

    /** Per-thread task counter */

    volatile long completedTasks;



    /**

     * Creates with given first task and thread from ThreadFactory.

     * @param firstTask the first task (null if none)

     */

    Worker(Runnable firstTask) {

        setState(-1); // inhibit interrupts until runWorker

        this.firstTask = firstTask;

        this.thread = getThreadFactory().newThread(this);

    }



    public void run() {

        runWorker(this);

    }

    

 }

Worker的构造函数中持有了传入的Task,并通过ThreadFactory创建了个新的线程。

note: 新创建的线程持有了Worker对象自己，而Worker本身又实现了Runnable接口。所以当该线程启动时，run()就会被执行。

看下Worker的run()方法具体干了什么？

首先里面有个while循环，主要是获取task的，如果task一直能获取到，则就能执行到while内部。

1. 当前task非空，即核心线程创建的时候，自带了一个task。会触发task.run()方法，并在它前后分别又beforeExecute(wt, task)和afterExecute(task, thrown)hook点。


2. 当前task==null，就需要到getTask()中获取。

final void runWorker(Worker w) {

    Thread wt = Thread.currentThread();

    Runnable task = w.firstTask;

    w.firstTask = null;

    w.unlock(); // allow interrupts

    boolean completedAbruptly = true;

    try {

        while (task != null || (task = getTask()) != null) {

            w.lock();

            // If pool is stopping, ensure thread is interrupted;

            // if not, ensure thread is not interrupted.  This

            // requires a recheck in second case to deal with

            // shutdownNow race while clearing interrupt

            if ((runStateAtLeast(ctl.get(), STOP) ||

                 (Thread.interrupted() &&

                  runStateAtLeast(ctl.get(), STOP))) &&

                !wt.isInterrupted())

                wt.interrupt();

            try {

                beforeExecute(wt, task);

                Throwable thrown = null;

                try {

                    task.run();

                } catch (RuntimeException x) {

                    thrown = x; throw x;

                } catch (Error x) {

                    thrown = x; throw x;

                } catch (Throwable x) {

                    thrown = x; throw new Error(x);

                } finally {

                    afterExecute(task, thrown);

                }

            } finally {

                task = null;

                w.completedTasks++;

                w.unlock();

            }

        }

        completedAbruptly = false;

    } finally {

        processWorkerExit(w, completedAbruptly);

    }

}

getTask()就跟ThreadPoolExecutor构造函数中的BlockQueue关联上了。当前线程如果执行完第一个Task后，应该怎么办呢？如果还不满足结束条件(比如说存活时间超过keepAlive*unit)，则会向worksQueue（BlockQueue）中所要任务，然后执行。

private Runnable getTask() {

    boolean timedOut = false; // Did the last poll() time out?



    for (;;) {

        int c = ctl.get();

        int rs = runStateOf(c);



        // Check if queue empty only if necessary.

        if (rs >= SHUTDOWN && (rs >= STOP || workQueue.isEmpty())) {

            decrementWorkerCount();

            return null;

        }



        int wc = workerCountOf(c);



        // Are workers subject to culling?

        boolean timed = allowCoreThreadTimeOut || wc > corePoolSize;



        if ((wc > maximumPoolSize || (timed && timedOut))

            && (wc > 1 || workQueue.isEmpty())) {

            if (compareAndDecrementWorkerCount(c))

                return null;

            continue;

        }



        try {

            Runnable r = timed ?

                workQueue.poll(keepAliveTime, TimeUnit.NANOSECONDS) :

                workQueue.take();

            if (r != null)

                return r;

            timedOut = true;

        } catch (InterruptedException retry) {

            timedOut = false;

        }

    }

}

上面前段代码就是判断当前线程池是否还能继续存在，如果能存在并且未超时，那么就从workQueue中取task()。Runnable r = timed ?workQueue.poll(keepAliveTime, TimeUnit.NANOSECONDS):workQueue.take();

/**

 * Retrieves and removes the head of this queue, waiting if necessary

 * until an element becomes available.

 *

 * @return the head of this queue

 * @throws InterruptedException if interrupted while waiting

 */

E take() throws InterruptedException;

是个阻塞的行为。所以TheadPoolExecutor中的workQueue参数传入哪种类型的BlockQueue直接影响了未执行任务的执行顺序。 不过需要注意的是即使使用了优先级队列，高优先级的任务也不一定比低优先级任务先执行，因为任务是由线程发起的，workQueue没法影响线程的执行顺序。

一、题目

难度中等

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"输出: 3解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个*子序列，*不是子串。

示例 4:

输入: s = ""输出: 0

提示：

• 0 <= s.length <= 5 * 104

• s 由英文字母、数字、符号和空格组成

二、我的解答

第一次解答：

我的思路跟官方的差不多，把光标从第一个开始，寻找最长

只不过我是每次删除第一个就全部重新加，而不是他那个窗口移动的概念

public static int lengthOfLongestSubstring(String s) {

    int selection = 0;

    int maxSize=0;

    while (selection < s.length()) {

        HashMap map = new HashMap<>();

        List mapList = new ArrayList<>();

        for (int i = selection; i < s.length(); i++) {

            char val = s.charAt(i);

            if (!map.containsKey(val)) {

                map.put(val, val);

                mapList.add(val);

            } else {

                break;

            }

        }

        maxSize=Math.max(mapList.size(),maxSize);

        selection++;

        if (mapList.size() >= (s.length() - selection)) {

            break;

        }

    }

    return maxSize;

}

通过：

三、系统解答

方法一：滑动窗口

思路及算法

我们先用一个例子考虑如何在较优的时间复杂度内通过本题。

我们不妨以示例一中的字符串abcabcbb 为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：

以(a)bcabcbb 开始的最长字符串为(abc)abcbb；

以a(b)cabcbb 开始的最长字符串为a(bca)bcbb；

以 ab(c)abcbb 开始的最长字符串为ab(cab)cbb；

以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb；

以 abca(b)cbb 开始的最长字符串为abca(bc)bb；

以abcab(c)bb 开始的最长字符串为abcab(cb)b；

以abcabc(b)b 开始的最长字符串为abcabc(b)b；

以abcabcb(b) 开始的最长字符串为 abcabcb(b)。

发现了什么？如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！这里的原因在于，假设我们选择字符串中的第 k 个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为 r_k 。那么当我们选择第 k+1 个字符作为起始位置时，首先从 k+1到 r_k的字符显然是不重复的，并且由于少了原本的第 k 个字符，我们可以尝试继续增大 r_k，直到右侧出现了重复字符为止。

这样一来，我们就可以使用「滑动窗口」来解决这个问题了：

我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为上文中的 r_k；

在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；

在枚举结束后，我们找到的最长的子串的长度即为答案。

判断重复字符

在上面的流程中，我们还需要使用一种数据结构来判断是否有重复的字符，常用的数据结构为哈希集合（即 C++ 中的 std::unordered_set，Java 中的 HashSet，Python 中的 set, JavaScript 中的 Set）。在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合中添加一个字符。

至此，我们就完美解决了本题。

注释：思路和我一样，代码比我写的简单太多了吧

class Solution {    public int lengthOfLongestSubstring(String s) {

        // 哈希集合，记录每个字符是否出现过

        Set<Character> occ = new HashSet<Character>();

        int n = s.length();

        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动

        int rk = -1, ans = 0;

        for (int i = 0; i < n; ++i) {

            if (i != 0) {

                // 左指针向右移动一格，移除一个字符

                occ.remove(s.charAt(i - 1));

            }

            //判断rk+1<n是为了确定右指针是否已经走到了最后

            //右指针走到最后的情况，说明后续都可以走到最后，只需用rk-i+1确定

            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {

                // 不断地移动右指针

                occ.add(s.charAt(rk + 1));

                ++rk;

            }

            // 第 i 到 rk 个字符是一个极长的无重复字符子串

            ans = Math.max(ans, rk - i + 1);

        }

        return ans;

    }

}

复杂度分析

• 时间复杂度：O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。

• 空间复杂度：O(∣Σ∣)，其中Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0,128) 内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)。

这个网友的很精彩

class Solution {    public int lengthOfLongestSubstring(String s) {

        // 记录字符上一次出现的位置

        int[] last = new int[128];

        for(int i = 0; i < 128; i++) {

            last[i] = -1;

        }

        int n = s.length();



        int res = 0;

        int start = 0; // 窗口开始位置

        for(int i = 0; i < n; i++) {

            int index = s.charAt(i);

            start = Math.max(start, last[index] + 1);

            res   = Math.max(res, i - start + 1);

            last[index] = i;

        }



        return res;

    }

}

答案有个缺点，左指针并不需要依次递增，即多了很多无谓的循环。 发现有重复字符时，可以直接把左指针移动到第一个重复字符的下一个位置即可。

每次左指针右移一位，移除set的一个字符，这一步会导致很多无用的循环。while循环发现的重复字符不一定就是Set最早添加那个，还要好多次循环才能到达，这些都是无效循环，不如直接用map记下每个字符的索引，直接进行跳转

文字环绕

需求

最近接到一个需求，类似于文字环绕，标题最多两行，超出省略，标题后面可以添加标签。效果如下：

富文本不能控制省略和折行，Flutter 提供了 TextPainter可以实现。

分析

标签有文字和颜色两个属性，个数不定：

class Tag {



  /// 标签文本

  final String label;

  /// 标签背景颜色

  final Color color;



  Tag({required this.label, required this.color});

}

标题最大行数可变，可能明天产品要最多显示三行；

文本样式可变；

先创建出来对应的Widget：

class TagTitle extends StatefulWidget {

  const TagTitle(

    this.text, {

    Key? key,

    required this.tags,

    this.maxLines = 2,

    this.style = const TextStyle(color: Colors.black, fontSize: 16),

  }) : super(key: key);

  

  final String text;

  final int maxLines;

  final TextStyle style;

  final List<Tag> tags;

  }

实现

标题文字和标签文字有两种显示情况：

1. 超出最大行数；


2. 未超出最大行数；

先假设第一种情况，因为标签前后有间距，所以每个标签前后补一个空格，再把标题和文字拼接创建对应的TextSpan：

    tagTexts = widget.tags.fold<String>(

        ' ', (previousValue, element) => '$previousValue${element.label} ');

        

    _allSp = TextSpan(

      text: '${widget.text}$tagTexts',

      style: widget.style,

    );

        

要绘制标题、省略号、标签、都需要TextSpan，所以一并创建出来，当然还有最重要的TextPainter：

// 标签

final tagsSp = TextSpan(

  text: tagTexts,

  style: widget.style,

);



// 省略号

final ellipsizeTextSp = TextSpan(

  text: ellipsizeText,

  style: widget.style,

);



// 标题

final textSp = TextSpan(

  text: widget.text,

  style: widget.style,

);



final textPainter = TextPainter(

  text: tagsSp,

  textDirection: TextDirection.ltr,

  maxLines: widget.maxLines,

)..layout(

    minWidth: constraints.minWidth,

    maxWidth: constraints.maxWidth,

  );

拿到标签、省略号、标题的尺寸：

final tagsSize = textPainter.size;



textPainter.text = ellipsizeTextSp;

textPainter.layout(

  minWidth: constraints.minWidth,

  maxWidth: constraints.maxWidth,

);



final ellipsizeSize = textPainter.size;



textPainter.text = textSp;

textPainter.layout(

  minWidth: constraints.minWidth,

  maxWidth: constraints.maxWidth,

);

final textSize = textPainter.size;

算出标题超出最大长度的位置：

textPainter.text = _allSp;

textPainter.layout(

  minWidth: constraints.minWidth,

  maxWidth: constraints.maxWidth,

);



final pos = textPainter.getPositionForOffset(Offset(

  textSize.width - tagsSize.width - ellipsizeSize.width,

  textSize.height,

));



final endIndex = textPainter.getOffsetBefore(pos.offset);

如果超出的话，文字显示区域的宽度减去标签宽度减去省略号宽度，剩下的位置就是标题最大宽度偏移量，根据偏移量得到此位置的文字位置下标。

textPainter.didExceedMaxLines返回的是是否超出最大长度，也就是一开始分析的两种情况的哪一种，如果超出，就根据上面计算出来的下标截取标题文字，添加省略号，然后添加上标签；否则，直接显示标题文本和标签：

TextSpan textSpan;



if (textPainter.didExceedMaxLines) {

  textSpan = TextSpan(

    style: widget.style,

    text: widget.text.substring(0, endIndex) + ellipsizeText,

    children: _getWidgetSpan(),

  );

} else {

  textSpan = TextSpan(

    style: widget.style,

    text: widget.text,

    children: _getWidgetSpan(),

  );

}

return RichText(

  text: textSpan,

  overflow: TextOverflow.ellipsis,

  maxLines: widget.maxLines,

);

标签因为带有背景，所以可以用WidgetSpan加上标签背景，这里使用CustomPaint实现：

List<WidgetSpan> _getWidgetSpan() {

  return widget.tags

      .map((e) => WidgetSpan(

            child: CustomPaint(

              painter: BgPainter(e.color),

              child: Text(

                ' ' + e.label + ' ',

                style: widget.style,

              ),

            ),

          ))

      .toList();

}

这个BgPainter就一个功能，绘制背景色：

class BgPainter extends CustomPainter {

  final Paint _painter;



  final Color color;



  BgPainter(this.color) : _painter = Paint()..color = color;



  @override

  void paint(Canvas canvas, Size size) {

    canvas.drawRect(Rect.fromLTWH(2, 0, size.width - 2, size.height), _painter);

  }



  @override

  bool shouldRepaint(covariant CustomPainter oldDelegate) =>

      oldDelegate != this;

}

使用：

TagTitle(

  '据法新社报道，法国总统府爱丽舍宫发布消息称，法国',

  tags: [

    Tag(label: '热门', color: Colors.red),

    Tag(label: '国际', color: Colors.blue),

  ],

),

const Divider(

  color: Color(0xFF167F67),

),

TagTitle(

  '据法新社报道，法国总统府爱丽舍宫发布消息称，法国总统马克龙提议俄罗斯总统普京和美国总统sadaasdadadada',

  tags: [

    Tag(label: '热门', color: Colors.red),

    Tag(label: '国际', color: Colors.blue),

  ],

),

const Divider(

  color: Color(0xFF167F67),

),

TagTitle(

  '据法新社报道，法国总统府爱丽舍宫发布',

  tags: [

    Tag(label: '热门', color: Colors.red),

    Tag(label: '国际', color: Colors.blue),

  ],

),

const Divider(

  color: Color(0xFF167F67),

),

TagTitle(

  '据法新社报道，法国总统府爱丽舍宫发布消息称，法国总统马克龙提议俄罗',

  tags: [

    Tag(label: '热门', color: Colors.red),

    Tag(label: '国际', color: Colors.blue),

  ],

),

附上完整代码：

main.dart

import 'package:custom/review/tag_title.dart';

import 'package:flutter/material.dart';



void main() {

  runApp(const MyApp());

}



class MyApp extends StatelessWidget {

  const MyApp({Key? key}) : super(key: key);



  @override

  Widget build(BuildContext context) {

    return MaterialApp(

      title: 'Flutter Demo',

      theme: ThemeData(

        primarySwatch: Colors.blue,

      ),

      home: const MyHomePage(title: 'Flutter Demo Home Page'),

    );

  }

}



class MyHomePage extends StatefulWidget {

  const MyHomePage({Key? key, required this.title}) : super(key: key);



  final String title;



  @override

  State<MyHomePage> createState() => _MyHomePageState();

}



class _MyHomePageState extends State<MyHomePage> {

  @override

  Widget build(BuildContext context) {

    return Scaffold(

      appBar: AppBar(

        title: Text(widget.title),

      ),

      body: Column(

        crossAxisAlignment: CrossAxisAlignment.start,

        children: [

          TagTitle(

            '据法新社报道，法国总统府爱丽舍宫发布消息称，法国',

            tags: [

              Tag(label: '热门', color: Colors.red),

              Tag(label: '国际', color: Colors.blue),

            ],

          ),

          const Divider(

            color: Color(0xFF167F67),

          ),

          TagTitle(

            '据法新社报道，法国总统府爱丽舍宫发布消息称，法国总统马克龙提议俄罗斯总统普京和美国总统sadaasdadadada',

            tags: [

              Tag(label: '热门', color: Colors.red),

              Tag(label: '国际', color: Colors.blue),

            ],

          ),

          const Divider(

            color: Color(0xFF167F67),

          ),

          TagTitle(

            '据法新社报道，法国总统府爱丽舍宫发布',

            tags: [

              Tag(label: '热门', color: Colors.red),

              Tag(label: '国际', color: Colors.blue),

            ],

          ),

          const Divider(

            color: Color(0xFF167F67),

          ),

          TagTitle(

            '据法新社报道，法国总统府爱丽舍宫发布消息称，法国总统马克龙提议俄罗',

            tags: [

              Tag(label: '热门', color: Colors.red),

              Tag(label: '国际', color: Colors.blue),

            ],

          ),

        ],

      ),

    );

  }

}

Tag_title.dart:

//@dart=2.12

import 'package:flutter/material.dart';



import 'bg_painter.dart';



class TagTitle extends StatefulWidget {

  const TagTitle(

    this.text, {

    Key? key,

    required this.tags,

    this.maxLines = 2,

    this.style = const TextStyle(color: Colors.black, fontSize: 16),

  }) : super(key: key);



  final String text;

  final int maxLines;

  final TextStyle style;

  final List<Tag> tags;



  @override

  TagTitleState createState() => TagTitleState();

}



class TagTitleState extends State<TagTitle> {

  late final String tagTexts;

  late final TextSpan _allSp;

  final String ellipsizeText = '...';



  @override

  void initState() {

    super.initState();

    tagTexts = widget.tags.fold<String>(

        ' ', (previousValue, element) => '$previousValue${element.label} ');

    _allSp = TextSpan(

      text: '${widget.text}$tagTexts',

      style: widget.style,

    );

  }



  List<WidgetSpan> _getWidgetSpan() {

    return widget.tags

        .map((e) => WidgetSpan(

              child: CustomPaint(

                painter: BgPainter(e.color),

                child: Text(

                  ' ' + e.label + ' ',

                  style: widget.style,

                ),

              ),

            ))

        .toList();

  }



  @override

  Widget build(BuildContext context) {

    return LayoutBuilder(

      builder: (BuildContext context, BoxConstraints constraints) {

        assert(constraints.hasBoundedWidth);

        // 标签

        final tagsSp = TextSpan(

          text: tagTexts,

          style: widget.style,

        );



        // 省略号

        final ellipsizeTextSp = TextSpan(

          text: ellipsizeText,

          style: widget.style,

        );



        // 标题

        final textSp = TextSpan(

          text: widget.text,

          style: widget.style,

        );



        final textPainter = TextPainter(

          text: tagsSp,

          textDirection: TextDirection.ltr,

          maxLines: widget.maxLines,

        )..layout(

            minWidth: constraints.minWidth,

            maxWidth: constraints.maxWidth,

          );

        final tagsSize = textPainter.size;



        textPainter.text = ellipsizeTextSp;

        textPainter.layout(

          minWidth: constraints.minWidth,

          maxWidth: constraints.maxWidth,

        );



        final ellipsizeSize = textPainter.size;



        textPainter.text = textSp;

        textPainter.layout(

          minWidth: constraints.minWidth,

          maxWidth: constraints.maxWidth,

        );

        final textSize = textPainter.size;



        textPainter.text = _allSp;

        textPainter.layout(

          minWidth: constraints.minWidth,

          maxWidth: constraints.maxWidth,

        );



        final pos = textPainter.getPositionForOffset(Offset(

          textSize.width - tagsSize.width - ellipsizeSize.width,

          textSize.height,

        ));



        final endIndex = textPainter.getOffsetBefore(pos.offset);



        TextSpan textSpan;



        if (textPainter.didExceedMaxLines) {

          textSpan = TextSpan(

            style: widget.style,

            text: widget.text.substring(0, endIndex) + ellipsizeText,

            children: _getWidgetSpan(),

          );

        } else {

          textSpan = TextSpan(

            style: widget.style,

            text: widget.text,

            children: _getWidgetSpan(),

          );

        }

        return RichText(

          text: textSpan,

          overflow: TextOverflow.ellipsis,

          maxLines: widget.maxLines,

        );

      },

    );

  }

}

class Tag {



  /// 标签文本

  final String label;

  /// 标签背景颜色

  final Color color;



  Tag({required this.label, required this.color});

}

bg_painter.dart:

//@dart=2.12

import 'dart:ui' as ui;



import 'package:flutter/cupertino.dart';

import 'package:flutter/material.dart';



class BgPainter extends CustomPainter {

  final Paint _painter;



  final Color color;



  BgPainter(this.color) : _painter = Paint()..color = color;



  @override

  void paint(Canvas canvas, Size size) {

    canvas.drawRect(Rect.fromLTWH(2, 0, size.width - 2, size.height), _painter);

  }



  @override

  bool shouldRepaint(covariant CustomPainter oldDelegate) =>

      oldDelegate != this;

}