项目简介

此框架旨在将常规的Flutter项目中使用到的通用（与业务无关）的功能从剥离出来，构成Flutter开发项目的框架，在开发新的Flutter项目时，可以直接引用本项目 import 'package:framework/framework.dart'来使用框架中相关的功能，提升开发效率。

Github项目地址：可以看我主页找我拿

此框架目前包含以下功能模块：接口请求API模块、消息提示模块、路由模块、统一错误处理、日志模块、屏幕适配测试、自定义UI组件库、本地存储模块构成

框架使用说明

引用

import 'package:framework/framework.dart';

使用

参考 Example 中使用的例子

框架首页

网络HTTP模块

消息提示模块

路由模块

统一错误处理介绍

日志模块

屏幕适配测试

自定义UI组件库

本地存储模块

前言

OkHttp可以说是Android开发中最常见的网络请求框架,OkHttp使用方便，扩展性强，功能强大，OKHttp源码与原理也是面试中的常客

但是OKHttp的源码内容比较多，想要学习它的源码往往千头万绪，一时抓不住重点.

本文从几个问题出发梳理OKHttp相关知识点，以便快速构建OKHttp知识体系，如果对你有用，欢迎点赞~

本文主要包括以下内容

1. OKHttp请求的整体流程是怎样的?


2. OKHttp分发器是怎样工作的?


3. OKHttp拦截器是如何工作的?


4. 应用拦截器和网络拦截器有什么区别?


5. OKHttp如何复用TCP连接?


6. OKHttp空闲连接如何清除?


7. OKHttp有哪些优点?


8. OKHttp框架中用到了哪些设计模式?

1. OKHttp请求整体流程介绍

首先来看一个最简单的Http请求是如何发送的。

   val okHttpClient = OkHttpClient()

   val request: Request = Request.Builder()

       .url("https://www.google.com/")

       .build()



   okHttpClient.newCall(request).enqueue(object :Callback{

       override fun onFailure(call: Call, e: IOException) {

       }



       override fun onResponse(call: Call, response: Response) {

       }

   })

这段代码看起来比较简单,OkHttp请求过程中最少只需要接触OkHttpClient、Request、Call、 Response，但是框架内部会进行大量的逻辑处理。

所有网络请求的逻辑大部分集中在拦截器中，但是在进入拦截器之前还需要依靠分发器来调配请求任务。

关于分发器与拦截器，我们在这里先简单介绍下，后续会有更加详细的讲解

• 分发器:内部维护队列与线程池，完成请求调配;


• 拦截器:五大默认拦截器完成整个请求过程。

整个网络请求过程大致如上所示

1. 通过建造者模式构建OKHttpClient与 Request


2. OKHttpClient通过newCall发起一个新的请求


3. 通过分发器维护请求队列与线程池，完成请求调配


4. 通过五大默认拦截器完成请求重试，缓存处理，建立连接等一系列操作


5. 得到网络请求结果

2. OKHttp分发器是怎样工作的?

分发器的主要作用是维护请求队列与线程池,比如我们有100个异步请求，肯定不能把它们同时请求，而是应该把它们排队分个类，分为正在请求中的列表和正在等待的列表，
等请求完成后，即可从等待中的列表中取出等待的请求，从而完成所有的请求

而这里同步请求各异步请求又略有不同

同步请求

synchronized void executed(RealCall call) {

	runningSyncCalls.add(call);

}

因为同步请求不需要线程池，也不存在任何限制。所以分发器仅做一下记录。后续按照加入队列的顺序同步请求即可

异步请求

synchronized void enqueue(AsyncCall call) {

	//请求数最大不超过64,同一Host请求不能超过5个

	if (runningAsyncCalls.size() < maxRequests && runningCallsForHost(call) < maxRequestsPerHost) 	  {

		runningAsyncCalls.add(call);

		executorService().execute(call);

	} else {

		readyAsyncCalls.add(call);

	}

}

当正在执行的任务未超过最大限制64，同时同一Host的请求不超过5个，则会添加到正在执行队列，同时提交给线程池。否则先加入等待队列。

每个任务完成后，都会调用分发器的finished方法,这里面会取出等待队列中的任务继续执行

3. OKHttp拦截器是怎样工作的?

经过上面分发器的任务分发，下面就要利用拦截器开始一系列配置了

# RealCall

  override fun execute(): Response {

    try {

      client.dispatcher.executed(this)

      return getResponseWithInterceptorChain()

    } finally {

      client.dispatcher.finished(this)

    }

  }

我们再来看下RealCall的execute方法，可以看出，最后返回了getResponseWithInterceptorChain,责任链的构建与处理其实就是在这个方法里面

internal fun getResponseWithInterceptorChain(): Response {

    // Build a full stack of interceptors.

    val interceptors = mutableListOf<Interceptor>()

    interceptors += client.interceptors

    interceptors += RetryAndFollowUpInterceptor(client)

    interceptors += BridgeInterceptor(client.cookieJar)

    interceptors += CacheInterceptor(client.cache)

    interceptors += ConnectInterceptor

    if (!forWebSocket) {

      interceptors += client.networkInterceptors

    }

    interceptors += CallServerInterceptor(forWebSocket)



    val chain = RealInterceptorChain(

        call = this,interceptors = interceptors,index = 0

    )

    val response = chain.proceed(originalRequest)

  }

如上所示，构建了一个OkHttp拦截器的责任链

责任链，顾名思义，就是用来处理相关事务责任的一条执行链，执行链上有多个节点，每个节点都有机会（条件匹配）处理请求事务，如果某个节点处理完了就可以根据实际业务需求传递给下一个节点继续处理或者返回处理完毕。

如上所示责任链添加的顺序及作用如下表所示：

我们的网络请求就是这样经过责任链一级一级的递推下去，最终会执行到CallServerInterceptor的intercept方法，此方法会将网络响应的结果封装成一个Response对象并return。之后沿着责任链一级一级的回溯，最终就回到getResponseWithInterceptorChain方法的返回,如下图所示：

4. 应用拦截器和网络拦截器有什么区别?

从整个责任链路来看，应用拦截器是最先执行的拦截器，也就是用户自己设置request属性后的原始请求，而网络拦截器位于ConnectInterceptor和CallServerInterceptor之间，此时网络链路已经准备好，只等待发送请求数据。它们主要有以下区别

1. 首先，应用拦截器在RetryAndFollowUpInterceptor和CacheInterceptor之前，所以一旦发生错误重试或者网络重定向，网络拦截器可能执行多次，因为相当于进行了二次请求，但是应用拦截器永远只会触发一次。另外如果在CacheInterceptor中命中了缓存就不需要走网络请求了，因此会存在短路网络拦截器的情况。


2. 其次，除了CallServerInterceptor之外，每个拦截器都应该至少调用一次realChain.proceed方法。实际上在应用拦截器这层可以多次调用proceed方法（本地异常重试）或者不调用proceed方法（中断），但是网络拦截器这层连接已经准备好，可且仅可调用一次proceed方法。


3. 最后，从使用场景看，应用拦截器因为只会调用一次，通常用于统计客户端的网络请求发起情况；而网络拦截器一次调用代表了一定会发起一次网络通信，因此通常可用于统计网络链路上传输的数据。

5. OKHttp如何复用TCP连接?

ConnectInterceptor的主要工作就是负责建立TCP连接，建立TCP连接需要经历三次握手四次挥手等操作，如果每个HTTP请求都要新建一个TCP消耗资源比较多

而Http1.1已经支持keep-alive,即多个Http请求复用一个TCP连接，OKHttp也做了相应的优化，下面我们来看下OKHttp是怎么复用TCP连接的

ConnectInterceptor中查找连接的代码会最终会调用到ExchangeFinder.findConnection方法，具体如下：

# ExchangeFinder

//为承载新的数据流 寻找 连接。寻找顺序是 已分配的连接、连接池、新建连接

