十七、算法与计算机基础（6 题）

17.1 ★进程、线程、协程的区别是什么？IO 多路复用（select/poll/epoll）的原理是什么？死锁的四个必要条件是什么？

📖 点击查看答案

进程、线程、协程对比：

维度	进程	线程	协程
资源	独立地址空间	共享进程内存	共享线程内存
调度	OS 调度	OS 调度	用户态调度
切换成本	高（切页表）	中（切寄存器/栈）	低（仅切栈）
通信	IPC（管道/消息队列/共享内存）	共享内存	共享内存
并发数	几十-几百	几百-几千	几万-几十万
典型	应用程序	Java Thread	Go goroutine、Kotlin 协程

IO 多路复用原理：

select：

int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);
// 原理：
// 1. 将 fd 集合从用户态拷贝到内核态
// 2. 内核遍历所有 fd 检查就绪
// 3. 返回就绪 fd 数量，用户态再次遍历找出就绪 fd
// 缺点：
// - 1024 个 fd 限制（FD_SETSIZE）
// - 每次拷贝 fd 集合开销大
// - O(n) 遍历效率低

poll：

struct pollfd { int fd; short events; short revents; };
int poll(struct pollfd *fds, nfds_t nfds, int timeout);
// 改进：用链表替代位图，无 1024 限制
// 缺点：仍需拷贝、O(n) 遍历

epoll：

int epoll_create(int size);
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);
// 原理：
// 1. epoll_create 创建 epoll 实例（红黑树 + 就绪链表）
// 2. epoll_ctl 注册 fd（加入红黑树），内核回调将就绪 fd 加入就绪链表
// 3. epoll_wait 只返回就绪链表中的 fd，O(1) 效率
// 优势：
// - 无 fd 数量限制
// - 无需每次拷贝 fd 集合
// - O(1) 获取就绪 fd（回调机制）
// - 支持边缘触发（ET）和水平触发（LT）

// LT（水平触发）：只要 fd 有数据可读，一直通知（默认）
// ET（边缘触发）：只在 fd 状态变化时通知一次，需一次性读完

epoll vs select/poll：

维度	select	poll	epoll
fd 上限	1024	无限制	无限制
fd 拷贝	每次全量	每次全量	仅注册时一次
就绪检测	O(n) 遍历	O(n) 遍历	O(1) 回调
触发模式	LT	LT	LT/ET
适用	连接数少	连接数少	高并发（C10K+）

死锁四个必要条件：

互斥条件：资源同一时刻只能被一个进程占有
请求保持条件：进程持有资源并请求新资源，不释放已持有资源
不剥夺条件：资源不能被强制剥夺，只能主动释放
循环等待条件：存在进程-资源的循环等待链

java

// 经典死锁示例
// 线程1：持有 A，请求 B
synchronized (lockA) {
    synchronized (lockB) { /* ... */ }
}
// 线程2：持有 B，请求 A
synchronized (lockB) {
    synchronized (lockA) { /* ... */ }
}
// 四条件均满足：互斥(A/B互斥) + 请求保持(持有A请求B) + 不剥夺 + 循环等待

死锁预防（破坏条件）：

破坏请求保持：一次性申请所有资源
破坏循环等待：按顺序申请资源
破坏不剥夺：tryLock 超时释放

17.2 ★TCP 三次握手和四次挥手的过程是什么？`TIME_WAIT` 的作用是什么？为什么是三次握手而非两次？

📖 点击查看答案

三次握手（建立连接）：

客户端                    服务端
  |  SYN, seq=x             |
  |------------------------>|  服务端进入 SYN_RCVD
  |  SYN+ACK, seq=y, ack=x+1|
  |<------------------------|
  |  ACK, ack=y+1           |
  |------------------------>|  连接建立 ESTABLISHED

客户端发送 SYN（seq=x），进入 SYN_SENT
服务端回复 SYN+ACK（seq=y, ack=x+1），进入 SYN_RCVD
客户端发送 ACK（ack=y+1），双方进入 ESTABLISHED

