Runtime的定义？

为了更好的认识类是怎么工作的，我们将要将一段Object-C的代码用clang看下底层的C/C++的写法。

在Object-C中的NSObject对象中

@interface NSObject <NSObject> {

      Class isa  OBJC_ISA_AVAILABILITY;

}

Objective-C类是由Class类型来表示的，它实际上是一个指向objc_class结构体的指针。

/// An opaque type that represents an Objective-C class.

typedef struct objc_class *Class;

/// Represents an instance of a class.

struct objc_object {

    Class _Nonnull isa  OBJC_ISA_AVAILABILITY;

};



/// A pointer to an instance of a class.

typedef struct objc_object *id;

由此可见可以看到id是指向objc_object的一个指针。

objc_class结构体中的定义如下：

struct objc_class {

    Class _Nonnull isa  OBJC_ISA_AVAILABILITY;



#if !__OBJC2__

    Class _Nullable super_class                              OBJC2_UNAVAILABLE;

    const char * _Nonnull name                               OBJC2_UNAVAILABLE;

    long version                                             OBJC2_UNAVAILABLE;

    long info                                                OBJC2_UNAVAILABLE;

    long instance_size                                       OBJC2_UNAVAILABLE;

    struct objc_ivar_list * _Nullable ivars                  OBJC2_UNAVAILABLE;

    struct objc_method_list * _Nullable * _Nullable methodLists                    OBJC2_UNAVAILABLE;

    struct objc_cache * _Nonnull cache                       OBJC2_UNAVAILABLE;

    struct objc_protocol_list * _Nullable protocols          OBJC2_UNAVAILABLE;

#endif



} OBJC2_UNAVAILABLE;

/* Use `Class` instead of `struct objc_class *` */

在runtime使用当中，我们经常需要用到的字段，它们的定义

isa为Class对象，指向objc_class结构体的指针，也就是这个Class的MetaClass(元类)

类的实例对象的 isa 指向该类;该类的 isa 指向该类的MetaClass，MetaCalss的isa对象指向RootMetaCalss

super_class Class对象指向父类对象

• 如果该类的对象已经是RootClass，那么这个super_class指向nil
  


• 
  MetaCalss的SuperClass指向父类的MetaCalss
  


• 
  MetaCalss是RootMetaCalss，那么该MetaClass的SuperClass指向该对象的RootClass
  

ivars 类中所有 属性的列表，使用场景：我们在字典转换成模型的时候需要用到这个列表找到属性的名称，去取字典中的值，KVC赋值，或者直接Runtime赋值

methodLists 类中 所有的方法的列表，使用场景：如在程序中写好方法，通过外部获取到方法名称字符串，然后通过这个字符串得到方法，从而达到外部控制App已知方法。

cache 主要用于 缓存常用方法列表，每个类中有很多方法，我平时不用的方法也会在里面，每次运行一个方法，都要去 methodLists遍历得到方法，如果类的方法不多还行，但是基本的类中都会有很多方法，这样势必会影响程序的运行效率，所以 cache在这里就会被用上，当我们使用这个类的方法时先判断 cache是否为空，为空从 methodLists找到调用，并保存到 cache，不为空先从 cache中找方法，如果找不到在去 methodLists，这样提高了程序方法的运行效率。

protocols故名思义，这个类中都遵守了 哪些协议，使用场景：判断类是否遵守了某个协议上

在介绍runtime的时候，需要了解下类的本质。

类底层代码、类的本质？

为了更好的认识类是怎么工作的，我们将要将一段Object-C的代码用clang看下底层的C/C++的写法

typedef enum : NSUInteger {

    ThisRPGGame = 0,

    ThisActionGame = 1,

    ThisBattleFlagGame = 2,

} ThisGameType;



@interface Game : NSObject

@property (copy,nonatomic)NSString *Name;

@property (assign,nonatomic)ThisGameType Type;

@end



@implementation Game

@synthesize Name,Type;



- (void)GiveThisGameName:(NSString *)name{

    Name = name;

}



- (void)GiveThisGameType:(ThisGameType)type{

    Type = type;

}

@end

使用命令，在当前文件夹中会出现Game.cpp的文件

# clang -rewrite-objc Game.m

由于生成的文件很庞大，可以仔细去研读，受益匪浅

/*

 * 顾名思义存放property的结构体

 * 当我们使用perproty的时候，会生成这样一个结构体

 * 具体存储的数据为 

 * 实际内容："Name","T@\"NSString\",C,N,VName" 

 * 原型：@property (copy,nonatomic)NSString *Name;

 * 这个具体是怎么实现的，我会在后面继续深入研究，本文主要来理解runtime的理解

 **/

struct _prop_t {

    const char *name;        //名字

    const char *attributes;  //属性

};



/*

 *类中方法的结构体,cmd和imp的关系是一一对应的关系

 *创建对象生成isa指针，指向这个对象的结构体时 

 *同时生成了一个表"Dispatch table"通过这个_cmd的编号找到对应方法

 *使用场景：

 *例如方法交换，方法判断。。。

 **/ 

struct _objc_method {

    struct objc_selector * _cmd;   //SEL 对应着OC中的@selector()

    const char *method_type;       //方法的类型

    void  *_imp;                   //方法的地址

}; 





/*

 * method_list_t 结构体：

 * 原型：

 * - (void)GiveThisGameName:(NSString *)name；

 * 实际存储的方式：

 * {(struct objc_selector *)"GiveThisGameName:", "v24@0:8@16", (void *)_I_Game_GiveThisGameName_}

 * 其主要目的是存储一个数组，基本的数据类型是 _objc_method

 * 扩展：当然这其中有你的属性，自动生成的setter、getter方法

 **/

 

static struct _method_list_t {

    unsigned int entsize;  // sizeof(struct _objc_method)

    unsigned int method_count;

    struct _objc_method method_list[6];

}



/*

 * 表示这个类中所遵守的协议对象

 * 使用场景：

 * 判断类是否遵守这个协议，从而动态添加、重写、交换某些方法，来达到某些目的

 * 

 **/