private RealConnection findConnection(int connectTimeout, int readTimeout, int writeTimeout,

    int pingIntervalMillis, boolean connectionRetryEnabled) throws IOException {

  synchronized (connectionPool) {

    // 1.尝试使用 已给数据流分配的连接.（例如重定向请求时，可以复用上次请求的连接）

    releasedConnection = transmitter.connection;

    result = transmitter.connection;



    if (result == null) {

      // 2. 没有已分配的可用连接，就尝试从连接池获取。（连接池稍后详细讲解）

      if (connectionPool.transmitterAcquirePooledConnection(address, transmitter, null, false)) {

        result = transmitter.connection;

      }

    }

  }



  synchronized (connectionPool) {

    if (newRouteSelection) {

      //3. 现在有了IP地址，再次尝试从连接池获取。可能会因为连接合并而匹配。（这里传入了routes，上面的传的null）

      routes = routeSelection.getAll();

      if (connectionPool.transmitterAcquirePooledConnection(address, transmitter, routes, false)) {

        foundPooledConnection = true;

        result = transmitter.connection;

      }

    }



  // 4.第二次没成功，就把新建的连接，进行TCP + TLS 握手，与服务端建立连接. 是阻塞操作

  result.connect(connectTimeout, readTimeout, writeTimeout, pingIntervalMillis,

      connectionRetryEnabled, call, eventListener);



  synchronized (connectionPool) {

    // 5. 最后一次尝试从连接池获取，注意最后一个参数为true，即要求 多路复用（http2.0）

    //意思是，如果本次是http2.0，那么为了保证 多路复用性，（因为上面的握手操作不是线程安全）会再次确认连接池中此时是否已有同样连接

    if (connectionPool.transmitterAcquirePooledConnection(address, transmitter, routes, true)) {

      // 如果获取到，就关闭我们创建里的连接，返回获取的连接

      result = transmitter.connection;

    } else {

      //最后一次尝试也没有的话，就把刚刚新建的连接存入连接池

      connectionPool.put(result);

    }

  }

 

  return result;

}

上面精简了部分代码，可以看出，连接拦截器使用了5种方法查找连接

1. 首先会尝试使用 已给请求分配的连接。（已分配连接的情况例如重定向时的再次请求，说明上次已经有了连接）


2. 若没有 已分配的可用连接，就尝试从连接池中 匹配获取。因为此时没有路由信息，所以匹配条件：address一致——host、port、代理等一致，且匹配的连接可以接受新的请求。


3. 若从连接池没有获取到，则传入routes再次尝试获取，这主要是针对Http2.0的一个操作,Http2.0可以复用square.com与square.ca的连接


4. 若第二次也没有获取到，就创建RealConnection实例，进行TCP + TLS握手，与服务端建立连接。


5. 此时为了确保Http2.0连接的多路复用性，会第三次从连接池匹配。因为新建立的连接的握手过程是非线程安全的，所以此时可能连接池新存入了相同的连接。


6. 第三次若匹配到，就使用已有连接，释放刚刚新建的连接；若未匹配到，则把新连接存入连接池并返回。

以上就是连接拦截器尝试复用连接的操作，流程图如下：

6. OKHttp空闲连接如何清除?

上面说到我们会建立一个TCP连接池，但如果没有任务了，空闲的连接也应该及时清除，OKHttp是如何做到的呢?

  # RealConnectionPool

  private val cleanupQueue: TaskQueue = taskRunner.newQueue()

  private val cleanupTask = object : Task("$okHttpName ConnectionPool") {

    override fun runOnce(): Long = cleanup(System.nanoTime())

  }



  long cleanup(long now) {

    int inUseConnectionCount = 0;//正在使用的连接数

    int idleConnectionCount = 0;//空闲连接数

    RealConnection longestIdleConnection = null;//空闲时间最长的连接

    long longestIdleDurationNs = Long.MIN_VALUE;//最长的空闲时间



    //遍历连接：找到待清理的连接, 找到下一次要清理的时间（还未到最大空闲时间）

    synchronized (this) {

      for (Iterator<RealConnection> i = connections.iterator(); i.hasNext(); ) {

        RealConnection connection = i.next();



        //若连接正在使用，continue，正在使用连接数+1

        if (pruneAndGetAllocationCount(connection, now) > 0) {

          inUseConnectionCount++;

          continue;

        }

		//空闲连接数+1

        idleConnectionCount++;



        // 赋值最长的空闲时间和对应连接

        long idleDurationNs = now - connection.idleAtNanos;

        if (idleDurationNs > longestIdleDurationNs) {

          longestIdleDurationNs = idleDurationNs;

          longestIdleConnection = connection;

        }

      }

	  //若最长的空闲时间大于5分钟 或 空闲数 大于5，就移除并关闭这个连接

      if (longestIdleDurationNs >= this.keepAliveDurationNs

          || idleConnectionCount > this.maxIdleConnections) {

        connections.remove(longestIdleConnection);

      } else if (idleConnectionCount > 0) {

        // else，就返回 还剩多久到达5分钟，然后wait这个时间再来清理

        return keepAliveDurationNs - longestIdleDurationNs;

      } else if (inUseConnectionCount > 0) {

        //连接没有空闲的，就5分钟后再尝试清理.

        return keepAliveDurationNs;

      } else {

        // 没有连接，不清理

        cleanupRunning = false;

        return -1;

      }

    }

	//关闭移除的连接

    closeQuietly(longestIdleConnection.socket());



    //关闭移除后 立刻 进行下一次的 尝试清理

    return 0;

  }

思路还是很清晰的：

1. 在将连接加入连接池时就会启动定时任务


2. 有空闲连接的话，如果最长的空闲时间大于5分钟 或 空闲数 大于5，就移除关闭这个最长空闲连接；如果 空闲数 不大于5 且 最长的空闲时间不大于5分钟，就返回到5分钟的剩余时间，然后等待这个时间再来清理。


3. 没有空闲连接就等5分钟后再尝试清理。


4. 没有连接不清理。

流程如下图所示：

7. OKHttp有哪些优点?

1. 使用简单，在设计时使用了外观模式，将整个系统的复杂性给隐藏起来，将子系统接口通过一个客户端OkHttpClient统一暴露出来。


2. 扩展性强，可以通过自定义应用拦截器与网络拦截器，完成用户各种自定义的需求


3. 功能强大，支持Spdy、Http1.X、Http2、以及WebSocket等多种协议


4. 通过连接池复用底层TCP(Socket)，减少请求延时


5. 无缝的支持GZIP减少数据流量


6. 支持数据缓存,减少重复的网络请求


7. 支持请求失败自动重试主机的其他ip，自动重定向

8. OKHttp框架中用到了哪些设计模式?

1. 构建者模式：OkHttpClient与Request的构建都用到了构建者模式


2. 外观模式： OkHttp使用了外观模式,将整个系统的复杂性给隐藏起来，将子系统接口通过一个客户端OkHttpClient统一暴露出来。


3. 责任链模式: OKHttp的核心就是责任链模式，通过5个默认拦截器构成的责任链完成请求的配置


4. 享元模式: 享元模式的核心即池中复用,OKHttp复用TCP连接时用到了连接池，同时在异步请求中也用到了线程池

总结

本文主要梳理了OKHttp原理相关知识点，并回答了以下问题:

1. OKHttp请求的整体流程是怎样的?


2. OKHttp分发器是怎样工作的?


3. OKHttp拦截器是如何工作的?


4. 应用拦截器和网络拦截器有什么区别?


5. OKHttp如何复用TCP连接?


6. OKHttp空闲连接如何清除?


7. OKHttp有哪些优点?


8. OKHttp框架中用到了哪些设计模式?

1. 即时通讯简述

即时通讯是端开发工作中常见的需求，本篇文章以作者工作中使用FLutter开发社交软件即时通讯需求为背景，描述一下即时通讯功能设计的要点。

2. 重要概念

即时通讯需要前后端配合，约定消息格式与消息内容。本次IM客户端需求开发使用了公司已有的基于Socket.io搭建的后台，下文描述涉及到的一些概念。

2.1 WebSocket协议

WebSocket是一种在单个TCP连接上进行全双工通信的协议。WebSocket协议与传统的HTTP协议的主要区别为，WebSocket协议允许服务端主动向客户端推送数据，而传统的HTTP协议服务器只有在客户端主动请求之后才能向客户端发送数据。在没有WebSocket之前，即时通讯大部分采用长轮询方式。

2.2 Socket.io和WebSocket的区别

Socket.io不是WebSocket，它只是将WebSocket和轮询 （Polling）机制以及其它的实时通信方式封装成了通用的接口，并且在服务端实现了这些实时机制的相应代码。也就是说，WebSocket仅仅是Socket.io实现即时通信的一个子集。因此WebSocket客户端连接不上Socket.io服务端，当然Socket.io客户端也连接不上WebSocket服务端。

2.3 服务端socket消息

理解了服务端socket消息也就理解了服务器端的即时通讯逻辑，服务器发出的socket消息可以分为两种：

1. 
   

   服务器主动发出的消息：

   
   

   例如，社交软件中的A用户给B用户发出了消息，服务器在收到A用户的消息后，通过socket链接，将A用户的消息转发给B用户，B用户客户端接收到的消息就属于服务器主动发出的。其他比较常见的场景例如直播软件中，全平台用户都会收到的礼物消息广播。

   
   


2. 
   

   服务器在接收到客户端消息后的返回消息：

   
   

   例如，长链接心跳机制，客户端向服务器发送ping消息，服务器在成功接受客户端的ping消息后返回的pong消息就属于服务器的返回消息。其他常见的场景如社交软件中A用户给B用户发出了消息，服务器在收到A用户的消息后，给A客户端返回一条消息，供A客户端了解消息的发送状态，判断发送是否成功。大部分场景，服务器在接收到客户端主动发出的消息之后都需要返回一条消息。

   
   

3. 客户端实现流程

几个设计客户端即时通讯的重点。

3.1 心跳机制

所谓心跳就是客户端发出ping消息，服务器成功收到后返回pong消息。当客户端一段时间内不在发送ping消息，视为客户端断开，服务器就会主动关闭socket链接。当客户端发送ping消息，服务器一段时间内没有返回pong消息，视为服务器断开，客户端就会启动重连机制。

3.2 重连机制

重连机制为客户端重新发起连接，常见的重连条件如下：

• 客户端发送ping消息，服务器一段时间内没有返回pong。


• 客户端网络断开。


• 服务器主动断开连接。


• 客户端主动连接失败。

当出现极端情况（客户端断网）时，频繁的重连可能会导致资源的浪费，可以设置一段时间内的最大重连次数，当重连超过一定次数时，休眠一段时间。

3.3 消息发送流程

1. 将消息存储到本地数据库，发送状态设为等待。


2. 发送socket消息。


3. 接收到服务器返回的socket消息后，将本地数据库等待状态的消息改为成功。

注意事项：

将消息存储到本地数据库时需要生成一个id存入数据库，同时传给服务器，当收到消息时根据id判断更新本地数据库的哪一条消息。

3.4 消息接收流程

3.5 其他相关

• 聊天页消息的排序：在查询本地数据库时使用order by按时间排序。


• 消息列表：也推荐做本地存储，当收到消息的时候需要先判断本地消息列表是否有当前消息用户的对话框，如果没有就先插入，有就更新。消息列表的维护就不展开说了，感兴趣可以看代码。


• 图片语音消息：将图片和语言先上传到专门的服务器上（各种专门的云存储服务器），sokcet消息和本地存储传递的是云服务器上的URL。


• 多人聊天（群聊）：与单人聊天逻辑基本一致，区别位本地数据库需要添加一个会话ID字段，打开一个群就查询对应会话ID的数据。聊天消息不再是谁发给谁，而是在哪个群聊下。

4. 客户端Flutter代码

把部分代码贴上来，完整项目在作者的github上。

4.1 心跳机制

  heart() {

    pingTimer = Timer.periodic(Duration(seconds: 30), (data) {

      if (pingWaitTime >= 60) {

        socket.connect();

        pingWaitTime = 0;

        pingWaitTimer!.cancel();

        ping();

      }

      if (!pingWaitFlag) ping();

    });

  }



  ping() {

    debugPrint("ping");

    String pingData =

        '{"type":"ping","payload":{"front":true},"msg_id":${DateTime.now().millisecondsSinceEpoch}}';

    socket.emit("message", pingData);

    pingWaitFlag = true;

    pingWaitTime = 0;

    pingWaitTimer = Timer.periodic(Duration(seconds: 1), (data) {

      pingWaitTime++;

      print(data.hashCode);

      if (pingWaitTime % 10 == 0) debugPrint(pingWaitTime.toString());

    });

  }

	//pong

  if (socketMessage.type == PONG && socketMessage.code == 1000) {

        pingWaitFlag = false;

        pingWaitTimer!.cancel();

        pingWaitTime = 0;

      }

4.2 本地数据库设计

数据库表的设计是比较重要的，理解了数据库设计，读代码也就无压力了。

      //消息表

      CREATE TABLE chatDetail (

         chat_id TEXT PRIMARY KEY,//主键

         from_id TEXT,//发送人

         to_id TEXT,//接收人

         created_at TEXT,

         content TEXT,//消息内容

         image TEXT,//UI展示用，用户头像

         name TEXT,//UI展示用，用户名

         sex TEXT,//UI展示用，用户性别

         status TEXT,//消息状态

         type INTEGER,//消息类型，图片/文字/语音等

         chat_object_id TEXT//聊天对象ID，对当前用户而言的聊天对象，是一系列本地操作的核心

         )

       //消息列表表

       CREATE TABLE chatList (

         cov_id TEXT,

         unread_count INTEGER,

         last_msg_text TEXT,

         last_msg_at TEXT,

         image TEXT,

         name TEXT,

         sex TEXT,

         chat_object_id TEXT PRIMARY KEY)

5. 总结

无论是Flutter技术，或是IOS/Android/Web。只要掌握了即时通讯的核心开发流程，不同的技术只是API有些变化。API往往看文档就能解决，大前端或是特定平台的工程师还是要掌握核心开发流程，会几种做同样事情的API意义不大。

demo写的比较简单，有问题可以评论。

项目github地址。

简介

平衡二叉搜索树是一种特殊的二叉搜索树。为什么会有平衡二叉搜索树呢？

考虑一下二叉搜索树的特殊情况，如果一个二叉搜索树所有的节点都是右节点，那么这个二叉搜索树将会退化成为链表。从而导致搜索的时间复杂度变为O(n),其中n是二叉搜索树的节点个数。

而平衡二叉搜索树正是为了解决这个问题而产生的，它通过限制树的高度，从而将时间复杂度降低为O(logn)。

AVL的特性

在讨论AVL的特性之前，我们先介绍一个概念叫做平衡因子，平衡因子表示的是左子树和右子树的高度差。

如果平衡因子=0，表示这是一个完全平衡二叉树。

如果平衡因子=1，那么这棵树就是平衡二叉树AVL。

也就是是说AVL的平衡因子不能够大于1。

先看一个AVL的例子：

总结一下，AVL首先是一个二叉搜索树，然后又是一个二叉平衡树。

AVL的构建

有了AVL的特性之后，我们看下AVL是怎么构建的。

public class AVLTree {



    //根节点

    Node root;



    class Node {

        int data; //节点的数据

        int height; //节点的高度

        Node left;

        Node right;



        public Node(int data) {

            this.data = data;

            left = right = null;

        }

    }

同样的，AVL也是由各个节点构成的，每个节点拥有data，left和right几个属性。

因为是二叉平衡树，节点是否平衡还跟节点的高度有关，所以我们还需要定义一个height作为节点的高度。

在来两个辅助的方法，一个是获取给定的节点高度：

//获取给定节点的高度

    int height(Node node) {

        if (node == null)

            return 0;

        return node.height;

    }

和获取平衡因子：

//获取平衡因子

    int getBalance(Node node) {

        if (node == null)

            return 0;

        return height(node.left) - height(node.right);

    }

AVL的搜索

AVL的搜索和二叉搜索树的搜索方式是一致的。

先看一个直观的例子，怎么在AVL中搜索到7这个节点：

搜索的基本步骤是：

1. 从根节点15出发，比较根节点和搜索值的大小


2. 如果搜索值小于节点值，那么递归搜索左侧树


3. 如果搜索值大于节点值，那么递归搜索右侧树


4. 如果节点匹配，则直接返回即可。

相应的java代码如下：

//搜索方法，默认从根节点搜索

    public Node search(int data){

        return search(root,data);

    }



    //递归搜索节点

    private Node search(Node node, int data)

    {

        // 如果节点匹配，则返回节点

        if (node==null || node.data==data)

            return node;



        // 节点数据大于要搜索的数据，则继续搜索左边节点

        if (node.data > data)

            return search(node.left, data);



        // 如果节点数据小于要搜素的数据，则继续搜索右边节点

        return search(node.right, data);

    }

AVL的插入

AVL的插入和BST的插入是一样的，不过插入之后有可能会导致树不再平衡，所以我们需要做一个再平衡的步骤。

看一个直观的动画：

插入的逻辑是这样的：

1. 从根节点出发，比较节点数据和要插入的数据


2. 如果要插入的数据小于节点数据，则递归左子树插入


3. 如果要插入的数据大于节点数据，则递归右子树插入


4. 如果根节点为空，则插入当前数据作为根节点

插入数据之后，我们需要做再平衡。

再平衡的逻辑是这样的：

1. 从插入的节点向上找出第一个未平衡的节点，这个节点我们记为z


2. 对z为根节点的子树进行旋转，得到一个平衡树。

根据以z为根节点的树的不同，我们有四种旋转方式：

• left-left：

如果是left left的树，那么进行一次右旋就够了。

右旋的步骤是怎么样的呢？

1. 找到z节点的左节点y


2. 将y作为旋转后的根节点


3. z作为y的右节点


4. y的右节点作为z的左节点


5. 更新z的高度

相应的代码如下：

Node rightRotate(Node node) {

        Node x = node.left;

        Node y = x.right;



        // 右旋

        x.right = node;

        node.left = y;



        // 更新node和x的高度

        node.height = max(height(node.left), height(node.right)) + 1;

        x.height = max(height(x.left), height(x.right)) + 1;



        // 返回新的x节点

        return x;

    }

• right-right:

如果是right-right形式的树，需要经过一次左旋：

左旋的步骤正好和右旋的步骤相反：

1. 找到z节点的右节点y


2. 将y作为旋转后的根节点


3. z作为y的左节点


4. y的左节点作为z的右节点


5. 更新z的高度

相应的代码如下：

//左旋

    Node leftRotate(Node node) {

        Node x = node.right;

        Node y = x.left;



        //左旋操作

        x.left = node;

        node.right = y;



        // 更新node和x的高度

        node.height = max(height(node.left), height(node.right)) + 1;

        x.height = max(height(x.left), height(x.right)) + 1;



        // 返回新的x节点

        return x;

    }

• left-right：

如果是left right的情况，需要先进行一次左旋将树转变成left left格式，然后再进行一次右旋，得到最终结果。

• right-left：

如果是right left格式，需要先进行一次右旋，转换成为right right格式，然后再进行一次左旋即可。

现在问题来了，怎么判断一个树到底是哪种格式呢？我们可以通过获取平衡因子和新插入的数据比较来判断：

1. 
   

   如果balance>1,那么我们在Left Left或者left Right的情况，这时候我们需要比较新插入的data和node.left.data的大小

   
   

   如果data < node.left.data，表示是left left的情况，只需要一次右旋即可

   
   

   如果data > node.left.data，表示是left right的情况，则需要将node.left进行一次左旋，然后将node进行一次右旋

   
   


2. 
   

   如果balance<-1,那么我们在Right Right或者Right Left的情况，这时候我们需要比较新插入的data和node.right.data的大小
   如果data > node.right.data，表示是Right Right的情况，只需要一次左旋即可

   
   

   如果data < node.left.data，表示是Right left的情况，则需要将node.right进行一次右旋，然后将node进行一次左旋

   
   

插入节点的最终代码如下：

//插入新节点，从root开始

    public void insert(int data){

        root=insert(root, data);

    }



    //遍历插入新节点

    Node insert(Node node, int data) {



        //先按照普通的BST方法插入节点

        if (node == null)

            return (new Node(data));



        if (data < node.data)

            node.left = insert(node.left, data);

        else if (data > node.data)

            node.right = insert(node.right, data);

        else

            return node;



        //更新节点的高度

        node.height = max(height(node.left), height(node.right)) + 1;



        //判断节点是否平衡

        int balance = getBalance(node);



        //节点不平衡有四种情况

        //1.如果balance>1,那么我们在Left Left或者left Right的情况，这时候我们需要比较新插入的data和node.left.data的大小

        //如果data < node.left.data，表示是left left的情况，只需要一次右旋即可

        //如果data > node.left.data，表示是left right的情况，则需要将node.left进行一次左旋，然后将node进行一次右旋

        //2.如果balance<-1,那么我们在Right Right或者Right Left的情况，这时候我们需要比较新插入的data和node.right.data的大小

        //如果data > node.right.data，表示是Right Right的情况，只需要一次左旋即可

        //如果data < node.left.data，表示是Right left的情况，则需要将node.right进行一次右旋，然后将node进行一次左旋



        //left left

        if (balance > 1 && data < node.left.data)

            return rightRotate(node);



        // Right Right

        if (balance < -1 && data > node.right.data)

            return leftRotate(node);



        // Left Right

        if (balance > 1 && data > node.left.data) {

            node.left = leftRotate(node.left);

            return rightRotate(node);

        }



        // Right Left

        if (balance < -1 && data < node.right.data) {

            node.right = rightRotate(node.right);

            return leftRotate(node);

        }



        //返回插入后的节点

        return node;

    }

AVL的删除

AVL的删除和插入类似。

首先按照普通的BST删除，然后也需要做再平衡。

看一个直观的动画：

删除之后，节点再平衡也有4种情况：

1. 
   

   如果balance>1,那么我们在Left Left或者left Right的情况，这时候我们需要比较左节点的平衡因子

   
   

   如果左节点的平衡因子>=0，表示是left left的情况，只需要一次右旋即可

   
   

   如果左节点的平衡因<0，表示是left right的情况，则需要将node.left进行一次左旋，然后将node进行一次右旋

   
   


2. 
   

   如果balance<-1,那么我们在Right Right或者Right Left的情况，这时候我们需要比较右节点的平衡因子

   
   

   如果右节点的平衡因子<=0，表示是Right Right的情况，只需要一次左旋即可

   
   

   如果右节点的平衡因子>0，表示是Right left的情况，则需要将node.right进行一次右旋，然后将node进行一次左旋

   
   

相应的代码如下：

Node delete(Node node, int data)

    {

        //Step 1. 普通BST节点删除

        // 如果节点为空，直接返回

        if (node == null)

            return node;



        // 如果值小于当前节点，那么继续左节点删除

        if (data < node.data)

            node.left = delete(node.left, data);



        //如果值大于当前节点，那么继续右节点删除

        else if (data > node.data)

            node.right = delete(node.right, data);



       //如果值相同，那么就是要删除的节点

        else

        {

            // 如果是单边节点的情况

            if ((node.left == null) || (node.right == null))

            {

                Node temp = null;

                if (temp == node.left)

                    temp = node.right;

                else

                    temp = node.left;



                //没有子节点的情况

                if (temp == null)

                {

                    node = null;

                }

                else // 单边节点的情况

                    node = temp;

            }

            else

            {  //非单边节点的情况

                //拿到右侧节点的最小值

                Node temp = minValueNode(node.right);

                //将最小值作为当前的节点值

                node.data = temp.data;

                // 将该值从右侧节点删除

                node.right = delete(node.right, temp.data);

            }

        }



        // 如果节点为空，直接返回

        if (node == null)

            return node;



        // step 2: 更新当前节点的高度

        node.height = max(height(node.left), height(node.right)) + 1;



        // step 3: 获取当前节点的平衡因子

        int balance = getBalance(node);



        // 如果节点不再平衡，那么有4种情况

        //1.如果balance>1,那么我们在Left Left或者left Right的情况，这时候我们需要比较左节点的平衡因子

        //如果左节点的平衡因子>=0，表示是left left的情况，只需要一次右旋即可

        //如果左节点的平衡因<0，表示是left right的情况，则需要将node.left进行一次左旋，然后将node进行一次右旋

        //2.如果balance<-1,那么我们在Right Right或者Right Left的情况，这时候我们需要比较右节点的平衡因子

        //如果右节点的平衡因子<=0，表示是Right Right的情况，只需要一次左旋即可

        //如果右节点的平衡因子>0，表示是Right left的情况，则需要将node.right进行一次右旋，然后将node进行一次左旋

        // Left Left Case

        if (balance > 1 && getBalance(node.left) >= 0)

            return rightRotate(node);



        // Left Right Case

        if (balance > 1 && getBalance(node.left) < 0)

        {

            node.left = leftRotate(node.left);

            return rightRotate(node);

        }



        // Right Right Case

        if (balance < -1 && getBalance(node.right) <= 0)

            return leftRotate(node);



        // Right Left Case

        if (balance < -1 && getBalance(node.right) > 0)

        {

            node.right = rightRotate(node.right);

            return leftRotate(node);

        }

        return node;

    }

本文的代码地址：

learn-algorithm

简介

为了抵御密码破解，科学家们想出了很多种方法，比如对密码进行混淆加盐操作，对密码进行模式变换和组合。但是这些算法逐渐被一些特制的ASIC处理器打败，这些ASIC处理器不做别的，就是专门来破解你的密码或者进行hash运算。

最有名的当然是比特币了，它使用的是为人诟病的POW算法，谁的算力高，谁就可以挖矿，这样就导致了大量无意义的矿机的产生，这些矿机什么都不能干，就算是用来算hash值。结果浪费了大量的电力。

普通人更是别想加入这个只有巨头才能拥有的赛道，如果你想用一个普通的PC机来挖矿，那么我估计你挖到矿的几率可能跟被陨石砸中差不多。

为了抵御这种CPU为主的密码加密方式，科学家们发明了很多其他的算法，比如需要占用大量内存的算法，因为内存不像CPU可以疯狂提速，所以限制了很多暴力破解的场景，今天要将的scrypt算法就是其中一种，该算法被应用到很多新的加密货币挖矿体系中，用以表示他们挖矿程序的公平性。

scrypt算法

scrypt是一种密码衍生算法，它是由Colin Percival创建的。使用scrypt算法来生成衍生key，需要用到大量的内存。scrypt算法在2016年作为RFC 7914标准发布。

密码衍生算法主要作用就是根据初始化的主密码来生成系列的衍生密码。这种算法主要是为了抵御暴力破解的攻击。通过增加密码生成的复杂度，同时也增加了暴力破解的难度。

但是和上面提到的原因一样，之前的password-based KDF，比如PBKDF2虽然提高了密码生成的遍历次数，但是它使用了很少的内存空间。所以很容易被简单的ASIC机器破解。scrypt算法就是为了解决这样的问题出现的。

scrypt算法详解

scrypt算法会生成非常大的伪随机数序列，这个随机数序列会被用在后续的key生成过程中，所以一般来说需要一个RAM来进行存储。这就是scrypt算法需要大内存的原因。

接下我们详细分析一下scrypt算法，标准的Scrypt算法需要输入8个参数，如下所示：

• Passphrase: 要被hash的输入密码


• Salt: 对密码保护的盐，防止彩虹表攻击


• CostFactor (N): CPU/memory cost 参数，必须是2的指数(比如: 1024)


• BlockSizeFactor (r): blocksize 参数


• ParallelizationFactor (p): 并行参数


• DesiredKeyLen (dkLen): 输出的衍生的key的长度


• hLen: hash函数的输出长度


• MFlen: Mix函数的输出长度

这个函数的输出就是DerivedKey。

首先我们需要生成一个expensiveSalt。首先得到blockSize：

blockSize = 128*BlockSizeFactor 

然后使用PBKDF2生成p个blockSize，将这p个block组合成一个数组：

[B0...Bp−1] = PBKDF2HMAC-SHA256(Passphrase, Salt, 1, blockSize*ParallelizationFactor)

使用ROMix对得到的block进行混合：

   for i ← 0 to p-1 do

      Bi ← ROMix(Bi, CostFactor)

将B组合成新的expensiveSalt：

expensiveSalt ← B0∥B1∥B2∥ ... ∥Bp-1

接下来使用PBKDF2和新的salt生成最终的衍生key：

return PBKDF2HMAC-SHA256(Passphrase, expensiveSalt, 1, DesiredKeyLen);

下面是ROMix函数的伪代码：

Function ROMix(Block, Iterations)



   Create Iterations copies of X

   X ← Block

   for i ← 0 to Iterations−1 do

      Vi ← X

      X ← BlockMix(X)



   for i ← 0 to Iterations−1 do

      j ← Integerify(X) mod Iterations 

      X ← BlockMix(X xor Vj)



   return X

其中BlockMix的伪代码如下：

Function BlockMix(B):



    The block B is r 128-byte chunks (which is equivalent of 2r 64-byte chunks)

    r ← Length(B) / 128;



    Treat B as an array of 2r 64-byte chunks

    [B0...B2r-1] ← B



    X ← B2r−1

    for i ← 0 to 2r−1 do

        X ← Salsa20/8(X xor Bi)  // Salsa20/8 hashes from 64-bytes to 64-bytes

        Yi ← X



    return ← Y0∥Y2∥...∥Y2r−2 ∥ Y1∥Y3∥...∥Y2r−1

scrypt的使用

Scrypt被用在很多新的POW的虚拟货币中，比如Tenebrix、 Litecoin 和 Dogecoin。感兴趣的朋友可以关注一下。

• 情景：一个集合对象list，现在想获取这个集合中每个对象的id，并将这些id值存放在另一个集合中，方便我去查询数据。如果是你来实现这个需求，你会用什么方法去实现呢。

我猜会有许多人会选择循环变量这个集合对象，取出id存放在集合里面，代码是这样的：

List<Clazz> list = clazzes;

List<Long> ids = new ArrayList();

for (Clazz clazz : list) {

    ids.add(clazz.getId());

}

但是！实际上，这个需求可以只用一行代码就可以解决，那是用的什么呢？“流”请看代码：

List<Clazz> list = clazzes;

List<Long> collect = list.stream().map(Clazz::getId).collect(Collectors.toList());

使用流一行代码就可以解决关键看着清晰明了。
上面list.stream().map(Clazz::getId).collect(Collectors.toList())这一行代码用了JAVA8 的两个新特性

• 双冒号 双冒号就是把方法当作参数传递给需要的方法，或者是传递到stream()中去。在这里就是将其传到stream中去其语法格式 类名：：方法名


• stream 流 通过Collectors 类将流转换成集合元素 流的操作还有许多，可以参考搜索网络

再分享一下 最近根据echart图来查询数据，我在写查询语句筛选条件使用了大量的stream流，发现使用stream流是真的舒服。

我先描述我最近的一个接口：这个接口需要展示四个饼图。而四个饼图是：1.男女教师占比；2.各年龄段占比 3.学历占比，4.职称统计
我想在一个接口中完成这个四个的查询 我的思路有几个：

1.是写多个查询语句 需要一个查询一个（但是各种筛选条件下来 很麻烦）

2.利用视图 可以用来多次调用（但是在查询中会存在in操作 觉得麻烦）

3.利用stream流 根据筛选条件查出符合的教师信息 对每一个操作进行筛选

 通过各种筛选条件查出的结果： teacherList （集合类型）

Long count1 = teacherList.stream().filter(e -> e.getGender().equals(0)).count(); //男生数量

Long count2 = teacherList.stream().filter(e -> e.getGender().equals(1)).count(); //女生数量

通过这样可以直接算出数量 而不用去便利算数据

而更多详细的stream流的信息可以去网上搜索学习

我对stream流的学习还在表面 还有许多灵活的用法我还需要继续学习 欢迎大佬指导！

事件起因

今天，我需要上线一个非常小但是又非常重要的系统改动，即给核心接口的RPC接口出参增加序列化接口（由下图可见，原实体类未实现序列化）。

编码、测试、代码审核一气呵成，然后收到驳回通知，架构师说实现序列化接口时注意不要忘记配置serialversionUID，还非常贴心的跟我说，IDEA 有一个插件可以自动生成UID，推荐我下载使用（IDEA serialversionUID 插件地址），按照要求调整之后，提测、编译、发布一气呵成，进入今天的午觉模式 （😎）

梦中惊魂

我突然梦见企业微信以每毫秒弹出一个窗口的速度不停的闪烁，周围的人熙熙攘攘，面露忧色，不知道在说些什么...

线上出问题了？和我有什么关系呢（🤪）肯定不是我的问题，不过为了保险起见，还是回忆一下今天都做了什么事吧。

**做了什么？**中台系统上线。**改了什么？**对部分类增加了序列化接口，并增加了serialversionUID... 会导致什么？ 接口调用失败...COE...

蹭的一下，我立即从梦中醒来，开始看企业微信，看监控，看接口可用率，看了一切数据正常无误后才逐渐心安。

纳尼？我们不用Java序列化？

回顾自己所了解的关于序列化的知识，打开了各种关于序列化的文章，都给我指向了一个答案：我这种改动铁定会影响序列化，就像下面这样程序会报错。

Exception in thread "main" java.io.InvalidClassException: ser.demo.StuDemo; local class incompatible: stream classdesc serialVersionUID = 6395135316924936201, local class serialVersionUID = 1

	at java.io.ObjectStreamClass.initNonProxy(ObjectStreamClass.java:616)

	at java.io.ObjectInputStream.readNonProxyDesc(ObjectInputStream.java:1843)

	at java.io.ObjectInputStream.readClassDesc(ObjectInputStream.java:1713)

	at java.io.ObjectInputStream.readOrdinaryObject(ObjectInputStream.java:2000)

	at java.io.ObjectInputStream.readObject0(ObjectInputStream.java:1535)

	at java.io.ObjectInputStream.readObject(ObjectInputStream.java:422)

	at ser.demo.App.main(App.java:27)

现在线上没报错，只有一种可能，即：我们的RPC框架并没有使用原生的序列化方式。遇事不决架构师，咨询完毕之后果然和我猜测的一样，还从架构师的口中知晓了另外几种序列化方式，比如：MessagePack、Hessian等等。

常见序列化方式

Java序列化

Java序列化就是将一个对象转化为一个二进制表示的字节数组，通过保存或则转移这些二进制数组达到持久化的目的。

要实现序列化，需要实现java.io.Serializable接口，反序列化是和序列化相反的过程，就是把二进制数组转化为对象的过程，在反序列化的时候，必须有原始类的模板才能将对象还原，其核心方法在于以下两个方法，其中Serializable接口起到的作用是标识是否实现序列化、以及前后对象是否一致等作用。

序列化：java.io.ObjectOutputStream#writeObject0

反序列化：java.io.ObjectInputStream#readObject0

以测试类（StuDemo）为例，序列化后的结果如下：

// 序列化

FileOutputStream fos = new FileOutputStream("C:\\Users\\Kerwin\\Desktop\\log\\object.out");

ObjectOutputStream oos = new ObjectOutputStream(fos);

StuDemo demo = new StuDemo("Kerwin");

oos.writeObject(demo);

oos.flush();

oos.close();

   

// 结果如下

//  sr ser.demo.StuDemoX??莅	 L namet Ljava/lang/String;xpt Kerwin

一堆乱码，但还是能看出来文件内容大致是指向某一个类，有什么字段、对应的值等信息。

MessagePack 序列化

MessagePack(简写Msgpack)是一个高效的二进制序列化格式，它让你像JSON一样可以在各种语言之间交换数据，但是它比JSON更快、更小。

更快更小就代表着性能更高，它是如何实现的？

Msgpack序列化的时候，字段不会标明Key，仅会按照字段的先后顺序存储，类似数组一样，它的编码方式是类型 + 长度 + 内容，如下所示：

这种高效的编码方式就带来一些限制，例如：

• 服务端不可随意在任意位置增加字段，因为客户端不升级的话会导致反序列化失败


• 不能使用第三方包提供的集合类工具包作为返回值

使用方式如下：

// 其中 StuDemo 类需要增加 @Message 注解标识需要被MessagePack序列化

// MessagePack 序列化方式不需要依赖 Serializable

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

    StuDemo demo = new StuDemo("Kerwin");

    MessagePack pack = new MessagePack();



    // 序列化

    byte[] bytes = pack.write(demo);



    // 反序列化

    StuDemo res = pack.read(bytes, StuDemo.class);

    System.out.println(res.getName());

PS：我司的RPC框架目前就使用的MessagePack序列化方式，也是因为此，所以上述调整 serialVersionUID 时没有发生任何问题
同理，受制于底层序列化的限制，我们的新人文档中也明确提到了上述的限制，比如必须在最末尾增加字段等等。

Hessian2 序列化

Hessian是动态类型、二进制、紧凑的，并且可跨语言移植的一种序列化框架，在Hessian的基础之上，Hessian2的性能和压缩率大大提升。

Hessian会把复杂的对象所有属性存储在一个类似Map的结构中进行序列化，所以在父类、子类中存在同名成员变量的情况下，它先序列化子类，然后序列化父类，因此会导致子类同名成员变量的值被父类覆盖等情况。

它有八大核心设计目标，官网：

• 必须自我描述序列化类型，即不需要外部模式或接口定义


• 必须与语言无关，包括支持脚本语言


• 必须在一次传递中可读或可写


• 必须尽可能紧凑（压缩）


• 必须简单


• 必须尽可能快


• 必须支持Unicode字符串


• 必须支持8位二进制数据


• 必须支持加密

使用方式如下：

public class StuHessianDemo implements Serializable {



    private static final long serialVersionUID = -640696903073930546L;



    private String name;



    public StuHessianDemo(String name) {

        this.name = name;

    }



    public String getName() {

        return name;

    }



    public void setName(String name) {

        this.name = name;

    }

}

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

    StuHessianDemo hessianDemo = new StuHessianDemo("Kerwin");



    ByteArrayOutputStream stream = new ByteArrayOutputStream();

    HessianOutput hessianOutput = new HessianOutput(stream);

    hessianOutput.writeObject(hessianDemo);



    ByteArrayInputStream inputStream = new ByteArrayInputStream(stream.toByteArray());



    // Hessian的反序列化读取对象

    HessianInput hessianInput = new HessianInput(inputStream);

    System.out.println(((StuHessianDemo) hessianInput.readObject()).getName());

}



// 结果：Kerwin

选择的依据

由上文我们得知了几种常用的序列化方式，及其优劣，比如MessagePack就是极致的压缩和快，Hessian2则依赖Serializable接口，在保证安全性、自身描述性的基础上，尽可能的追求空间利用率，效率等，而Java序列化方式则一直被诟病，难等大雅之堂，因此在RPC框架选择底层序列化方式时，需要根据自身所需，有所侧重的选择某一项序列化方式。

选择的依据如下，优先级从高到低：

一点思考

JSON序列化的地位

其实JSON序列化才是我们最熟知的序列化方式，它本身也不需要实现Serializable接口，为什么大多数RPC框架没有选择用它作为默认的序列化方式呢？

在了解完上文的内容后，我们知道关键还是在性能，效率、空间开销上，因为JSON是一种文本类型序列化框架，采用KEY-VALUE的方式存储数据，它在进行序列化的额外空间开销相对就更大，在反序列化时更不必说，需要依赖反射，因此性能进一步缩水。

然而JSON本身又具备极强的可读性、因此被作为Web中HTTP协议的事实标准。

为什么还要自定义 serialVersionUID

在《Effect Java》中有一句提到：

不管你选择了哪种序列化方式，都要为自己编写的每个可序列化的类声明一个显式的序列版本UID。

为什么架构师会提醒我实现它？为什么书中也会这么说？

serialVersionUID分解下来全称为：serial Version UID，序列版本UID，每一个可序列化的类都有一个long域中显式地指定该编号，如果编码者未定义的话，系统就会对这个类的结构运用一个加密的散列函数（SHA-1），从而在运行时自动产生该标识号，该编号会受类名称、接口名称、公有及受保护的成员变量所影响，一旦有相关改动例如增加一个不重要的公有方法即会影响UID，导致异常发生。

因此这是一个习惯问题，也是为了避免潜在风险。

总结

截止到这里，我们了解了原来之前学习到的Java序列化是那么的不实用（甚至到了被吐槽的地步），也知晓了一些框架使用注意事项底层的秘密（比如MsgPack增加字段），下面是关于序列化的一些小建议：

1. 无论是否依赖Serializable，接口出参都建议实现序列化接口。


2. 如果实现了序列化接口，务必自行实现serialVersionUID。


3. 接口出参对象不宜使用特殊的数据类型（如MsgPack第三方集合等）、过于复杂的结构（继承等），不然会导致很多莫名其妙的问题发生。


4. 当发生服务端/客户端数据不一致时，第一时间想到是序列化问题，并针对当前序列化方式的特点，仔细排查。

本文面试情节虚假，但知识真实，请在家人或者朋友的陪同下仔细观看，防止在观看的过程发呆、走神导致没学到知识。

性能篇

一位身穿格子衬衣，头发好似一拳超人的中年人走了过来，没错他就是面试官，他手握简历，若有所思，我当时害怕极了，然后他开口：小伙子啊，我们这边是基础架构的中间件组，既然你的简历没提到kafka，那我接下来问问你kafka的知识吧。

我：好的，kafka平时看的不多，但也还了解一点，不是特别精通所以没写了。（嘿嘿，我是故意没写的，早就知道你要来这一套，kafka其实是俺最精通的东西了）
面试官捋了捋他那稀疏的胡须：那我们开始吧，先说说kafka的Log文件存在什么地方？
我：kafka的topic可以分区，所以Log对应了一个命名形式为topic-partition的文件夹，比如对于一个有两个分区的topic来说，它的log分别存在xxx/topic-1和xxx/topic-2中。
面试官：那按照这样的说法，所以log文件的位置应该就是xxx/topic-1/data.log或者xxx/topic-2/data.log？
我：不是的，kafka的log会分段，每个分区文件夹下，其实有很多的log段，它们共同组成了log，每个日志段大小是1G，如果一个日志段写完，会自动写入一个新的段。
面试官：为什么要分段？不分段行不行？
我：分段可以很好的维护数据，首先不分段，当查找一条数据的时候会很麻烦，就像在一本没有目录的新华字典里找数据一样，如果分了段我们只要知道数据在哪个段中，然后在对应的段中查找即可。同时由于log是持久化磁盘的，磁盘的空间不可能无穷无尽的，当需要清除一些老数据，通过分段机制，只需要删除较老的数据段即可。
面试官：hold on，hold on～，你说分了段后我们只要知道数据在哪个段中即可，那么我们怎么知道数据在哪个段中的？
我：easy，easy～，kafka内部维护一个跳跃表，跳跃表的节点就是每个段的段号。这样当查询数据的时候，先根据跳跃表就可以快速定位到目标数据段。
面试官：跳跃表是可以加速访问，但是每个段的段号是咋确定的？
我：kakfa的段号其实就是根据偏移量来的，它代表当前段内偏移量最小的那条数据的offset，比如：

 segment1的段号是200，segment2的段号是500，那么segment1就存储了偏移量200-499的消息。
面试官：嗯嗯，那定位到段后，如何定位到具体的消息，直接遍历吗？
我：不是直接遍历，直接遍历效率太低，kafka采用稀疏索引的方式来搜索具体的消息，其实每个log分段后，除了log文件外，还有两个索引文件，分别是.index和.timeindex，

 其中.index就是我说的偏移量索引文件，它不会为每条消息创建索引，它会每隔一个范围区间创建索引，所以称之为稀疏索引。

 比如我们要查找消息6的时候，首先加载稀疏文件索引.index到内存中，然后通过二分法定位到消息5，最后通过消息5指向的物理地址接着向下顺序查找，直至找到消息6。
面试官：那稀疏索引的好处是什么？
我：稀疏索引是一个折中的方案，既不占用太多空间，也提供了一定的快速检索能力。
面试官：上面你说到了.timeindex文件，它是干嘛的？
我：这和kafka清理数据有着密切的关系，kafka默认保留7天内的数据，对于超过7天的数据，会被清理掉，这里的清理逻辑主要根据timeindex时间索引文件里最大的时间来判断的，如果最大时间与当前时间差值超过7天，那么对应的数据段就会被清理掉。
面试官：说到数据清理，除了你说的根据时间来判断的，还有哪些？
我：还有根据日志文件大小和日志起始偏移量的方式，对于日志文件大小，如果log文件（所有的数据段总和）大于我们设定的阈值，那么就会从第一个数据段开始清理，直至满足条件。对于日志起始偏移量，如果日志段的起始偏移量小于等于我们设定的阈值，那么对应的数据段就会被清理掉。
面试官：你知道消息合并吗？如果知道说说消息合并带来的好处。
我：了解一点，消息合并就是把多条消息合并在一起，然后一次rpc调用发给broker，这样的好处无疑会减少很多网络IO资源，其次消息会有个crc校验，如果不合并每条消息都要crc，合并之后，多条消息可以一起crc一次。
面试官：那合并之后的消息，什么时候会给broker？
我：合并的消息会在缓冲区内，如果缓冲区快满了或者一段时间内没有生产消息了，那么就会把消息发给broker。
面试官：那你知道消息压缩吗？
我：知道一点，压缩是利用cpu时间来节省带宽成本，压缩可以使数据包的体积变得更小，生产者负责将数据消息压缩，消费者拿到消息后自行解压。
面试官：所有只有生产者可以压缩？
我：不是的，broker也可以压缩，当生产者指定的压缩算法和broker指定压缩算法的不一样的时候，broker会先按照生产者的压缩算法解压缩一下，然后再按照自己的压缩算法压缩一下，这是需要注意的，如果出现这种情况会影响整体的吞吐。还有就是新老版本的问题，如果新老版本的压缩算法不兼容，比如broker版本比较老，不支持新的压缩算法，那么也会发生一样的事情。
面试官：我们知道kafka的消息是要写入磁盘的，磁盘IO会不会很慢？
我：是这样的，kafka的消息是磁盘顺序读写的，有关测试结果表明，一个由6块7200r/min的RAID-5阵列组成的磁盘簇的线性（顺序）写入速度可以达到 600MB/s，而随机写入速度只有 100KB/s，两者性能相差6000倍。操作系统可以针对线性读写做深层次的优化，比如预读（read-ahead，提前将一个比较大的磁盘块读入内存）和后写（write-behind，将很多小的逻辑写操作合并起来组成一个大的物理写操作）技术。顺序写盘的速度不仅比随机写盘的速度快，而且也比随机写内存的速度快。
面试官：顺序读写是为了解决了缓慢的磁盘问题，那在网络方面还有其他的优化吗？
我：有，零拷贝，在没有零拷贝的时候，消息是这样交互的：

1. 切到内核态：内核把磁盘数据copy到内核缓冲区
2. 切到用户态：把内核的数据copy到用户程序
3. 切到内核态：用户数据copy到内核socket缓冲区
4. socket把数据copy给网卡

可以发现一份数据经过多次copy，最终兜兜转转又回到了内核态，实属浪费。

当有了零拷贝之后：

1. 磁盘数据copy到内核缓冲
2. 内核缓冲把描述符和长度发给socket，同时直接把数据发给网卡

可以发现通过零拷贝，减少了两次copy过程，大大降低了开销。

可靠篇

面试官：（关于性能方面的问的差不多了，接下来换换口味吧），kafka的多消费者模型是怎么做到的？
我：如果要支持多个消费者同时消费一个topic，最简单的方式就是把topic复制一份，但这无疑会浪费很多空间，尤其在消费者很多的情况下，

于是kafka设计出一套offset机制，即一份数据，不同的消费者根据位置来获取不同的消息即可。

面试官：那你知道消费者的offset存在哪吗？
我：很久以前，是存在zookeeper中的，但是offset需要频繁更新，zookeeper又不适合频繁更新，所以后来就把消费者位移存在了一个叫_consumer_offset的topic中，这个topic会在第一个消费者启动的时候自动创建，默认50个分区，3个副本。
面试官：那你说说这个_consumer_offset里面具体存了什么？
我：这里其实主要分为key和value，value可以简单的认为就是我们的消费者位移，关于key，这里要细说下，由于每个消费者都属于一个消费者组，并且每个消费者其实消费的是某个topic的分区，所以通过group-topic-partition就可以关联上对应的消费者了，这也就是key的组成。
面试官：那你能介绍下消费者提交位移的方式吗？
我：这里分为自动提交和手动提交。自动提交的话，就不需要我们干预，我们消费完消息后，kafka会自动帮我们提交，手动提交的话，就需要我们在消费到消息后自己主动commit。
面试官：自动提交会有什么问题？
我：自动提交的策略是consumer默认每隔5秒提交一次位移，如果consumer在接下来的很长时间内都没有数据消费，那么自动提交策略就会一直提交重复的位移，导致_consumer_offset有很多重复的消息。
面试官：那这有什么解决方案吗？
我：有，这种情况的核心问题就是可能会有大量的、重复的位移消息占用存储空间，只要把重复的去掉即可，kafka提供一种类似redis的aofrewrite的功能，叫compact策略，compact是由一个logCleaner线程来完成的，它会把重复的、并且较老的消息清除掉。

面试官：那如果consumer自动重启了，位移没来的及提交咋办？
我：这个会造成重复消费，一般业务上需要配合做幂等。
面试官：那手动提交能解决这个问题吗？
我：不能，如果我们在业务处理完之后手动提交，但是在还没得及提交的情况下，也发生了重启或者其他原因导致提交不上去，在消费者恢复后也会发生重复消费。
面试官：那如果我是先提交，后处理业务逻辑呢？
我：这种情况也不能保证100%没问题，如果提交成功，但是处理业务时出错，正常来说，这时希望重新消费这条数据是不行的，因为已经提交了，除非你重置offset。总之无论哪种方案都不能保证100%的完美，我们需要自己根据业务情况做幂等或者根据log来找到丢失的数据。
面试官：消费者提交消费位移时提交的是是当前消费到的最新消息的offset还是offset+1？
我：offset+1。
面试官：从生产者的角度谈谈消息不丢失的看法。
我：关于消息丢失问题，kafka的生产者提供了3种策略来供使用者选择，每种策略各有利弊，需要结合业务的实际状况来选择。

1. 第一种就是生产者不关心消息的情况，只负责发，这种模式无疑速度是最快的，吞吐是最好的，但是可能造成大量的数据丢失，比如在borker出现问题的时候，生产者还不停的发，那么到broker恢复期间的数据都将丢失。
2. 第二种就是生产者需要所有副本都写入成功，不管是Leader副本还是Follower副本，那么当Follower副本越多，吞吐理论就越差，但是这种模式下，消息是最安全的。
3. 第三种就是生产者只需要收到Leader副本的ack即可，不用关心Follower副本的写入情况，它是个折中的做法，保证了一定的安全性的同时也不会太影响吞吐。

如果你不在意自己的数据丢失问题，追求吞吐，比如像log这种，可以采用第一种，如果你非常在意自己的数据安全性，那么就选第二种。如果你希望吞吐稍微好点，同时数据又能安全些，建议第三种，但是第三种在Follower副本出现的问题的时候对生产者来说是无法感知的。

面试官：那你说说一个Follower副本如何被选举成Leader的？
我：在kafka中有这样几个概念：

• AR：所有副本集合
• ISR：所有符合选举条件的副本集合
• OSR：落后太多或者挂掉的副本集合

AR = ISR + OSR，在正常情况下，AR应该是和ISR一样的，但是当某个Follower副本落后太多或者某个Follower副本节点挂掉了，那么它会被移出ISR放入OSR中，kafka的选举也比较简单，就是把ISR中的第一个副本选举成新的Leader节点。比如现在AR=[1,2,3]，1挂掉了，那么ISR=[2,3]，这时会选举2为新的Leader。

面试官捋了捋自己左边的刘海：你还有什么要问我的吗？
我：老师，请问你会组合拳吗？

 面试官：组合拳我不会，但是等会会有很多人组合过来面你。
我：

未完待续...

前言：

字符串是程序开发当中，使用最频繁的类型之一，有着与基础类型相同的地位（字符串不属于基本类型），甚至在 JVM（Java 虚拟机）编译的时候会对字符串做特殊的处理，比如拼加操作可能会被 JVM 直接合成为一个最终的字符串，从而到达高效运行的目的。

1 ：构造方法：

将字节数组或者字符数组转成字符串。

String s1 = new String();//创建了一个空内容的字符串。



String s2 = null;//s2没有任何对象指向，是一个null常量值。



String s3 = "";//s3指向一个具体的字符串对象，只不过这个字符串中没有内容。



//一般在定义字符串时，不用new。



String s4 = new String("abc");



String s5 = "abc"; 一般用此写法



new String(char[]);//将字符数组转成字符串。



new String(char[],offset,count);//将字符数组中的一部分转成字符串。

2 ：一般方法：

    按照面向对象的思想：

2.1 获取：

    2.1.1：获取字符串的长度。length() ;

    2.1.2：指定位置的字符。char charAt(int index);

    2.1.3：获取指定字符的位置。如果不存在返回-1，所以可以通过返回值-1来判断某一个字符不存在的情况。           

 int indexOf(int ch);//返回第一次找到的字符角标



 int indexOf(int ch,int fromIndex); //返回从指定位置开始第一次找到的角标



 int indexOf(String str); //返回第一次找到的字符串角标



 int indexOf(String str,int fromIndex);



 int lastIndexOf(int ch);



 int lastIndexOf(int ch,int fromIndex);



 int lastIndexOf(String str);

 int lastIndexOf(String str,int fromIndex);

    2.1.4：获取子串。

String substring(int start);//从start位开始，到length()-1为止.

String substring(int start,int end);//从start开始到end为止。//包含start位，不包含end位。

substring(0,str.length());//获取整串

2.2 判断：

    2.2.1：字符串中包含指定的字符串吗？

            boolean contains(String substring);

    2.2.2：字符串是否以指定字符串开头啊？

            boolean startsWith(string);

    2.2.3：字符串是否以指定字符串结尾啊？

            boolean endsWith( string);

    2.2.4：判断字符串是否相同

            boolean equals(string);//覆盖了Object中的方法，判断字符串内容是否相同。

    2.2.5：判断字符串内容是否相同，忽略大小写。

            boolean equalsIgnoreCase(string) ;

2.3 转换：

    2.3.1：通过构造函数可以将字符数组或者字节数组转成字符串。

    2.3.2：可以通过字符串中的静态方法，将字符数组转成字符串。

            static String copyValueOf(char[] );



            static String copyValueOf(char[],int offset,int count);



            static String valueOf(char[]);



            static String valueOf(char[],int offset,int count);

    2.3.3：将基本数据类型或者对象转成字符串。

            static String valueOf(char);



            static String valueOf(boolean);



            static String valueOf(double);



            static String valueOf(float);



            static String valueOf(int);



            static String valueOf(long);



            static String valueOf(Object);

    2.3.4：将字符串转成大小写。

            String toLowerCase();

            String toUpperCase();

    2.3.5：将字符串转成数组。

            char[] toCharArray();//转成字符数组。

            byte[] getBytes();//可以加入编码表。转成字节数组。

    2.3.6：将字符串转成字符串数组。切割方法。

            String[] split(分割的规则-字符串);

    2.3.7：将字符串进行内容替换。注意：修改后变成新字符串，并不是将原字符串直接修改。

            String replace(oldChar,newChar);

            String replace(oldstring,newstring);

    2.3.8： String concat(string); //对字符串进行追加。

            String trim();//去除字符串两端的空格

    int compareTo();//如果参数字符串等于此字符串，则返回值 0；如果此字符串按字典顺序小于字符串参数，则返回一个小于 0 的值；如果此字符串按字典顺序大于字符串参数，则返回一个大于 0 的值。

3.StringBuffer 字符串缓冲区：

构造一个其中不带字符的字符串缓冲区，初始容量为 16 个字符。

特点：

1 ：可以对字符串内容进行修改。

2 ：是一个容器。

3 ：是可变长度的。

4 ：缓冲区中可以存储任意类型的数据。

5 ：最终需要变成字符串。

容器通常具备一些固定的方法：

1 ，添加。

    StringBuffer append(data):在缓冲区中追加数据。追加到尾部。

    StringBuffer insert(index,data):在指定位置插入数据。

2 ，删除。

    StringBuffer delete(start,end);删除从start至end-1范围的元素

    StringBuffer deleteCharAt(index);删除指定位置的元素

//sb.delete(0,sb.length());//清空缓冲区。

3 ，修改。

     StringBuffer replace(start,end,string);将start至end-1替换成string

    void setCharAt(index,char);替换指定位置的字符

    void setLength(len);将原字符串置为指定长度的字符串

4 ，查找。 （查不到返回-1）

    int indexOf(string); 返回指定子字符串在此字符串中第一次出现处的索引。



    int indexOf(string,int fromIndex);从指定位置开始查找字符串



    int lastIndexOf(string); 返回指定子字符串在此字符串中最右边出现处的索引。



    int lastIndexOf(string,int fromIndex); 从指定的索引开始反向搜索

5，获取子串。

    string substring(start); 返回start到结尾的子串

    string substring(start,end); 返回start至end-1的子串

6 ，反转。

    StringBuffer reverse();字符串反转

4. StringBuilder 字符串缓冲区：

JDK1.5 出现StringBuiler； 构造一个其中不带字符的字符串生成器，初始容量为 16 个字符。该类被设计用作 StringBuffer 的一个简易替换，用在字符串缓冲区被单个线程使用的时候（这种情况很普遍）。

方法和StringBuffer一样；

5.StringBuffer 和 StringBuilder 的区别：

StringBuffer 线程安全。

StringBuilder 线程不安全。

单线程操作，使用StringBuilder 效率高。

多线程操作，使用StringBuffer 安全。

        StringBuilder sb = new StringBuilder("abcdefg");



        sb.append("ak");  //abcdefgak



        sb.insert(1,"et");//aetbcdefg



        sb.deleteCharAt(2);//abdefg



        sb.delete(2,4);//abefg



        sb.setLength(4);//abcd



        sb.setCharAt(0,'k');//kbcdefg



        sb.replace(0,2,"hhhh");//hhhhcdefg

//想要使用缓冲区，先要建立对象。



        StringBuffer sb = new StringBuffer();     



        sb.append(12).append("haha");//方法调用链。



        String s = "abc"+4+'q';



        s = new StringBuffer().append("abc").append(4).append('q').toString();

class  Test{



    public static void main(String[] args) {



        String s1 = "java";



        String s2 = "hello";



        method_1(s1,s2);



        System.out.println(s1+"...."+s2); //java....hello



       



        StringBuilder s11 = new StringBuilder("java");



        StringBuilder s22 = new StringBuilder("hello");



        method_2(s11,s22);



        System.out.println(s11+"-----"+s22); //javahello-----hello



    }



    public static void method_1(String s1,String s2){



        s1.replace('a','k');



        s1 = s2;



    }



    public static void method_2(StringBuilder s1,StringBuilder s2){



        s1.append(s2);



        s1 = s2;



    }



}

前言

北京时间10月16日0时23分，神舟十三号飞船成功发射，目前三名航天员已经顺利进驻空间站，开始为期6个月的“太空差旅”生活。

国家的航天技术的突飞猛进也让岛上码农很自豪，今天看 Flutter 的动画知识，看到了 AnimatedPositioned 这个组件，可以用于控制组件的相对位置移动。结合这个神舟十三号的发射，灵机一动，正好可以使用AnimatedPositioned 这个组件实现火箭发射动画。话不多说，先上效果！

效果说明

这里其实是两张图片叠加，一张是背景地球星空的背景图，一张是火箭。火箭在发射过程中有两个变化：

• 高度越来越高，其实就是相对图片背景图底部的位置越来越大就可以实现；


• 尺寸越来越小，这个可以控制整个组件的尺寸实现。

然后是动画取消的选择，火箭的速度是越来越快，试了几个 Flutter 自带的曲线，发现 easeInCubic 这个效果挺不错的，开始慢，后面越来越快，和火箭发射的过程是类似的。

AnimatedPositioned介绍

AnimatedPositioned组件的使用方式其实和 AnimatedContainer 类似。只是AnimatedPositioned是 Positioned 组件的替代。构造方法定义如下：

const AnimatedPositioned({

    Key? key,

    required this.child,

    this.left,

    this.top,

    this.right,

    this.bottom,

    this.width,

    this.height,

    Curve curve = Curves.linear,

    required Duration duration,

    VoidCallback? onEnd,

  }) 

前面的参数和 Positioned 一样，后面是动画控制参数，这些参数的定义和 AnimatedContainer 的是一样的：

• curve：动画效果曲线；


• duration：动画时长；


• onEnd：动画结束后回调。

我们可以改变 left，top，width等参数来实现动画过渡的效果。比如我们的火箭发射，就是修改 bottom （飞行高度控制）和 width （尺寸大小控制）来实现的。

火箭发射动画实现

有了上面的两个分析，火箭发射动画就简单了！完整代码如下：

class RocketLaunch extends StatefulWidget {

  RocketLaunch({Key? key}) : super(key: key);



  @override

  _RocketLaunchState createState() => _RocketLaunchState();

}



class _RocketLaunchState extends State<RocketLaunch> {

  var rocketBottom = -80.0;

  var rocketWidth = 160.0;

  @override

  Widget build(BuildContext context) {

    return Scaffold(

      appBar: AppBar(

        title: Text('火箭发射'),

        brightness: Brightness.dark,

        backgroundColor: Colors.black,

      ),

      backgroundColor: Colors.black,

      body: Center(

        child: Stack(

          alignment: Alignment.bottomCenter,

          children: [

            Image.asset(

              'images/earth.jpeg',

              height: double.infinity,

              fit: BoxFit.fill,

            ),

            AnimatedPositioned(

              child: Image.asset(

                'images/rocket.png',

                fit: BoxFit.fitWidth,

              ),

              bottom: rocketBottom,

              width: rocketWidth,

              duration: Duration(seconds: 5),

              curve: Curves.easeInCubic,

            ),

          ],

        ),

      ),

      floatingActionButton: FloatingActionButton(

        child: Text(

          '发射',

          style: TextStyle(

            color: Colors.white,

          ),

          textAlign: TextAlign.center,

        ),

        onPressed: () {

          setState(() {

            rocketBottom = MediaQuery.of(context).size.height;

            rocketWidth = 40.0;

          });

        },

      ),

    );

  }

}

其中一开始设置 bottom 为负值，是为了隐藏火箭的焰火，这样会更有感觉一些。然后就是在点击发射按钮的时候，通过 setState 更改底部距离和火箭尺寸就可以搞定了。

总结

通过神舟十三飞船发射，来一个火箭动画是不是挺有趣？其实这篇主要的知识点还是介绍 AnimatedPositioned 的应用。通过 AnimatedPositioned可以实现很多层叠组件的相对移动变化效果，比如进度条的滑块，滑动开关等。各位 Flutter 玩家也可以利用 AnimatedPositioned 这个组件自己来玩一下好玩的动画效果哦！

基础版本

所有情况下时间复杂度都为O($n^2$n2)

public static void bob(int[] array) {

    // 总共比较n-1轮

    for (int i = 0; i < array.length - 1; i++) {

        // 因为每次都能确定一个最大元素，所以每次都能少比较一次

        for (int j = 0; j < array.length - i - 1; j++) {

            if (array[j] > array[j + 1]) {

                int temp = array[j];

                array[j] = array[j + 1];

                array[j + 1] = temp;

            }

        }

    }

}

上述算法简单粗暴，对任意数组上来就是两层for套着猛干。

如果现在有个有序数组，比如{1,2,3,4,5,6,7,8}，也会白费力气去浪费cpu，这是不必要的。怎么避免呢？

我们看到，如果元素整体有序，那么上述代码中的

if (arr[j] > arr[j + 1])

就永远不会满足，那么就不会发生元素的交换，所以我们可以添加个布尔值，来判断是否发生了元素交换，如果没发生，则认为已经整体有序了，直接跳出即可。如下:

1 进阶版本

这里添加了一个boolean来判断本次是否有元素交换，没有则提前结束。

private static void bob2(int[] arr) {

    int length = arr.length;

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

        boolean swap = false;

        for (int j = 0; j < length - 1; j++) {

            if (arr[j] > arr[j + 1]) {

                int temp = arr[j];

                arr[j] = arr[j + 1];

                arr[j + 1] = temp;



                swap = true;

            }

        }

        if (!swap) break;

    }

}