四次挥手（断开连接）：

客户端                    服务端
  |  FIN, seq=u              |
  |------------------------>|  服务端进入 CLOSE_WAIT
  |  ACK, ack=u+1           |
  |<------------------------|
  |  (服务端处理剩余数据)     |
  |  FIN, seq=w              |
  |<------------------------|  服务端进入 LAST_ACK
  |  ACK, ack=w+1           |
  |------------------------>|  服务端 CLOSED
  |  (客户端 TIME_WAIT 2MSL) |
  |  客户端 CLOSED           |

主动方发送 FIN，进入 FIN_WAIT_1
被动方回复 ACK，进入 CLOSE_WAIT（此时可继续发送未发完的数据）
被动方数据发完后发送 FIN，进入 LAST_ACK
主动方回复 ACK，进入 TIME_WAIT，等待 2MSL 后 CLOSED

为什么三次握手而非两次？：

防止历史连接：旧的 SYN 到达服务端，服务端回复后若两次握手即建立连接，浪费资源
同步序列号：三次握手确保双方都能确认对方的接收能力
避免资源浪费：两次握手下，服务端收到 SYN 即分配资源，若 SYN 迟到会造成无效连接

// 两次握手的问题：
// 1. 客户端发送 SYN1（网络延迟）
// 2. 客户端超时，重发 SYN2
// 3. 服务端收到 SYN2，回复后建立连接，完成通信
// 4. SYN1 到达服务端，服务端又建立连接（但客户端不会响应）→ 浪费资源
// 三次握手：服务端回复 SYN+ACK 后，客户端发现 seq 不对，发 RST 终止

TIME_WAIT 的作用：

保证被动方正常关闭：
- 最后的 ACK 可能丢失，被动方会重发 FIN
- TIME_WAIT 状态可以重发 ACK，保证被动方进入 CLOSED
防止旧连接的报文干扰新连接：
- 等待 2MSL（最大报文生存时间），让旧连接的报文消失
- 避免新连接（相同四元组）收到旧连接的延迟报文

TIME_WAIT 过多的问题：

占用端口和内存
新连接无法复用四元组
解决：
- SO_REUSEADDR：允许复用 TIME_WAIT 端口
- tcp_tw_reuse=1：快速回收 TIME_WAIT
- 使用长连接减少挥手次数
- 主动关闭方放在服务端（让客户端承担 TIME_WAIT）

MSL（Maximum Segment Lifetime）：

报文最大生存时间（Linux 默认 30s）
2MSL = 60s，TIME_WAIT 默认持续 60s

17.3 ★HTTP/HTTPS 的区别是什么？HTTP 1.1、2.0、3.0 有什么演进？输入 URL 到页面显示的全过程是什么？

📖 点击查看答案

HTTP vs HTTPS：

维度	HTTP	HTTPS
端口	80	443
加密	明文传输	TLS/SSL 加密
证书	不需要	需要 CA 证书
性能	快	略慢（TLS 握手开销）
安全	可被窃听/篡改/伪造	防窃听/篡改/伪造

HTTPS 握手流程：

1. ClientHello：客户端发送支持的 TLS 版本、加密套件、随机数
2. ServerHello：服务端选择加密套件、返回随机数、证书
3. 客户端验证证书（CA 链、有效期、域名）
4. 客户端生成 pre-master secret，用服务端公钥加密发送
5. 双方根据随机数 + pre-master 生成会话密钥
6. 后续使用对称加密通信

HTTP 版本演进：

版本	特性	改进
HTTP/1.0	每次请求新建连接	-
HTTP/1.1	长连接（Keep-Alive）、管道化、Host 头	减少连接开销
HTTP/2.0	二进制分帧、多路复用、头部压缩（HPACK）、服务端推送	解决队头阻塞
HTTP/3.0	基于 QUIC（UDP）、0-RTT、连接迁移	解决 TCP 队头阻塞

bash

