计算机网络
详细讲解一下 TCP 三次握手、四次挥手这个内容?为什么不能是两次?
TCP 是面向连接、可靠、全双工的传输层协议。全双工意味着两个方向的数据传输是独立的,A 能发数据给 B,B 也能同时发数据给 A,两个方向的连接需要分别建立、分别关闭。
三次握手
客户端发 SYN:
客户端随机生成初始序列号
seq=x,置 SYN 标志位,进入SYN_SENT状态。SYN 报文不携带数据,但消耗一个序列号(所以对方要 ack x+1)。第一步为了让服务器知道 客户端的发送能力正常。
服务器回 SYN+ACK:
服务器收到后,也随机生成自己的初始序列号
seq=y,同时ack=x+1表示 我已收到你的 x,期待下一个字节 x+1。服务器进入SYN_RCVD状态。第二步为了让客户端知道 服务器接收能力正常 + 服务器发送能力正常。
客户端回 ACK:
客户端
ack=y+1,确认收到服务器的 SYN。此报文可以携带数据。双方进入连接建立。让服务器知道 客户端接收能力正常。
三次之后,双方都确认了对方和自己的收发能力均正常,且双方的初始序列号都被对方确认。
两次握手无法让服务器确认客户端的接收能力,也无法防止历史失效连接请求造成的问题,而且序列号同步需要双向确认。因为 TCP 靠序列号保证可靠性和顺序。所以需要三次握手
四次握手
客户端发 FIN 表示 我没有数据要发了(注意:只是这个方向不再发数据,仍可接收)。客户端进入
FIN_WAIT_1。服务器回 ACK 服务器确认收到 FIN,进入
CLOSE_WAIT。此时连接处于半关闭状态:客户端不再发数据,但服务器可能还有数据要发给客户端,可以继续发。客户端收到 ACK 后进入FIN_WAIT_2。服务器发 FIN 等服务器把剩余数据发完,它也发 FIN 表示”我也没数据要发了”,进入
LAST_ACK。客户端回 ACK 客户端确认,进入
TIME_WAIT,等待 2MSL(Maximum Segment Lifetime,报文最大生存时间的两倍)后进入CLOSED。服务器收到 ACK 后直接CLOSED。为什么客户端最后要等 2MSL
保证最后一个 ACK 能到达服务器
如果客户端发的第四个 ACK 丢失了,服务器会超时重发 FIN。此时客户端还在 TIME_WAIT 状态,能重新回 ACK。如果客户端直接关闭,服务器重发的 FIN 就无人应答,服务器会一直卡在 LAST_ACK 无法正常关闭。
让本次连接的旧报文在网络中消亡
连接关闭后,如果立刻用相同的四元组建立新连接,网络中滞留的旧连接报文可能被新连接误收,造成数据错乱。等待 2MSL 让旧报文自然过期消亡,保证新连接干净。
四次握手,是因为 TCP 是全双工的,两个方向的关闭必须分别进行,而且服务器收到 FIN 后往往不能立刻关闭自己这一侧。
初始序列号(ISN)为什么必须随机?固定 ISN 会带来什么风险?
- 序列号是 TCP 实现可靠传输与连接身份识别的基石,一旦可预测,攻击者就能伪造报文、劫持或干扰连接
TCP 是怎么保证可靠传输的?
TCP 的可靠性是一套组合机制的结果
序列号与确认应答
TCP 为发送的每个字节都编了号。接收方收到数据后,会返回一个确认号(ACK),告诉发送方:“我期待收到的下一个字节序号是 X”,这表示 X 之前的所有字节都已安全到达。
超时重传 发送方为每个发出的报文段设置一个定时器。如果在合理的往返时间(RTT)内没有收到对应的 ACK,就判定该报文段丢失,并重新发送它。
数据排序与去重 由于 IP 网络可能导致数据包乱序到达,接收方的 TCP 会依据序列号,将乱序的报文段重新排列成正确的顺序,再交给应用层。同时,对于序列号重复的报文段(例如因重传导致),接收方会识别并丢弃,避免重复数据。
校验和 TCP 首部包含一个校验和字段,覆盖了首部和数据部分。发送方计算并填入,接收方收到后重新计算并比对。如果校验失败,说明数据在传输中发生了比特错误,该报文段会被直接丢弃,等待发送方超时重传。
流量控制 TCP 使用滑动窗口机制。接收方通过 ACK 报文中的“窗口”字段,动态告知发送方自己当前还能接收多少数据。发送方根据这个窗口值调整发送速率,防止发送太快导致接收方缓冲区溢出。
拥塞控制 流量控制是为了保护接收方,而拥塞控制是为了保护网络。TCP 通过慢启动、拥塞避免、快重传和快恢复等算法,探测网络的承载能力,并动态调整发送速率,避免过多数据注入网络导致路由器过载丢包。
TCP 和 UDP 有什么区别?
TCP 是面向连接、提供可靠传输的协议,而 UDP 是无连接、尽最大努力交付的协议。
连接方式
- TCP:面向连接。通信前必须通过“三次握手”建立连接,结束后通过“四次挥手”释放。
- UDP:无连接。发送数据前不建立连接,直接封装成数据报发送。
可靠性
- TCP:可靠。通过确认、重传、排序等机制,确保数据无差错、不丢失、不重复且按序到达。
- UDP:不可靠。不保证数据到达,不保证顺序,也不进行重传,可能出现丢失、重复或乱序。
传输方式
- TCP:面向字节流。将数据视为无结构的字节流进行分段传输。
- UDP:面向报文。保留应用层交下来的报文边界,直接添加首部后发送。
开销与效率
- TCP:首部至少 20 字节,且需要维护连接状态,开销大,速度相对较慢。
- UDP:首部仅 8 字节,无需维护连接状态,开销小,传输速度快、实时性好。
适用场景
- TCP:适用于对可靠性要求高、但对实时性要求相对宽松的场景,如网页浏览(HTTP)、文件传输(FTP)、邮件(SMTP)。
- UDP:适用于对实时性要求高、能容忍少量丢包的场景,如音视频流、在线游戏、DNS 查询。
HTTP/1.1、HTTP/2、HTTP/3 分别解决了什么问题?HTTPS 是怎么保证安全的?
HTTP/1.1、HTTP/2、HTTP/3,这些演进本质上都是为了 如何更快、更高效地传输 Web 资源 展开的
- HTTP/1.1 解决了 HTTP/1.0
需要为每个请求单独建立连接的问题,引入了持久连接,允许在同一个 TCP
连接上发送多个请求。
- 但是存在队头阻塞和头部冗余的问题
- HTTP/2 的主要目标是解决 HTTP/1.1 的性能问题
- 通过多路复用,允许在同一个 TCP 连接上并行交错地发送多个请求和响应,每个请求/响应被拆分为独立的帧并打上流标识符。这彻底解决了 HTTP/1.1 应用层的队头阻塞问题,多个请求可以真正并行处理。
- 头部压缩,针对 HTTP/1.1 头部冗余的问题,HTTP/2 使用 HPACK 算法压缩头部,减少了传输开销。
- HTTP/3 的核心变革是不再使用 TCP,而是改用基于 UDP 的 QUIC 协议。
- 解决 TCP 队头阻塞:QUIC 在 UDP 之上实现了独立的流控制。每个 HTTP 请求/响应在 QUIC 中拥有独立的流,一个流上的丢包只会阻塞该流本身,不会影响同一连接上的其他流。这从根本上解决了 HTTP/2 在 TCP 层面无法回避的队头阻塞问题。
- 更快的连接建立:QUIC 将传输层握手和 TLS 1.3 加密握手合并,通常只需 1 个 RTT 即可建立安全连接
HTTPS 并非一个全新的协议,而是 HTTP over TLS/SSL。它在 HTTP 和 TCP 之间加入了一个安全层,主要解决 HTTP 明文传输带来的窃听、篡改和冒充风险。
身份认证:数字证书
服务器会向客户端出示由受信任的证书颁发机构(CA) 签发的数字证书。客户端(浏览器)会验证证书的签名链是否指向自己信任的根 CA,以及证书中的域名是否与正在访问的站点一致。这确保了客户端正在与真正的服务器通信,而不是中间人。
密钥:非对称加密
在握手阶段,客户端和服务器使用非对称加密来安全地协商出一个只有双方知道的会话密钥。服务器用私钥解密客户端用其公钥加密的信息,从而在不安全的信道上安全地交换了用于后续通信的对称密钥。
数据加密与完整性:对称加密
握手完成后,双方使用协商好的会话密钥,通过对称加密算法来加密实际的 HTTP 报文。
从浏览器输入 URL 到页面展示,整个过程中间发生了什么?
网络请求与导航:找到服务器、取回网页数据,并准备好渲染环境
- 浏览器处理输入与发起网络请求
- DNS 查询,获得目标服务器的 IP 地址
- 拿到 IP 后,浏览器会与服务器进行 TCP 三次握手建立连接。如果网址是 HTTPS,还会在此基础上进行 TLS 握手
- 发送请求与接收响应
- 网络线程处理响应与准备渲染进程
- 提交导航,地址栏更新,导航完成,进入渲染阶段
浏览器渲染:渲染进程拿到 HTML 数据后,开始将代码变成可视化的页面。这个过程是渐进式的。
- 解析 HTML 构建 DOM
- 解析 CSS 构建 CSSOM
- 合成渲染树,将 DOM 和 CSSOM 结合
- 布局和绘制,计算渲染树中每个节点在屏幕上的精确位置和大小,并进行合成显示。
一些额外的问题
DNS 递归查询与迭代查询的区别
- 递归查询:通常发生在客户端与本地 DNS 服务器之间。客户端发出请求后,要求本地 DNS 服务器必须给出一个最终结果。本地 DNS 服务器如果自己没有缓存,就必须代替客户端去询问其他服务器,直到拿到答案再返回给客户端。
- 迭代查询:通常发生在 DNS 服务器之间。本地 DNS 服务器去询问根服务器或顶级域服务器,得到指引然后不断查询。
本地 DNS 缓存分布在哪里
- 为了加速解析,DNS 结果会缓存,一般在浏览器缓存,操作系统缓存,路由器缓存,ISP缓存
TCP 三次握手与 TLS 握手能同时进行吗
- 在标准、常规的 HTTPS 流程中,不能同时进行。必须先完成 TCP 三次握手,建立可靠传输信道后,才能开始 TLS 握手
请求到达服务端后,Nginx、网关、应用服务器分别做了什么
Nginx 通常作为流量的第一入口。它负责接收外部请求,并依据配置的规则(如轮询、权重)将请求分发(负载均衡)到后端的多个网关或服务实例上,同时可能承担 SSL 卸载、静态资源缓存等职责。
网关作为内部服务的统一门面。它负责路由(将请求精准转发到对应的微服务)、鉴权(校验
Token、权限)、限流、协议转换或日志记录等。例如,Nginx 可能先把请求交给
Zuul 或 Spring Cloud Gateway,再由网关根据路径(如
/user/)路由到具体的用户服务。
应用服务器,接收网关转发过来的请求,进行业务处理,生成响应数据,然后沿着原链路返回给客户端
操作系统
进程、线程、协程有什么区别?进程间通信有哪些方式?
进程是操作系统资源分配的基本单位,线程是 CPU 调度的基本单位,协程则是用户态下由程序自身调度的轻量级执行单元。
- 进程:操作系统进行资源分配的基本单位。每个进程拥有独立的虚拟地址空间、文件描述符表、信号处理等资源。进程间的隔离性强,一个进程崩溃通常不会影响其他进程,但创建和切换进程的开销也最大,因为涉及内核态的资源分配和上下文切换。
- 线程:线程是 CPU 调度的基本单位,也是进程内的一个执行流。同一进程内的多个线程共享该进程的地址空间、全局变量、打开的文件等资源,但每个线程有自己独立的栈、寄存器和程序计数器。线程切换只需保存少量寄存器状态,开销远小于进程切换。但共享内存也带来了数据竞争问题,需要同步机制(如互斥锁)来保护临界区。
- 协程:协程是用户态的轻量级线程,其调度完全由程序控制,不经过操作系统内核。协程的切换仅需保存少量用户态上下文,开销极小,因此可以在单线程内创建成千上万个协程。
进程间通信(IPC)则需要借助操作系统提供的机制,因为进程拥有独立的地址空间。
管道 Pipe 和 命名管道 FIFO
管道是半双工的字节流,通常用于具有亲缘关系的进程间通信。
命名管道(FIFO)则在文件系统中有一个路径名,允许无亲缘关系的进程通过打开同一个文件来通信。
消息队列
内核维护的消息链表,进程可以按类型发送和接收消息。
共享内存
多个进程将同一块物理内存映射到各自的地址空间,直接读写,是速度最快的 IPC 方式,因为数据不需要在内核与用户空间之间拷贝。
信号量
主要用于同步与互斥。是一个计数器,用于控制多个进程对共享资源的访问。
信号
一种异步通知机制,用于通知进程发生了某个事件
套接字
最通用的 IPC 方式,既可用于同一主机上的进程间通信,也可用于跨主机的网络通信
一些追问
进程和线程在地址空间、文件描述符、栈、寄存器上分别共享和独享什么?
线程切换和进程切换的开销差在哪?上下文切换具体保存了哪些内容?
协程为什么更轻量?它和线程的调度方式有什么本质区别?Java 虚拟线程算协程吗?
死锁产生的必要条件是什么?怎么预防、避免和排查?
这四个条件必须同时满足才会发生死锁
- 互斥:资源一次只能被一个进程占用。如果其他进程请求该资源,必须等待。
- 占有并等待:一个进程已持有至少一个资源,同时又提出新的资源请求,而该资源被其他进程占有,此时请求进程阻塞,但对自己已获得的资源保持不放。
- 不可剥夺:资源只能由持有它的进程主动释放,不能被强行剥夺。
- 循环等待:存在一个进程资源的循环等待链,链中每个进程都在等待下一个进程所持有的资源。
破坏其中任何一个即可防止死锁
- 破坏互斥:理论上可将资源改造为可共享,但多数资源(如打印机、写锁)本质互斥,难以推广。
- 破坏占有并等待:要求进程一次性申请全部资源,要么全拿到,要么一个不拿。缺点是资源浪费严重、可能饥饿。
- 破坏不可剥夺:当进程请求新资源被拒时,释放已持有的全部资源,稍后重试。实现复杂,且反复释放重试开销大。
- 破坏循环等待:对资源全局编号,要求进程必须按递增顺序申请资源。这是最常用、最可行的预防策略,但编号需合理,且限制了编程灵活性。
避免死锁就是在运行时动态判断是否可能进入不安全状态,典型算法是银行家算法。
死锁检测:维护资源分配图,定期或按需检测图中是否存在环。若存在环且资源类型单一,则发生死锁
死锁恢复:检测到死锁后,可选择终止部分或全部死锁进程,或回滚到安全点,或剥夺某些进程的资源。
虚拟内存是什么?分页、缺页中断和页面置换算法是怎么回事?
五种 I/O 模型是什么?select、poll、epoll 有什么区别?
阻塞 I/O
先等待数据到达内核缓冲区,数据就绪后再等待内核把数据拷贝到用户空间,整个过程中进程一直睡眠。两个阶段都阻塞,一个线程只能处理一个连接
非阻塞 I/O
若数据未就绪,内核立即返回错误,进程不阻塞,可以轮询重试。但数据拷贝阶段仍然是阻塞的。
I/O 多路复用
进程通过
select/poll/epoll同时监视多个文件描述符,一个线程管理大量连接信号驱动 I/O
进程先注册
SIGIO信号处理函数,然后立即返回不阻塞。数据就绪时内核发信号通知进程,进程再在信号处理中发起recvfrom拷贝数据。准备阶段不阻塞,拷贝阶段阻塞。异步 I/O
进程发命令后立即返回,内核负责准备和拷贝两个阶段,全部完成后才通知进程。进程全程不阻塞、不参与拷贝。
select、poll、epoll 三者都是 I/O 多路复用的实现
计算机组成原理
为什么 CPU 要有缓存?局部性原理、缓存映射和缓存一致性是怎么回事?
一条指令在 CPU 里是怎么执行的?
一条指令从取到执行完,经典划分为 五个阶段:
取地址
PC(程序计数器) 指向下一条要执行的指令地址;然后根据缓存情况取出指令,放入指令寄存器,PC 自增
译码
指令译码器解析 IR 中的操作码(opcode)和操作数,确定这是什么指令,以及操作数来自寄存器还是内存;
执行
如果是运算,ALU(算术逻辑单元) 执行运算。如果是访存指令,计算有效地址。如果是分支指令,判断跳转条件。
访存
只有 load/store 指令才真正访问数据缓存或内存,才有这。
写回
把执行结果写回寄存器堆,更新标志寄存器,供后续分支指令使用。
真实 CPU 为了提升吞吐做了大量优化
- 流水线:把五个阶段拆成流水线,多条指令重叠执行
- 多级缓存
关联一下 Java:
- Java 字节码也是指令
- JVM 执行的是字节码指令,JVM 解释器本质上就是一个 字节码指令周期:取字节码 → 译码 → 执行,与 CPU 指令周期同构。
- JIT 编译后,热点字节码被编译成本地机器码,这时才真正落到 CPU 的指令执行
- volatile 与内存屏障
volatile的可见性和有序性,最终靠 CPU 的内存屏障指令实现,禁止指令重排序、强制刷写缓存;- happens-before 与指令重排
- Java 内存模型(JMM)的
happens-before规则,本质是在约束编译器和 CPU 的重排序行为,与 CPU 乱序执行直接相关。
中断和异常有什么区别?系统调用为什么会让 CPU 从用户态切到内核态?
中断和异常都是 CPU 在执行过程中 暂停当前指令流,保存现场,跳转到处理程序 的情况。区别在于触发来源和与当前指令的关系
- 中断:触发来源来自外部硬件,和当前指令是异步的,可在任意指令边界产生,典型就是时钟中断和 IO 中断,处理完返回原程序继续
- 异常:触发来源 CPU 内部,当前指令执行产生,是同步的,由当前指令触发,是”这条指令的产物”,例如缺页异常、除零、非法指令等等,一般会进行故障修复,返回,中止等
系统调用为什么会让 CPU 从用户态切到内核态,因为用户态无权直接操作硬件和内核资源,必须通过受控入口进入内核,由内核代为完成,并借此完成特权级切换与安全隔离。
具体拆成几点:
特权级隔离
CPU 划分特权级。用户程序运行在低特权级,不能执行特权指令。文件、网络、内存分配等资源由内核统一管理,用户态只能请求,不能直接操作
系统调用是一条特殊的陷入指令
用户程序执行一条陷入指令,这条指令会:触发一个同步异常,CPU 硬件自动完成特权级切换,保存用户态现场,根据系统调用表跳转到内核的入口处理程序
因此,上下文切换成本高,所以高性能场景会减少系统调用
切换需要硬件和内核合作
硬件负责:切换栈指针、切换特权级、保存/恢复现场、查中断向量;
内核负责:根据系统调用号查系统调用表,执行对应内核函数,完成后执行返回指令,恢复用户态现场并切回权级
编译原理基础
源文件到可执行程序,编译过程分哪几个阶段?解释器和编译器有什么区别?
源文件到可执行程序的编译过程,以C/C++这类静态编译语言为参照,经典分为四个阶段:
预处理
处理以
#开头的预处理指令等内容,输出预处理后的.i文件。一般情况下,预处理就是文本替换和处理,不检查编译
对预处理后的代码做词法分析、语法分析、语义分析,生成中间代码,再优化,最终生成汇编代码
这一步是真正意义上的”编译”,会做类型检查、语法报错。
汇编
把编译产生的汇编代码翻译成机器指令,生成目标文件,此时已是二进制,但还不能直接运行
链接
把多个目标文件和库文件合并,解析符号引用、重定位地址,最终生成可执行文件。
链接分静态链接和动态链接:静态链接把库代码复制进可执行文件;动态链接只记录依赖,运行时由加载器加载。
解释器与编译器的区别
| 维度 | 编译器(Compiler) | 解释器(Interpreter) |
|---|---|---|
| 工作方式 | 一次性把整个源程序翻译成目标代码(机器码/字节码),生成独立文件 | 逐行/逐条读取源代码,翻译并立即执行,不生成独立目标文件 |
| 执行时机 | 先编译,后执行(离线) | 边翻译边执行(在线) |
| 输出 | 生成可执行文件 | 不产生可执行文件,只产生执行结果 |
| 执行速度 | 编译后运行快(无翻译开销) | 每次运行都要翻译,通常较慢 |
| 启动/调试 | 编译耗时,启动快;出错在编译期集中暴露 | 启动快,便于交互式调试;错误在运行时才暴露 |
| 跨平台 | 生成的目标码通常与平台相关 | 源程序可跨平台,但需对应平台的解释器 |
| 典型代表 | C/C++ 编译器(gcc)、Go | Python、JavaScript(早期)、Shell |
关键区别一句话:编译器是先整体翻译、后执行,解释器是翻译一句、执行一句。
Java 的特殊性
javac是编译器,把.java编译成平台无关的字节码;- JVM 里既有解释器(逐条解释字节码执行,启动快),又有 JIT 编译器(把热点字节码编译成本地机器码,运行快);
- 程序刚启动用解释器保证响应速度,热点代码交给 JIT 编译优化,兼顾启动性能与峰值性能。这就是 Java 编译与解释并存 的特点。
数据结构与算法
时间复杂度怎么分析?常见复杂度的大小顺序是什么?
时间复杂度是衡量算法执行时间随输入规模 n 增长的变化趋势。分析时通常做三件事:
- 确定输入规模 nn:是数组长度、字符串长度、节点数、矩阵维度等。
- 找出基本操作:循环体、比较、赋值、递归调用等执行最频繁的操作。
- 忽略常数和低阶项:只保留增长最快的项。
常见复杂度的大小顺序
\(O(1)<O(logn)<O(n)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)\)
大 O、大 Ω、大 Θ 有什么区别?
- 大 O:渐进上界,说“这个算法是 O(nlogn)”通常意思是“最坏不超过这个量级”
- 大 Ω:渐进下界,一般是说这个算法的复杂度至少是这样的
- 大 Θ:渐进紧界,同阶增长
均摊复杂度是把一系列操作的总代价分摊到每次操作上得到的平均代价。
数组和链表有什么区别?为什么数组随机访问是 O(1)?
| 维度 | 数组 | 链表 |
|---|---|---|
| 内存布局 | 连续内存 | 节点分散,靠指针连接 |
| 随机访问 | O(1) | O(n) |
| 按值查找 | O(n),有序可二分 O(logn) | O(n) |
| 头部插入/删除 | O(n),要搬移元素 | O(1),改指针 |
| 尾部插入 | 动态数组均摊 O(1),静态数组可能越界 | 有尾指针 O(1),否则 O(n) |
| 中间插入/删除 | O(n),搬移后续元素 | 找到位置后 O(1) 改指针,但找位置 O(n) |
| 额外空间 | 小,基本只存数据 | 每个节点多存指针,有内存开销 |
| 缓存友好性 | 好,连续访问 | 差,节点分散 |
| 扩容 | 动态数组需扩容复制 | 不需要整体扩容,按节点申请 |
| 随机访问能力 | 强 | 弱,只能顺序遍历 |
数组胜在随机访问和缓存友好,适合读多、下标访问多、遍历多的场景。
链表胜在已知位置时插入删除快,适合频繁在中间插入删除、不需要随机访问的场景
数组的随机访问是 O(1)
- 因为数组元素在内存中连续存放,且每个元素大小固定。知道首地址和下标后,可以直接算出目标元素地址
链表为什么查询是 O(n)
- 链表节点在内存中不连续,每个节点只保存数据和指向下一个节点的指针。要访问第
i 个节点,必须从
head开始,沿着next指针走 i 步
为什么数组对 CPU 缓存更友好
- CPU 访问内存时不是一次只读一个字节,而是按缓存行读取,常见缓存行大小是 64 字节。数组元素连续存放,访问一个元素时,相邻元素也会被一起加载到缓存中。程序访问了某个内存位置,很可能很快访问它附近的位置。
- 链表节点是分散分配的,逻辑上相邻的节点在内存中可能相隔很远
二叉树有哪些遍历方式?BST、AVL、红黑树、B+ 树有什么区别?
二叉树遍历分为两大类:
DFS
前序遍历:根 → 左 → 右。一般用于复制树、序列化、打印目录结构
1
2
3
4
5
6def preorder(root):
if not root:
return
print(root.val)
preorder(root.left)
preorder(root.right)中序遍历:左 → 根 → 右。BST 中序能得到有序序列(对于 BST,中序遍历结果一定升序)
1
2
3
4
5
6def inorder(root):
if not root:
return
inorder(root.left)
print(root.val)
inorder(root.right)后序遍历:左 → 右 → 根。一般是表达式求值和计算子树
1
2
3
4
5
6def postorder(root):
if not root:
return
postorder(root.left)
postorder(root.right)
print(root.val)
BFS
层序遍历:按层从上到下、从左到右访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17from collections import deque
def levelorder(root):
if not root:
return []
res, q = [], deque([root])
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(level)
return res
BST 二叉搜索树
性质:
- 左子树所有节点值 < 根节点值
- 右子树所有节点值 > 根节点值
- 左右子树也都是 BST
优点:查找、插入、删除平均 O(logn)。
缺点:不保证平衡。升序插入会退化成链表,查找为 O(n)
AVL 平衡树
- 任意节点左右子树高度差(平衡因子)绝对值 ≤ 1。
- 插入/删除后通过旋转恢复平衡。
- 查找、插入、删除最坏都是 O(logn)。
平衡严格,树高更低,查找快;但插入删除旋转更频繁,维护成本高。
红黑树
红黑树是近似平衡的二叉搜索树,通过颜色约束保证最长路径不超过最短路径的 2 倍:
- 每个节点是红或黑。
- 根是黑。
- 叶子(NIL)是黑。
- 红节点的子节点必须是黑,不能红红相连。
- 从任一节点到其所有叶子路径上的黑节点数相同(黑高相同)。
结果:树高最多 \(2log_2 (n+1)\),查找、插入、删除最坏 O(logn)。
平衡条件比 AVL
松,插入删除旋转更少,综合性能好。Java
TreeMap、C++ std::map、Linux
内核等常用红黑树。
B+树
B+ 树是多路平衡搜索树,不是二叉树:
- 每个节点可存多个 key 和多个子节点。
- 只有叶子节点存实际数据(或数据指针),内部节点只存索引 key。
- 所有叶子节点用链表相连,支持范围查询。
- 树高低,磁盘 I/O 少。
主要用于数据库索引和文件系统,如 MySQL InnoDB 的聚簇索引。
AVL 树和红黑树怎么保持平衡?
平衡树:平衡因子 + 旋转
平衡因子 BF = 左子树高度 − 右子树高度。
AVL 要求每个节点 BF∈{−1,0,1}。插入/删除后,从修改点向上更新高度,发现某节点失衡就旋转。
红黑树:靠颜色约束 + 旋转 + 变色
红黑树不直接要求高度平衡,而是通过 5 条颜色规则保证最长路径 ≤ 2 × 最短路径。
插入时新节点先染红,然后修复:
- 叔叔是红:父和叔变黑,祖父变红,继续向上检查。
- 叔叔是黑:根据 LL/LR/RL/RR 做旋转 + 变色。
删除更复杂,需要处理“双黑”情况,通过兄弟节点颜色和侄子颜色决定旋转和变色。
红黑树特点:近似平衡,插入删除旋转次数少(插入最多 2 次旋转,删除最多 3 次),综合性能好。
B 树和 B+ 树都是多路平衡搜索树,面向磁盘/数据库设计,核心目标是降低树高、减少磁盘 I/O。
B 树
- 每个节点既存 key,也可能存数据。
- 内部节点和叶子节点都存数据。
- 查找可能在内部节点就命中。
- 所有叶子节点在同一层。
B+ 树
- 内部节点只存索引 key,不存数据。所有数据都在叶子节点。
- 叶子节点之间用链表相连。
- 查找必须走到叶子节点。
- 支持高效范围查询。
哈希表是怎么实现的?哈希冲突和扩容怎么处理?
哈希表的核心是用空间换时间:通过哈希函数把键映射到数组下标,实现平均 O(1)O(1) 的查找、插入和删除。
哈希表的底层通常是一个数组。存入一个键值对时,先用哈希函数计算键的哈希值,再通过取模或位运算映射到数组的某个下标位置。一个好的哈希函数应满足两点:计算简单且分布均匀。
为什么容量通常取 2 的幂?
位运算替代取模,当数组长度
length是 2 的幂时,hash % length等价于hash & (length - 1),而位运算比取模快得多。同时,length - 1的二进制全是 1,能保证哈希值的低位都参与运算,使下标分布更均匀。
理想情况下,每个键都能落到不同的位置,查找时直接算出下标就能访问,这是 O(1)的来源。但不同的键可能算出相同的下标,这就是哈希冲突,需要额外的策略来处理。
- 拉链法:数组的每个位置挂一个链表(或红黑树)。冲突的元素追加到同一个位置的链表中。
- 优点:实现简单,对负载因子不敏感,删除操作方便。
- 缺点:有指针开销,缓
- 存不友好;冲突严重时链表变长,查询退化为O(n)
- 适合元素数量不可预测、频繁插入删除的场景。Java
HashMap使用的是拉链法。
- 开放寻址法:所有元素都存在数组里。冲突时,按某种探测序列(如线性探测、二次探测)寻找下一个空槽。
- 优点:无指针,缓存友好,空间利用率高。
- 缺点:删除麻烦(需要标记墓碑),容易产生“聚集”现象,性能对负载因子非常敏感。
- 适合内存紧凑、缓存敏感的场景,无需额外指针。
负载因子是哈希表装满程度的度量,负载因子 = 元素数量 / 数组容量。它决定了何时扩容。
堆是什么?Top K 问题有哪几种解法?堆排序的过程是什么?数据流中位数怎么用两个堆维护?
堆是一棵完全二叉树,通常用数组存储,满足堆序性质:
- 大顶堆:每个父节点 ≥ 子节点,堆顶是最大值,堆下的所有人比堆顶小
- 小顶堆:每个父节点 ≤ 子节点,堆顶是最小值,堆下的所有人比堆顶大
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 插入元素 | O(logn)O(logn) | 放到末尾,向上浮 |
| 删除堆顶 | O(logn)O(logn) | 末尾元素换到堆顶,向下沉 |
| 取堆顶 | O(1)O(1) | 直接访问数组首元素 |
| 建堆 | O(n)O(n) | 从最后一个非叶子节点向前下沉,不是 O(nlogn)O(nlogn) |
| 查找任意元素 | O(n)O(n) | 堆无全局有序性 |
| 堆排序 | O(nlogn)O(nlogn) | 建堆 O(n)O(n) + nn 次删除堆顶 |
完全二叉树用数组存的好处是父子下标可直接计算(0 下标):
- 父节点
i的左孩子:2i + 1 - 父节点
i的右孩子:2i + 2 - 孩子
i的父节点:(i - 1) // 2
堆只保证父子之间的大小关系,所以堆一般只用于快速取最值
Top K 指从 n 个元素中找出最大(或最小)的 K 个元素。这里以求最大 K 个为例子
维护一个大小为 K 的小顶堆,堆顶是这 K 个元素中最小的,也就是当前第 K 大的候选。遍历时:
- 遍历元素,堆未满就入堆;
- 堆满后,若当前元素大于堆顶,弹出堆顶,当前元素入堆;
- 遍历结束,堆中就是最大的 K 个元素。
时间复杂度 O(nlogK),空间 O(K)。适合 n 很大、K 较小的场景。
当数据量远大于内存时,不能一次性建堆。常用分治 + 堆:
- 将大文件按哈希值分成 M 个小文件,保证相同元素落到同一文件。每个小文件大小可放入内存。
- 对每个小文件用大小为 K 的小顶堆求 Top K,得到 M×K 个候选
- 对所有候选再用一个大小为 K 的小顶堆求全局 Top K。
那么,数据流中位数怎么用两个堆维护
数据流不断到来,要求随时能取中位数。用一个大顶堆 + 一个小顶堆:
- 大顶堆存较小的一半元素,堆顶是这一半的最大值。
- 小顶堆存较大的一半元素,堆顶是这一半的最小值。
维护规则:
- 新元素先入大顶堆或按大小分配
- 保持两个堆大小平衡:大顶堆大小等于小顶堆大小,或大顶堆比小顶堆多 1。
- 保持顺序:大顶堆堆顶 ≤ 小顶堆堆顶。若不满足,交换堆顶。
取中位数:
- 两堆大小相等:中位数 = (大顶堆顶 + 小顶堆顶) / 2。
- 大顶堆多 1:中位数 = 大顶堆顶。
堆排序
建堆
从最后一个非叶子节点开始,依次向下调整(下沉),把数组调整成大顶堆。最后一个非叶子节点下标:
n//2 - 1。排序
重复以下过程:
- 将堆顶(当前最大值)与堆末尾元素交换;
- 堆大小减 1;
- 对新堆顶做下沉调整,恢复大顶堆。
这样最大值依次被放到数组末尾,最终得到升序数组。
1 | def heapify(a, n, i): |
常见排序算法有哪些,分别讲解一下它们。这些排序算法该怎么选?
常见的排序算法主要分为比较类排序和非比较类排序两大类。
比较类排序
- 冒泡排序:反复走访数列,比较相邻元素并交换。
- 从列表的第一个元素开始,比较相邻的两个元素。如果前一个元素比后一个元素大,则交换它们的位置。对列表中的每一对相邻元素重复上述步骤,直到列表的末尾。
- 过程演示