上述代码可以避免对整体有序的数组瞎排序。但是，如果一个数组不是整体有序，而是局部有序呢，比如{4,3,2,1,5,6,7,8}，我们观察到后半部分是不需要参加排序的，也就是说，只需要将前半部分排序即可。

所以，我们就要确定从哪开始的元素是有序的，也就是确定有序区开始的下标。

那么，怎么确定这个下标呢？

我们可以想一下，对于冒泡排序，如果后面的元素比前面的大，才交换，否则就不交换，也就是说，最后一次发生交换的位置，其后面一定是有序的。比如在位置i发生了交换，i后面没有发生过交换，那么i后面一定是有序的，否则i后面就还会发生交换。

所以，每次元素最后一次交换的位置，就是有序区下标的起点，也是无序区下标的终点。

定义一个下标，每次有元素交换就更新下标，下标后面的元素就是有序的，每次比较只比较下标前面的元素即可。

代码如下:

2 高阶版本

private static void bob3(int[] arr) {

    int length = arr.length;

    int lastSwapIndex = 0;

    // 定义有序区起始点，也就是无序区终点

    int sortedBorder = length - 1;

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

        boolean swap = false;

        // 只比较无序区

        for (int j = 0; j < sortedBorder; j++) {

            if (arr[j] > arr[j + 1]) {

                int temp = arr[j];

                arr[j] = arr[j + 1];

                arr[j + 1] = temp;

                swap = true;

                // 发生了交换，就更新下标

                lastSwapIndex = j;

            }

        }

        // 更新下标

        sortedBorder = lastSwapIndex;

        if (!swap) break;

    }

}