# HTTP/1.1 问题：
# - 文本协议，解析慢
# - 队头阻塞：一个请求慢影响后续
# - 头部冗余：每次发送完整头部

# HTTP/2.0 改进：
# - 二进制分帧：将数据拆成帧传输
# - 多路复用：一个 TCP 连接并发多个请求
# - 头部压缩：HPACK 算法
# - 服务端推送：主动推送资源

# HTTP/3.0 改进：
# - 基于 QUIC（UDP）：避免 TCP 队头阻塞
# - 0-RTT 握手：快速建立连接
# - 连接迁移：IP 变化不断连

输入 URL 到页面显示全过程：

1. DNS 解析：

浏览器缓存 → 系统缓存（hosts）→ 本地 DNS → 根 DNS → 顶级 DNS → 权威 DNS
递归查询 + 迭代查询

2. TCP 连接：

三次握手建立 TCP 连接
HTTPS 还需 TLS 握手

3. 发送 HTTP 请求：

构造请求行（GET /path HTTP/1.1）
请求头（Host、Cookie、User-Agent）
请求体（POST）

4. 服务器处理：

负载均衡 → 反向代理（Nginx）→ 应用服务器 → 数据库
生成响应（状态码、响应头、响应体）

5. 浏览器渲染：

解析 HTML → DOM 树
解析 CSS → CSSOM 树
DOM + CSSOM → 渲染树（Render Tree）
布局（Layout/Reflow）：计算元素位置
绘制（Paint/Repaint）：绘制像素

6. 加载子资源：

异步加载 JS/CSS/图片
JS 阻塞 DOM 解析（async/defer 优化）

URL → DNS 解析 → TCP 三次握手 → TLS 握手(HTTPS) → HTTP 请求 → 服务器处理
→ HTTP 响应 → TCP 四次挥手 → 浏览器解析渲染 → 页面显示

关键优化点：

DNS 预解析：<link rel="dns-prefetch" href="//cdn.example.com">
CDN 加速：静态资源就近访问
HTTP/2：多路复用减少连接数
缓存：强缓存（Cache-Control）、协商缓存（ETag/Last-Modified）
Gzip 压缩：减少传输体积
懒加载：图片/组件按需加载

17.4 ★Docker 与虚拟机的区别是什么？K8s 的核心组件有哪些？Pod 和 Service 是什么？

📖 点击查看答案

Docker vs 虚拟机：

维度	Docker 容器	虚拟机
隔离级别	进程级	硬件级
操作系统	共享宿主内核	独立内核
启动速度	秒级	分钟级
资源占用	MB 级	GB 级
隔离性	弱	强
性能	接近原生	有损耗
镜像大小	MB	GB

Docker 核心概念：

镜像（Image）：只读模板，分层存储
容器（Container）：镜像的运行实例
仓库（Registry）：镜像存储分发（Docker Hub）
Dockerfile：镜像构建脚本

K8s 核心组件：

控制平面（Master）：

API Server：统一入口，所有组件通过它通信
etcd：分布式 KV 存储，保存集群状态
Scheduler：Pod 调度器，决定 Pod 运行在哪个 Node
Controller Manager：控制器（Deployment/ReplicaSet/Node 等）
Cloud Controller Manager：云厂商对接

工作节点（Node）：

kubelet：节点代理，管理 Pod 生命周期
kube-proxy：网络代理，实现 Service 负载均衡
容器运行时：containerd / Docker / CRI-O

Pod：

K8s 最小调度单位
一个 Pod 可包含多个容器（共享网络、存储）
通常一个 Pod 一个业务容器 + sidecar 容器
生命周期：Pending → Running → Succeeded/Failed
每个 Pod 有唯一 IP，Pod 内容器共享 Pod IP

Service：

为一组 Pod 提供稳定的访问入口（Pod IP 会变）
通过 Label Selector 关联 Pod
类型：
- ClusterIP：集群内访问（默认）
- NodePort：暴露节点端口
- LoadBalancer：云厂商负载均衡
- ExternalName：CNAME 到外部域名
本质：kube-proxy 维护 iptables/ipvs 规则，负载均衡到后端 Pod

