知识复习汇总

数据结构

哈希相关

简单介绍一下哈希表？
- 哈希表是一种根据键（Key）直接计算出存储位置的数据结构。能够通过哈希函数 (Hash Function) 把键映射到一个数组的索引上，从而实现快速的增删查改操作。
什么是解决哈希冲突？
- 哈希表用哈希函数把键映射到桶（数组槽位）。不同键可能落到同一桶，这就是冲突。冲突不可避免，核心是：怎么在冲突出现时，仍保持增删查改接近 O (1) 的开销。
如何解决哈希冲突？
- 1、拉链法：每个桶保存一个“容器”（通常是链表、动态小数组或小型平衡树）。冲突的元素都挂到该桶的容器里。
- 2、线性探测法：在哈希表中，如果某个键经过哈希函数映射得到的槽位（bucket）已被占用，就按照一个固定的探测序列去找下一个空槽。
- 3、二次探测法：发生冲突时，它不像线性探测法一样一步步顺序探测，而是按照二次方步长往外扩展。
- 4、双重散列：当发生冲突时，不是固定加 1（线性探测），也不是平方步长（二次探测），而是用“第二个哈希函数”决定探测步长。
如果用散列链表解决哈希冲突，那么查找时间复杂度会变成 $O(n)$ $O (n)$ ，如何下降时间复杂度？
- 1、控制负载因子：让期望复杂度回到 $O(1)$ ，负载因子 α = 元素数/桶数，当 α 逼近设定阈值的时候就扩容➕重新哈希
- 2、优化哈希函数：降低冲突几率
- 3、桶内结构升级：把链表换成平衡树

排序相关

稳定排序和不稳定排序
- 如果一个排序算法在对一组数据进行排序时，相等的元素在排序后仍然保持它们原来的相对顺序，那么这种算法就是稳定的。
- 若相等的元素在排序后相对顺序可能发生变化，这种算法就是不稳定的。
稳定排序算法

稳定排序算法

不稳定排序算法：

不稳定排序算法

快排为什么不稳定？
- 快速排序的主要过程是：
  1. 选择一个基准（pivot）；
  2. 将数组分为三部分：
    - 左边放比基准小的元素；
    - 中间放和基准相等的元素；
    - 右边放比基准大的元素；
  3. 递归地对两部分进行排序。
- 快速排序的不稳定性来源于——“交换操作”可能跨越相等元素之间的原始相对顺序。

语言语法

Golang

GMP 相关

当一个 goroutine 进入系统调用被阻塞，底层线程与 p 如何解绑？
- 在系统调用前，首先该线程 m 的 g0 会保存当前 g 的执行环境
- 然后将 g 和 p 的状态更新为 syscall；
- 解除 p 和当前 m 之间的绑定，因为 m 即将进入系统调用而导致短暂不可用；
- 最后将 p 添加到当前 m 的 oldP 容器当中，后续 m 恢复后，会优先寻找旧的 p 重新建立绑定关系。
当 m 完成了内核态的系统调用之后，如何寻找 p 开始重新运作？
- 方法执行之初，此时的执行权是普通 g 倘若此前设置的 oldp 仍然可用，则重新和 oldP 绑定，将当前 g 重新置为 _Grunning 状态，然后开始执行后续的用户函数；
- old 绑定失败，则调用 mcall 方法切换到 m 的 g0，并执行 exitsyscall0 方法；
- 将 g 由系统调用状态切换为可运行态（_Grunnable），并解绑 g 和 m 的关系；
- 从全局 p 队列获取可用的 p，如果获取到了，则执行 g；
- 如若无 p 可用，则将 g 添加到全局队列，当前 m 陷入沉睡，直到被唤醒后才会继续发起调度。
讲讲 Go 协程：
- 与线程存在映射关系，为 M:N，M 可以大于 N；
- 创建、销毁、调度在用户态完成，对内核透明，足够轻便；
- 可利用多个线程，实现并行；
- 通过调度器 p 的斡旋，实现和线程间的动态绑定和灵活调度；
- 栈空间大小可动态扩缩，因地制宜。
讲讲 GMP 模型中 p 的作用，一定需要 p 吗？
- p 即 processor，是 golang 中协程的调度器；
- p 是 gmp 的中枢，借由 p 承上启下，实现 g 和 m 之间的动态有机结合；
- 对 g 而言，p 是其 cpu，g 只有被 p 调度，才得以执行；
- 对 m 而言，p 是其执行代理，为其提供必要信息的同时（可执行的 g、内存分配情况等），并隐藏了繁杂的调度细节；
- p 的数量决定了 g 最大并行数量，可由用户通过 GOMAXPROCS 进行设定（超过 CPU 核数时无意义）。
- 在目前的 GMP 模型下，p 是必须的，当去掉 p 让 m 从全局队列中直接取 g 进行执行的话会导致无法高效控制并行度，导致运行效率大幅下降。