上述代码就可以解决局部有序但整体无序的情况。

但是我们发现，上面的代码，都是从左向右比较的，如果数组是{2,3,4,5,6,7,8,1}这样呢，也是局部有序，但是，如果从左往右比，则很费时间，而从右往左比，则一轮就能结束。

但是！如果从右往左比的话，遇见{8,1,2,3,4,5,6,7}这样的又跪了，怎么办呢？我们可以采用双向比较法，也就是一次从左向右比，一次从右向左比，这就叫鸡尾酒排序。

现在我们使用鸡尾酒排序(双向排序)，每次排序后交换方向，代码如下:

3 最终版本(鸡尾酒排序)

private static void bob4(int[] arr) {

    int length = arr.length;

    for (int i = 0; i < (length >>> 1); i++) {

        boolean swap = false;

        // 从左到右

        for (int j = 0; j < length - 1; j++) {

            if (arr[j] > arr[j + 1]) {

                swap(arr, j, j + 1);

                swap = true;

            }

        }



        if (!swap) break;



        // 从右到左

        swap = false;

        for (int j = length - 1; j > 0; j--) {

            if (arr[j] < arr[j - 1]) {

                swap(arr, j, j - 1);

                swap = true;

            }

        }



        if (!swap) break;

    }

}



// 交换元素