yaml

# Pod 示例
apiVersion: v1
kind: Pod
metadata:
  name: nginx
  labels:
    app: nginx
spec:
  containers:
  - name: nginx
    image: nginx:1.21
    ports:
    - containerPort: 80

# Service 示例
apiVersion: v1
kind: Service
metadata:
  name: nginx-service
spec:
  selector:
    app: nginx          # 关联 label app=nginx 的 Pod
  ports:
  - port: 80            # Service 端口
    targetPort: 80      # Pod 端口
  type: ClusterIP

其他核心概念：

Deployment：管理 Pod 副本集，支持滚动更新
ReplicaSet：保证 Pod 副本数
ConfigMap/Secret：配置/密钥管理
Ingress：七层路由（Nginx/Traefik）
Namespace：资源隔离
Volume/PV/PVC：存储卷

17.5 ★常用的设计模式有哪些？单例的 DCL（双重检查锁）为什么要加 `volatile`？工厂、策略、责任链模式的应用场景？

📖 点击查看答案

设计模式分类：

创建型：单例、工厂、建造者、原型
结构型：适配器、装饰器、代理、外观、组合
行为型：策略、责任链、观察者、模板方法、状态

单例 DCL 为什么要 volatile：

java

public class Singleton {
    private static volatile Singleton instance;  // 必须 volatile

    public static Singleton getInstance() {
        if (instance == null) {                  // 第一次检查（避免每次加锁）
            synchronized (Singleton.class) {
                if (instance == null) {          // 第二次检查
                    instance = new Singleton();  // 非原子操作！
                }
            }
        }
        return instance;
    }
}

原因：防止指令重排序导致返回未初始化的对象

instance = new Singleton() 实际分三步：

分配内存
初始化对象（调用构造方法）
将引用指向内存地址

JVM 可能将 2、3 重排序为 1→3→2，导致：

线程 A 执行到 3（引用已赋值但对象未初始化）
线程 B 第一次检查 instance != null，返回未初始化的对象 → NPE

volatile 禁止指令重排序（内存屏障），保证 2 在 3 之前完成。

替代方案（更推荐）：

java

// 静态内部类（懒加载 + 线程安全）
public class Singleton {
    private static class Holder {
        static final Singleton INSTANCE = new Singleton();
    }
    public static Singleton getInstance() {
        return Holder.INSTANCE;  // 类加载时初始化，JVM 保证线程安全
    }
}

// 枚举单例（最佳，防反射攻击）
public enum Singleton {
    INSTANCE;
}

工厂模式：

场景：根据参数创建不同对象，屏蔽创建细节
应用：Spring BeanFactory、日志框架 LoggerFactory

java

public interface Payment {
    void pay(double amount);
}
public class AlipayPayment implements Payment { /* ... */ }
public class WechatPayment implements Payment { /* ... */ }

public class PaymentFactory {
    public static Payment create(String type) {
        return switch (type) {
            case "alipay" -> new AlipayPayment();
            case "wechat" -> new WechatPayment();
            default -> throw new IllegalArgumentException("Unknown type");
        };
    }
}

策略模式：

场景：多种算法可互换，避免 if-else 过多
应用：折扣计算、支付方式选择

java

public interface DiscountStrategy {
    double discount(double price);
}
public class FullReductionDiscount implements DiscountStrategy { /* ... */ }
public class PercentageDiscount implements DiscountStrategy { /* ... */ }

public class OrderService {
    private DiscountStrategy strategy;
    public void setStrategy(DiscountStrategy strategy) {
        this.strategy = strategy;
    }
    public double calculate(double price) {
        return strategy.discount(price);
    }
}
// 配合 Spring：注入不同策略 Bean，按类型选择

责任链模式：

场景：请求经过多个处理器依次处理，可中断或传递
应用：过滤器（Filter）、拦截器、审批流、日志级别