slice 相关

说一下 slice 的扩容机制
- 当需要 append 的长度在原来 slice 的 cap 容量以内则不需要扩容；
- 倘若预期的新容量超过老容量的两倍，则直接采用预期的新容量；
- 倘若原容量小于 256，则扩容后新容量为原容量的两倍；
- 倘若老容量已经大于等于 256，则在老容量的基础上扩容 1/4 的比例并且累加上 192 的数值，持续这样处理，直到得到的新容量已经大于等于预期的新容量为止。

channel 相关

介绍一下 channel
- channel 是 go 语言一种内置的同步原语，可以在多个并发执行的 goroutine 之间通过通信来共享数据，而不需要显式使用锁。
- channel 分为有缓冲管道和无缓冲管道：
  - 其中无缓冲管道的发送和接收必须同时存在，发送操作会阻塞直到有接收者，适合用于同步通信。
  - 而有缓冲管道可以存储一定数量的元素，当缓冲区未满时，发送不会阻塞；当缓冲区为空时，接收会阻塞；更适合异步任务队列。
- 管道是并发安全的，内部使用 锁和环形队列 实现；无需额外的 mutex 就能保证安全通信。
- 管道的关闭只能由发送方关闭，接收方可以检测通道是否关闭，但发送方往关闭的管道发送数据会触发 panic。
select 是怎么和 channel 配合的？
- select 是 Go 专门用于同时等待多个 channel 操作的控制结构。它的作用类似于多路复用器，让 goroutine 能够「同时监听多个 channel 」，只要其中任意一个可以通信（发送或接收），就立即执行对应的分支。
- select 的行为可以分为三种情况：
  - 至少有一个 case 可执行，随机选择一个执行；
  - 所有通道都阻塞，阻塞等待直到某个通道可用；
  - 有 default 且所有通道都阻塞，立即执行 default（非阻塞）。

Contex 相关

介绍一下 contex 接口中的四个方法
- 1. Deadline() (deadline time.Time, ok bool)
  - 作用：返回 context 的截止时间（Deadline），即何时会自动取消。用于限制某个操作的最长执行时间，比如 HTTP 请求或数据库查询。
  - 返回值：
    - deadline: 截止时间；
    - ok: 如果没有设置截止时间，返回 false。
- 1. Done() <-chan struct{}
  - 作用：返回一个只读 channel，当 context 被取消或超时时，该 channel 会被关闭。监听 ctx.Done() 的 goroutine 会在取消信号到来时被唤醒，用于清理、退出等。
  - 特性：
    - 通常用来检测“是否该退出”；
    - 一旦 Done() 关闭，表示应该立即结束当前操作。
- 1. Err() error
  - 作用：返回 context 结束的原因。Err() 常用于在退出前打印或处理取消原因。
  - 可能的返回值：
    - nil：context 仍然有效；
    - context.Canceled：被手动取消；
    - context.DeadlineExceeded：超过截止时间。
- 1. Value(key any) any
  - 作用：在 context 中存取键值对数据；传递请求范围内的数据（例如用户ID、请求ID、追踪信息）；
  - 注意事项：
    - 不建议滥用 context 存放大量数据；
    - 只应用于跨 API、跨 goroutine 传递请求级别元信息。

Gin 框架