- 时间复杂度,O(n^2);空间复杂度:原地O(1)
- 插入排序:将元素逐个插入到已排序序列的合适位置。对小规模或基本有序的数据非常高效,常作为高级排序算法的子过程。
- 将列表分为已排序部分和未排序部分。初始时,已排序部分只包含第一个元素,未排序部分包含剩余元素。从未排序部分中取出第一个元素。将该元素与已排序部分的元素从后向前依次比较,找到合适的位置插入。
- 过程演示

- 选择排序:每次从未排序部分选出最小(或最大)元素放到已排序末尾。交换次数少,但比较次数固定。
- 将列表分为已排序部分和未排序部分。初始时,已排序部分为空,未排序部分为整个列表。然后在未排序部分中查找最小的元素。将找到的最小元素与未排序部分的第一个元素交换位置。将未排序部分的起始位置向后移动一位,扩大已排序部分的范围。重复上述步骤,直到未排序部分为空,列表完全有序。
- 过程演示

- 时间复杂度,O(n^2);空间复杂度:原地O(1)
- 希尔排序:插入排序的改进版,通过增量分组让元素大步移动,逐步缩小增量。效率取决于增量序列的选择。
- 选择一个增量序列,用于将列表分成若干子列表。常见的增量序列有希尔增量(
n/2, n/4, ..., 1)等。按照增量序列将列表分成若干子列表,对每个子列表进行插入排序。逐步缩小增量,重复上述分组和排序过程,直到增量为 1。当增量为 1 时,对整个列表进行一次插入排序,完成排序。 - 过程演示