java

public abstract class Handler {
    protected Handler next;
    public Handler setNext(Handler next) { this.next = next; return next; }
    public abstract void handle(Request req);
}

public class AuthHandler extends Handler {
    public void handle(Request req) {
        if (!authenticate(req)) throw new RuntimeException("未认证");
        if (next != null) next.handle(req);
    }
}
public class LogHandler extends Handler {
    public void handle(Request req) {
        log(req);
        if (next != null) next.handle(req);
    }
}

// 使用
Handler chain = new AuthHandler();
chain.setNext(new LogHandler()).setNext(new BusinessHandler());
chain.handle(request);

Spring 中的应用：

工厂：BeanFactory、FactoryBean
代理：AOP（JDK 动态代理 / CGLIB）
策略：Resource 接口（ClassPathResource/FileSystemResource）
责任链：HandlerInterceptor、Filter
模板方法：JdbcTemplate、RestTemplate
观察者：ApplicationEvent / ApplicationListener

17.6 ★★如何实现海量数据的 TopN 查询？有哪些技术方案？十亿级数据如何分页？如何去重（布隆过滤器/BitMap）？

📖 点击查看答案

海量数据 TopN 方案：

1. 堆排序（小顶堆）：

java

// 维护大小为 N 的小顶堆，遍历数据，比堆顶大则替换
public List<Integer> topN(int[] nums, int n) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(n);  // 小顶堆
    for (int num : nums) {
        if (minHeap.size() < n) {
            minHeap.offer(num);
        } else if (num > minHeap.peek()) {
            minHeap.poll();
            minHeap.offer(num);
        }
    }
    return new ArrayList<>(minHeap);
}
// 时间复杂度 O(N logK)，空间 O(K)

2. 分治 + 归并（分布式）：

10 亿数据分布在 100 台机器
1. 每台机器本地 TopN（小顶堆）
2. 汇总 100 * N 个结果
3. 再次 TopN 得到全局 TopN

3. 快速选择（Quick Select）：

java

// 基于 partition，平均 O(N)，最坏 O(N²)
public int findKthLargest(int[] nums, int k) {
    int target = nums.length - k;
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int p = partition(nums, lo, hi);
        if (p == target) return nums[p];
        else if (p < target) lo = p + 1;
        else hi = p - 1;
    }
    return nums[lo];
}

4. 桶排序（数据范围已知）：

按值分桶，统计每桶数量，从大到小累加找 TopN

5. 大数据方案：

MapReduce：Mapper 本地 TopN，Reducer 汇总
Spark：rdd.top(N) 或 rdd.mapPartitions + reduce
Redis ZSet：实时 TopN（如热搜榜）

十亿级数据分页：

问题：LIMIT 10000000, 10 需扫描 10000010 行，极慢

方案1：游标分页（推荐）：

sql

-- 第一页
SELECT * FROM t_order WHERE id > 0 ORDER BY id LIMIT 10;
-- 后续页（携带上一页最后 id）
SELECT * FROM t_order WHERE id > 10000000 ORDER BY id LIMIT 10;
-- 索引扫描，O(1) 定位，极快

方案2：覆盖索引：

sql

-- 子查询走覆盖索引，再 JOIN 取详情
SELECT * FROM t_order t
INNER JOIN (SELECT id FROM t_order ORDER BY id LIMIT 10000000, 10) tmp
ON t.id = tmp.id;

方案3：搜索引擎：

数据同步到 ES，利用倒排索引分页
search_after：基于排序值的游标分页

方案4：预计算：

热门分页预计算存缓存

海量数据去重：

1. BitMap：

java

// 适用于整数去重，每个数 1 bit
// 10 亿整数只需 125MB（10^9 / 8 bytes）
public class BitMap {
    private byte[] bits;
    public BitMap(int capacity) {
        bits = new byte[capacity / 8 + 1];
    }
    public void add(int num) {
        bits[num / 8] |= (1 << (num % 8));
    }
    public boolean contains(int num) {
        return (bits[num / 8] & (1 << (num % 8))) != 0;
    }
}
// 限制：仅适用于非负整数、范围不能过大