private static void swap(int[] arr, int i, int j) {

    arr[i] ^= arr[j];

    arr[j] ^= arr[i];

    arr[i] ^= arr[j];

}

总结

我们虽然针对冒泡排序进行了多次优化，但是它的时间复杂度还是O(n2)，这是无法避免的，因为冒泡排序每次只是交换相邻元素，也就是只消除了一个逆序对，凡是通过交换相邻元素进行的排序，其时间复杂度都是O(n2)。

为什么呢？因为交换相邻元素每次只消除了一个逆序对。我们来证明下。

学过<线性代数>的应该知道逆序这个定义。

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

证明: 凡是通过交换相邻元素进行的排序，其时间复杂度都是O($n^2$n2)

假设现有任意序列L，其共有n个元素，则其共能组成$C_n^2$Cn2个数对(从n个元素中，挑出2个元素组成的数对)，也就是$(\frac{n(n-1)}{2})$(2n(n−1))个, 其中逆序数为a；然后取其反序列Lr，其逆序数为b，而且b=$(\frac{n(n-1)}{2})$(2n(n−1))-a，因为原来L中的顺序对，在Lr中全变成了逆序对，而且对于任意的数对，要么是顺序，要么是逆序(相同的可以认为是顺序)，所以a+b=$(\frac{n(n-1)}{2})$(2n(n−1))。

