• Spring Boot 3.x swagger 迁移 SpringFox 到 SpringDoc

    背景

    有一个项目升级到 Spring Boot 3.0,同事踩坑填坑花了点时间。遇到最大的一个坑就是 swagger 了,我顺便记录一下。

    SpringFox

    可以去它的官网看,SpringFox 已经有两三年没有更新了,属于被遗忘的项目。我去年也遇到 SpringFox 的问题,当时我用 Spring Boot 2.6,已经出现了不兼容报错的情况,所以退回了 2.5。今年是 Spring Boot 3.0,SpringFox 直接就别用了。

    SpringDoc

    SpringDoc 可以自动化生成 API 文档,它支持:(注意,本文所指均是 SpringDoc v2 版本)

    • OpenAPI 3
    • Spring Boot v3 (Java 17 & Jakarta EE 9)
    • JSR-303, specifically for @NotNull, @Min, @Max, and @Size.
    • Swagger-ui
    • OAuth 2
    • GraalVM native images

    从 SpringFox 迁移

    引入依赖

    把原来的io.springfoxswagger 2相关的依赖都删除,然后添加 SpringDoc 的依赖:

    <dependency>
       <groupId>org.springdoc</groupId>
       <artifactId>springdoc-openapi-starter-webmvc-ui</artifactId>
       <version>2.1.0</version>
    </dependency>

    替换注解

    把原来 swagger 2 的注解替换成 swagger 3 的,springdoc-openapi-starter-webmvc-ui中已经包含了 swagger 3 的依赖。

    • @Api → @Tag
    • @ApiIgnore → @Parameter(hidden = true) 或 @Operation(hidden = true) 或 @Hidden
    • @ApiImplicitParam → @Parameter
    • @ApiImplicitParams → @Parameters
    • @ApiModel → @Schema
    • @ApiModelProperty(hidden = true) → @Schema(accessMode = READ_ONLY)
    • @ApiModelProperty → @Schema
    • @ApiOperation(value = "foo", notes = "bar") → @Operation(summary = "foo", description = "bar")
    • @ApiParam → @Parameter
    • @ApiResponse(code = 404, message = "foo") → @ApiResponse(responseCode = "404", description = "foo")

    之后 swagger 就可以在 http://server:port/context-path/swagger-ui.html 访问了。

    简单例子

    创建一个 controller:

    @RestController
    @RequestMapping("/test")
    public class TestController {
    
        @GetMapping("/greet")
        @CrossOrigin
        @Operation(summary = "say hello", description = "这里写描述")
        public String greet(@RequestParam(required = false) String name) {
            return "hello " + name;
        }
    }

    访问 swagger 大概是这样:

    具体的接口:

    结语

    上面只展示了最简单的使用,高级的用法和具体的配置在这里先不展开,需要时自己看官网文档。

    参考链接

  • Spring Boot 动态修改日志级别

    背景

    服务在生产环境跑,出了点问题,需要 debug 级别的日志;但是平时生产环境谁用 debug,都是用 info 级别。

    按一般的流程,改日志级别需要修改文件、重新打包发版,重启是免不了了,但重启可能导致问题不能复现。

    现在才知道,日志级别是可以在运行过程中动态修改的。记录下来。

    依赖

    这个功能有赖于 Spring Boot Actuator。诶,又是你,之前项目中已经有引入的,用来做服务的监控。

    如果没有引入,需要在pom.xml中添加

    <dependency>
    	<groupId>org.springframework.boot</groupId>
    	<artifactId>spring-boot-starter-actuator</artifactId>
    </dependency>

    配置

    然后找一下配置项management.endpoints.web.exposure.include是否存在,如果没有就添加

    management.endpoints.web.exposure.include=info,health,loggers

    如果有的话,就在原有值里加上loggers即可。

    接口

    开启了 loggers endpoint,应用启动后就可以访问以下3个接口:

    • GET /actuator/loggers 返回当前应用全部的日志级别信息
    • GET /actuator/loggers/{name} 查看{name}的日志级别
    • POST /actuator/loggers/{name} 修改{name}的日志级别

    首先访问第一个接口(http://localhost:8080/actuator/loggers)看一看:

    找到loggers部分,我这里返回的是

    "loggers": {
        "ROOT": {
            "configuredLevel": "INFO",
            "effectiveLevel": "INFO"
        }
    }

    表示根节点的日志级别是INFO。(访问http://localhost:8080/actuator/loggers/ROOT也可以看到)

    那么要怎么修改呢,调用对应的POST接口即可:

    curl -X POST http://localhost:8080/actuator/loggers/ROOT  -H "Content-Type: application/json"  -d "{\"configuredLevel\":\"DEBUG\",\"effectiveLevel\":\"DEBUG\"}"

    再次查看GET接口,可以看到已经变为DEBUG级别。

    有关原理和其他细节,可以查看以下的参考。

    相关参考

    1. Spring Boot 系列(4):日志动态配置详解 – 掘金 (juejin.cn)
  • Kotlin 使用 protobuf 的正确方法(Maven)

    背景

    有一个后端的 Java/Kotlin 项目需要与同事的模块通信,协议是 protobuf。

    这块我想用 Kotlin 来写,当然 Java 也不是不行。没想到踩了些坑,故以本文作记录。

    文档

    protobuf 官方是有 Kotlin 的教程的,但是并不全面,这是出现各种坑的根源。

    另外,我原以为 protobuf 对 Kotlin 的专门支持是多年前就有的(指的是支持 Kotlin 的各种方便写法),然而我后来才发现是2021年才有,见 Announcing Kotlin support for protocol buffers

    方法

    1. 从 .proto 生成 .java .kt

    首先找同事得到 .proto 文件,然后下载 protoc,解压后得到一个可执行文件。

    然后按照官方教程,在命令行中执行

    protoc --java_out=$DST_DIR --kotlin_out=$DST_DIR xxxxxx.proto

    注意--java_out--kotlin_out都是需要的,当前版本的 protoc 对 Kotlin 的支持是在原来 Java 生成的基础上多了 Kotlin 的增强。

    然后就得到了一些 .java .kt 文件。

    2. Maven

    把生成的文件放进项目中,可以发现编译是不能通过的,因为缺少 protobuf 相关库。我的项目是 Maven 的,所以在 pom.xml 中加上

    <!-- https://mvnrepository.com/artifact/com.google.protobuf/protobuf-kotlin -->
    <dependency>
        <groupId>com.google.protobuf</groupId>
        <artifactId>protobuf-kotlin</artifactId>
        <version>3.19.4</version>  <!-- version 要与之前 protoc 的版本对应 -->
    </dependency>
    

    这个 pom 的 artifactId (protobuf-kotlin) 是关键!!我看到的文档写的都是protobuf-java,就会导致生成的 .kt 里面的

    @kotlin.OptIn(com.google.protobuf.kotlin.OnlyForUseByGeneratedProtoCode::class)

    报找不到的错误,必须使用protobuf-kotlin

    3. 使用

    这里参照 Announcing Kotlin support for protocol buffers 举的例子,用了 Kotlin 之后,写法更简洁了。假设原来 Java 的是这样写:

    DiceSeries series = DiceSeries.newBuilder()
        .addRoll(DiceRoll.newBuilder()
            .setValue(5))
        .addRoll(DiceRoll.newBuilder()
            .setValue(20)
            .setNickname("critical hit"))
        .build()

    而 Kotlin 可以改成:

    val series = diceSeries {
      rolls = listOf(
        diceRoll { value = 5 },
        diceRoll {
          value = 20
          nickname = "critical hit"
        }
      )
    }

    至于如何序列化和反序列化,继续用刚才的例子,序列化是这样的:

    series.toByteArray()

    反序列化:

    DiceSeries.parseFrom(message)
  • CTP Java API Linux/Windows x64 编译(SWIG 封装 C++ 动态库),并解决中文乱码问题

    前言

    网上有不少教程讲到 CTP API 的编译,但是我按照多数教程照着做都不太成功,只有一份是成功了。在此把过程记录下来,希望可以帮到更多的人。

    (2022年4月更新:补充 Windows 下的支持,写在文末)

    Linux

    1. 下载 CTP API

    在上期的官网下载,然后解压到某一个工作目录。我们只需要 Linux x64 的,工作目录的文件如下:

    error.dtd
    error.xml
    ThostFtdcMdApi.h
    ThostFtdcTraderApi.h
    ThostFtdcUserApiDataType.h
    ThostFtdcUserApiStruct.h
    thostmduserapi_se.so
    thosttraderapi_se.so
    阅读更多…
  • 禁用 Hibernate 的代理(proxy),获取其真实对象 / Disable Hibernate Proxy and Retrieve Real Entity Object

    Java 的各种框架还是很复杂的,不看文档或者不踩坑,都不知道原来框架还“偷偷地”做了一些别的事情——可能这就是一部分面试题的出处吧😂

    踩坑

    假设有一个 Model 叫做 Person,存到数据库里,框架用的是 Hibernate。代码中用 personDao.findById() 来从数据库中获取一个 Person 实例。项目中大概就是这么写的。

    问题来了:要把这个 Person 实例序列化,之后再反序列化。序列化的时候没发现什么问题,反序列化的时候报错了,告诉我这不是一个 Person,而是一个 Person$HibernateProxy$9cjcxRNr

    啥情况,代码明明写的是 Person person = personDao.findById(123); 怎么出来的不是 Person 而是 Person 后面加了一长串东西?

    解惑

    经过搜索,得知 Hibernate 使用 Proxy 实现延迟加载(Lazy Loading)功能。延迟加载,这个我懂,真正用到时才去查询。

    找到的资料还告诉我,被偷偷换成了 proxy 之后,还可能有别的坑:直接访问成员变量可能访问不到、用 IDE 断点调试时的行为和实际运行的行为不一致、instanceOf 的行为可能与预期不一致等。

    解决

    第一个办法,若不确定它是不是 proxy,可以强行让 Hibernate 给我们转回真正的实例,是就转,不是就原样返回:

    Object unproxiedEntity = Hibernate.unproxy(proxy); // 自己再做强制类型转换

    第二个办法,通过注解,不让 Hibernate 给这个 Model / Entity Class 做延迟加载:

    @Proxy(lazy = false)

    相关参考

  • FIX 协议开发(3):QuickFIX/J 实战经验小结

    本系列导航

    FIX 协议开发(1):协议介绍及开发方案
    FIX 协议开发(2):QuickFIX/J 入门
    FIX 协议开发(3):QuickFIX/J 实战经验小结(本文)

    代码结构

    这里主要讲一下我们的思路,具体的代码不方便贴上来。

    首先需要实现 Application,主要是其中的 fromApp() 需要 crack 不同类型的 Message。但是,不把具体业务逻辑写在 crack() 方法里,crack() 主要就是把 message 通过一个或多个队列传到外部。

    收发信息的部分,从上一节可以看到,具体代码还是挺零碎的,所以做一层抽象会方便一点。
    另一个重点是注意同步/异步:有些方法做成同步会方便一点,例如查询持仓/资金,又例如撤单【同步/异步都可以】;而下单则应做成异步。

    Fix Session 持久化

    程序启动时,会自动读入之前保存的状态。FIX 协议对序列号的要求严格,如果收到的序列号偏大或偏小,会导致需要额外的处理甚至 session 被断掉。因此,持久化非常重要,尤其是维护收发序列号。

    以我方下一次发送的序列号 NextSenderMsgSeqNum 为例。Session.javasendRaw()方法调用了persist()方法,该方法中 MessageStore 实例把即将发送的消息持久化;该步骤完成后,MessageStore 实例接着执行incrNextSenderMsgSeqNum(),把序列号保存下来。在persist()完成之后,才真正把数据发送出去。

    MessageStore 自带了几种实现,例如基于文件的FileStore,放在内存里的MemoryStore,我们参考MemoryStore稍作修改,做了一个RedisStore,感觉会灵活一点。

    关于 session 的另一个话题是,如何手动控制一个 session,例如使 session logout、reset 等。

    可以使用静态函数Session.lookupSession(sessionID)来从 ID 获取对应的 session,接下来就可以调用 session.logon()、logout()、reset() 方法。后两个的区别,logout 是发送 FIX 的 logout 信号,然后断开连接,不影响序列号等内部状态,之后调用 logon() 即可回到正常使用的模式。reset() 会清除序列号等内部状态及其持久化,下次收发包会都从 1 开始。盘中就别用这个了。

    如果不需要手动控制 session,而是每天自动从几点连到几点,那么只需要在参数中配置StartTimeEndTime即可。

    异常处理

    进行 QFJ 开发时,特别需要注意的是,如何捕捉“异常”。不像 API 调用,时刻都有 error code 字段。对方返回的消息中如有错误信息或特殊情况时,是需要针对性处理的。

    例如查询持仓是空仓,服务器不可能什么都不返回,而会返回一个特殊的空仓标记。又例如各种字段填写不合法,报错信息很可能藏在可选的 Text 字段中。

    接收业务信息后报错

    主要有两个原因:

    • 一是不符合 xml 的定义,在底层就会自动给对方发送拒绝消息“MsgType (35): 3 (REJECT)”,不会传到 Application 的应用层;
    • 二是在应用层的 fromApp() 内 crack 信息时没有找到对应 crack 的方法,会发送“BusinessRejectReason (380): 3 (UNSUPPORTED MESSAGE TYPE)”给服务器。

    解决的要点都在于我方的字典没有适配对方的字典(对方故意发错误的数据包除外)。参考上一篇的“自定义字段”一节,根据实际情况修改 xml,自行打造合适的 Message 库才是王道。

    消息自动按类型分类、处理流程

    对比自己构造数据包、自己解析收到的数据全 DIY 的实现方式, QFJ 框架已经为我们做了很多。如果好奇的话,数据包是如何解析,最终传给我们的 fromApp() 方法?先从源头,即 MINA 框架接收到数据包说起。

    对方发来的数据包,首先经过 quickfix.mina.message.FIXMessageDecoder 解码,进行基础的校验,例如检测 FIX 协议头、获取消息体的长度、校验 checksum 等。

    如果校验正常,InitiatorIoHandler/AcceptorIoHandler 调用其父类 Quickfix.mina.AbstractIoHandler 继续处理消息,包括但不限于:从 session 获取字典、解析 FIX 数据【通过调用quickfix.MessageUtils的函数】等。解析时,先提取 msgType,调用 session 对应的 messageFactory 创建 msgType 类型的 message 实例,接下来根据字典解析数据内容。

    解析 message 完成后,InitiatorIoHandler/AcceptorIoHandler 把 message 传给 processMessage() 方法;执行 eventHandlingStrategy.onMessage(),该方法内把 message 塞到队列 queueTracker 中。

    最后,队列的元素会被“QFJ Message Processor”线程取出,给到 quickfix.Session 的 next(Message) 方法。这个 next() 方法,里面还有对字段的校验,里面的 verify(message) 再进而校验登录状态、时间、seq num 等,最终调用我们写的 fromApp() 方法。

    可见,从接收到数据,到我们实现的 Application,经历了很多很多层的调用。😅

    这个流程还没有结束。

    我们让自己的 Application 继承 quickfix.MessageCracker,从而拥有了 crack(),crack 是怎样根据不同实际类型的 message 调用对应的 onMessage() 的呢?

    MessageCracker 在初始化时,执行 initialize() ,通过反射,找到所有 handler【也就是各种自己写的 onMessage()】,并存到一个 mapping。之后 fromApp() 调用 crack() 时,就通过传入的 message 提取其类型以及 mapping 找到对应的 handler,调用对应的 onMessage()。

    如果觉得这个 crack 过程有点太“黑科技”,我们可以不用它,不继承 quickfix.MessageCracker,转而继承 quickfix.fix42.MessageCracker【按实际对应的版本】。点进去可以看到,全是各种 onMessage,这样就不涉及反射,都是 override 了。我喜欢 explicit 的方法。

    性能

    目前业务是用来接入券商。还没做过大规模的测试,但按当前测试数据估计每秒可发单 100 个以上,性能满足当前业务需求。

    相关参考

    1. https://www.quickfixj.org/usermanual/2.1.0/
    2. https://blog.csdn.net/u011279740/category_1517545.html
  • FIX 协议开发(2):QuickFIX/J 入门

    本系列导航

    FIX 协议开发(1):协议介绍及开发方案
    FIX 协议开发(2):QuickFIX/J 入门 (本文)
    FIX 协议开发(3):QuickFIX/J 实战经验小结

    安装

    QuickFIX/J 的官网是 https://www.quickfixj.org,其 GitHub 是 https://github.com/quickfix-j/quickfixj。撰写本文时,GitHub 上的版本是 2.2,官网上的文档给到了 2.1 的版本。所以这里选择安装 2.1,避免与文档不匹配。

    我们通过 Maven 来引入 quickfixj 库,见此页的“Maven Integration”部分,在 pom.xml 中添加对应 xml 片段(该网页中的xml引入的是2.0.0版本的库,或许是笔误,我将其改为2.1.0)即可:

    <!-- QuickFIX/J dependencies -->
    <dependency>
        <groupId>org.quickfixj</groupId>
        <artifactId>quickfixj-core</artifactId>
        <version>2.1.0</version>
    </dependency>
    <!-- 选择所需版本的messages -->
    <dependency>
        <groupId>org.quickfixj</groupId>
        <artifactId>quickfixj-messages-fix42</artifactId>
        <version>2.1.0</version>
    </dependency>
    <dependency>
        <groupId>org.slf4j</groupId>
        <artifactId>slf4j-log4j12</artifactId>
        <version>1.7.22</version>
    </dependency>
    <dependency>
        <groupId>org.slf4j</groupId>
        <artifactId>slf4j-api</artifactId>
        <version>1.7.22</version>
    </dependency>
    阅读更多…
  • FIX 协议开发(1):协议介绍及开发方案

    本系列导航

    FIX 协议开发(1):协议介绍及开发方案(本文)
    FIX 协议开发(2):QuickFIX/J 入门
    FIX 协议开发(3):QuickFIX/J 实战经验小结

    本文背景

    公司因业务需要,准备接入 FIX 协议。在调研过程中,我发现中文的 FIX 协议相关资料不太多,准备边学边记录,预计会写 3 篇左右。

    FIX 协议简介

    FIX(Financial Information eXchange Protocol,金融信息交换协议)是由国际FIX协会组织提供的一个开放式协议,目的是推动国际贸易电子化进程,在各类参与者之间,包括投资经理、经纪人、买方、卖方建立起实时的电子化通讯协议。

    FIX协议的目标是把各类证券金融业务需求流程格式化,成为一个可用计算机语言描述的功能流程,并在每个业务功能接口上统一交换格式,方便各个功能模块的连接。

    消息格式

    FIX 协议消息均由多个 “key=value” 组成。其中 key 可以是协议规定的字段,或自定义字段。协议规定的key可查询 FIX 协议字典,【不同版本的 FIX 协议均有其字典,用于开发的库一般也有自带;也可参考第三方,如 wireshark】例如 8 代表 begin string,34 代表消息的序列号,52 代表时间戳等。自定义字段不与规定的 key 重复,供金融机构定制,开发时需要向对应金融机构获取其专有字段的字典。只要有了对应的字典,就可以读懂 FIX 数据包的内容。

    一般来说,一个 消息由“头部 + 消息体 + 尾部”构成。头部包含一些必要的字段,例如 BeginString (8)、BodyLength (9)、MsgType (35)、MsgSeqNum (34)、SenderCompID (49) 等,尾部包含的必要字段是 CheckSum (10)。

    FIX 登陆消息示例(假设”^”是分隔符):

    8=FIX.4.3^9=65^35=A^34=1^49=TESTACC^52=20130703-15:55:08.609^56=EXEC^98=0^108=30^10=225^

    对照字典可知,BeginString (8) 是 FIX.4.3;BodyLength (9) 是 65 字节;MsgType (35) 是 A,A 对应 logon 操作;MsgSeqNum (34) 是 1,即这是我方发送的第 1 个消息。

    有关更详细的协议介绍,可参考 https://blog.51cto.com/9291927/2536105

    开发方案

    不使用库

    由上面的示例可以发现,FIX 协议十分简单。可以不需要依赖第三方库,手动查字典构造消息
    8=FIX.4.3^9=65^35=A^34=1<省略>
    再通过标准的 socket 通信,即可完成交互。

    这个方案自由度最高,不依赖底层开发语言,但开发流程与查字典较为繁琐,后续维护也不太方便。

    Python 库 simplefix

    simplefix 是一个 FIX 协议的简易实现。它使用户可以方便地任意构造 FIX 消息,非常适合学习、测试协议。但这个库不包含任何网络收发、FIX 异常处理等功能模块。因此,开发 FIX 客户端时,我使用该库构造数据包,然后通过标准 socket 发送,再分析其网络底层交互。

    示例:发送 logon 消息的代码

    import socket
    import time
    
    import simplefix
    from simplefix.constants import (ENCRYPTMETHOD_NONE, MSGTYPE_LOGON,
                                     TAG_BEGINSTRING, TAG_CLIENTID,
                                     TAG_ENCRYPTMETHOD, TAG_HEARTBTINT,
                                     TAG_MSGSEQNUM, TAG_MSGTYPE, TAG_SENDER_COMPID,
                                     TAG_SENDING_TIME, TAG_TARGET_COMPID)
    
    HOST = '1.2.3.45'
    PORT = 9000
    CLIENT_ID = 12345678
    PASSWORD = 'mypassword'
    
    seq_num = 1  # 需维护msg sequence number,每次发送后加1
    
    
    if __name__ == "__main__":
        sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        sock.setsockopt(socket.SOL_SOCKET, socket.SO_KEEPALIVE, 1)  # 长连接
        sock.connect((HOST, PORT))
    
        # logon
        msg_logon = simplefix.FixMessage()
        msg_logon.append_pair(TAG_BEGINSTRING, 'FIX.4.2')
        msg_logon.append_pair(TAG_MSGSEQNUM, seq_num)  # 需维护msg sequence number,每次发送后加1
        msg_logon.append_pair(TAG_SENDER_COMPID, 'FIXTEST001')
        msg_logon.append_utc_timestamp(TAG_SENDING_TIME)
        msg_logon.append_pair(TAG_TARGET_COMPID, 'TESTENV')
    
        msg_logon.append_pair(TAG_MSGTYPE, MSGTYPE_LOGON)  # 类型
    
        msg_logon.append_pair(TAG_ENCRYPTMETHOD, ENCRYPTMETHOD_NONE)
        msg_logon.append_pair(TAG_HEARTBTINT, 30)
        msg_logon_buffer = msg_logon.encode()
    
        sock.send(msg_logon_buffer)
        print('seq', seq_num, 'sent')
        seq_num += 1
    
    
        time.sleep(1)
        sock.close()

    多平台 QuickFix 引擎

    QuickFix 是全功能的 FIX 开源引擎,目前很多 Fix 解决方案都是根据或参考 QuickFix 实现的。目前(2020年10月)它有 C++、Python、Java、.NET、Go 和 Ruby 共 6 种语言的实现/接口。

    根据我司的情况,选择其中的 Java 实现 QuickFIX/J 进行下一步开发。其使用方法,将在下一篇文章继续。

  • 一图流领悟跳跃列表(Skip List),附 Python/Java/Kotlin 实现

    跳跃列表是一种随机数据结构。它使得包含 n 个元素的有序序列的查找、插入、删除操作的平均时间复杂度都是 O(log n)。(注意关键词有序,如果不需要有序,也不需要用到跳跃列表;数据量大时,时间复杂度退化到较慢的概率微乎其微)

    平均最差
    搜索O(log n)O(n)
    插入O(log n)O(n)
    删除O(log n)O(n)
    空间O(n)O(n log n)

    跳跃列表是通过维护一个多层链表实现的。每一层链表中的元素的数量,在统计上来说都比下面一层链表元素的数量更少。也就是说,上层疏,下层密,底层数据是完整的,上面的稀疏层作为索引——这就是链表的“二分查找”啊。

    一开始时,算法在最稀疏的层次进行搜索,直至需要查找的元素在该层两个相邻的元素中间。这时,算法将跳转到下一个层次,重复刚才的搜索,直到找到需要查找的元素为止。

    Wikipedia 的道理就讲到这里,我不希望把本文写得难懂。说好的一图流就能领悟呢?其实我有点标题党,本文不止一幅图,但是核心的图只有一幅,上图(来自 Wikipedia):

    请多次认真观看插入节点的全过程 gif。我看完之后,就觉得自己可以实现出来了(虽然后来实际开发调试了很多次)。

    例如想在上图中所示的跳跃列表中插入 80,首先要找到应该插入的位置。

    首先从最稀疏的层的 30 开始,把当前位置设置为顶层的 30。
    80 比当前位置右边的 NIL 小,所以把当前位置移到下一层的 30;
    80 比当前位置右边的 50 大,所以把当前位置右移到 50;
    80 比当前位置右边的 NIL 小,所以把当前位置移到下一层的 50;
    80 比当前位置右边的 70 大,所以把当前位置右移到 70;
    80 比当前位置右边的 NIL 小,所以把当前位置移到下一层的 70;(当前位置已到达底层)
    之后用 80 不断与右边的节点比较大小,右移至合适的位置插入 80 节点。(底层插入完毕)
    接下来用随机决定是否把这个 80 提升到上面的层中,例如图中的提升概率是 50%(抛硬币),不断提升至硬币为反面为止。

    上面一段描述了 gif 中插入 80 的搜索和插入过程。那么,代码如何实现?右移和下移的逻辑很浅显,那么重点就在如何提升节点到上层的逻辑。

    阅读更多…