struct _protocol_t {

    void * isa;  // NULL

    const char *protocol_name;

    const struct _protocol_list_t * protocol_list; // super protocols

    const struct method_list_t *instance_methods;  // 实例方法

    const struct method_list_t *class_methods;     //类方法

    const struct method_list_t *optionalInstanceMethods;  //可选的实例方法

    const struct method_list_t *optionalClassMethods;  //可选的类方法

    const struct _prop_list_t * properties;  //属性列表

    const unsigned int size;  // sizeof(struct _protocol_t)

    const unsigned int flags;  // = 0

    const char ** extendedMethodTypes;  //扩展的方法类型

};



/*

 * 类的变量的结构体

 * 原型：

 * NSString *Name;

 * 存储内容：

 * {(unsigned long int *)&OBJC_IVAR_$_Game$Name, "Name", "@\"NSString\"", 3, 8}

 * 根据存储内容可以大概了解这些属性的工作内容

 **/

struct _ivar_t {

    unsigned long int *offset;  // pointer to ivar offset location

    const char *name;  //名字

    const char *type;  //属于什么变量

    unsigned int alignment; //未知

    unsigned int  size;    //大小

};





/*

 *  这个就是类中的各种方法、属性、等等信息

 *  底层也是一个结构体

 *  名称、方法列表、协议列表、变量列表、layout、properties。。

 *  

 **/

struct _class_ro_t {

    unsigned int flags;

    unsigned int instanceStart;

    unsigned int instanceSize;

    unsigned int reserved;

    const unsigned char *ivarLayout;  //布局

    const char *name;  //名字

    const struct _method_list_t *baseMethods;//方法列表 

    const struct _objc_protocol_list *baseProtocols; //协议列表

    const struct _ivar_list_t *ivars;  //变量列表

    const unsigned char *weakIvarLayout;  //弱引用布局

    const struct _prop_list_t *properties;  //属性列表

};



/*

 * 类本身

 * oc在创建类的时候都会创建一个 _class_t的结构体

 * 我的理解是在runtime中的object-class结构体在底层就会变成_class_t结构体

 **/

struct _class_t {

    struct _class_t *isa;  //元类的指针

    struct _class_t *superclass; //父类的指针

    void *cache;   //缓存

    void *vtable;  //表信息、未知

    struct _class_ro_t *ro;  //这个就是类中的各种方法、属性、等等信息

};





/*

 * 类扩展的结构体

 * 在OC中写的分类

 **/

struct _category_t {

    const char *name;  //名称

    struct _class_t *cls;  //这个是哪个类的扩展

    const struct _method_list_t *instance_methods;  //实例方法列表

    const struct _method_list_t *class_methods;     //类方法列表

    const struct _protocol_list_t *protocols;       //协议列表

    const struct _prop_list_t *properties;          //属性列表

};

类就是多个结构体组合的一个集合体，类中的行为、习惯、属性抽象，按照机器能懂的数据存储到我们底层的结构体当中，在我们需要使用的时候直接获取使用。

那么就开始研究一下，类是如何使用，类的基本使用过程以及过程中runtime所做的事情。

类底层是如何调用方法？

了解了类的组成，那么类是通过什么样的形式去获取方法属性并得到应用?

在Object-C开发中我们经常会说到，对象调用方法，其本质就是想这个对象发送消息，为什么会有这么一说？下面我们来验证一下。

Object-C代码

int main(int argc, char * argv[]) {



    Game *game = [Game alloc];

    [game init];

    [game Play];

    return  0;

}

底层代码的实现

int main(int argc, char * argv[]) {



    Game *game = ((Game *(*)(id, SEL))(void *)objc_msgSend)((id)objc_getClass("Game"), sel_registerName("alloc"));

    game = ((Game *(*)(id, SEL))(void *)objc_msgSend)((id)game, sel_registerName("init"));

    ((void (*)(id, SEL))(void *)objc_msgSend)((id)game, sel_registerName("Play"));

    return 0;

}

代码中使用了

objc_msgSend 消息发送

objc_getClass 获取对象

sel_registerName 获取方法的SEL