2. 布隆过滤器（Bloom Filter）：

java

// 适用于字符串等任意类型，有误判率
public class BloomFilter {
    private BitSet bits;
    private int size;
    private int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};

    public boolean mightContain(String value) {
        for (int seed : seeds) {
            int hash = hash(value, seed);
            if (!bits.get(hash)) return false;
        }
        return true;  // 可能有误判
    }
    public void add(String value) {
        for (int seed : seeds) {
            int hash = hash(value, seed);
            bits.set(hash);
        }
    }
}
// 优点：内存极省（1 亿 URL 约 100MB）
// 缺点：有误判率（false positive），不能删除
// 应用：缓存穿透防护、爬虫 URL 去重、邮箱去重

3. 分治去重（Hash 拆分）：

10 亿 URL 去重：
1. 对每个 URL hash 取模，分到 1000 个小文件
2. 相同 URL 必在同一文件
3. 每个小文件加载内存 HashSet 去重
4. 合并结果

4. HyperLogLog（近似基数）：

java

// Redis HLL，统计 UV
redisTemplate.opsForHyperLogLog().add("uv:20240101", userId);
long uv = redisTemplate.opsForHyperLogLog().size("uv:20240101");
// 12KB 内存统计 2^64 元素，误差 0.81%

方案选型：

精确去重 + 整数：BitMap
近似去重 + 字符串：布隆过滤器
大规模基数统计：HyperLogLog
精确去重 + 大数据：Hash 分治 + HashSet
小规模去重：HashSet / TreeSet

📌 网站部署提示：本文件为标准 Markdown 格式，可直接用于 VitePress、Docusaurus、docsify、Hugo 等静态站点生成器。答案使用 <details> 标签折叠，在浏览器中可展开/收起。建议搭配搜索插件（如 Algolia DocSearch）使用。

十七、算法与计算机基础（6 题） ​

17.1 ★进程、线程、协程的区别是什么？IO 多路复用（select/poll/epoll）的原理是什么？死锁的四个必要条件是什么？ ​

17.2 ★TCP 三次握手和四次挥手的过程是什么？TIME_WAIT 的作用是什么？为什么是三次握手而非两次？ ​

17.3 ★HTTP/HTTPS 的区别是什么？HTTP 1.1、2.0、3.0 有什么演进？输入 URL 到页面显示的全过程是什么？ ​

17.4 ★Docker 与虚拟机的区别是什么？K8s 的核心组件有哪些？Pod 和 Service 是什么？ ​

17.5 ★常用的设计模式有哪些？单例的 DCL（双重检查锁）为什么要加 volatile？工厂、策略、责任链模式的应用场景？ ​

17.6 ★★如何实现海量数据的 TopN 查询？有哪些技术方案？十亿级数据如何分页？如何去重（布隆过滤器/BitMap）？ ​

十七、算法与计算机基础（6 题）

17.1 ★进程、线程、协程的区别是什么？IO 多路复用（select/poll/epoll）的原理是什么？死锁的四个必要条件是什么？

17.2 ★TCP 三次握手和四次挥手的过程是什么？`TIME_WAIT` 的作用是什么？为什么是三次握手而非两次？

17.3 ★HTTP/HTTPS 的区别是什么？HTTP 1.1、2.0、3.0 有什么演进？输入 URL 到页面显示的全过程是什么？

17.4 ★Docker 与虚拟机的区别是什么？K8s 的核心组件有哪些？Pod 和 Service 是什么？

17.5 ★常用的设计模式有哪些？单例的 DCL（双重检查锁）为什么要加 `volatile`？工厂、策略、责任链模式的应用场景？

17.6 ★★如何实现海量数据的 TopN 查询？有哪些技术方案？十亿级数据如何分页？如何去重（布隆过滤器/BitMap）？