• 第01篇_编程通识

    第01章_计算机基础

    第一节 操作系统

    1. 操作系统概述

    什么是操作系统?

    操作系统是计算机的核心软件,是底层硬件其他软件之间的桥梁,为用户提供一个高效、方便、安全的操作环境。

    它的组成如下:

     

    什么是用户态和内核态?

    用户态和内核态是操作系统中定义的两种运行级别

    用于区分程序运行时的权限和对系统资源的访问能力,是现代操作系统实现安全性和稳定性的关键机制之一。

     

    用户态切换到内核态的 3 种方式?

     

     

    2. 进程和线程

    进程 vs 线程?

     

    进程的5种状态

    进程状态图转换图

     

    进程的调度算法有哪些?

     

    进程间的通信方式有哪些?

     

    PCB 是什么?包含哪些信息?

    PCB(Process Control Block)进程控制块,是操作系统中用来管理和跟踪进程的数据结构,主要包含内容如下:

     

    什么是僵尸进程和孤儿进程?

     

    进程死锁?如何检测?

    死锁指多个进程/线程之间循环等待互斥资源的现象,检测方式如下:

    image-20250407225450912

     

     

    3. 内存管理

    内存管理包括哪些内容?

     

    什么是内存碎片?

    内存碎片主要分为两种类型:

    image-20250407231439977

     

    什么是虚拟内存?有什么用?

    虚拟内存(Virtual Memory)是一种内存管理技术,它通过内存管理单元(MMU)物理内存(RAM)进行映射,使每个进程都有一份自己的虚拟地址空间。

    主要作用如下:

    地址翻译过程

     

    虚拟地址与物理内存地址是如何映射的?

    现代操作系统广泛采用分页机制将虚拟地址翻译为物理地址:

    image-20250408205317516

     

     

    4. 文件系统

    文件系统的主要功能?

    文件系统主要负责管理和组织计算机存储设备上的文件和目录,其功能包括以下几个方面:

     

     

    Linux的文件系统

    Linux 使用一种称为目录树的层次结构来组织文件和目录。目录树由根目录(/)作为起始点,向下延伸,形成一系列的目录和子目录。

    image-20250427204402176

    /bin: 存放二进制可执行文件(ls、cat、mkdir 等),常用命令一般都在这里;

    /etc: 存放系统管理和配置文件;

    /home: 存放所有用户文件的根目录,是用户主目录的基点,比如用户 user 的主目录就是/home/user,可以用~user表示;

    /usr: 用于存放系统应用程序;

    /opt: 额外安装的可选应用程序包所放置的位置。一般情况下,我们可以把 tomcat 等都安装到这里;

    /proc: 虚拟文件系统目录,是系统内存的映射。可直接访问这个目录来获取系统信息;

    /root: 超级用户(系统管理员)的主目录;

    /sbin: 存放二进制可执行文件,一般 root 才能访问。这里存放的是系统管理员使用的系统级别的管理命令和程序,如 ifconfig 等;

    /dev: 用于存放设备文件;

    /mnt: 系统管理员安装临时文件系统的安装点,系统提供这个目录是让用户临时挂载其他的文件系统;

    /boot: 存放用于系统引导时使用的各种文件;

    /lib 和/lib64: 存放着和系统运行相关的库文件 ;

    /tmp: 用于存放各种临时文件,是公用的临时文件存储点;

    /var: 用于存放运行时需要改变数据的文件,也是某些大文件的溢出区,比方说各种服务的日志文件等;

    /lost+found: 这个目录平时是空的,系统非正常关机而留下“无家可归”的文件(windows 下叫什么.chk)就在这里。

     

    Linux的文件类型

    在Linux系统中,文件类型主要分为以下几种:

     

    硬链接和软链接有什么区别?

    在 Linux/类 Unix 系统上,文件链接(File Link)是一种特殊的文件类型,可以在文件系统中指向另一个文件。

     

     

    5. I/O模型

    什么是I/O?常见I/O模型有哪些?

    根据冯.诺依曼结构,计算机分为 5 大部分:运算器控制器存储器输入设备输出设备,I/O 即输入/输出

    冯诺依曼体系结构

    在 UNIX 系统下, I/O 模型一共有 5 种:同步阻塞 I/O同步非阻塞 I/OI/O 多路复用、信号驱动 I/O 和异步 I/O

     

    BIO (Blocking I/O)

    BIO 属于同步阻塞 I/O 模型,应用程序发起系统调用 read() 后,会一直阻塞等待,直到内核把数据拷贝到用户空间。

    图源:《深入拆解Tomcat & Jetty》

    在客户端连接数量不高的情况下,是没问题的,如果并发量较高,则不推荐。

     

    NIO (Non-blocking/New I/O)

    NIO 既可以通过同步非阻塞 I/O模型实现,也可以通过I/O 多路复用模型实现,也可两者结合使用。

    image-20250408214854117

     

    AIO (Asynchronous I/O)

    AIO 是基于事件和回调机制实现的异步 IO 模型,应用操作之后会直接返回,不会堵塞在那里,当后台处理完成,操作系统会通知相应的线程进行后续的操作。

    img

     

    NIO的核心组件有哪些?

    Java NIO(New Input/Output)的核心组件主要包括以下三个部分:

    Buffer、Channel和Selector三者之间的关系

     

    关于零拷贝技术

    传统的文件传输,一般使用 read + write 方式实现,需要进行 2 次 CPU 拷贝4 次运行级别切换

    image-20250409221241111

    零拷贝0次CPU拷贝,是提升 I/O 操作性能的一个常用技术手段,最基础的方式通过mmap+write实现。首先使用 mmap 对磁盘文件进行映射,然后在write 时就可以直接从内核缓冲区拷贝到 Socket 缓冲区了,节省了1次CPU拷贝消耗,但仍有4次运行级别切换。

    image-20250409221550336

    在 Linux 2.1 后,引入了sendfile方式支持零拷贝,直接在内核进行拷贝操作,又节省了2次运行级别切换。

    image-20250409222007135

    在 Linux2.4 后,如果网卡支持SG-DMA技术,还可以直接从内核缓冲区发送到网卡,真正实现0拷贝

    image-20250409222412018

    在 Java 中, MappedByteBufferFileChannel.transferTo()/transferFrom()分别用于支持上述两种方式。

     

     

     

    第二节 网络通信

    1. 网络通信概述

    OSI七层模型

    OSI 七层模型是由国际标准化组织(ISO)提出的一个用于计算机或网络系统互联的参考模型,它将网络通信的工作分为7个层次

    注意:

    1. OSI 的七层体系结构概念清楚,理论也很完整,但是它比较复杂而且不实用,而且有些功能在多个层中重复出现。

     

    TCP/IP四层模型

    TCP/IP 四层模型 是目前被广泛采用的一种模型,可以看作是 OSI 七层模型的精简版本,由以下 4 层组成:

     

    常见的网络协议

    应用层常见的网络协议有:

    传输层常见的网络协议有:

    网络层常见的网络协议有:

    链路层常见的网络协议有:

    TCP/IP 各层协议概览

     

    网页浏览数据流程

    img

     

    URL 的组成结构

    *URL(Uniform Resource Locator):是统一资源定位符,是可以提供该资源的路径,就像人的联系住址。

    URL的组成结构

    注意:

    1. URI(Uniform Resource Identifier): 是 统一资源标识符,可以唯一标识一个资源,就像人的身份证号。

     

    常见协议的默认端口
    协议名称默认端口协议类型功能描述
    HTTP80TCP超文本传输协议,用于Web浏览
    HTTPS443TCP安全超文本传输协议,加密的Web通信
    FTP21TCP文件传输协议,用于文件传输
    SMTP25/465/587TCP简单邮件传输协议,用于发送邮件
    POP3110/995TCP邮局协议版本3,用于接收邮件
    IMAP143/993TCP互联网消息访问协议,用于管理邮件
    DNS53TCP/UDP域名系统,用于域名解析
    Telnet23TCP远程登录协议
    SSH22TCP安全外壳协议,用于安全远程登录
    SNMP161/162UDP简单网络管理协议,用于网络设备管理
    NTP123UDP网络时间协议,用于时间同步
    TFTP69UDP简单文件传输协议
    DHCP67/68UDP动态主机配置协议,自动分配IP地址
    SIP5060TCP/UDP会话初始化协议,用于VoIP
    RDP3389TCP远程桌面协议,用于远程桌面访问

     

    常见应用的默认端口
    协议名称默认端口协议类型功能描述
    MySQL3306TCP数据库管理系统
    PostgreSQL5432TCP数据库管理系统
    Redis6379TCP内存数据库
    MongoDB27017TCPNoSQL数据库
    RabbitMQ5672TCP消息队列
    Memcached11211TCP/UDP分布式缓存系统
    Docker2375/2376TCP容器化平台
    Kafka9092TCP分布式消息系统
    Elasticsearch9200TCP搜索引擎
    Consul8500TCP服务发现和配置工具
    Prometheus9090TCP监控系统
    Grafana3000TCP可视化工具
    Jenkins8080TCP持续集成工具
    Tomcat8080TCPJava应用服务器
    Nginx80/443TCP/UDPWeb服务器
    Zookeeper2181TCP分布式协调服务

     

     

    2. DNS协议

    什么是DNS 协议?

    DNS(Domain Name System)域名管理系统,是用户浏览网页时用到的第一个重要协议,主要用于解决域名和 IP 地址的映射问题

    DNS:域名系统

    注意:

    1. DNS 是应用层协议,它可以在 UDP 或 TCP 协议之上运行,默认端口为 53

     

    DNS 解析路径

    本地缓存 -> 本地hosts文件 -> 本地DNS服务器 -> 根域名服务器(13组) -> 顶级域名服务器 -> 权威DNS服务器。

     

    常见DNS记录类型?
    记录类型用途示例
    A将域名映射到IPv4地址example.com. IN A 192.0.2.1
    AAAA将域名映射到IPv6地址example.com. IN AAAA 2001:db8::1
    CNAME将一个域名(别名)指向另一个域名(规范名)www.example.com. IN CNAME example.com.
    MX指定域名的邮件服务器example.com. IN MX 10 mail.example.com.
    NS指定域名的权威DNS服务器example.com. IN NS ns1.example.com.
    TXT存储任意文本信息,常用于SPF、DKIM和DMARC等example.com. IN TXT "test"

     

    DNS 劫持了解吗?如何应对?

    DNS 劫持是一种网络攻击,它通过修改 DNS 服务器的解析结果,使用户访问的域名指向错误的 IP 地址,从而导致用户无法访问正常的网站,或者被引导到恶意的网站。

    提示:

    1. DNS 劫持有时也被称为 DNS 重定向、DNS 欺骗或 DNS 污染。

     

     

    3. HTTP协议

    HTTP 协议通信过程

    HTTP 是应用层协议,它以 TCP 作为传输层协议,默认端口为 80,通信过程主要如下:

     

    HTTP请求方式有哪些?

    注意:

    1. GET 请求的响应结果可能会被浏览器或其它中间件(如代理、网关)缓存起来,而POST请求一般不会。

     

    HTTP请求头中常见的字段有哪些?

    HTTP 头部用于在客户端和服务器之间传递额外的信息,下面是请求头中常见的字段:

     

    HTTP响应头中常见的字段有哪些?

    下面是响应头中常见的字段:

     

    HTTP 状态码有哪些?

    HTTP 状态码用于描述 HTTP 请求的结果,分类如下:

    常见 HTTP 状态码

    最常见的几种状态码和含义如下:

    状态码英文简称中文解释
    200OK请求成功
    301/302Moved Permanently/Found重定向错误。资源已被永久/临时重定向。
    400Bad Request错误的请求。发送的 HTTP 请求存在问题,比如请求参数不合法、请求方法错误等。
    401Unauthorized未授权。在未认证时,请求需要认证之后才能访问的资源。
    403Forbidden被禁止。直接拒绝 HTTP 请求,不处理,一般用来针对非法请求。
    404Not Found不存在。请求的资源在服务器不存在。
    500Internal Server Error服务器内部错误。服务器遇到无法处理的异常。
    502Bad Gateway网关错误。网关收到无效或无法理解的服务器响应。

     

    HTTP 不同版本之间有什么区别?

     

    关于HTTP 队头阻塞?

    HTTP队头阻塞指前面的请求/响应延迟,导致后续请求/响应也延迟的现象,这是由于请求/响应的顺序处理机制造成的。

     

    HTTP 请求如何保存用户状态?

    HTTP 是一种无状态(stateless)协议,需要通过 Session 机制在服务端标识并跟踪用户。

     

    HTTP 和 HTTPS 有什么区别?

    HTTPS 协议(Hyper Text Transfer Protocol Secure)是 HTTP 的加强安全版本,是运行在 SSL/TLS 之上的 HTTP 协议,其传输内容采用了对称加密,对称加密的密钥用服务器方的证书进行了非对称加密

    此外,公钥可能被拦截伪造,在向服务器发送 HTTPS 请求时,一定要先获取目标服务器的证书,并根据证书上的信息(证书颁发机构(CA,Certificate Authority)的电子签名等),检验证书的合法性。

    注意:

    1. HTTP 采用http://前缀和 80 端口,HTTPS 采用https://前缀和 443 端口。

     

     

    4. WebSocket协议

    什么是WebSocket协议?

    WebSocket 是一种基于 TCP 连接全双工通信协议,即客户端和服务器可以同时发送接收数据,前缀为:ws://wss://,用于弥补 HTTP 协议在持久通信能力上的不足,常用场景如:即时通讯、视频弹幕、游戏对战、协同编辑等等。

     

    WebSocket 和 HTTP 有什么区别?

    两者都是基于 TCP 的应用层协议,都可以在网络中传输数据,主要区别如下:

    扩展:

    1. 在HTTP协议下,可通过服务器发送事件(Server-Sent Events,SSE) 实现服务端向客户端发送文本数据。

     

    WebSocket 的工作过程是什么样的?

    WebSocket 的工作过程可以分为以下几个步骤:

    1. 客户端向服务器发送一个 HTTP 请求,请求头中包含 Upgrade: websocketSec-WebSocket-Key 等字段,表示要求升级协议为 WebSocket;

    2. 服务器收到这个请求后,会进行升级协议的操作,如果支持 WebSocket,它将回复一个 HTTP 101 状态码,响应头中包含 ,Connection: UpgradeSec-WebSocket-Accept: xxx 等字段,表示成功升级到 WebSocket 协议。

    3. 客户端和服务器之间建立了一个 WebSocket 连接,可以进行双向的数据传输。

    4. 数据以帧(frames)的形式进行传送,WebSocket 的每条消息可能会被切分成多个数据帧(最小单位)。发送端会将消息切割成多个帧发送给接收端,接收端接收消息帧,并将关联的帧重新组装成完整的消息。

    5. 客户端或服务器可以主动发送一个关闭帧,表示要断开连接。另一方收到后,也会回复一个关闭帧,然后双方关闭 TCP 连接。

    image-20250414212828114

    另外,建立 WebSocket 连接之后,通过心跳机制来保持 WebSocket 连接的稳定性和活跃性。

     

     

    5. TCP与UDP协议

    TCP与UDP的区别?
    1. 是否面向连接:UDP发送数据之前不需要建立连接,而TCP发送数据前需要建立连接且发送结束后需释放连接。

    2. 是否可靠传输:UDP协议不保证数据完整性和有序性,而TCP协议保证数据完整性、正确性、有序性。

    3. 是否维护状态:UDP协议不维护任何状态,TCP协议则需记录消息是否发送成功,是否接收成功。

    4. 传输效率:UPD无需建立连接、消息确认、丢包重传等,且包头更小(8字节 vs 20~60字节),因此传输效率比TCP更高。

    5. 传输形式:UDP 是面向报文的,各个报文之间相互独立,而 TCP 是面向字节流的,有严格的先后顺序。

    6. 是否支持广播/多播:UDP 支持一对一、一对多、多对一、多对多,而 TCP 只支持点对点通信。

    7. 适用场景:UDP 一般用于即时通信,比如:语音、 视频、直播等等;TCP 用于对传输准确性要求特别高的场景,比如文件传输、发送和接收邮件、远程登录等等。

     

    基于TCP/UDP的应用层协议

     

    HTTP协议基于TCP还是UDP?

     

    TCP三次握手(重要)

    建立一个 TCP 连接需要“三次握手”,才能确认双方都正常通信,缺一不可:

    当建立了 3 次握手之后,客户端和服务端就可以传输数据啦!

    image-20250422224847643

    注意:

    1. 当服务端收到客户端的 SYN 请求时,会把半连接状态的连接放在半连接队列

    2. 当服务端收到客户端的 ACK 响应时,会将该连接从半连接队列移动到全连接队列,或者重传N次后从半连接队列删除。

    3. 在 TCP 三次握手过程中,第三次握手是可以携带数据的(客户端发送完 ACK 确认包之后就进入 ESTABLISHED 状态了)。

     

    TCP四次挥手(重要)

    断开一个 TCP 连接则需要“四次挥手”,才能确认双方都断开连接,缺一不可:

    只要四次挥手没有结束,客户端和服务端就可以继续传输数据!

    image-20250422230207593

    注意:

    1. 关闭连接时交互次数由三次拆分成了四次,因为在服务端ACK时,还需将剩余数据包发完,等一下再发送FIN关闭连接。

    2. 第四次挥手时,客户端发送给服务端的 ACK 有可能丢失,因此需要等待2MSL ,应答服务器重传过来的FIN请求。

     

    TCP如何保证传输的可靠性?

     

     

    6. 其它网络协议

    IP协议

    IP(Internet Protocol,互联网协议) 属于网络层的协议,主要作用是定义数据包的格式、对数据包进行路由寻址,以便它们可以跨网络传播并到达正确的目的地。

    IP地址是在互联网上唯一标识设备的逻辑地址,通常用于跨网络通信,可以静态分配或基于 DHCP 协议动态分配。

    它有两种主流版本:

    在发送数据包时,网络设备根据目的IP地址将数据包转发到正确的目的地网络或子网络,从而实现了设备间的通信。

     

    NAT协议

    NAT(Network Address Translation,网络地址转换) 主要用于公有 IP私有 IP 之间的映射,从而实现局域网内的多个设备通过一个公有 IP 地址访问互联网。

    主要作用如下:

     

    ARP协议

    ARP 协议,地址解析协议(Address Resolution Protocol),解决的是网络层地址(IP地址)和链路层地址(MAC地址)之间的转换问题。

    解析流程如下:

    注意:

    1. 如果目标IP地址不在同一子网,则以类似方式获取目标IP子网所在路由器MAC地址,再进行发送。

    2. MAC地址是在局域网中唯一标识设备的硬件地址,通常用于局域网内的通信,由网络设备的制造商在生产时预先分配。

    3. MAC 地址有一个特殊地址:FF-FF-FF-FF-FF-FF(全 1 地址),该地址表示广播地址

     

    ICMP协议

    互联网控制报文协议(Internet Control Message Protocol)是一种用于传输网络状态错误消息的网络层协议,它的报文类型可分为:

    PING 命令是一种基于ICMP协议的网络诊断工具,经常用来测试网络中主机之间的连通性网络延迟

    注意:

    1. 其中TTL指生存时间(Time To Live),用于控制数据包在网络中的最大跳数,防止数据包在网络中无限循环。

    2. PING 命令会向目标主机发送 ICMP Echo Request(报文类型为 8 ),如果两个主机的连通性正常,目标主机会返回一个对应的 ICMP Echo Reply(报文类型为 0)。

     

     

    7. 常见网络攻击手段

    IP欺骗

    IP欺骗指通过伪造IP地址和目标主机进行通信,该IP地址一般是受信任的IP地址。

     

    DDos攻击

    DDos(Distributed Denial of Service),分布式拒绝服务,指处于不同位置的多个攻击者同时向一个或数个目标发动攻击,是一种分布的、协同的大规模攻击方式。

     

    中间人攻击

    中间人攻击指攻击者与通信双方建立连接,并在中间修改传输内容,常见防御措施有:引入第三方机构验证数字证书和签名。

     

     

    第02章_数据结构

    第一节 线性表

    1. 数组与链表

    什么是数组?

    数组(Array)是一种基本的数据结构,它由一组相同类型的数据元素组成,这些元素在内存中是连续存储的。

    image-20250506194708096

     

    什么是链表?

    链表(Linked List)是一种通过指针将节点连接起来的线性数据结构,支持动态存储和高效的插入与删除操作。

    链表可分为:单向链表、双向链表、循环链表、双向循环链表等。

    image-20250506194950926

     

    数组 vs 链表
    特性/指标数组链表
    内存分配静态分配,大小固定,连续存储动态分配,大小可变,分散存储
    访问效率随机访问,时间复杂度 O(1)顺序访问,时间复杂度 O(n)
    插入/删除需要移动大量元素,时间复杂度 O(n)修改指针即可,时间复杂度 O(1)
    内存利用内存利用率高,可能浪费部分内存内存利用率低,额外的指针开销
    适用场景频繁随机访问元素,固定大小数据存储频繁插入和删除操作,动态大小数据存储
    不适用场景频繁插入和删除操作频繁随机访问元素

     

    实现一个动态数组

     

    实现一个双向循环链表

     

     

    2.栈与队列

    什么是栈?

    是一种后进先出(LIFO)的线性数据结构,支持在栈顶进行元素的插入和删除操作,常用一维数组链表来实现。

    image-20250506201413328

    常见的应用场景有:函数调用、表达式解析、撤销/重做功能、回溯算法、深度优先搜索(DFS)等。

     

    什么是队列?

    队列是一种先进先出(FIFO)的线性数据结构,支持在队尾插入元素和在队头删除元素,常用一维数组链表来实现。

    队列可分为:单队列、循环队列、双端队列、优先级队列(堆,非线性)等。

    image-20250506201454665

    常见的应用场景有:消息传递、对象池(线程池、连接池)、模拟栈、广度优先算法(BFS)等。

     

    实现一个栈

     

    实现一个双端队列

     

     

    第二节 树

    1. 树

    什么是树?

    是一种非线性数据结构,它由一个或多个节点组成,用于表示具有层次关系的数据。它的组成元素如下:

     

    树的分类

    树可分为:

    提示:

    1. B+树相对于比B树,查询次数更少、查询效率更文档,且更适合范围查询(B树需要通过中序遍历进行范围查询)。

     

    树的存储

    树的存储主要分为:

    注意:

    1. 顺序存储一般用于二叉树,且是完全二叉树(如:堆等),否则数组中就会出现空隙,导致内存利用率降低。

     

    树的遍历

    树的遍历主要分为:

    注意:

    1. 先序/中序/后序指的是根节点先遍历,或中间遍历,或最后遍历。

    2. 树的遍历还可以通过循环来实现,可以是基于栈的深度优先遍历或基于队列的广度优先遍历

     

     

    2. 平衡二叉树

    AVL树和红黑树的区别?

     

    红黑树的特性

    除了满足二叉搜索树的基本前提外,还需额外满足如下条件,以维持二叉树的平衡:

    注意:

    1. 红黑树可以保证:最长路径不超过最短路径的两倍,即任意节点左右子树的高度差不超过两倍。

     

    为什么红黑树插入节点默认为红色?

     

    红黑树破坏后怎么调整?

     

    实现一个红黑树

    视频讲解:https://www.bilibili.com/video/BV1Xm421x7Lg?vd_source=c27a4551ddd1aa07c2454e0df15bc296

     

     

    3. B+树

    B+树的特性

     

    实现一个B+树

     

    4. 堆(存于数组的逻辑树)

    什么是堆?

    是基于数组顺序存储的,在逻辑上近似完全二叉树的非线性数据结构,可分为:

    image-20250507213528056

    堆常用于:实现优先级队列或解决最大值或最小值问题。

     

    实现一个堆

     

     

    第三节 图

    1. 图的基本概念

    什么是图?

    是一种由顶点组成的非线性数据结构,用于表示对象之间的复杂关系。它的组成元素如下:

     

    图的分类与应用

    图可分为:无向图和有向图、无权图和带权图,下面是一张带权有向图

    image-20250506204317270

    常见的应用场景有:同学关系图(无向图)、抖音关注关系图(有向图)、城市交通图(带权有向图,使用距离作为权)等。

     

    图的存储方式

    图的常见存储方式有:

     

     

    2. 图的搜索

    深度优先搜索(DFS)

    深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索的算法,它的核心思想是从起始节点出发,沿着图的分支一路深入,直到无法继续深入为止,然后回溯到最近的分支点,继续深入其他路径,直到所有节点都被访问。

    一般使用使用(或递归)实现,适合于路径探索回溯问题,如解决迷宫问题。

    image-20250506211326731

     

    广度优先搜索(BFS)

    广度优先搜索(Breadth-First Search,BFS)是一种用于遍历或搜索的算法,它的核心思想是从起始节点开始,逐层向外扩散,先访问所有邻接节点,再依次访问这些邻接节点的邻接节点,直到所有节点都被访问。

    一般使用队列实现,适合于最短路径层级遍历,如计算图中两点之间的最短路径、社交网络分析、网络爬虫等。

    image-20250506211403505

     

    深度优先 vs 广度优先

     

     

    第四节 其它结构

    1. 布隆过滤器

    什么是布隆过滤器?

    布隆过滤器(Bloom Filter)是一种空间效率很高的概率型数据结构,主要是为了解决海量数据的存在性问题。

    它的核心思想是通过多个哈希函数将元素映射到一个位数组中,可以判断某个数据大概率存在一定不存在

    image-20250506212440476

    注意:

    1. 布隆过滤器中的元素一旦被插入,就无法单独删除(除非使用计数型布隆过滤器)。

     

    实现一个布隆过滤器

     

    Guava包的布隆过滤器

    首先我们需要在项目中引入 Guava 的依赖:

    使用如下:

     

    Redis的布隆过滤器

    Redis v4.0 之后有了 Module(模块/插件) 功能,可以添加一个布隆过滤器模块,如:https://github.com/RedisBloom/RedisBloom

     

     

    2. 散列表

    什么是散列表?

    散列表(Hash Table)是一种通过散列函数将键映射到存储位置的数据结构,用于实现快速的插入、删除和查找操作。

     

    如何解决散列表的冲突

     

    实现一个散列表

     

     

    第03章_常见算法

    第一节 基本算法思想

    1. 贪心算法

    什么是贪心算法?

    贪心算法的本质是选择每一阶段的局部最优,从而达到全局最优。其一般步骤如下:

     

    贪心算法的典型案例

     

    2. 动态规划

    什么是动态规划?

    动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的。

     

    动态规划的典型案例

     

    3. 回溯算法

    什么是回溯算法?

    回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径,其本质就是穷举。

     

    回溯算法的典型案例

    组合:https://leetcode.cn/problems/combinations/

    39.组合总和:https://leetcode.cn/problems/combination-sum/

    40.组合总和 II:https://leetcode.cn/problems/combination-sum-ii/

    78.子集:https://leetcode.cn/problems/subsets/

    90.子集 II:https://leetcode.cn/problems/subsets-ii/

    51.N 皇后:https://leetcode.cn/problems/n-queens/

     

    4. 分治算法

    什么是分治算法?

    分治算法指将一个规模为 N 的问题分解为 K 个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。

     

    分治算法的典型案例

     

     

    第二节 经典算法

    1. 排序算法

    交换排序-冒泡排序 (Bubble Sort)

    冒泡排序的基本思路:通过N-1轮比较,每轮将1个最大(最小)的元素移至未排序序列末尾

    视频讲解:https://www.bilibili.com/video/BV181421876R

     

    插入排序-插入排序 (Insertion Sort)

    插入排序的基本思路:依次将第2-N个元素插入到前面有序的部分。

    视频讲解:https://www.bilibili.com/video/BV1tf421Q7eh

     

    选择排序-选择排序 (Selection Sort)

    简单选择排序的基本思路:每轮都在剩下的数里选最小的换到前面,每轮排好一个元素,总共n-1轮。

    视频讲解:https://www.bilibili.com/video/BV1kjsuenE8v

     

    交换排序-快速排序 (Quick Sort)

    快速排序的基本思路:任取一元素作为枢轴,多次交换元素,使得左边元素都小于枢轴,右边元素都大于枢轴, 然后递归处理左右子数组,直到子数组元素为空只剩1个

    视频讲解:https://www.bilibili.com/video/BV1y4421Z7hK

     

    插入排序-希尔排序 (Shell Sort)

    希尔排序(Shell Sort)是一种基于插入排序的改进算法,也叫做缩小增量排序,它通过将记录按不同的步长分组,对每组使用直接插入排序算法排序,随着步长逐渐缩小,整个序列向有序状态演进,最后步长为1时,整个序列变为有序。

    视频讲解:https://www.bilibili.com/video/BV1bm42137UZ/

     

    选择排序-堆排序 (Heap Sort)

    堆排序(Heap Sort)是一种基于二叉堆的比较排序算法。它利用了堆这种数据结构的特性,通过构建最大堆(最小堆)来实现排序。

    视频讲解:https://www.bilibili.com/video/BV1HYtseiEQ8

     

    归并排序-归并排序 (Merge Sort)

    归并排序是一种分治算法,它将数组分成两半,通过递归分别对这两半进行排序,然后将排序后的两半合并成一个有序数组。

    视频讲解:https://www.bilibili.com/video/BV1em1oYTEFf

     

    非比较排序-计数排序 (Counting Sort)

    计数排序(Counting Sort)是一种非比较型的排序算法,适用于一定范围内的整数排序。

    视频讲解:https://www.bilibili.com/video/BV1sU4y1R7pm

     

    非比较排序-桶排序 (Bucket Sort)

    桶排序(Bucket Sort)是一种基于分而治之思想的排序算法,它将数组分到有限数量的桶里,每个桶再分别排序(通常使用其他排序算法或递归使用桶排序),适用于输入数据服从均匀分布的情况。

    视频讲解:https://www.bilibili.com/video/BV1QT411u7MA

     

    非比较排序-基数排序 (Radix Sort)

    基数排序(Radix Sort)是一种非比较型的排序算法,它通过按位排序的方式对整数进行排序。

    基数排序有两种实现方式:最低位优先(LSD,Least Significant Digit)和最高位优先(MSD,Most Significant Digit),一般使用前者。

    视频讲解:https://www.bilibili.com/video/BV1KrzrYeEDw

     

    排序算法总结
    排序算法最好时间最坏时间平均时间空间排序方式稳定性适用场景
    冒泡排序O(n)O(n^2)O(n^2)O(1)内部排序稳定基本有序的小规模数据
    插入排序O(n)O(n^2)O(n^2)O(1)内部排序稳定基本有序的小规模数据
    选择排序O(n^2)~~O(1)内部排序不稳定对交换操作敏感的小规模数据
    快速排序O(nlogn)O(n^2)O(nlogn)O(logn)内部排序不稳定数据随机性较好的大规模数据
    希尔排序O(n)O(n^2)O(n^1.3)O(1)内部排序不稳定基本有序的中规模数据
    堆排序O(nlogn)~~O(1)内部排序不稳定需要快速选择最大(或最小)元素的场景
    归并排序O(nlogn)~~O(n)外部排序稳定超大规模数据的稳定排序
    计数排序O(n+s)~~O(s)外部排序稳定范围跨度小的整数
    桶排序O(n+k)~~O(n+k)外部排序稳定分布均匀的数据
    基数排序O(d(n+r))~~O(n+k)外部排序稳定位数较少、分布均匀的整数

    注意:

    1. 内部排序:指通过内存完成排序。外部排序:一般是对大规模数据在磁盘排序。

    2. 稳定:如果 A 原本在 B 前面,而 A = B,排序之后 A 仍然在 B 的前面。

    3. 时间复杂度:定性描述一个算法执行所耗费的时间。空间复杂度:定性描述一个算法执行所需内存的大小。

    4. 比较类排序:通过比较来决定元素间的顺序,其时间复杂度不能突破 O(nlogn)

     

     

    2. 查找算法

    顺序查找(线性查找)

    顺序查找是一种简单的查找算法,适用于无序数组链表

    它从数组或链表的起始位置开始,逐个比较每个元素,直到找到目标元素或遍历完所有元素。

     

    二分查找(折半查找)

    二分查找是一种高效的查找算法,适用于有序数组

    它通过不断将数组分成两半,逐步缩小查找范围,直到找到目标元素或查找范围为空。

     

    插值查找

    插值查找是一种改进的二分查找算法,适用于数据分布较为均匀的有序数组。

    它通过估计目标元素的位置,而不是简单地取中间位置,从而可能更快地找到目标元素。

     

    跳跃查找

    跳跃查找是一种适用于有序数组的查找算法。

    它通过跳跃式地前进,逐步缩小查找范围,然后在范围内进行线性查找。

     

    哈希表查找

    哈希表查找是一种基于哈希表的数据结构,适用于快速查找。它通过哈希函数将键映射到哈希表中的位置,从而实现快速查找。

     

    深度优先搜索(DFS)

    从图的某个起始顶点开始,沿着一条路径尽可能深入地访问图中的所有顶点,直到不能继续为止,然后返回并探索其他路径。

    时间复杂度为O(V+E),空间复杂度为O(V),其中V是顶点数,E是边数。

     

    广度优先搜索(BFS)

    从图的某个起始顶点开始,先依次访问这个顶点的所有邻居顶点,然后再按照距离逐层遍历图中的所有顶点。

    时间复杂度和空间复杂度均为O(V+E)。

     

    A*算法

    结合了Dijkstra算法的广度优先搜索和贪婪最佳优先搜索的优点,通过估计从当前节点到目标节点的成本来指导搜索方向,从而在较短时间内找到最优解。时间复杂度和空间复杂度取决于启发函数和搜索树的大小。

     

     

    3. 字符串算法

    KMP算法(Knuth-Morris-Pratt)

    KMP算法是一种高效的字符串匹配算法,用于在一个主字符串中查找一个子字符串的首次出现位置。

    它通过预处理子字符串,避免了暴力匹配中的重复比较。

     

     

    第三节 分布式算法

    1. 分布式理论基础

    CAP理论

    CAP 理论是分布式系统领域的一个重要理论,它用于描述一致性、可用性和分区容错性三者之间的权衡关系。

    CAP理论指出,分布式系统在一致性(C)、可用性(A)和分区容错性(P)这三者之间最多只能同时满足两个

    注意:

    1. ZooKeeper保证的是一致性(CP),在Leader选举时整个集群不可用,在极端环境下可能会丢弃一些请求,需要用户重新请求。

    2. Eruka保证的是可用性,部分节点数据可能出现短暂不一致;Nacos 两者都支持,可以通过配置进行选择。

     

    BASE理论

    BASE 理论是对 CAP 理论 的延伸和补充,它强调通过适当放宽对一致性的要求,来换取系统的可用性和分区容错性。

     

     

    2. 分布式一致性算法

    两阶段提交(2PC)

     

    三阶段提交(3PC)

     

    TCC模式(Try-Confirm-Cancel)

    TCC模式将事务划分为三个阶段:Try(尝试预留资源)、Confirm(确认并提交)、Cancel(取消预留资源)。在Try阶段提前锁定资源,确保后续的 Confirm 阶段可以成功执行,若失败则执行Cancel。

     

    Saga模式

    Saga模式将一个全局事务拆分成多个独立的本地事务,每个本地事务成功后都会触发下一步操作。如果某个步骤失败,则通过执行补偿操作来撤销之前已执行的本地事务。

     

    Paxos算法

    Paxos算法是一种基于共识的分布式一致性算法,用于解决分布式系统中多个节点之间如何达成最终一致的问题。

    涉及的角色如下:

    主要步骤如下:

    注意:

    1. 在网络复杂的情况下,Paxos算法可能很久都无法收敛,甚至陷入活锁,因此一般会选择一个 Leader 负责进行提案。

     

    ZAB算法

    ZAB(Zookeeper Atomic Broadcast)算法是Zookeeper中使用的一种基于共识的一致性协议,用于解决分布式系统中的数据一致性问题。

    主要角色如下:

    主要步骤如下:

    注意:

    1. ZAB 算法能在部分节点故障的情况下保证事务的原子性顺序性,但 Leader 故障时,会影响系统的可用性。

     

    Raft算法

    Raft 算法是一种用于分布式系统中实现一致性(Consensus)的算法,它主要用于解决分布式系统中的数据复制故障恢复问题。

     

    Gossip协议

    Gossip协议是一种基于Epidemic算法的去中心化的一致性协议,主要用于最终一致性模型,常见于分布式数据库和分布式缓存系统。

     

     

    第04章_设计模式

    第一节 设计模式概述

    1. 设计模式是什么?

    设计模式是软件开发中的最佳实践,帮助开发者在面对复杂设计问题时提供有效的解决方案。

     

     

    2. 面向对象设计原则

    面向对象设计原则为支持可维护性复用而诞生,这些原则蕴含在很多设计模式中,它们是从许多设计方案中总结出的指导性原则。

    image-20241125164240619

     

     

    3. 设计模式的分类

    1) 创建型模式

    image-20241125164044746

     

    2) 结构型模式

    image-20241125164119204

     

    3) 行为型模式

    image-20241125164139799

     

     

    第二节 创建型模式(Creational Patterns)

    创建型模式关注于对象的创建,提供了更灵活的对象创建方式。

     

    1. 单例模式(Singleton Pattern)

    单例模式指一个类只有一个实例,并提供一个全局访问点。下面是 Java 中的一些实现方式:

     

    1) 饿汉式(静态常量)【可用】

    优点:这种写法比较简单,就是在类装载的时候就完成实例化,避免了线程同步问题。

    缺点:在类装载的时候就完成实例化,没有达到 Lazy Loading 的效果。如果从始至终从未使用过这个实例,则会造成内存的浪费。

     

    2) 饿汉式(静态代码块)【可用】

    这种方式和上面的方式类似,只不过将类实例化的过程放在了静态代码块中,也是在类装载的时候执行静态代码块中的代码,初始化类的实例。优缺点和上面一样。

     

    3) 懒汉式(线程不安全)【不可用】

    这种写法起到了 Lazy Loading 的效果,但是只能在单线程下使用。如果在多线程下,一个线程进入了 if (instance == null) 判断语句块,还未来得及往下执行,另一个线程也通过了这个判断语句,这时便会产生多个实例。所以在多线程环境下不可使用这种方式。

     

    4) 懒汉式(线程安全,同步方法)【不推荐用】

    解决上面线程不安全问题的方式是对 getInstance() 方法进行同步。但这种方式效率太低,每个线程在想获得类的实例时,执行getInstance() 方法都要进行同步。其实这个方法只需执行一次实例化代码,后面直接 return 实例化对象即可。

     

    5) 懒汉式(线程安全,同步代码块)【不可用】

    这种方式尝试使用同步代码块来提高效率,但仍无法保证线程安全。如果一个线程进入了 if (instance == null) 判断语句块,还未来得及往下执行,另一个线程也通过了这个判断语句,这时便会产生多个实例。

     

    6) 双重检查【推荐使用】

    Double-Check 概念对于多线程开发者来说不会陌生,进行了两次 if (instance == null) 检查,这样就可以保证线程安全。实例化代码只需执行一次,后面再次访问时,判断 if (instance == null),直接 return 实例化对象。

    优点:线程安全;延迟加载;效率较高。

     

    7) 静态内部类【推荐使用】

    这种方式与饿汉式方式类似,都是采用类装载机制来保证实例化时只有一个线程。但不同的是,饿汉式在类装载时就实例化,没有 Lazy-Loading 效果,而静态内部类方式在需要实例化时才装载静态内部类,从而实例化 Singleton。类的静态属性只会在第一次加载类时初始化,所以这里JVM帮助保证了线程的安全性。

    优点:避免了线程不安全,延迟加载,效率高。

     

    8) 单元素枚举【推荐使用】

    创建枚举默认就是线程安全的,不需要担心 double checked locking,并且还能防止反序列化导致重新创建新的对象。枚举让JVM保证线程安全和单一实例问题,是 JDK1.5 版本后最适合用于创建单例设计模式的方法,是唯一一种不会被反射破坏单例状态的模式。

     

     

    2. 原型模式(Prototype Pattern)

    定义:指通过复制现有的实例来创建新实例,而不是通过构造函数。

    原理:实现 Cloneable 接口并重写 clone() 方法来复制对象。

    优点

     

     

    3. 建造者模式(Builder Pattern)

    定义:使用多个简单的对象一步一步构建一个复杂的对象。

    原理:定义一个建造者接口和具体建造者类,通过建造者类来创建复杂对象。

    优点

     

     

    4. 简单工厂模式

    定义:通过一个静态方法,根据传入的参数,返回不同类型的对象。

    优点:客户端不需要知道具体产品类的类名,只需要知道一个参数即可创建产品实例,降低了客户端与具体产品类的耦合。

    缺点

    使用场景

     

     

    5. 工厂方法模式(Factory Method Pattern)

    定义:定义一个创建对象的接口,但由子类决定实例化哪个类。

    原理:将对象的创建逻辑放在子类中,而不是在客户端代码中。

    优点:

    缺点:

    使用场景:

     

     

    6. 抽象工厂模式(Abstract Factory Pattern)

    定义:提供一个创建一系列相关或相互依赖对象的接口,而无需指定它们具体的类。

    原理:通过定义多个工厂接口,每个接口负责创建一组相关的对象。

    优点:

    缺点:

    使用场景:

     

     

    第三节 结构型模式(Structural Patterns)

    结构型模式关注如何将类或对象组合成更大的结构,以便更好地实现功能。

     

    1. 适配器模式(Adapter Pattern)

    定义:将一个类的接口转换成客户希望的另一个接口。适配器模式使得原本接口不兼容的类可以合作。

    原理:通过引入一个适配器类,将目标接口转换为适配者接口。

    优点:

     

     

    2. 桥接模式(Bridge Pattern)

    定义:将抽象部分与实现部分分离,使它们可以独立地变化。

    原理:通过定义抽象类和实现类,将它们的变化解耦。

    优点:

     

     

    3. 组合模式(Composite Pattern)

    定义:将对象组合成树形结构以表示部分-整体层次结构,使得客户端对单个对象和组合对象的使用具有一致性。

    原理:通过定义一个组件接口,将叶子节点和容器节点统一处理。

    优点:

     

     

    4. 装饰器模式(Decorator Pattern)

    定义:动态地给一个对象添加一些额外的职责。装饰器模式提供了比继承更灵活的扩展功能的方式。

    原理:通过定义装饰器类来扩展被装饰对象的功能。

    优点:

     

     

    5. 外观模式(Facade Pattern)

    定义:为子系统中的一组接口提供一个一致的界面,使得子系统更容易使用。

    原理:通过定义一个外观类来封装子系统的复杂性,提供简化的接口。

    优点:

     

     

    6. 享元模式(Flyweight Pattern)

    定义:运用共享技术有效地支持大量细粒度的对象。

    原理:通过将对象的共享部分与独享部分分开,将共享部分提取出来。

    优点:

     

     

    7. 代理模式(Proxy Pattern)

    定义:为其他对象提供一种代理以控制对这个对象的访问。

    原理:通过定义代理类来控制对真实对象的访问。

    优点:

    分类:

     

    1) 静态代理

     

    2) JDK动态代理

     

    3) CGLIB动态代理

     

     

    第四节 行为型模式(Behavioral Patterns)

    行为型模式关注对象之间的沟通和职责分配

     

    1. 责任链模式(Chain of Responsibility Pattern)

    定义:使多个对象都有机会处理请求,从而避免请求的发送者和接收者之间的耦合关系。将这些对象连成一条链,并沿着这条链传递请求,直到有一个对象处理它为止。

    原理:通过定义处理请求的链,并逐步将请求传递给链中的各个对象,直到找到合适的处理者。

    优点:

     

     

    2. 命令模式(Command Pattern)

    定义:将请求封装成一个对象,从而使你能够用不同的请求对客户进行参数化、队列化请求、以及支持可撤销操作。

    原理:通过定义命令接口和具体命令类,将请求封装为对象,并将其传递给调用者。

    优点:

     

     

    3. 迭代器模式(Iterator Pattern)

    定义:提供一种方法访问一个容器对象中各个元素,而又不暴露该对象的内部表示。

    原理:通过定义迭代器接口和具体迭代器类来遍历集合对象中的元素。

    优点:

     

     

    4. 中介者模式(Mediator Pattern)

    定义:定义一个对象来封装一组对象之间的交互,使得对象之间的耦合松散,从而使得它们可以独立地改变。

    原理:通过定义中介者接口和具体中介者类来协调对象之间的交互。

    优点:

     

     

    5. 备忘录模式(Memento Pattern)

    定义:在不暴露对象内部状态的情况下,捕获一个对象的内部状态,并在该对象外部保存这个状态。可以在以后将对象恢复到保存的状态。

    原理:通过定义备忘录类来保存对象的状态,并通过发起人类和恢复者类来实现状态的恢复。

    优点:

     

     

    6. 解释器模式(Interpreter Pattern)

    定义:给定一个语言,定义它的文法的一种表示,并定义一个解释器,该解释器使用该表示来解释语言中的句子。

    原理:通过定义解释器类和表达式类,将文法规则和解释逻辑分开。

    优点:

     

     

    7. 状态模式(State Pattern)

    定义:允许对象在内部状态改变时改变它的行为,对象看起来好像修改了它的类。

    原理:通过定义状态接口和具体状态类,将对象的状态和行为分开,使得状态改变时可以改变行为。

    优点:

     

     

    8. 策略模式(Strategy Pattern)

    定义:定义一系列算法,将每一个算法封装起来,并使它们可以相互替换。策略模式让算法独立于使用它的客户而独立变化。

    原理:通过定义策略接口和具体策略类,将算法封装为对象,并在运行时选择使用。

    优点:

     

     

    9. 模板方法模式(Template Method Pattern)

    定义:定义一个操作中的算法的骨架,将一些步骤延迟到子类中。模板方法使得子类可以在不改变算法结构的情况下重新定义算法中的某些步骤。

    原理:通过定义模板方法在父类中,并将一些步骤的实现延迟到子类中。

    优点:

     

     

    10. 访问者模式(Visitor Pattern)

    定义:表示一个作用于某对象结构中的各元素的操作,它可以在不改变元素类的前提下定义作用于这些元素的新操作。

    原理:通过定义访问者接口和具体访问者类,将操作和对象结构分离,使得可以在不改变对象结构的情况下增加新的操作。

    优点:

     

     

    11. 观察者模式(Observer Pattern)

    定义:定义对象之间的一对多依赖,使得当一个对象改变状态时,所有依赖于它的对象都得到通知并被自动更新。

    原理:通过定义观察者接口和被观察者类来实现一对多的通知机制。

    优点:

     

     

    第五节 UML图

    1. UML简介

    UML 是 Unified Model Language 的缩写,中文是统一建模语言,是由一整套图表组成的标准化建模语言。分类如下:

    img

     

     

    2. 类图(Class Diagram)

    类图是面向对象系统建模中最常用和最重要的图,是定义其它图的基础,主要用来表示接口以及它们之间的静态结构和关系

    在类图中,常见的有以下几种关系:

     

    1) 泛化/继承(Generalization)

    泛化关系是一种继承关系(is A),表示子类继承父类的所有特征和行为。

    img

     

    2) 实现(Realization)

    实现关系是一种类与接口的实现关系(is A),表示类是接口所有特征和行为的实现。

    img

     

    3) 组合(Composition)

    组合关系是一种整体部分的关系,且部分不能离开整体而单独存在。组合关系是关联关系的一种,是比聚合关系还要强的关系。

    img

    鸟是整体,翅膀是部分。鸟死了,翅膀也就不能飞了。所以是组合。

     

    4) 聚合(Aggregation)

    聚合关系是一种整体部分的关系(has A),但部分可以离开整体而单独存在。聚合关系是关联关系的一种,是较强的关联关系;

    img

    电脑有键盘才能输入信息,电脑是整体,键盘是部分,键盘也可以离开电脑,单纯的拿去敲,所以是聚合。

     

    5) 关联(Association)

    关联关系是一种拥有关系(has A),它使得一个类知道另一个类的属性和方法。

    img

    车是车,人是人,没有整体与部分的关系。

    6) 依赖(Dependency)

    依赖关系是一种使用关系(use A),即一个类的实现需要另一个类的协助。

    img

    老司机只管开车,车是谁的不重要,给什么车开什么车。

     

     

    3. 其它UML图

    1) 组件图

    img

    订单系统组件依赖于客户资源库和库存系统组件。中间的虚线箭头表示依赖关系。另外两个符号,表示组件连接器,一个提供接口,一个需要接口。

     

    2) 部署图

    img

    图中简单的表示,不同机器上面部署的不同软件。

     

    3) 对象图

    img

    图中就是描述的,某时间点 bat 这个公司有一个研发部,一个销售部,两个部门只有一个人iisheng

     

    4) 包图

    img

    5) 组合结构图

    img

    图中描述了Car是由车轴连接着的两个前面轮子、两个后面轮子,和引擎组合的。

     

    6) 轮廓图

    img

    图中我们定义了一个简易的EJB的概要图。Bean是从Component扩展来的。Entity BeanSession Bean继承了BeanEJB拥有RemoteHome接口,和JAR包。

     

    7) 用例图

    img

    用例图中包含以下三种关系:

     

    8) 活动图

    img

    图中简单描述了,从开始到登录到查看订单列表,或者登录失败直接结束。

     

    9) 状态图

    img

    图中描述了,门在其生命周期内所经历的状态。

     

    10) 序列图

    img

    图中展示的是支付宝条码支付场景的序列图。其中,loop是循环,alt是选择,序列图的其他关系这里就不介绍了。

     

    11) 通讯图/协作图

    img

    图中展示了一个线上书店的通讯图,方框和小人表示生命线,不同生命线之间可以传递消息,消息前面的数字可以表达序列顺序。

     

    12) 交互概览图

    img

    图中表示一个调度系统的交互概览图,跟活动图很像。其中sd的框代表具体的交互流程,ref框代表使用交互。

     

    13) 时序图

    img

    图中展示了老年痴呆病人随着时间的变化病情的变化。