介绍一下 Gin 框架的路由注册
- Gin 框架的路由注册本质是通过内部维护一个压缩前缀路由树来实现快速匹配。
- 每个请求方法（如 GET、POST）都有一棵独立的路由树。
  - 例如：
    - GET 请求 → r.trees["GET"]
    - POST 请求 → r.trees["POST"]
  - 注册时会将路径分解为节点（node），构建成前缀树，以便快速查找。
- 内部逻辑：
  1. 拼接路径（加上分组前缀）；
  2. 调用 engine.addRoute(method, path, handlers)；
  3. 在对应方法的路由树中插入节点。
- 查找请求时，Gin 按照路径层级匹配节点（包括参数与通配符），找到匹配的 handler 列表。

内存模型

介绍一下 Go 语言的内存模型与分配机制
- 内存分配机制的整个体系由三层组成：
  - MCache：每个 P（Processor）的本地缓存，访问时无锁，快速分配，用于管理小对象；
  - MCentral：每种对象大小规格（全局共划分为 68 种）对应的缓存，锁的粒度也仅限于同一种规格以内，从 8 B 到 32 KB 不等。这样可以减少外部碎片化。
  - MHeap：全局的内存起源，访问要加全局锁。
- page：
  - 是 Go 中最小的内存分配单元是 8 KB（一个 page）；
  - MHeap 以页为单位管理内存；
  - 页可以被划分为不同大小的块（span）。
- Span（内存块组）：
  - Span 是多个连续页的集合；
  - 每个 Span 负责管理特定大小（size class）的对象；
  - Span 内部被切割成相同大小的对象块（object）。

GC 相关

介绍一下 GC 流程
- Golang 中的垃圾回收采用并发三色标记法+混合写屏障机制。
  - 三色标记法的流程：
    - 对象分为三种颜色标记：黑、灰、白
    - 黑对象代表，对象自身存活，且其指向对象都已标记完成
    - 灰对象代表，对象自身存活，但其指向对象还未标记完成
    - 白对象代表，对象尙未被标记到，可能是垃圾对象
    - 标记开始前，将根对象（全局对象、栈上局部变量等）置黑，将其所指向的对象置灰
    - 标记规则是，从灰对象出发，将其所指向的对象都置灰. 所有指向对象都置灰后，当前灰对象置黑
    - 标记结束后，白色对象就是不可达的垃圾对象，需要进行清扫
  - 混合写屏障机制：
    - 插入写屏障（Dijkstra）：目标是实现强三色不变式，保证当一个黑色对象指向一个白色对象前，会先触发屏障将白色对象置为灰色，再建立引用
    - 删除写屏障（Yuasa barrier）：目标是实现弱三色不变式，保证当一个白色对象即将被上游删除引用前，会触发屏障将其置灰，之后再删除上游指向其的引用

插入写屏障

删除写屏障

sync.Pool

介绍一下 sync.Pool
- sync.Pool 是 golang 标准库下并发安全的对象池，适合用于有大量对象资源会存在被反复构造和回收的场景，可缓存资源进行复用，以提高性能并减轻 GC 压力。
- sync.Pool 缓存的是 any 类型的对象（通常是指针类型），由程序员决定具体类型。
- sync.Pool 结构体的源码：