所以，L和Lr的总逆序对就是$(\frac{n(n-1)}{2})$(2n(n−1))，那么单个L的逆序对就是$(\frac{n(n-1)}{4})$(4n(n−1))，当n趋近于+∞时，就是$n^2$n2，而通过交换相邻元素每次只能消除一个逆序对，所以总共需要交换$n^2$n2次，所以相应算法的时间复杂度就是O($n^2$n2)。

为什么交换相邻元素只能消除一个逆序对呢，因为只改变了相邻俩元素的位置，它俩前后的该比它大还是比它大，该比它小还是比它小。比如{5,4,3,2,1}，我们交换了3和2，变为{5,4,2,3,1}，我们发现，只是消除了{1,2}这个逆序对，前面的5和4，还是比它俩大，后面的1，还是比它俩小，所以只消除了一个逆序对，这里不再废话。

证明完毕。

其实，我们可以扩展一下，凡是每次只能消除一个逆序对的算法，其时间复杂度都是O($n^2$n2)。也不再废话。

1. 背景介绍

在移动端应用开发场景下，不可避免的要与网络打交道。有时在网络请求失败时，我们想知道网络的质量；有时需要明确的告知用户当前网络质量（比如游戏场景实时显示延迟）。网络监控离不开最经典的TCP/IP模型，基于模型分层统计网络耗时有助于我们更清晰的了解当前网络质量。

TCP/IP参考模型中物理层难以在网络层面统计，网络层有Ping工具，传输层有系统提供的Socket接口，应用层最常用的有HTTP、RTMP协议。本文我们介绍ping工具、DNS解析耗时、TCP连接耗时、HTTP建立耗时。

2. ping

ping是基于网络层ICMP协议的，发送的是ICMP回显请求报文。下面我们先了解下ICMP。

2.1 ICMP（Internet控制报文协议）简介

ICMP是IP层的一个组成部分，主要传递差错报文以及其他需要注意的信息。ICMP报文通常被IP层或更高层协议（TCP或UDP）使用。ICMP的正式规范参见RFC 792[Posterl 1981b]，ICMP封装在IP数据包内部，格式是20字节的IP首部+ICMP报文。ICMP报文格式如下：

所有报文的前4个字节都是一样的，但是剩下的其他字节则互不相同。类型字段可以有15个不同的值，以描述特定类型的ICMP报文，某些CIMP报文还是用代码字段的值来进一步描述不同的条件。校验和字段覆盖整个ICMP报文。

不同类型由报文中的类型字段和代码字段来共同决定。报文可以分为查询报文和差错报文，ICMP差错报文有时需要做特殊处理（如在对ICMP差错报文进行响应时，永远不会生成另一份ICMP差错报文）。

对于我们今天用到的ping程序，使用了：

• 类型为0，代码为0的回显应答的查询报文


• 类型为8，代码为0的请求回显的查询报文

2.2 Ping程序协议简介

ping的工作原理很简单，一台网络设备发送请求等待另一网络设备的回复，并记录下发送时间。接收到回复之后，就可以计算报文传输时间了。只要接收到回复就表示连接是正常的。耗费的时间喻示了路径长度。重复请求响应的一致性也表明了连接质量的可靠性。因此，ping回答了两个基本的问题：是否有连接？连接的质量如何？

我们称发送回显请求的ping程序为客户，称被ping的主机为服务器。大多数的TCP/IP实现都在内核中直接支持ping服务器，这种服务器不是一个用户进程。ICMP回显请求和回显应答报文如下：

Unix系统在实现ping程序时是把ICMP报文中的标识符字段置成发送进程的ID号。这样即使在同一台主机上同时运行了多个ping程序实例，ping程序也可以识别出返回的信息。序列号从0开始，每发送一次新的回显请求就加1。

2.3 ping程序命令介绍

ping程序的主要选项：

1. -c：选项允许用户指定发送报文的数量，例如，ping –c10会发送10个报文然后停止；


2. -f：选项表明报文发送速率与接收主机能够处理速率相同，这一参数可用于链路压力测试或接口性能比较；


3. -l：选项用于计数，尽可能快的发送该数量报文，然后恢复正常，该命令用于测试处理泛洪的能力，需要root权限执行；


4. -i：选项用于用户在两个连续报文之间指定等待秒数。该命令对于将报文间隔开或用在脚本中非常有用。正常情况下，偶然的ping包对数据流的影响是很小的。但重复报文或报文泛洪影响就很大了。因此，使用该选项时需谨慎；


5. -n：选项将输出限制为数字形式，这在碰见DNS问题时很有用；


6. -v：显示更详尽输出，较少输出为-q和-Q；


7. -s：选项指定发送数据的大小。但如果设置的太小，小于8，则报文中就没有空间留给时间戳了。设置报文大小能诊断有路径MTU(Maximum Transmission Unit)设置或分段而导致的问题。如果不使用该选项，ping默认是64字节。

2.4 Android端执行ping程序

Android系统提供了ping命令行程序，在程序中可以通过popen执行系统自带ping程序，下面是执行ping程序的代码：

int RunPingQuery(int _querycount, int interval/*S*/, int timeout/*S*/, const char* dest, unsigned int packetSize) {

    char cmd[256] = {0};





    int index = snprintf(cmd, 256, "ping -c %d -i %d -w %d", _querycount, interval, timeout);



    if (index < 0 || index >= 256) {

        //sprintf return error

        return -1;

    }



    int tempLen = 0;



    if (packetSize > 0) {

        tempLen = snprintf((char*)&cmd[index], 256 - index, " -s %u  %s", packetSize, dest);

    } else {

        tempLen = snprintf((char*)&cmd[index], 256 - index, " %s", dest);

    }



    if (tempLen < 0 || tempLen >= 256 - index) {

        //sprintf return error

        return -1;

    }

    FILE* pp = popen(cmd, "r");



    if (!pp) {

        //popen error

        return -1;

    }



		std::string pingresult_;

    while (fgets(line, sizeof(line), pp) != NULL) {

        pingresult_.append(line, strlen(line));

    }



    pclose(pp);



    if (pingresult_.empty()) {

        //m_strPingResult is empty

        return -1;

    }



    struct PingStatus pingStatusTemp;  //= {0};notice: cannot initial with = {0},crash

    GetPingStatus(pingStatusTemp);

    if (0 == pingStatusTemp.avgrtt && 0 == pingStatusTemp.maxrtt) {

        //remote host is not available

        return -1;

    }

    return 0;

}



int GetPingStatus(struct PingStatus& _ping_status, std::string pingresult_) {

    if (pingresult_.empty())  return -1;



    _ping_status.res = pingresult_;

    std::vector<std::string> vecPingRes;

    str_split('\n', pingresult_, vecPingRes);



    std::vector<std::string>::iterator iter = vecPingRes.begin();



    for (; iter != vecPingRes.end(); ++iter) {

        if (vecPingRes.begin() == iter) {  // extract ip from the result string and assign to _ping_status.ip

            int index1 = iter->find_first_of("(", 0);



            if (index1 > 0) {

                int index2 = iter->find_first_of(")", 0);



                if (index2 > index1) {

                    int size = index2 - index1 - 1;

                    std::string ipTemp(iter->substr(index1 + 1, size));

                    strncpy(_ping_status.ip, ipTemp.c_str(), (size < 16 ? size : 15));

                }

            }

        }  // end if(vecPingRes.begin()==iter)



        int num = iter->find("packet loss", 0);



        if (num >= 0) {

            int loss_rate = 0;

            int i = 3;



            while (iter->at(num - i) != ' ') {

                loss_rate += ((iter->at(num - i) - '0') * (int)pow(10.0, (double)(i - 3)));

                i++;

            }

            _ping_status.loss_rate  = (double)loss_rate / 100;

        }



        int num2 = iter->find("rtt min/avg/max", 0);



        if (num2 >= 0) {

            int find_begpos = 23;

            int findpos = iter->find_first_of('/', find_begpos);

            std::string sminRTT(*iter, find_begpos, findpos - find_begpos);

            find_begpos = findpos + 1;

            findpos = iter->find_first_of('/', find_begpos);

            std::string savgRTT(*iter, find_begpos, findpos - find_begpos);

            find_begpos = findpos + 1;

            findpos = iter->find_first_of('/', find_begpos);

            std::string smaxRTT(*iter, find_begpos, findpos - find_begpos);

            _ping_status.minrtt = atof(sminRTT.c_str());

            _ping_status.avgrtt = atof(savgRTT.c_str());

            _ping_status.maxrtt = atof(smaxRTT.c_str());

        }

    }

    return 0;

}

2.5 iOS端发送ping指令

iOS端主要通过创建socket发送ICMP执行，主要思路如下：

1. 如果设置的是域名，需要将DNS转换为IP；


2. 创建socketn = socket(family, type, protocol)，family为AF_INET, type为SOCK_DGRAM, protocol为IPPROTO_ICMP；


3. 构造ICMP包：

struct icmp {

    u_char    icmp_type;        /* type of message, see below */