因为目前重点是objc_msgSend，其他的Runtime的方法会在后面继续一一道来, So 一个对象调用其方法，在`=Object-C中就是向这个对象发送一条消息，消息的格式

objc_msgSend("对象","SEL","参数"...)

objc_msgSend( id self, SEL op, ... )

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流的学习还在表面 还有许多灵活的用法我还需要继续学习 欢迎大佬指导！

前两天我收到安全部门的一个通知：高风险XSS攻击漏洞。

我们部门首先确定风险来源，并给出了解决方案。前端部分由我解决，并紧急修复上线。

一：那么什么是XSS攻击呢？

人们经常将跨站脚本攻击（Cross Site Scripting）缩写为CSS，但这会与层叠样式表（Cascading Style Sheets，CSS）的缩写混淆。因此，有人将跨站脚本攻击缩写为XSS。恶意攻击者往Web页面里插入恶意html代码，当用户浏览该页之时，嵌入其中Web里面的html代码会被执行，从而达到恶意用户的特殊目的。主要指的自己构造XSS跨站漏洞网页或者寻找非目标机以外的有跨站漏洞的网页。XSS是web安全最为常见的攻击方式，在近年来，常居web安全漏洞榜首。

光看这个定义，很多同学一定不理解是什么意思，下面我会模拟XSS攻击，同学们应该就知道怎么回事了。
在模拟XSS攻击之前，我们先来看看XSS攻击的分类。

二：XSS攻击有几种类型呢？

①反射型XSS攻击（非持久性XSS攻击）

②存储型XSS攻击（持久型XSS攻击）

③DOM-based型XSS攻击

三：接下来我们将模拟这几种XSS攻击

第一种：反射型XSS攻击（非持久性XSS攻击）

反射型XSS攻击一般是攻击者通过特定手法，诱使用户去访问一个包含恶意代码的URL，当受害者点击这些专门设计的链接的时候，恶意代码会直接在受害者主机上的浏览器执行。此类XSS攻击通常出现在网站的搜索栏、用户登录口等地方，常用来窃取客户端Cookies或进行钓鱼欺骗。

下面我们来看一个例子：

这是一个普通的点击事件，当用户点击之后，就执行了js脚本，弹窗了警告。

你会说，这能代表啥，那如果这段脚本是这样的呢？

当浏览器执行这段脚本，就盗用了用户的cookie信息，发送到了自己指定的服务器。你想想他接下来会干什么呢？

第二种：存储型XSS攻击（持久型XSS攻击）

攻击者事先将恶意代码上传或者储存到漏洞服务器中，只要受害者浏览包含此恶意代码的页面就会执行恶意代码。这意味着只要访问了这个页面的访客，都有可能会执行这段恶意脚本，因此存储型XSS攻击的危害会更大。此类攻击一般出现在网站留言、评论、博客日志等交互处，恶意脚本存储到客户端或者服务端的数据库中。

增删改查在web管理系统中中很常见，我们找到一个新增功能页面，这以一个富文本输入框为例，输入以下语句，点击保存，再去查看详情，你觉得会发生什么？

没错，如果是前端的同学或许已经猜到了，h是浏览器的标签，这样传给服务器，服务器再返回给前端，浏览器渲染的时候，会把第二行当成h1标签来渲染，就会出现以下效果，第二行文字被加粗加大了。

这里我只是输入了普通的文本，而近几年随着互联网的发展，出现了很多h5多媒体标签，那要是我利用它们呢？
不清楚的同学，可自行打开W3cschool网站查看：

黑客是怎么攻击我们的呢？黑客会自己写一些脚本，来获取我们的cookies敏感等信息，然后他发送到他自己的服务器，当他拿到我们这些信息后，就能绕过前端，直接调后端的接口，比如提现接口，想想是不是很恐怖！！！

这里我利用一个在线远程网站来模拟XSS攻击。地址如下：
svg.digi.ninja/xss.svg**
目前网站还能访问，同学们可以自己体验一下，如果后期链接失效不可访问了，同学们可以重新找一个，或者自己手写一个脚本，然后伪装成svg上传到自己的服务器。
我们在地址栏输入上面这个地址，来看看实际效果，提示你已经触发了XSS攻击。

当我们点击确定，出现了一个黑人，哈哈哈，恭喜你，你银行卡里的钱已经全被黑客取走了。这就是黑客得逞后的样子，他得逞后还在嘲讽你。

接下来，我们利用多媒体标签和这个脚本来攻击我们实际的的网站。

这里记得在地址前面加上//表示跨越，如图：

当我们点击保存之后，再去查看详情页面发现。

哦豁，刚刚那个网站的场景在我们的web管理系统里面触发了，点击确定，那个小黑人又来嘲讽你了。

这脚本在我们的管理系统成功运行，并获取了我们的敏感信息，就可以直接绕过前端，去直接掉我们后端银行卡提现接口了。并且这类脚本由于保存在服务器中，并存着一些公共区域，网站留言、评论、博客日志等交互处，因此存储型XSS攻击的危害会更大。

第三种：DOM-based型XSS攻击

客户端的脚本程序可以动态地检查和修改页面内容，而不依赖于服务器端的数据。例如客户端如从URL中提取数据并在本地执行，如果用户在客户端输入的数据包含了恶意的JavaScript脚本，而这些脚本没有经过适当的过滤或者消毒，那么应用程序就可能受到DOM-based型XSS攻击。

下面我们来看一个例子

这段代码的意思是点击提交之后，将输入框中的内容渲染到页面。效果如下面两张图。

①在输入框中输入内容

②点击确定，输入框中的内容渲染到页面

那如何我们输内容是不是普通文本，而是恶意的脚本呢？

没错，恶意的脚本在渲染到页面的时候，没有被当成普通的文本，而是被当成脚本执行了。

总结：XSS就是利用浏览器不能识别是普通的文本还是恶意代码，那么我们要做的就是阻止恶意代码执行，比如前端的提交和渲染，后端接口的请求和返回都要对此类特殊标签做转义和过滤处理，防止他执行脚本，泄露敏感的数据。感兴趣的同学可以根据我上面的步骤，自己去模拟一个XSS攻击，让自己也体验一次当黑客的感觉。

最近做项目的时候，就是产品经理给的图总是很大，不压缩。每天要处理这些图片真的很累哇。于是一怒之下写下了这个**「vscode 插件」。「插件核心功能是压缩，然后上传图片」。 压缩的网站其实就是「tinypng」** 这个网站然后图片压缩后，然后再上传到cdn上，然后然后这个压缩过的url 直接放到我们的粘贴板上。下面跟着我的步伐一步一步来写实现它。 先看效果图：

演示gif 图

效率对比

开发这个主要是提高团队开发效率， 绝不是为了炫技。 看图：

image-20211017224316386

需求分析

1. 可在vscodde的setting中配置上传所需的参数，可以根据个人的需求单独进行配置；


2. 2.在开发过程中可在编辑器中直接选择图片并上传到阿里云将图片链接填写到光标位置；

中文文档

❝

一个好的文档可以帮助我们更容易的开发：如果英文比较好的同学可以直接看Vscode英文文档，这里api会比较全，可以找到更简洁的方案实现功能； 不过我的话，还是花很久时间找了这篇比较全的中文文档

❞

搭建项目

vscode 插件的开发需要全局安装脚手架：

 npm install -g yo generator-code

安装成功后，直接使用对应命令 「yo code」 来生成一个插件工程：

vscode开始这个页面

这就开始脚手架页面了，可以选择自己习惯的配置。输入对应的配置 然后 就创建了对应的项目了。

我们看下项目结构：

插件结构

插件运行

这时候我们先要去测试下我的这个插件到底是不是能够成功运行。在项目根目录按住F5 然后运行 「vscode extension」 ,这时候会出现一个新的vscode 窗口，但是我这里遇到的一个问题就是这个：

插件

我大概理解了下就是vscode 插件的依赖版本比较低：

目前是：

插件

这上面说的很清楚 vscode扩展指定 与其兼容的 vscode 版本兼容 很显然我这里太高了， 给他降级。然后给他换成1.60.2 完美解决

插件运行——成功演示

ok, 怎么查看自己查看插件有没有成功运行呢， 分为3步

1. F5 开始调试 —— 产生一个新的调试窗口


2. 在新的窗口—— command + shift + P 找到 hello word


3. 点击运行看见弹窗 显示 表示弹窗运行成功

直接看下面的gif 图吧：

gif 演示

插件开发——配置参数

配置插件的属性面板， 这个主要是要在package.json 配置一些参数

配置参数

第一个参数我们稍后再讲其实就是对应你注册的自定义command， 下面的配置 其实就是对应插件属性面板一些参数，然后你可以通过vscode 的一些api 可以获得你配置的这些参数

下面我是我配置的参数，你可以会根据插件自定义去调整

"properties": {

    "upload_image.domain": {

      "type": "string",

      "default": "",

      "description": "设置上传域名"

    },

    "upload_image.accessKey": {

      "type": "string",

      "default": "",

      "description": "设置oss上传accessKey"

    },

    "upload_image.secretKey": {

      "type": "string",

      "default": "",

      "description": "设置oss上传secretKey"

    },

    "upload_image.scope": {

      "type": "string",

      "default": "",

      "description": "设置oss上传上传空间"

    },

    "upload_image.gzip": {

      "type": "boolean",

      "default": "true",

      "description": "是否启用图片压缩"

    }

  }

大概就是这几个参数， 然后我们测试下同样打开f5 然后在新窗口 找到设置然后找到扩展， 设置项其实就是对应我们的 上面的**「title」**

压缩图片。

我们看下效果：

效果

插件开发——配置右键菜单

这个功能描述大概就是，你在写的时候突然要上传，直接点击鼠标右键，然后直接选择图片。 对就是这个简单的东西，做东西需要从用户的角度考虑，一定要爽，能省一步是一步。呵呵哈哈哈

这个配置其实就是在 还是在刚才的**「package.json」** 上继续配置：

"menus": {

    "editor/context": [

      {

        "when": "editorFocus",

        "command": "extension.choosedImage",

        "group": "navigation"

      }

    ]

  }

when:就是你鼠标在编辑的时候

command: 就是自定义的事件，我叫他选择图片， 这个其实就是在extension.js 注册的事件名字 tips： 就是对应的事件名称

let texteditor = vscode.commands.registerTextEditorCommand(

  'extension.choosedImage', ... )

这个其实就是在extension .js 注册对应的事件名，这里的**「事件名」** 一定要和 「package.json」 中文件对应不然会出不来的。 给大家演示下：

图片

重启插件 按下f5 然后按下右键就有我们自定义的右键菜单了。但是问题来了我们按住右键 是不是得弹出一个选择图片的框哇，不然怎么上传对吧？

打开图片上传 弹框

强大的vscode支持了内置的api, 支持打开：

const uri = await vscode.window.showOpenDialog({

    canSelectFolders: false,

    canSelectMany: false,

    filters: {

      images: ['png', 'jpg','apng','jpeg','gif','webp'],

    },

  }); 

就是这个 api, 你可以过滤出想要的图片， 在filters 里面，然后呢 吐出给我们的是对应图片的路径。

我们看下效果：

读取图片数据

其实这个时候我们我们已经有了图片的路径，这时候就要利用 **「node.js」**的fs 模块 去读取 这个图片的数据 buffer ,这个其实为了方便我们将图片上传到oss 上。 代码如下：

const uri = await vscode.window.showOpenDialog({

    canSelectFolders: false,

    canSelectMany: false,

    filters: {

      images: ['png', 'jpg','apng','jpeg','gif','webp'],

    },

  }); 

let imgBuffer =  await fs.readFile(uri[0].path);

这里还涉及到一个就是说： 本地图片的名字 进行加密， 不能上传到oss 各种中文啥的， 显示的我们很不专业哇

所以这里写了一个MD5的转换

function md5Name(name) {

 const index = name.lastIndexOf('.')

 const sourceFileName = name.substring(0, index)

 const suffix = name.substring(index)

 const fileName = md5(sourceFileName + Date.now()) + suffix

 return fileName.toLowerCase()

}

就是将名字搞成花里胡哨的样子，呵呵哈哈哈！

图片压缩

我们得到图片的buffer 数据后其实要对图片要支持压缩， 其实社区里面有很多方案， 这里的话我调研的很多还是决定使用tinfiy, 他也有对应的**「node.js」** 使用的他主要理由主要是看下面这张图：

apng

对的这家伙支持**「apng」, 其他的不是很清楚。 但是他不是免费的一个人一个月免费「500」** 次， 思考了下还行，我们也用不到辣么多次最终还是考虑用它去实现。

安装

安装npm包并添加到您应用的依赖中，您就可以使用Node.js客户端：

npm install --save tinify

认证

您必须提供您的API密钥来使用API。您可以通过注册您的姓名和Email地址来获取API密钥。 请秘密保存API密钥。

const tinify = require("tinify");

tinify.key = "YOUR_API_KEY";

这个的话其实就是你的邮箱去注册一下，然后把你对应的**「key」** 去激活其实就可以了

如图

其实就是下面这个你的key 设置激活就好了

tinify压缩图片

您可以上传任何JPEG或PNG图片到Tinify API来进行压缩。我们将自动检测图片类型并相应的使用TinyPNG或TinyJPG引擎进行优化。 只要上传文件或提供图片URL，就会开始压缩。

您可以选择一个本地文件作为源并写入到另一个文件中。

const source = tinify.fromFile("unoptimized.webp");

source.toFile("optimized.webp");

您还可以从缓冲区（buffer）（二进制字符串）上传图片并获取压缩后图片的数据。

const fs = require("fs");

fs.readFile("unoptimized.jpg", function(err, sourceData) {

  if (err) throw err;

  tinify.fromBuffer(sourceData).toBuffer(function(err, resultData) {

    if (err) throw err;

    // ...

  });

});

代码实现

function compressBuffer(sourceData, key = 'xxx') {

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

  tinify.key = key;

  tinify.fromBuffer(sourceData).toBuffer(function(err, resultData) {

   if(resultData) {

    resolve(resultData)

   }

   if (err) {

    reject(err);

   }

   // ...

  });

 })

}

基于他这个封装了一个promise, 这个**「fromBuffer」** , 到 「toBuffer」 是真的好用。 哈哈哈哈很香，记得一定要设置key 不然promise 直接会报错的， 设置key的方法 就在上面👆🏻， 然后这样其实我们就获得了压缩的图片数据了。

上传图片到oss

这里的话其实有的使用七牛云、 有的使用阿里云。去上传图片，或者是ajax 去上传其实都可以

一般都是要获取token 啥的以及各种签名信息，然后直接上传就好了， 然后呢你就可以获得一张图片地址了。代码我就不展示了， 都是前端应该都懂。这里我说下我遇到的一些问题

1. 第一个就是js 跑的 是node js 的环境， 如果使用**「FormData」** 这个类的话 他直接会报找不到， 这个方法是 undefined, 还有**「fetch」**, 所以说要去安装对应node js 包 ，我这里使用的是 「cross-fetch」 和 「form-data」

这里我说一下配置的问题就是你在扩展中如何获得的你配置的参数：

"configuration": [

   {

    "title": "压缩图片",

    "properties": {

     "upload_image.secretKey": {

      "type": "string",

      "default": "",

      "description": "设置tinify的ApIKey"

     },

     "upload_image.secretTokenUrl": {

      "type": "string",

      "default": "",

      "description": "设置得物的tokenUrl"

     }

    }

   }

  ]

每个属性前面对应的 upload_image 其实你在扩展中你可以通过：

const imageConfig =  vscode.workspace.getConfiguration('upload_image')

然后你就可以拿到配置了，upload_image 后面的属性 其实对应的就是对象中的key 然后呢你就可以对吧操作了

这个东西还是具体项目， 具体分析，你们自己 可以针对自己的项目去配置

插件开发——图片链接写入编辑器中

通过上面的方法已经可以获得图片上传后的链接，接下来就是将链接写入编辑器中： 首先判断编辑器选择位置，editor.selection中可以获得光标位置、光标选择首尾位置。若光标有选中内容则editBuilder.replace替换选中内容，否则editBuilder.insert在光标位置插入图片链接:

// 将图片链接写入编辑器

function addImageUrlToEditor(url) {

 let editor = vscode.window.activeTextEditor

 if (!editor) {

   return

 }

 const { start, end, active } = editor.selection

 if (start.line === end.line && start.character === end.character) {

   // 在光标位置插入内容

   const activePosition = active

   editor.edit((editBuilder) => {

  editBuilder.insert(activePosition, url)

   })

 } else {

   // 替换内容

   const selection = editor.selection

   editor.edit((editBuilder) => {

  editBuilder.replace(selection, url)

   })

 }

}

插件发布

到这里，其实一整个vscode插件 其实已经可以开发完成了， 然后我们要把他进行打包发布到vscode 的应用市场

创建账号

我是直接github 登录创建， 首先我们进入文档中提到的主页，完成验证登录后创建一个组织。

创建一个组织

创建发布者

进入下面这个页面 marketplace.visualstudio.com/manage/publ…** 插件发布者， 给大家看下我的：

发布者

打包发布

首先全局 安装脚手架

npm install -g vsce

然后 cd 到当前插件目录 使用下面命令

$ cd myExtension

$ vsce package

# myExtension.vsix generated

这里的打包会报一些error:

第一个就是插件的package.json 增加发布者

"publisher": "Fly",

如果给插件加图标： 其实在项目中创建一个文件夹： image 然后把图片放进去： 同时也要在package.json 中配置

"icon": "images/dewu.jpeg",

这里可能有⚠️，不过没什么关系，继续跑就完事了

warn

最后的话其实就是要写readme ,不然 不让你发布。

打包上传

一切准备就绪： 命令行 输入

vsce package 

然后项目中就会出现：

照片

然后可以把这个东西拖到页面这个页面

marketplace.visualstudio.com/manage/publ…

上传

然后点击上传就好了，你就可以在vscode 插件商场可以看到自己写的插件了

现在 JS 的很多库都用 typescript 写了，面试也几乎必问 typescript，可能你对 ts 的各种语法和内置高级类型都挺熟悉了，对 ts 的配置、命令行的使用也没啥问题，但总感觉对 ts 的理解没那么深，苦于没有很好的继续提升的方式。这时候我推荐你研究下 typescript compiler api。

typescript 会把 ts 源码 parse 成 AST，然后对 AST 进行各种转换，之后生成 js 代码，在这个过程中会对 AST 进行类型检查。typescript 把这整个流程封装到了 tsc 的命令行工具里，平时我们一般也是通过 tsc 来编译 ts 代码和进行类型检查的。

但其实 ts 除了提供 tsc 的命令行工具外，也暴露了很多 api，同时也能自定义 transformer。这就像 babel 可以编译 esnext、ts 语法到 js，可以写 babel 插件来转换代码，也暴露了各种 api 一样。只不过 typescript transformer 的生态远远比不上 babel 插件，知道的人也比较少。

其实 typescript transformer 能做到一些 babel 插件做不到的事情：

babel 是从 ts、exnext 等转 js，生成的 js 代码里会丢失类型信息，不能生成 ts 代码。

babel 只是转换 ts 代码，并不会进行类型检查。

这两个 babel 插件做不到的事情，通过 typescript transformer 都可以做到。

而且，学会 typescript compiler 的 api 能够帮助你深入 typescript 的编译流程，更好的掌握 typescript。

说了这么多，我们通过一个例子来入门下 typescript transformer 吧。

案例描述

这样一段 ts 代码：

type IsString<T> = T extends string ? 'Yes' : 'No';



type res = IsString<true>;

type res2 = IsString<'aaa'>;

我们希望能把 res 和 res2 的类型的值算出来，通过注释加在后面。

像这样：

type IsString<T> = T extends string ? 'Yes' : 'No';



type res = IsString<true> //No;

type res2 = IsString<'aaa'> //Yes;

这个案例既用到了 transformer api，又用到了类型检查的 api。

下面我们来分析下思路：

思路分析

我们首先要把 ts 代码 parse 成 AST，然后通过 AST 找到要转换的节点，这里是 TypeReference 节点。

可以用 astexplorer.net 看一下:

IsString 是一个 TypeReference，也就是引用了别的类型，然后有 typeName 是 IsString 和类型参数 typeArguments，这里的类型参数就是 true。

是不是很像一个函数调用，这就是高级类型的本质，通过把类型参数传到引用的高级类型里求出最终的类型。

然后我们找到 TypeReference 的节点之后就可以通过 type checker 的 api 来求出类型值，之后创建一个注释节点添加到后面就行了。

转换完 AST，再把它打印成 ts 代码字符串。

思路就是这样，接下来我们具体来实现下，也熟悉下 ts 的 api。

代码实现

parse 代码成 AST 需要先指定要编译的文件和编译参数（createProgram 的 api），然后就可以拿到不同文件的 AST 了（getSourceFile 的 api）。

const ts = require("typescript");



const filename = "./input.ts";

const program = ts.createProgram([filename], {}); // 第二个参数是 compiler options，就是配置文件里的那些



const sourceFile = program.getSourceFile(filename);

这里的 sourceFile 就是 AST 的根结点。

接下来我们要对 AST 进行转换，使用 transform 的 api：

const  { transformed } = ts.transform(sourceFile, [

    function (context) {

        return function (node) { 

            return ts.visitNode(node, visit); 



            function visit(node) {

                if (ts.isTypeReferenceNode(node)) {

                   // ...

                }

                return ts.visitEachChild(node, visit, context)

            }

        };

    }

]);

transform 要传入遍历的 AST 以及 transfomerFactory。

AST 就是上面 parse 出的 sourceFile。

transformerFactory 可以拿到 context 中的很多 api 来用，它的返回值就是转换函数 transformer。

transformer 参数是 node，返回值是修改后的 node。

要修改 node 就要遍历 node，使用 visit api 和 vistEachChild 的 api，过程中根据类型过滤出 TypeReference 的节点。

之后对 TypeReference 节点做如下转换：

if (ts.isTypeReferenceNode(node)) {

    const type = typeChecker.getTypeFromTypeNode(node);



    if (type.value){

        ts.addSyntheticTrailingComment(node, ts.SyntaxKind.SingleLineCommentTrivia, type.value);

    }

}

也就是通过 typeCheker 来拿到 IsString 这个类型的最终类型值，然后通过 addSyntheticTrailingComment 的 api 在后面加一个注释。

其中用到的 typeChecker 是通过 getTypeChecker 的 api 拿到的：

const typeChecker = program.getTypeChecker();

这样就完成了我们的转换 ts AST 的目的。

然后通过 printer 把 AST 打印成 ts 代码。

const printer =ts.createPrinter();



const code = printer.printNode(false, transformed[0], transformed[0]);



console.log(code);

这样就可以了，我们来测试下。

测试之前，全部代码放这里了：

const ts = require("typescript");



const filename = "./input.ts";

const program = ts.createProgram([filename], {}); // 第二个参数是 compiler options，就是配置文件里的那些



const sourceFile = program.getSourceFile(filename);



const typeChecker = program.getTypeChecker();



const  { transformed } = ts.transform(sourceFile, [

    function (context) {

        return function (node) { 

            return ts.visitNode(node, visit); 

            function visit(node) {

                if (ts.isTypeReferenceNode(node)) {

                    const type = typeChecker.getTypeFromTypeNode(node);



                    if (type.value){

                        ts.addSyntheticTrailingComment(node, ts.SyntaxKind.SingleLineCommentTrivia, type.value);

                    }

                }

                return ts.visitEachChild(node, visit, context)

            }

        };

    }

]);



const printer =ts.createPrinter();



const code = printer.printNode(false, transformed[0], transformed[0]);



console.log(code);

测试效果

经测试，我们达到了求出类型添加到后面的注释里的目的

复盘

激不激动，这是我们第一个 ts transformer 的例子，虽然功能比较简单，但是我们也学会了如何对 ts 代码做 parse、 transform，print，以及 type check。

其实 babel 也有 parse、transform、generate 这 3 步，但没有 type check 的过程，也不能打印成 ts 代码。

用 compiler api 的过程中你会发现原来高级类型就是一个 typeReference，需要传入 typeArguments 来求值的，从而对高级类型的理解更深了。

总结

对 typescript 语法和配置比较熟悉后，想更进一步的话，可以学习下 compiler 的 api 来深入 ts 的编译流程。它包括 transfomer、type checker 等 api，可以达到像 babel 插件一样的转换 ts 代码的目的，而且还能做类型检查。

我们通过一个例子来熟悉了下 typescript 的编译流程和 transformer 的写法。

当你需要修改 ts 代码然后生成 ts 代码的时候，babel 是做不到的，它只能生成 js 代码，这时候可以考虑下 typescript 的自定义 transformer。

而且用 typescript compiler api 能够加深你对 ts 编译流程和类型检查的理解。

ts compiler api 尤其是其中的自定义 transformer 是 typescript 更进一层的不错的方向。

在正式学习Event Loop之前，先需要解决几个问题：

什么是同步与异步？

JavaScript是一门单线程语言，那如何实现异步？

同步任务和异步任务的执行顺序如何？

异步任务是否存在优先级？

同步与异步

计算机领域中的同步与异步和我们现实社会的同步和异步正好相反。现实中的同步，就是同时进行，突出的是"同"，比如看足球比赛的时候吃着零食，两件事情同时发生；异步就是不同时。但计算机中与现实存在一定差异。

举个栗子

天气冷了，早上刚醒来想喝点热水暖暖身子，但这每天起早贪黑996，晚上回来太累躺下就睡，没开水啊，没法子，只好急急忙忙去烧水。

现在早上太冷了啊，不由得在被窝里面多躺了一会，收拾的时间紧紧巴巴，不能空等水开，于是我便趁此去洗漱，收拾自己。
洗漱完，水开了，喝到暖暖的热水，舒服啊！

舒服完，开启新的996之日，打工人出发！

烧水和洗漱是在同时间进行的，这就是计算机中的异步。

计算机中的同步是连续性的动作，上一步未完成前，下一步会发生堵塞，直至上一步完成后，下一步才可以继续执行。例如：只有等水开，才能喝到暖暖的热水。

单线程却可以异步？

JavaScript的确是一门单线程语言，但是浏览器UI是多线程的，异步任务借助浏览器的线程和JavaScript的执行机制实现。
例如，setTimeout就借助浏览器定时器触发线程的计时功能来实现。

浏览器线程

1. GUI渲染线程
   
   
   
   • 绘制页面，解析HTML、CSS，构建DOM树等
   
   
   • 页面的重绘和重排
   
   
   • 与JS引擎互斥(JS引擎阻塞页面刷新)
   
   
   
   


2. JS引擎线程
   
   
   
   • js脚本代码执行
   
   
   • 负责执行准备好的事件，例如定时器计时结束或异步请求成功且正确返回
   
   
   • 与GUI渲染线程互斥
   
   
   
   


3. 事件触发线程
   
   
   
   • 当对应的事件满足触发条件，将事件添加到js的任务队列末尾
   
   
   • 多个事件加入任务队列需要排队等待
   
   
   
   


4. 定时器触发线程
   
   
   
   • 负责执行异步的定时器类事件：setTimeout、setInterval等
   
   
   • 浏览器定时计时由该线程完成，计时完毕后将事件添加至任务队列队尾
   
   
   
   


5. HTTP请求线程
   
   
   
   • 负责异步请求
   
   
   • 当监听到异步请求状态变更时，如果存在回调函数，该线程会将回调函数加入到任务队列队尾
   
   
   
   

同步与异步执行顺序

1. JavaScript将任务分为同步任务和异步任务，同步任务进入主线中中，异步任务首先到Event Table进行回调函数注册。


2. 当异步任务的触发条件满足，将回调函数从Event Table压入Event Queue中。


3. 主线程里面的同步任务执行完毕，系统会去Event Queue中读取异步的回调函数。


4. 只要主线程空了，就会去Event Queue读取回调函数，这个过程被称为Event Loop。

举个栗子

• setTimeout(cb, 1000)，当1000ms后，就将cb压入Event Queue。


• ajax(请求条件, cb)，当http请求发送成功后，cb压入Event Queue。

EventLoop执行流程

Event Loop执行的流程如下：

下面一起来看一个例子，熟悉一下上述流程。

// 下面代码的打印结果？

// 同步任务 打印 first

console.log("first");     

setTimeout(() => {        

// 异步任务 压入Event Table 4ms之后cb压入Event Queue

  console.log("second");

},0)

// 同步任务 打印last

console.log("last");     

// 读取Event Queue 打印second

常见异步任务

DOM事件

AJAX请求

定时器setTimeout和setlnterval

ES6的Promise

异步任务的优先级

下面继续来看一个案例：

setTimeout(() => {

  console.log(1);

}, 1000)

new Promise(function(resolve){

    console.log(2);

    for(var i = 0; i < 10000; i++){

        i == 99 && resolve();

    }

}).then(function(){

    console.log(3)

});

console.log(4)

按照上面的学习：
可以很轻松得出案例的打印结果：2，4，1，3。

Promise定义部分为同步任务，回调部分为异步任务

将案例代码在控制台运行，最终返回结果却有些出人意料：

刚看到如此结果，我的第一感觉是，setTimeout函数1s触发太慢导致它加入Event Queue的时间晚于Promise.then

于是我修改了setTimeout的回调时间为0(浏览器最小触发时间为4ms)，但结果仍为发生改变。

那么也就意味着，JavaScript的异步任务是存在优先级的。

宏任务和微任务

JavaScript除了广义上将任务划分为同步任务和异步任务，还对异步任务进行了更精细的划分。异步任务又进一步分为微任务和宏任务。

• history traversal任务（h5当中的历史操作）


• process.nextTick（nodejs中的一个异步操作）


• MutationObserver（h5里面增加的，用来监听DOM节点变化的）

宏任务和微任务分别有各自的任务队列Event Queue，即宏任务队列和微任务队列。

Event Loop执行过程

了解到宏任务与微任务过后，我们来学习宏任务与微任务的执行顺序。

代码开始执行，创建一个全局调用栈，script作为宏任务执行

执行过程过同步任务立即执行，异步任务根据异步任务类型分别注册到微任务队列和宏任务队列

同步任务执行完毕，查看微任务队列

若存在微任务，将微任务队列全部执行(包括执行微任务过程中产生的新微任务)

若无微任务，查看宏任务队列，执行第一个宏任务，宏任务执行完毕，查看微任务队列，重复上述操作，直至宏任务队列为空

更新一下Event Loop的执行顺序图：

总结

在上面学习的基础上，重新分析当前案例：

setTimeout(() => {

  console.log(1);

}, 1000)

new Promise(function(resolve){

    console.log(2);

    for(var i = 0; i < 10000; i++){

        i == 99 && resolve();

    }

}).then(function(){

    console.log(3)

});

console.log(4)

分析过程见下图：

事件起因

今天，我需要上线一个非常小但是又非常重要的系统改动，即给核心接口的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 这个组件自己来玩一下好玩的动画效果哦！

与UIKIT交互

SwiftUI可以在苹果全平台上无缝兼容现有的UI框架。例如，可以在SwiftUI视图中嵌入UIKit视图或UIKit视图控制器，反过来在UIKit视图或UIKit视图控制器中也可以嵌入SwiftUI视图。

本篇教程展示如何把landmark应用的主页混合使用UIPageViewController和UIPageControl。使用UIPageViewController来展示由SwiftUI视图构成的轮播图，使用状态变量和绑定来操作用户界面数据的更新。

跟着教程一步步走，可以下载工程文件进行实践。

第一节 创建一个用来展示UIPageViewController的SwiftUI视图

为了在SwiftUI视图中展示UIKit视图和UIKit视图控制器，需要创建遵循UIViewRepresentable和UIViewControllerRepresentable协议的类型。创建的自定义视图类型，用来创建和配置所要展示的UIKit类型，SwiftUI框架来管理UIKIt类型的生命周期并在适当的时机更新它们。

步骤1 创建一个新的SwiftUI视图文件，命名为PageViewController.swift，并且声明PageViewController类型遵循UIViewControllerRepresentable。这个页面视图控制器存放一个UIViewController实例数组，数组中的每一个元素代表在地标滚动过程中的一页视图。

下一步添加UIViewControllerRepresentable协议的两个实现, 目前因为协议方法没有完成实现，会有报错提示。

步骤2 添加一个makeUIViewController(context:)方法，方法内部以指定的配置创建一个UIPageViewController。SwiftUI会在准备显示视图时调用一次makeUIViewController(context:)方法创建UIViewController实例，并管理它的生命周期。

由于还缺少一个协议方法没有实现，所以目前还是会报错。

步骤3 添加updateUIViewController(_:context:)方法，这个方法里调用setViewControllers(_:direction:animated:)方法展示数组中的第一个视图控制器

创建另一个SwiftUI视图展示遵循UIViewControllerRepresentable协议的视图

步骤4 创建一个名为PageView.swift的视图，声明一个PageViewController作为子视图。初始化时使用一个视图数组来初始化，并把每一个视图都嵌入在一个UIHostingController中。UIHostingController是一个UIViewController的子类，用来在UIKit环境中表示一个SwiftUI视图。

步骤5 更新预览视图，并传入视图数组，预览视图就会开始工作了

步骤6 在继续下面的步骤前，先把PageView的预览视图固定住，以避免在文件切换时不能实现预览到PageView的改变。

第二节 创建视图控制器的数据源

短短几个步骤就做了很多事，PageViewController使用UIPageViewController去展示来自SwiftUI内容。现在是时候添加挥动手势进行页面之间的翻动了。

一个展示UIKit视图控制器的SwiftUI视图可以定义一个Coordinator类型，这个Coordinator类型由SwitUI管理，用来作为视图展示的环境

步骤1 在PageViewControlelr中定义一个嵌套类型Coordiantor。SwiftUI管理UIViewController Representable类型的coordinator，并在调用方法时把它作为环境的一部分。

步骤2 在PageView Controller中添加另一个方法，创建coordinator。SwiftUI在调用makeUIViewController(context:)前会先调用makeCoordinator()方法，因此在配置视图控制器时是可以访问到coordiantor对象的。可以使用coordinator为实现通用的Cocoa模式,例如：代理模式、数据源以及目标-动作。

步骤3 让Coordinator类型添加UIPageViewControllerDataSource协议遵循，并且实现两个必要方法。这两个必要方法会建立起视图控制器之间的联系，因此可以实现页面之前的前后切换。

步骤4 把coordiantor作为UIPageViewController的数据源

步骤5 打开实时预览，并测试一下前后页面切换的功能是否正常

组合复杂用户界面

Landmarks应用的首页是一个纵向滚动的地标类别列表，每一个类别内部是一个横向滑动列表。随后将构建应用的页面导航，这个过程中可以学习到如果组合各种视图，并让它们适配不同的设备尺寸和设备方向。

第一节 添加一个首页视图

已经创建了所有在Landmarks应用中需要的视图，现在给应用创建一个首页视图，把之前创建的视图整合起来。首页不仅仅包含之前创建的视图，它还提供页面间导航的方式，同时也可以展示各种地标信息。

步骤1 创建一个名为CategoryHome.swift的自定义视图文件

步骤2 把应用的场景代理(scene delegate)的根视图从之前的地标列表视图更改为新创建的首页视图。现在应用启动后的每一个页面就是首页了，所以还需要添加从首页导航跳转到其它页面的方法。

步骤3 添加NavigationView，这个NavigationView将会容纳Landmarks应用中其它不同的视图。配合使用NavigationView、NavigationLink及相关的修改器，就可以构建出应用的页面间导航结构

步骤4 设置导航栏标题为Featured

第二节 创建地标类别列表

Landmarks应用为了便于用户浏览各种类别的地标，将地标按类别竖向排列形成列表视图，对于每一个类别内的具体地标，又把它们按照水平方向排列，形成横向列表。组合使用垂直栈(vertical statck)和水平栈(horizontal stack)并给列表添加滚动

步骤1 使用Dictionary结构体的初始化方法init(grouping:by:)，把地标数据的类别属性category传入作为分组依据，可以把地标数据按类别分组。工程文件中已经为每一个地标样本数据预定义了类别。

步骤2 使用List显示地标数据的类别。Landmark.Category是枚举类型，它的值标识列表中每一种类别，可以保证类别不会有重复定义

第三节 添加针对单个类别的地标行列表

Landmarks应用对每个类别下的地标采用横向滑动的行进行展示。添加一个新的视图类型用来表示这样一个地标行，然后使用这个新创建的行类型具体展示某一具体类型上的所有地标。

步骤1 定义一个新的视图类型，用来展示地标类别行的内容。新建行视图需要存放地标具体类别的展示数据

步骤2 更新CategoryHome.swift的代码，把地标类别信息传给新建的行视图类型

步骤3 在CategoryRow.swift中使用一个HStack展示类别下的地标内容

步骤4 为行内容指定一个高度，并把行内容嵌入到ScrollView中，以支持横向滑动。预览视图时，可以多增加几个地标数据，用来查看列表的滑动是否正常。

基础版本

所有情况下时间复杂度都为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;

            }

        }

    }

}