- 时间复杂度,O(n log n) 到O(n^2) 之间,不稳定;空间复杂度:原地O(1)
- 选择一个增量序列,用于将列表分成若干子列表。常见的增量序列有希尔增量(
- 归并排序:分治法,将数组递归分成两半分别排序再合并。稳定,最坏也是
O(nlogn),但需要 O(n) 额外空间。
- 将待排序的数组分成两个子数组,每个子数组包含大约一半的元素。递归地对每个子数组进行排序。然后将两个已排序的子数组合并成一个有序的数组。通过不断地分解和合并,最终整个数组将被排序。
- 过程演示

- 时间复杂度:O(nlogn);空间复杂度O(n);
- 快速排序:分治法,选基准(pivot)分区,递归排序。平均性能极佳,原地排序(递归栈
O(logn)),但不稳定,最坏可退化到 O(n^2)。
- 从列表中选择一个元素作为基准;将列表重新排列,使得所有小于基准元素的元素都在基准的左侧,所有大于基准元素的元素都在基准的右侧,这样基准元素的位置就被确定。然后,对基准元素左侧和右侧的子列表分别递归地进行快速排序。
- 过程演示

- 时间复杂度:O(nlogn);空间复杂度O(n);
- 堆排序:利用堆结构,反复取出堆顶。原地且最坏
O(nlogn),但不稳定,且常数因子通常比快排大,缓存不友好。
- 创建一个堆,把堆首和堆尾互换,(大顶堆堆顶最大,用于升序,小顶堆对丁最小,用于降序),把堆的尺寸缩小 1,然后调整堆,然后循环,直到堆的尺寸为 1。
- 过程演示

- 时间复杂度:O(nlogn);空间复杂度O(1);
非比较类排序:不比较元素,利用数据特性
- 计数排序:统计每个元素出现次数,直接计算位置。线性时间,但要求数据是范围有限的整数。
- 遍历待排序的列表,统计每个元素出现的次数,存储在一个计数数组中。遍历待排序的列表,根据计数数组中的位置信息,将元素放到正确的位置。
- 过程演示

- 时间复杂度:O(n + k),其中 n 是列表长度,k 是数据的范围大小。
- 空间复杂度:O(n + k),需要额外的计数数组和结果数组
- 桶排序:将数据分到有限数量的桶里,每个桶单独排序(可用插入排序)。适合数据均匀分布。
- 根据数据的范围和分布,创建若干个桶。遍历待排序的列表,将每个元素分配到对应的桶中。对每个桶中的元素进行排序。然后将所有桶中的元素按顺序合并,得到最终排序结果。
- 过程演示

- 时间复杂度:O(n + k *mlogm),其中 n 是列表长度,k 是桶的数量,m 是每个桶的平均元素数量。
- 空间复杂度:O(n + k),需要额外的存储空间来存放桶和排序后的结果。
- 基数排序:按位从低到高依次排序(通常用计数排序作为子过程)。稳定,适合位数不多的整数或字符串。
- 找到列表中最大数字的位数,确定需要排序的轮数。从最低位开始,依次对每一位进行排序。每一轮排序后,更新列表的顺序,直到所有位数排序完成。
- 过程演示

- 时间复杂度:O(n * k)。其中 k 是最大数字的位数。
- 空间复杂度:O(n + k),需要额外的存储空间来存放计数数组和输出数组
最后这是十大经典排序算法的统计
动态规划的核心思想是什么?和递归、贪心有什么区别?
动态规划(DP)的核心是:把大问题拆成相互重叠的子问题,先求解子问题并保存结果,避免重复计算,最终组合出原问题的解。
它通常需要满足两个条件:
- 最优子结构:原问题的最优解可以由子问题的最优解构造出来。
- 重叠子问题:递归求解时会反复遇到相同的子问题。
而 DP 问题的要求是具有最优子结构和无后效性
- 最优子结构:原问题的最优解包含子问题的最优解。例如背包和最短路
- 无后效性:一旦当前状态确定,后续决策只依赖当前状态,与到达该状态的路径无关。
DP 的典型步骤:
- 定义状态:
dp[i]或dp[i][j]表示什么。 - 写状态转移方程:当前状态如何由更小状态推出。
- 确定初始条件和边界。
- 确定遍历顺序:保证计算当前状态时依赖的状态已经算好。
- 返回最终答案。
DP 的本质是用空间换时间:把子问题答案存起来,把指数级递归降为多项式时间。
而递归是一种程序结构,代表函数调用自身。DP 是一种算法思想,利用子问题重叠性,保存子问题结果。而贪心是每一步都选当前看起来最优的,从局部最优推导出全局最优。
那么,DP 可以用递归实现,也可以用迭代实现
记忆化搜索
从原问题出发递归,遇到子问题先查表,算过就直接返回,没算过就计算并存入表中。
递推
先算最小子问题,再逐步推出大问题,通常用循环和数组。
linux常用命令,Docker基础 等基础运维相关
线上 CPU 飙高、内存泄漏、端口被占用,分别怎么排查?分别用什么命令?
CPU 飙高是指先用 top
确认整体负载和最高占用进程,再看是用户态(us)还是系统态(sy)偏高。
us 高通常是业务死循环或 GC;sy
高往往是频繁系统调用或锁竞争
核心命令:
- 定位进程:
top -c,按P按 CPU 排序。 - 定位线程(Java):
top -Hp <PID>找到高 CPU 的线程 ID,转成十六进制后。 - 历史趋势:
sar -u 2查看 CPU 历史或实时采样。
内存泄漏特征是内存总体随时间增长,对于 Java,观察 GC
状况jstat -gc <PID> 1000,生成堆转储并分析文件是有必要的。
端口被占用,核心命令:
- 查监听与进程:
ss -lntp | grep :<端口>(ss比netstat更快更现代)。 - 看所有状态:
ss -antp | grep :<端口>。 - 统计
TIME_WAIT:
ss -antp state time-wait | wc -l。
查看端口占用和连接状态,查日志常用哪些命令组合?
端口与连接状态:
- 看所有 TCP
监听:
ss -lntp(列出监听端口、进程名、PID)。 - 统计各状态连接数:
ss -ant | awk '{print $1}' | sort | uniq -c | sort -rn,看 ESTABLISHED、TIME_WAIT 各有多少。 - 看特定端口的
ESTABLISHED:
ss -antp state established '( sport = :8080 )'。
查日志的常用组合:
- 实时跟踪 +
关键词过滤:
tail -f /var/log/app.log | grep -i "error\|exception"。 - 按时间范围看系统服务日志:
journalctl -u <服务名> --since "2025-11-08 10:00:00" --until "2025-11-08 11:00:00"。 - 看本次启动的错误:
journalctl -b -p err - 压缩日志搜索:
zgrep "关键词" /var/log/app.log.*.gz
Linux 的文件权限怎么理解?软链接和硬链接有什么区别?
Docker 的镜像和容器是什么关系?容器和虚拟机有什么区别?
Docker 镜像是只读模板。它由一系列只读层叠加而成。这种分层设计让多个镜像可以共享相同的底层,节省存储空间。镜像本身不会运行,它只是模板。
容器是运行实例。当你执行 docker run
时,Docker
会在镜像的只读层之上,添加一个可写层。容器内所有对文件的修改都发生在这个可写层,而底下的镜像层始终保持只读。
虚拟机虚拟化的是硬件,容器虚拟化的是操作系统。
| 维度 | 容器 | 虚拟机 |
|---|---|---|
| 隔离层级 | 操作系统级(共享宿主机内核) | 硬件级(Hypervisor 虚拟出完整硬件) |
| Guest OS | 无,直接共享宿主机内核 | 每个 VM 都有独立的完整操作系统 |
| 启动速度 | 秒级甚至毫秒级 | 分钟级(需启动整个 OS) |
| 资源开销 | 小,接近原生进程 | 大,每个 VM 都要分配独立内存、CPU、磁盘 |
| 隔离性 | 较弱(内核共享,依赖 namespace/cgroup) | 强(硬件级隔离,内核独立) |
| 镜像/体积 | 小(MB 级,分层共享) | 大(GB 级,含完整 OS) |
容器没有自己的内核,系统调用直接打到宿主机内核上,所以启动快、开销小。
虚拟机通过 Hypervisor 模拟出完整的硬件环境,里面跑着独立的 OS 和独立内核,因此隔离更彻底、更安全,但代价是重量级。