    u_char    icmp_code;        /* type sub code */

    u_short    icmp_cksum;        /* ones complement cksum of struct */

    union {

        u_char ih_pptr;            /* ICMP_PARAMPROB */

        struct in_addr ih_gwaddr;    /* ICMP_REDIRECT */

        struct ih_idseq {

            n_short    icd_id;

            n_short    icd_seq;

        } ih_idseq;

        int ih_void;



        /* ICMP_UNREACH_NEEDFRAG -- Path MTU Discovery (RFC1191) */

        struct ih_pmtu {

            n_short ipm_void;

            n_short ipm_nextmtu;

        } ih_pmtu;



        struct ih_rtradv {

            u_char irt_num_addrs;

            u_char irt_wpa;

            u_int16_t irt_lifetime;

        } ih_rtradv;

    } icmp_hun;

#define    icmp_pptr    icmp_hun.ih_pptr

#define    icmp_gwaddr    icmp_hun.ih_gwaddr

#define    icmp_id        icmp_hun.ih_idseq.icd_id

#define    icmp_seq    icmp_hun.ih_idseq.icd_seq

#define    icmp_void    icmp_hun.ih_void

#define    icmp_pmvoid    icmp_hun.ih_pmtu.ipm_void

#define    icmp_nextmtu    icmp_hun.ih_pmtu.ipm_nextmtu

#define    icmp_num_addrs    icmp_hun.ih_rtradv.irt_num_addrs

#define    icmp_wpa    icmp_hun.ih_rtradv.irt_wpa

#define    icmp_lifetime    icmp_hun.ih_rtradv.irt_lifetime

    union {

        struct id_ts {

            n_time its_otime;

            n_time its_rtime;

            n_time its_ttime;

        } id_ts;

        struct id_ip  {

            struct ip idi_ip;

            /* options and then 64 bits of data */

        } id_ip;

        struct icmp_ra_addr id_radv;

        u_int32_t id_mask;

        char    id_data[1];

    } icmp_dun;

#define    icmp_otime    icmp_dun.id_ts.its_otime

#define    icmp_rtime    icmp_dun.id_ts.its_rtime

#define    icmp_ttime    icmp_dun.id_ts.its_ttime

#define    icmp_ip        icmp_dun.id_ip.idi_ip

#define    icmp_radv    icmp_dun.id_radv

#define    icmp_mask    icmp_dun.id_mask

#define    icmp_data    icmp_dun.id_data

};



void __preparePacket(char* _sendbuffer, int& _len) {

    char    sendbuf[MAXBUFSIZE];

    memset(sendbuf, 0, MAXBUFSIZE);

    struct icmp* icmp;

    icmp = (struct icmp*) sendbuf;

    icmp->icmp_type = ICMP_ECHO;

    icmp->icmp_code = 0;

    icmp->icmp_id = getpid() & 0xffff;/* ICMP ID field is 16 bits */

    icmp->icmp_seq = htons(nsent_++);

    memset(&sendbuf[ICMP_MINLEN], 0xa5, DATALEN);   /* fill with pattern */



    struct timeval now;

    (void)gettimeofday(&now, NULL);

    now.tv_usec = htonl(now.tv_usec);

    now.tv_sec = htonl(now.tv_sec);

    bcopy((void*)&now, (void*)&sendbuf[ICMP_MINLEN], sizeof(now));

    _len = ICMP_MINLEN + DATALEN;        /* checksum ICMP header and data */

    icmp->icmp_cksum = 0;

    icmp->icmp_cksum = in_cksum((u_short*) icmp, _len);

    memcpy(_sendbuffer, sendbuf, _len);

}

4. 接收ICMP包：

int PingQuery::__recv() {

    char            recvbuf[MAXBUFSIZE];

    char            controlbuf[MAXBUFSIZE];

    memset(recvbuf, 0, MAXBUFSIZE);

    memset(controlbuf, 0, MAXBUFSIZE);



    struct msghdr   msg = {0};

    struct iovec    iov = {0};

    iov.iov_base = recvbuf;

    iov.iov_len = sizeof(recvbuf);

    msg.msg_name = &recvaddr_;

    msg.msg_iov = &iov;

    msg.msg_iovlen = 1;

    msg.msg_control = controlbuf;



    msg.msg_namelen = sizeof(recvaddr_);

    msg.msg_controllen = sizeof(controlbuf);



    int n = (int)recvmsg(sockfd_, &msg, 0);



    if (n < 0) {

        return -1;

    }

    //解析消息结构

    return n;

}

2.6 ping网络延迟的相关参考

ping外网小于50ms，网络的延迟就算良好，是正常的。

一般来说，网络的延迟PING值越低，速度会越快；但是网络的速度与网络延迟这二者之间没有必然的联系，以下是ping网络延迟的相关参考数据：

• ping网络：1到30ms：速度极快，几乎察觉不出有延迟，玩任何游戏速度都特别顺畅；~


• ping网络：31到50ms：速度良好，可以正常游戏浏览网页，没有明显的延迟情况；~


• ping网络：51到100ms：速度普通，对抗类游戏在一定水平以上能感觉出延迟，偶尔感觉到停顿；


• ping网络：100ms到200ms：速度较差，无法正常游玩对抗类游戏，有明显的卡顿现象，偶尔出现丢包和掉线现象。

3. dns解析耗时

在我们创建socket前，会有一个域名转IP的解析过程。域名系统是一种用于TCP/IP应用程序的分布式数据库，提供了域名和IP地址之间的转换及有关电子邮件的选路信息。在Unix主机中，通过两个库函数gethostbyname和gethostbyaddr来访问的。前者接收主机名字返回IP地址，后者接收IP地址来寻找主机名字。

我们知道域名解析要访问域名服务，连接域名服务是基于UDP还是TCP呢？DNS名字服务器使用的熟知端口号是53，通过tcpdump观察到所有例子都是采用UDP，为什么采用的是UDP呢？

当名字解析器发出一个查询请求，并且返回响应中的TC（删减标志）比特被设置为1时，它就意味着响应的长度超过了512个字节，而仅返回前512个字节。在遇到这种情况时，名字解析器通过使用TCP重发原来的查询请求，它将允许返回的响应超过512个字节。TCP能将用户的数据流分为一些报文段，它就能用多个报文段来传送任意长度的用户数据。

我们要统计DNS解析延时就需要自己创建socket，发送DNS报文并获取响应计算耗时。创建socket需要知道DNS服务地址，怎么获取DNS地址呢？

一种常见的方法通过获取手机配置文件获取：

char buf1[PROP_VALUE_MAX];

char buf2[PROP_VALUE_MAX];

__system_property_get("net.dns1", buf1);

__system_property_get("net.dns2", buf2);

这种方式高版本获取不到DNS服务地址，部分高版本手机可通过下面方法获取：

    char buf3[1024];

    __system_property_get("ro.config.dnscure_ipcfg", buf3);

    std::string dnsCureIPCfgStr(buf3);

    if (!dnsCureIPCfgStr.empty()) {

        const std::vector<std::string> &kVector = splitstr(dnsCureIPCfgStr, '|');

        if (kVector.size() > 2) {

            const std::vector<std::string> &kVector2 = splitstr(dnsCureIPCfgStr, ';');

            if (kVector2.size() > 2) {

                _dns_servers.push_back(kVector2[0]);  // 主DNS

                _dns_servers.push_back(kVector2[1]);  // 备DNS

                return;

            }

        }

    }

该方法获取到DNS列表，以逗号分隔地址列表，内网外网通过|区分。

通过ConnectivityManager获取：

private static String[] getDnsFromConnectionManager(Context context) {

    LinkedList<String> dnsServers = new LinkedList<>();

    if (Build.VERSION.SDK_INT >= 21 && context != null) {

      ConnectivityManager connectivityManager = (ConnectivityManager) context.getSystemService(context.CONNECTIVITY_SERVICE);

      if (connectivityManager != null) {

        NetworkInfo activeNetworkInfo = connectivityManager.getActiveNetworkInfo();

        if (activeNetworkInfo != null) {

          for (Network network : connectivityManager.getAllNetworks()) {

            NetworkInfo networkInfo = connectivityManager.getNetworkInfo(network);

            if (networkInfo != null && networkInfo.getType() == activeNetworkInfo.getType()) {

              LinkProperties lp = connectivityManager.getLinkProperties(network);

              for (InetAddress addr : lp.getDnsServers()) {

                dnsServers.add(addr.getHostAddress());

              }

            }

          }

        }

      }

    }

    return dnsServers.isEmpty() ? new String[0] : dnsServers.toArray(new String[dnsServers.size()]);

  }

获取到的是内网DNS地址。在Android端获取DNS服务地址需要考虑到Android品牌及系统的兼容性。

4. tcp连接耗时统计

TCP耗时从socket创建到连接、收发消息耗时：

1. 创建socketsocket(AF_INET, SOCK_STREAM, IPPROTO_TCP);


2. 建立连接：int connectRet = connect(fsocket, (sockaddr*)&_addr, sizeof(_addr));


3. 发送测试指令：send


4. 接收消息：recv

5. 总结

本文讨论了统计移动端网络耗时网络质量的主要方法：ping耗时、DNS耗时、TCP连接耗时等。在移动端要考虑到获取DNS服务地址的兼容性、tcp socket读写次数等策略，以及简要介绍了网络质量评估方法。

前言

本来想记录一下最近相机相关的知识点的，但发现需要时间整理一下，那这里就介绍一下最近写的直播app中使用的整体架构吧。

由于之前项目大多是用MVC,MVP的整体架构，所以这次一个人写直播项目时就干脆用MVVM进行开发（sunflower的架构让我很馋）

简介

最后现阶段是 基于 MVVM

• UI： AndroidX + DataBinding + RxView + Bravh


• 数据传递： LiveData + LiveEventBus


• 网络请求： Retrofit + RxAndroid + OkHttp3

 // 分包工具

    implementation deps.support.multidex

    // androidX

    implementation deps.androidX.appcompat

    implementation deps.androidX.recyclerview

    implementation deps.androidX.constraintLayout

    implementation deps.androidX.lifecycle

    implementation deps.androidX.palette

    // material

    implementation deps.material.runtime

//    implementation deps.support.design

//    implementation deps.support.recyclerview

    // 腾讯直播SDK

    implementation deps.liteavSdk.liteavsdk_smart

    // 自定义采集控件

    implementation deps.liveKit.runtime

    // OkHttp3 + OkHttp3拦截器 腾讯云需要

    implementation deps.okHttp3.runtime

    implementation deps.okHttp3.interceptor

    // gson

    implementation deps.gson.runtime

    // 腾讯IM

    implementation deps.imsdk.runtime

    // Glide

    implementation deps.glide.runtime

    // 腾讯存储服务

    implementation deps.cosxml.runtime

    // B站弹幕

    implementation deps.DanmakuFlameMaster.runtime

    // rxAndroid + rxJava

    implementation deps.rxAndroid.runtime

    implementation deps.rxAndroid.rxjava

    // rxBinding

    implementation deps.rxBinding.runtime

    // autoDispose

    implementation deps.autoDispose.android

    implementation deps.autoDispose.lifecycle

    // retrofit

    implementation deps.retrofit.runtime

    implementation deps.retrofit.adapter

    implementation deps.retrofit.converter

    // xxpermissions

    implementation deps.xxpermissions.runtime

    // liveEventBus

    implementation deps.liveEventBus.runtime

    // banner

    implementation deps.banner.runtime

    // bravh

    implementation deps.bravh.runtime

    // hilt

//    implementation deps.hilt.runtime

//    implementation deps.hilt.lifecycle

//    kapt deps.hilt.kapt

//    kapt deps.hilt.compiler

    // leakCanary

    debugImplementation deps.leakCanary.runtime

以上就是大致引入的包，然后接下来就是针对业务场景的一整套流程演示了：

登录场景

View

/**

 * 登录页面

 */

public class LoginActivity extends MVVMActivity {

    private static final String TAG = "LoginActivity";



    private LoadingDialog.Builder mLoading; // 加载页面

    private ActivityLoginBinding mDataBinding;// DataBinding

    private LoginViewModel mViewModel;



    @Override

    protected void onCreate(@Nullable Bundle savedInstanceState) {

        super.onCreate(savedInstanceState);

    }



    @Override

    public void initViewModel() {

        mDataBinding = DataBindingUtil.setContentView(this, R.layout.activity_login);

        ViewModelProvider.Factory factory = new LoginViewModelFactory(getApplication(), this);

        mViewModel = ViewModelProviders.of(this, factory).get(LoginViewModel.class);

    }



    @Override

    public void init(){

        mLoading = new LoadingDialog.Builder(LoginActivity.this);

        mLoading.setMessage(getString(R.string.login_loading_text));

        mLoading.create();

    }



    @Override

    public void bindUi(){

        // 登录请求

        RxView.clicks(mDataBinding.loginBtn)

                .subscribeOn(AndroidSchedulers.mainThread())

                .to(AutoDispose.autoDisposable(AndroidLifecycleScopeProvider.from(this)))

                .subscribe(unit ->

                        PermissionTools.requestPermission(this, () ->             //                       校验读写权限

                                        mViewModel.Login(mDataBinding.userNameEdt.getText().toString().trim()  //  登录请求

                                                , mDataBinding.passwordEdt.getText().toString().trim())

                                , Permission.READ_PHONE_STATE));

        // 注册按钮

        RxView.clicks(mDataBinding.registerImg)

                .to(AutoDispose.autoDisposable(AndroidLifecycleScopeProvider.from(this)))

                .subscribe(unit -> startActivity(new Intent(LoginActivity.this, RegisterActivity.class)));  //  跳转注册页面

    }



    /**

     * 不带粘性消息

     */

    @Override