type Pool struct {
    noCopy noCopy

    local     unsafe.Pointer // local fixed-size per-P pool, actual type is [P]poolLocal
    localSize uintptr        // size of the local array

    victim     unsafe.Pointer // local from previous cycle
    victimSize uintptr        // size of victims array

    // New optionally specifies a function to generate
    // a value when Get would otherwise return nil.
    // It may not be changed concurrently with calls to Get.
    New func()

noCopy 防拷贝标志；
local 类型为 [P]poolLocal 的数组，数组容量 P 为 goroutine 处理器 P 的个数；
victim 为经过一轮 gc 回收，暂存的上一轮 local；
New 为用户指定的工厂函数，当 Pool 内存量元素不足时，会调用该函数构造新的元素。

type poolLocal struct {
    poolLocalInternal
}

// Local per-P Pool appendix.
type poolLocalInternal struct {
    private any       // Can be used only by the respective P.
    shared  poolChain // Local P can pushHead/popHead; any P can popTail.
}

poolLocal 为 Pool 中对应于某个 P 的缓存数据；
poolLocalInternal.private：对应于某个 P 的私有元素，操作时无需加锁；
poolLocalInternal.shared : 某个 P 下的共享元素链表，由于各 P 都有可能访问，因此需要加锁.

defer

介绍一下 defer 以及执行顺序
- defer 主要用在函数或者方法上面，作用是用于函数和方法的延迟调用。
- defer 的执行顺序和栈一样，是先调用，后执行。
- defer 有两个主要的实际用处：
  - 用于资源回收，根据其延迟调用的机制，可以优雅地处理资源回收问题。
  - 可以配合 recover() 一起处理 panic 。
- defer 和 return 的处理顺序：
  - 先设置返回值
  - 执行 defer 语句
  - 将结果返回
- 注意下面这个例子输出是 2 ：

package main

import "fmt"

func main() {
   res := deferRun()
   fmt.Println(res)
}

func deferRun() (res int) {
  num := 1
  
  defer func() {
    res++
  }()
  
  return num
}

计网相关

HTTP 篇

HTTPS 比 HTTP 安全在哪？证书在其中起到什么作用，如何验证证书？
- HTTP 是明文传输的，传输的数据未经过加密，而 HTTPS 在 HTTP 基础上引入了 SSL/TLS 协议，提供了三大安全能力（加密、数据完整性、身份验证）；
- 证书由权威的 CA（证书颁发机构）签发，里面包含以下关键内容（服务器的公钥、服务器的域名信息、证书有效期、CA 的数字签名）
- 客户端拿到服务器的证书，沿着签发链（服务器证书 → 中级 CA → 根 CA）逐层验证签名是否有效。
- 检查证书中记录的域名是否与访问的网站一致。
- 确认证书是否在有效期内。
- 通过 CRL（证书吊销列表）或 OCSP 协议验证证书是否已被吊销。
- 如果以上都通过，浏览器才会信任这个证书，并继续进行 TLS 握手，协商出对称密钥来加密后续通信。
对称密钥和非对称的区别？
- 对称密钥：
  - 加密和解密使用同一把密钥。通信双方需要共享一把密钥。
  - 假如有 N 个用户相互通信，就需要 $\frac{N(N-1)}{2}$ 把不同的密钥，管理起来比较复杂。
  - 加密解密速度快，适合处理大量数据。
  - 缺点：如何安全地分发和保存密钥是个难题，如果密钥泄露，通信内容也就不安全了。
- 非对称加密：
  - 加密和解密使用一对密钥：公钥 (Public Key) 和私钥 (Private Key)。公钥可以公开，用来加密数据。私钥必须保密，用来解密数据。
  - 每个人只需要维护自己的一对密钥（公钥和私钥）。公钥可以对外公开，私钥由自己保管，密钥管理相对简单。
  - 加密解密速度慢，性能消耗大，但安全性更高，因为私钥不需要传输。
  - 通常用来做：
    - 数字签名（保证身份和不可否认性）
    - 密钥交换（先用非对称加密交换对称密钥，再用对称密钥加密数据）

TLS 的四次握手流程
- 1、客户端发起请求：告诉服务器自己支持的 TLS 版本、加密算法套件、随机数 (用于生产后续的会话密钥，也就是对称密钥)。
- 2、服务器回应：选择使用的 TLS 版本和加密算法、发送自己的随机数（也是用于生产后续的会话密钥，也就是对称密钥）、发送服务器证书（包含服务器公钥，用于身份认证）。
- 3、客户端再次发起请求做会话密钥协商：客户端生成一个“预主密钥” (Pre-Master Secret)，用服务器的公钥加密后发给服务器。同时发送加密算法改变通知，表示后续信息都用会话密钥来加密。
- 4、服务端通过“预主密钥” (Pre-Master Secret)计算出会话密钥后向客户端发信息：发送加密算法改变的通知，表示后续信息都用会话密钥来加密。

DNS 相关

在浏览器输入栏中输入 baidu.com 发生了什么？
- 为了找到 baidu.com 对应的服务器 IP 地址，浏览器会按层次查找缓存：
  1. 浏览器 DNS 缓存
    - 若近期访问过，会直接命中缓存。
  2. 操作系统缓存（OS Cache）
    - 否则，向操作系统查询本地缓存（例如 Windows 的 DNS Client Service）。
  3. 本地 hosts 文件
    - 检查系统文件 /etc/hosts（Linux/Mac）或 C:\Windows\System32\drivers\etc\hosts 是否有静态映射。
  4. 本地 DNS 服务器（ISP 或路由器）
    - 若都没有命中，系统会向配置的 DNS 服务器（例如电信、Google DNS 8.8.8.8）发起 DNS 查询请求。
DNS 什么时候用递归查询，什么时候用迭代（反复）查询？
- 递归查询（客户端 → 本地 DNS 服务器），意思是：“帮我查出 baidu.com 的 IP 地址，不要让我再管后面的细节。”
- 迭代查询（本地 DNS → 其他上级 DNS 服务器），这些过程中，每一层上级 DNS 都不会代为继续查询，只告诉下一级地址。
DNS 根服务器会不会同时接收到大量并发查询请求？
- 是的：根服务器会接收到大量并发查询
- 为什么根服务器能扛住如此高并发？
  - 分布式部署（Anycast 技术），全球共有 超过 1000+ 台根服务器实例（通过 Anycast 技术部署在各地）。
  - 高缓存利用率，实际上，绝大多数 DNS 查询 根本不会真的到达根服务器，本地 DNS 服务器（ISP 或公司内部 DNS）会缓存查询结果； .com、.net 等 顶级域名服务器 也会被缓存；根域的权威信息（比如顶级域的 NS 记录）变化极少，TTL 时间长（通常为 48 小时甚至更长）。
  - 根区数据非常小且易处理；
百度是如何处理大量对 baidu.com 的并发请求的？
- 1. DNS 多层调度 + 全球加速：当你访问 baidu.com，其实并不止一个 IP。同一个域名对应多个服务器 IP；根据用户地理位置，返回距离最近的服务器地址；DNS 还会考虑各节点的负载情况、延迟、可用性。
- 1. CDN（内容分发网络）缓存静态资源：静态资源（图片、CSS、JS、搜索页面模板等）被分发到全国各地的边缘节点。页面中的图片、脚本等资源就近从 CDN 节点获取；只有动态内容（如搜索结果）才需回源请求百度主站。
- 1. 分布式缓存与异步队列、高可扩展的搜索索引集群、健壮的监控与容灾体系等方式应对大量并发请求。

加密相关

MD5 是可逆的还是不可逆的？
- MD5 是不可逆的，它是一种 单向哈希函数，可以轻松计算出某个输入的 MD5 值，但无法从一个 MD5 值反推出原始输入。

MySQL

MySQL 常用的存储引擎
- innodb、MyISAM

Redis

缓存击穿和缓存雪崩的概念，以及怎么解决？
- 缓存击穿是指缓存中某个热点数据过期了，此时有大量请求访问这个数据，导致无法从缓存中直接读取，会去访问数据库，此时数据库很容易被高并发请求击垮，称为缓存击穿。解决方法是不给热点数据设置过期缓存，由后台异步更新缓存。
- 缓存雪崩是指缓存中有大量数据在同一时间段过期了，此时有大量的用户请求无法访问到缓存中的数据，会去访问数据库，此时数据库很容易被高并发请求击垮，称为缓存雪崩。解决方法是均匀设置缓存的过期时间，不要让大量数据在同一时间段过期。或者不给热点数据设置过期缓存，由后台异步更新缓存。
缓存一致性怎么解决？
- 采用旁路缓存，读的话先读缓存，缓存命中则返回。缓存未命中，则读数据库，然后将数据写入缓存，再返回。然后写操作：先更新数据库，再删除缓存。

面经

#面经

知识复习汇总

http://example.com/2025/02/20/Interview/

作者

Mr.CHUI

发布于

2025年2月20日

许可协议

左程云、代码随想录算法学习（一）上一篇

计量方法与误差理论下一篇