    public void subscribeUi() {

        // 页面状态变化通知  带粘性消息

        mViewModel.getLoginState().observe(this, state -> {

            switch (state) {

                case ERROR_CUSTOMER_SUCCESS_PASS:   // 通过校验

                    mLoading.getObj().show();

                    break;

                case ERROR_CUSTOMER_PASSWORD_ERROR: // 账号错误

                case ERROR_CUSTOMER_USERNAME_ERROR: // 密码错误

                    mDataBinding.passwordEdt.setText("");  // 清空密码输入框

                    ToastUtil.showToast(this, TCErrorConstants.getErrorInfo(state));

                    break;

            }

        });



        // 登录信息返回通知

        LiveEventBus.get(RequestTags.LOGIN_REQ, BaseResponBean.class)

                .observe(this, bean -> {

                    Optional.ofNullable(mLoading).ifPresent(builder -> mLoading.getObj().dismiss());  // 取消 Loading

                    if (bean.getCode() == 200) { // 登录成功

                        ToastUtil.showToast(LoginActivity.this, "登录成功！");

                        startActivity(new Intent(LoginActivity.this, MainActivity.class));

                        finish();

                    } else {                     // 登录失败

                        ToastUtil.showToast(LoginActivity.this, "登录失败:" + TCErrorConstants.getErrorInfo(bean.getCode()));

                        mDataBinding.passwordEdt.setText("");  // 清空密码输入框

                    }

                });

    }



    @Override

    public void initRequest() {



    }



    @Override

    protected void onDestroy() {

        super.onDestroy();

        Optional.ofNullable(mLoading).ifPresent(builder -> mLoading.getObj().dismiss()); // 取消 Loading

    }



}

以上的登录View中包含几个模块

1. initViewModel() 是为了保证MVVM的完整性，进行的VIewModel初始化


2. init() 用于处理一些View中控件的初始化


3. bindUi() 是通过RxView，将页面的事件转换成Observable，然后在于ViewModel中具体的功能进行绑定


4. subscribeUi() 是例如ViewModel中LiveData的变化，或是通过LiveEventBus返回的通知引起的View变化


5. initRequest() 用于处理刚进入View时就要请求的方法

public abstract class MVVMActivity extends AppCompatActivity {



    public abstract void initViewModel();



    public abstract void init();



    public abstract void bindUi();



    public abstract void subscribeUi();



    /**

     * 请求网络数据

     */

    public abstract void initRequest();



    @Override

    protected void onCreate(@Nullable Bundle savedInstanceState) {

        super.onCreate(savedInstanceState);

        initViewModel();

        init();

        subscribeUi();

        initRequest();

    }



    @Override

    protected void onResume() {

        super.onResume();

        bindUi();

    }

}

以上就是每个方法的调用顺序

ViewModel

public class LoginViewModel extends ViewModel {



    private final LoginRepository repository;

    private final LifecycleOwner lifecycleOwner;

    private final MutableLiveData<Integer> loginState = new MutableLiveData<>();  // 登录失败



    public LoginViewModel(LoginRepository repository,LifecycleOwner lifecycleOwner) {

        this.repository = repository;

        this.lifecycleOwner = lifecycleOwner;

    }



    /**

     * 登录行为

     *

     * @param userName 账号

     * @param passWord 密码

     */

    public void Login(String userName, String passWord) {

        if (checkInfo(userName, passWord)) {

            loginState.postValue(ERROR_CUSTOMER_SUCCESS_PASS);

            repository.loginReq(lifecycleOwner, userName, passWord);

        }

    }



    /**

     * 检测用户输入的账号密码是否合法

     *

     * @param userName 账号

     * @param passWord 密码

     * @return true：通过检测 false：未通过

     */

    private boolean checkInfo(String userName, String passWord) {

        if (!TCUtils.isUsernameVaild(userName)) {

            loginState.postValue(ERROR_CUSTOMER_USERNAME_ERROR);

            return false;

        }

        if (!TCUtils.isPasswordValid(passWord)) {

            loginState.postValue(ERROR_CUSTOMER_PASSWORD_ERROR);

            return false;

        }

        return true;

    }



    public LiveData<Integer> getLoginState() {

        return loginState;

    }

}

ViewModel作为连通View以及Model之间的通道，负责管理LiveData，以及一些业务上的逻辑，而View尽量通过LiveData的双向绑定实现UI的更新。

Model

这里时Model的代表 Repository

public class LoginRepository extends BaseRepository {



    private final static String TAG = "LoginRepository";



    private final static String PREFERENCE_USERID = "userid";

    private final static String PREFERENCE_USERPWD = "userpwd";



    /**

     * 单例模式

     */

    @SuppressLint("StaticFieldLeak")

    private static volatile LoginRepository singleton = null;



    /**********************************     本地数据缓存    **************************************/

    private LoginResponBean mUserInfo = new LoginResponBean();  // 登录返回后 用户信息存在这

    private final LoginSaveBean loginSaveBean = new LoginSaveBean();  // 用于保存用户登录信息

    private TCUserMgr.CosInfo mCosInfo = new TCUserMgr.CosInfo();   // COS 存储的 sdkappid



    private Context mContext;              //                                       初始化一些组件需要使用



    /**

     * 初始化缓存数据

     */

    private void initData() {

        loadUserInfo(); //  是否有缓存账号数据

    }



    private void loadUserInfo() {

        if (mContext == null) return;

        TXLog.d(TAG, "xzb_process: load local user info");

        SharedPreferences settings = mContext.getSharedPreferences("TCUserInfo", Context.MODE_PRIVATE);

        loginSaveBean.setmUserId(settings.getString(PREFERENCE_USERID, ""));

        loginSaveBean.setmUserPwd(settings.getString(PREFERENCE_USERPWD, ""));

    }



    private void saveUserInfo() {

        if (mContext == null) return;

        TXLog.d(TAG, "xzb_process: save local user info");

        SharedPreferences settings = mContext.getSharedPreferences("TCUserInfo", Context.MODE_PRIVATE);

        SharedPreferences.Editor editor = settings.edit();

        editor.putString(PREFERENCE_USERID, loginSaveBean.getmUserId());

        editor.putString(PREFERENCE_USERPWD, loginSaveBean.getmUserPwd());

        editor.apply();

    }



    /**

     * 登录请求

     *

     * @param userName 账号

     * @param passWord 密码

     */

    public void loginReq(LifecycleOwner lifecycleOwner, String userName, String passWord) {

        LoginRequestBuilder.loginFlowable(userName, passWord)

                .subscribeOn(Schedulers.io())

                .observeOn(AndroidSchedulers.mainThread())

                .flatMap((Function<BaseResponBean<LoginResponBean>, Flowable<BaseResponBean<AccountInfoBean>>>) loginBean -> {

                    if (loginBean != null) { // 登录成功

                        Optional.ofNullable(loginBean.getData()).ifPresent(userInfo -> mUserInfo = userInfo); //                        保存返回的数据

                        if (loginBean.getMessage() != null) {

                            LiveEventBus.get(RequestTags.LOGIN_REQ, BaseResponBean.class)

                                    .post(new BaseResponBean<>(loginBean.getCode(), loginBean.getMessage()));         // 页面要处理的逻辑（注册返回）

                        }

                        if (loginBean.getCode() == 200

                                && loginBean.getData() != null

                                && loginBean.getData().getToken() != null

                                && loginBean.getData().getRoomservice_sign() != null

                                && loginBean.getData().getRoomservice_sign().getUserID() != null) {

                            setToken(loginBean.getData().getToken());  //                                              Token 保存到本地 用于后期请求鉴权

                            setUserId(loginBean.getData().getRoomservice_sign().getUserID());//                        UserId 保存到本地 当前登录的账号

                            initMLVB();//                                                                              初始化直播SDK

                            return LoginRequestBuilder.accountFlowable(getUserId(), getToken()); //                             请求账户信息

                        } else {

                            return Flowable.error(new ApiException(loginBean.getCode(), loginBean.getMessage()));  // 抛出登录异常  不会继续链式调用

                        }

                    }

                    return Flowable.error(new ApiException(-1, "网络异常"));  // 抛出登录异常  不会继续链式调用

                })

                .subscribeOn(Schedulers.io())

                .observeOn(AndroidSchedulers.mainThread())

                .to(AutoDispose.autoDisposable(AndroidLifecycleScopeProvider.from(lifecycleOwner)))

                .subscribe(new DisposableSubscriber<BaseResponBean<AccountInfoBean>>() {

                    @Override

                    public void onNext(BaseResponBean<AccountInfoBean> accountBean) {

                        if (accountBean != null && accountBean.getCode() == 200) {  // 查询账户信息返回

                            if (accountBean.getData() != null) {

                                if (accountBean.getData().getAvatar() != null)

                                    loginSaveBean.setmUserAvatar(accountBean.getData().getAvatar());  //      保存用户头像信息

                                if (accountBean.getData().getNickname() != null)

                                    loginSaveBean.setmUserName(accountBean.getData().getNickname()); //       用户称呼

                                if (accountBean.getData().getFrontcover() != null)

                                    loginSaveBean.setmCoverPic(accountBean.getData().getFrontcover());//      直播封面？

                                if (accountBean.getData().getSex() >= 0) {

                                    loginSaveBean.setmSex(accountBean.getData().getSex());//                  用户性别

                                }

                            }

                        }

                    }



                    @Override

                    public void onError(Throwable t) {

                        if (t instanceof ApiException) {

                            Log.e("TAG", "request error" + ((ApiException) t).getStatusDesc());

                        } else {

                            Log.e("TAG", "request error" + t.getMessage());

                        }

                    }



                    @Override

                    public void onComplete() {



                    }

                });

    }







    /**

     * 注册账号请求

     *

     * @param username 账户名

     * @param password 密码

     */

    public void registerReq(LifecycleOwner lifecycleOwner,String username, String password) {

        LoginRequestBuilder.registerFlowable(username, password)

                .subscribeOn(Schedulers.io())

                .observeOn(AndroidSchedulers.mainThread())

                .to(AutoDispose.autoDisposable(AndroidLifecycleScopeProvider.from(lifecycleOwner)))

                .subscribe(new DisposableSubscriber<BaseResponBean>() {

                    @Override

                    public void onNext(BaseResponBean registerBean) {

                        if (registerBean != null) {

                            LiveEventBus.get(RequestTags.REGISTER_REQ, BaseResponBean.class)

                                    .post(new BaseResponBean<>(registerBean.getCode(), registerBean.getMessage()));         // 页面要处理的逻辑（登录返回）

                        }

                    }



                    @Override

                    public void onError(Throwable t) {



                    }



                    @Override

                    public void onComplete() {



                    }

                });

    }





    /**

     * 初始化直播SDK

     */

    public void initMLVB() {

        // 校验数据完整性

        if (mUserInfo == null || mContext == null

                || mUserInfo.getRoomservice_sign() == null

                || mUserInfo.getRoomservice_sign().getSdkAppID() == 0

                || mUserInfo.getRoomservice_sign().getUserID() == null

                || mUserInfo.getRoomservice_sign().getUserSig() == null) return;



        LoginInfo loginInfo = new LoginInfo();

        loginInfo.sdkAppID = mUserInfo.getRoomservice_sign().getSdkAppID();

        loginInfo.userID = getUserId();

        loginInfo.userSig = mUserInfo.getRoomservice_sign().getUserSig();



        String userName = loginSaveBean.getmUserName();

        loginInfo.userName = !TextUtils.isEmpty(userName) ? userName : getUserId();

        loginInfo.userAvatar = loginSaveBean.getmUserAvatar();

        MLVBLiveRoom liveRoom = MLVBLiveRoom.sharedInstance(mContext);

        liveRoom.login(loginInfo, new IMLVBLiveRoomListener.LoginCallback() {

            @Override

            public void onError(int errCode, String errInfo) {

                Log.i(TAG, "MLVB init onError: errorCode = " + errInfo + " info = " + errInfo);

            }



            @Override

            public void onSuccess() {

                Log.i(TAG, "MLVB init onSuccess: ");

            }

        });

    }



    /**

     * 自动登录

     */

    public void autoLogin() {



    }



    public void setmContext(Context context) {

        this.mContext = context;

        initData();

    }



    public LoginSaveBean getLoginInfo(){

        return loginSaveBean;

    }



    public static LoginRepository getInstance() {

        if (singleton == null) {

            synchronized (LoginRepository.class) {

                if (singleton == null) {

                    singleton = new LoginRepository();

                }

            }

        }

        return singleton;

    }

}

除去里面复杂的业务逻辑，可以看到Repository的主要作用是数据仓库，如用单例形式保存一些业务上的数据（用户账户信息），负责处理请求中的业务逻辑，通过RxAndroid和Retrofit的组合，来完成一系列的请求，并通过LiveEventBus或是LiveData来通知页面

HttpRequest

网络请求模块

// LoginRequestBuilder.java

public static Flowable<BaseResponBean<LoginResponBean>> loginFlowable(String userName, String passWord) {

    HashMap<String, String> requestParam = new HashMap<>();

    requestParam.put("userid", userName);

    requestParam.put("password", TCUtils.md5(TCUtils.md5(passWord) + userName));

    return RetrofitTools.getInstance(LoginService.class) // 这里是很标准的Retrofit写法

            .login(RequestBodyMaker.getRequestBodyForParams(requestParam));

}



// LoginService.java

@POST("/login")

Flowable<BaseResponBean<LoginResponBean>> login(@Body RequestBody requestBody);



// RetrofitTools.java

public static <T> T getInstance(final Class<T> service) {

    if (okHttpClient == null) {

        synchronized (RetrofitTools.class) {

            HttpLoggingInterceptor interceptor = new HttpLoggingInterceptor(new HttpInteraptorLog());

            interceptor.setLevel(HttpLoggingInterceptor.Level.BODY);

            okHttpClient = new OkHttpClient.Builder()

                        .addInterceptor(interceptor)

                        .connectTimeout(5, TimeUnit.SECONDS)

                        .readTimeout(5, TimeUnit.SECONDS)

                        .writeTimeout(5, TimeUnit.SECONDS)

                        .build();

            }

        }



        if (retrofit == null) {

            synchronized (RetrofitTools.class) {

                if(retrofit == null) {

                    retrofit = new Retrofit.Builder()

                            .baseUrl(TCGlobalConfig.APP_SVR_URL)         //BaseUrl

                            .client(okHttpClient)                       //请求的网络框架

                            .addConverterFactory(GsonConverterFactory.create())     //解析数据格式

                            .addCallAdapterFactory(RxJava3CallAdapterFactory.create()) // 使用RxJava作为回调适配器

                            .build();

                }

            }

        }

    return retrofit.create(service);

}

网络请求返回的Flowable（背压）可以直接通过组合，链式的方式，组合成符合业务逻辑的结构

以上看上去十分简单的一个例子就是糅合了MVVM + RxAndroid + RxView + DataBinding + LiveData + LiveEventBus + Retrofit

一些复杂的列表页面，则加入了Bravh，来优Adapter代码量