算法题

无序数组第k大数
最大子数组和
一个经典2*N多米诺骨牌
力扣240
lc151. 反转字符串中的单词
LRU手撕 重要
K翻转链表
滑动窗口最大值
K轮转链表
合并两个有序链表
旋转数组找最小值
查找二叉搜索树第K个节点的思路
升序链表合并降序链表
构造函数能不能虚函数
最长递增子序列
叉树搜索树返回第k大的值
括号匹配
子数组最大和
找数组中出现次数大于长度一半的数
leetcode41（缺失的第一个正数）
剪绳子

个人介绍

“面试官您好，我叫许涵飞，目前就读于郑州轻工业大学智能科学与技术专业，现为大三学生。过去一年，我有幸在郑州轻软科技有限公司担任 Qt 客户端开发工程师，参与了跟进了项目的开发，积累了一定的上位机开发经验。

在项目中，我熟悉使用 C++ 和 Qt 进行桌面端开发。例如，在电子音乐教室系统中，我通过 Qt 信号槽机制实现实时音频波形展示，在九泰管道智能检测机器人项目中，我利用 QQuick3D 实现点云数据的 3D 可视化，并通过 UDP 实现数据传输和解析。这些经历让我对客户端开发的技术挑战有了深刻认识，并培养了一定的技术攻关能力。

同时，我具备一定的学习能力和抗压能力，在工作中能够快速适应新的技术和环境。我对贵公司的岗位描述和需求进行了研究，发现我的技能与经验较为契合。我希望能将我的技术专长与团队的力量结合，提升贵公司产品的用户体验和市场竞争力。”

项目

根据你的项目描述，面试官可能会从以下几个方面进行深入提问，以考察你的技术深度、解决问题的能力以及项目的真实性。以下是可能的问题方向及应对建议：

1. 项目背景与需求分析

可能的问题：

• 你提到的“电子音乐教室系统”是为了解决什么问题？它的核心功能是什么？
• 这个系统的用户群体是谁？你如何保证功能满足用户需求？
• 在“管道智能检测机器人”项目中，为什么需要实时点云数据的 3D 渲染？

建议回答：

面试官关注的是你对项目整体的理解和需求背景的把握。可以从项目的目标、解决的核心问题、用户场景入手。

示例：
电子音乐教室系统旨在解决传统音乐教学中教师和学生互动性不足的问题，通过实时音频处理、波形可视化和多通道录制功能，提升教学效率。用户主要是音乐教师和学生，因此我们特别注重界面的直观性和交互性，例如通过波形展示帮助教师实时评估学生的练习效果。

追问可能：

• 如何设计满足用户需求的交互？
• 是否做过用户反馈？如果有，如何改进？

2. 技术选型与实现细节

可能的问题：

• 为什么选择 Qt 和 FFmpeg？这些技术在项目中如何分工协作？
• Qt 的信号槽机制在波形更新中是怎么实现的？是否有性能瓶颈？
• QQuick3D 如何实现点云渲染？与其他渲染技术（如 OpenGL）相比有何优劣？

建议回答：

展示你对技术选型的清晰思考，并提供具体实现细节。

示例：
我们选择 Qt 因为它具备跨平台能力，能够减少不同操作系统间的重复开发工作。FFmpeg 则是用于音视频处理的优秀开源库，在音频滤波、重采样方面有丰富的 API 支持。在实时音频波形的更新中，我使用 Qt 的信号槽机制，将后台采集的音频数据通过信号发送到前端 QML 组件，每隔 50ms 更新一次波形。为了提升性能，我们对更新频率进行了限制，并通过多线程保证实时性。

在管道检测项目中，QQuick3D 提供了一个较高层次的 3D 渲染接口，减少了我们直接使用 OpenGL 编程的复杂度，特别是在点云数据动态更新和交互设计上更方便。

追问可能：

• 信号槽更新频率如何确定？
• 如果波形更新卡顿，如何定位问题？
• 点云数据量较大时，如何优化渲染性能？

3. 性能优化

可能的问题：

• 多线程任务调度如何实现？哪些任务被分配到线程中？线程间如何通信？
• 在实时音频处理或点云渲染中，是否遇到性能瓶颈？如何优化？
• 在网络传输中，如何保证实时性和数据完整性？

建议回答：

从实际问题入手，解释遇到的挑战、分析原因以及解决办法。

示例：
在音频波形更新中，我们使用 QThread 将数据采集和处理分配到后台线程，主线程专注于 UI 渲染。线程之间通过信号槽进行数据同步。初期我们确实遇到波形卡顿的问题，原因是音频数据处理和波形绘制都在主线程进行，优化后通过 QThread 实现了任务分离，大幅提升了系统流畅性。

对于点云渲染，我们采用了分块加载的方式，对大规模点云数据进行分段解析和渲染，避免一次性加载导致卡顿。此外，通过降低点的显示密度和异步加载提升了帧率。

追问可能：

• QThread 使用过程中，如何避免线程安全问题？
• 分块加载点云数据如何设计？有哪些权衡？
• 网络传输中的丢包问题如何解决？

4. 网络通信

可能的问题：

• 使用 TCP/UDP 的具体场景是什么？为什么选择这种协议？
• 数据传输过程中是否需要序列化？如何实现？
• 如何确保实时音频或点云数据的传输质量？

建议回答：

重点解释协议选型和传输质量保证的措施。

示例：
我们在音频数据传输中使用了 TCP 协议，因为其可靠性可以保证音频数据的完整性。在点云数据传输中则使用了 UDP 协议，UDP 的低延迟更适合实时传输。为了确保传输质量，我们在 UDP 中引入了简单的重传机制，通过序列号检查数据包的完整性。此外，音频数据在传输前使用轻量级的压缩算法减小带宽占用，点云数据则通过稀疏化和分块传输减轻了网络负担。

追问可能：

• 选择 TCP/UDP 时的性能对比测试数据？
• 重传机制的具体实现？是否会增加延迟？
• 数据压缩的算法选择和效果？

5. 项目难点与问题解决

可能的问题：

• 项目中你遇到的最大难点是什么？你是如何解决的？
• 音频滤波或重采样的具体实现流程是怎样的？
• 实现点云 3D 渲染时，如何处理数据更新与显示的冲突？

建议回答：

展示你的问题分析能力和解决问题的思路，具体步骤要清晰。

示例：
在音频处理模块中，初期我们遇到的问题是音频滤波后的延迟较高，影响实时性。我们通过分析发现是因线程切换导致的延迟。优化方案是将滤波和重采样任务合并到同一线程中，并使用 FFmpeg 的高效 API 实现滤波器预设，最终将延迟从 300ms 降低到了 50ms。

在点云渲染中，挑战是动态更新与渲染之间的冲突。为此，我们在接收线程完成数据解析后，通过信号槽通知渲染线程更新显示，同时采用双缓冲机制，避免显示过程中读取数据导致的闪烁问题。

追问可能：

• 线程切换延迟的具体优化指标？
• 双缓冲机制如何设计？是否有线程安全问题？

总结建议：

• 提前梳理技术细节：准备好每个项目涉及的核心技术和算法，做到心中有数。
• 逻辑清晰，层层递进：回答时从整体到细节，避免泛泛而谈，最好结合代码实现的核心逻辑讲解。
• 坦诚面对不懂的问题：如果遇到不会的问题，可以表达自己思考的方向或如何查找答案，展现学习能力。

以下是可能的追问以及针对每个问题的详细答案：

1. 设计满足用户需求的交互，是否做过用户反馈？如果有，如何改进？

答案：
在电子音乐教室系统中，为了设计满足用户需求的交互，我们在开发初期与多位音乐教师沟通，了解他们的教学痛点，比如学生音频练习的实时反馈和多通道录制的需求。
用户反馈中提到最初版本的波形展示不够直观，我们根据建议调整了颜色编码来区分学生的音频轨道，并增加了缩放和滚动功能，让教师可以更方便地检查特定时间段的音频波形。通过持续的用户反馈和迭代，我们的产品逐渐贴合用户的实际使用场景。

2. 信号槽更新频率如何确定？

答案：
音频波形更新频率的选择是一个平衡 UI 流畅性和性能消耗的问题。我们通过实验发现，每秒更新 20 次（即 50ms 一次）可以确保波形展示流畅且对主线程性能影响较小。
如果更新频率过高，主线程可能会因频繁绘制而出现卡顿；如果频率过低，用户会感到波形不够实时。在性能测试中，我们使用 Qt 自带的工具（如 QML Profiler）分析了主线程的负载，最终验证了这一更新频率的合理性。

3. 如果波形更新卡顿，如何定位问题？

答案：
定位波形更新卡顿问题时，我们使用以下方法：

1. 使用 QML Profiler：分析是否存在频繁的主线程阻塞。
2. 检查信号槽机制：确保信号槽调用过程中没有长时间运行的阻塞代码。
3. 优化数据处理逻辑：将音频数据采集、处理和绘制拆分到不同的线程，避免处理耗时的任务在主线程中执行。
4. 渲染优化：减少波形绘制中的细节，比如降低采样点数量或使用 GPU 加速渲染。

最终通过调整线程分工和减少绘制负载解决了卡顿问题。

4. QThread 使用过程中，如何避免线程安全问题？

答案：
我们采取了以下措施避免线程安全问题：

1. 数据同步：通过 QMutex 或 QReadWriteLock 保护共享资源，避免多个线程同时修改数据。
2. 避免直接访问共享资源：线程之间通过信号槽通信，不直接共享数据，信号槽机制本身是线程安全的。
3. 任务分工明确：主线程专注于 UI 渲染，后台线程处理数据，避免资源争用。

例如，在音频波形更新中，我们通过信号将处理后的数据传递给主线程，主线程只负责渲染，不直接操作音频数据，确保线程安全。

5. 分块加载点云数据如何设计？有哪些权衡？

答案：
设计思路：

• 将点云数据按空间位置分块，每次只加载当前视图范围内的点云数据。
• 使用四叉树或八叉树对点云数据进行分区管理，通过视口裁剪机制动态加载和卸载数据。

权衡点：

1. 加载性能 vs 内存占用：
   分块加载减少了一次性加载的内存占用，但增加了视口切换时的加载延迟。我们通过预加载相邻块来缓解切换延迟的问题。
2. 分块大小的选择：
   块过大可能导致加载时间长，过小则增加管理复杂性。我们通过测试选择了 1MB 左右的分块大小，性能和复杂性达到了平衡。

6. 选择 TCP/UDP 时的性能对比测试数据？

答案：
在实际项目中，我们对 TCP 和 UDP 的性能进行了测试：

1. TCP（音频传输）：
   • 平均延迟：50ms
   • 丢包率：<0.1%
   • 适用场景：需要数据完整性（如音频文件传输）。
2. UDP（点云数据传输）：
   • 平均延迟：20ms
   • 丢包率：约 2%（无重传机制时）。
   • 适用场景：实时性要求较高的数据（如实时点云渲染）。

根据测试结果，音频传输对完整性要求高，我们选择 TCP；点云数据实时性优先，选择 UDP。

7. 重传机制的具体实现？是否会增加延迟？

答案：
实现方法：

• 在每个 UDP 数据包中加入序列号，接收端检查序列号连续性，发现丢包时通过反馈机制请求发送端重传。
• 设置重传时间窗口（如 50ms），超过窗口的数据丢弃，确保整体实时性。

延迟影响：

• 单次重传增加的延迟大约为网络往返时间（如 20-50ms）。
• 我们对非关键数据（如部分点云片段）采用丢弃策略，对关键数据才请求重传，减少了延迟影响。

8. 数据压缩的算法选择和效果？

答案：
算法选择：

• 音频数据使用简单的 ADPCM（自适应差分脉冲编码调制）算法，压缩比约 2:1。
• 点云数据使用 Octree 压缩，压缩比约 4:1，同时保留了空间结构信息。

效果：
通过数据压缩，我们将音频传输的带宽需求从 256kbps 降低到 128kbps；点云数据从每秒 20MB 降低到 5MB，有效降低了网络负载。

9. 双缓冲机制如何设计？是否有线程安全问题？

答案：
设计方法：

• 在内存中维护两个缓冲区（前台和后台缓冲区），后台线程负责数据更新，前台线程负责渲染。
• 数据更新完成后，后台缓冲区和前台缓冲区交换角色，确保渲染过程中数据一致。

线程安全保障：

• 通过 QMutex 保护缓冲区切换操作，避免读写冲突。
• 使用信号槽机制通知前台线程更新渲染，后台线程完成更新后才触发缓冲区切换。

总结：
准备这些追问答案时，尽量结合项目中的实际经验，提供清晰、具体、可量化的例子，展现你的技术深度和解决问题的能力。如果遇到无法回答的追问，可以冷静分析，并提出自己的思考方向。

25八股文

TCP怎么避免拥塞new

TCP 通过 拥塞窗口（cwnd） 动态调整发送速率来避免拥塞。当连接开始时，采用 慢启动（指数增长）快速探测网络容量；当达到一定阈值后进入 拥塞避免 阶段（线性增长）。如果检测到丢包（通过超时或重复 ACK），TCP 会将窗口减小，重新调整发送速率。快速重传和快速恢复机制用于尽快修复轻微丢包，同时避免大幅降低发送效率。通过这些机制，TCP 实现了对网络状态的动态适应，减少拥塞的发生。

http都是用的TCP吗（http3不是，用的UDP）new

HTTP/3 使用的是 UDP 而不是 TCP，通过基于 UDP 的 QUIC 协议 提供可靠传输功能。QUIC 集成了类似 TCP 的可靠性和拥塞控制机制，同时减少了连接建立的延迟。

那http3用UDP怎么保证可靠传输（QUIC协议包装过一次，聊quic原理）new

简短：HTTP/3 使用基于 UDP 的 QUIC 协议，通过分片重传、流级别的可靠性、多路复用、拥塞控制和 ACK 确认机制，来实现类似 TCP 的可靠传输，同时减少延迟和队头阻塞问题。

复杂：HTTP/3 使用基于 UDP 的 QUIC 协议 来保证可靠传输，具体通过以下机制实现：

1. 数据分片与重传

   • QUIC 将数据分片并标记序号，如果某个分片丢失，会针对该分片单独重传，而无需重新传输整个数据流。

2. 流级别的可靠性

   • QUIC 支持多路复用，将数据分为独立的流，每个流都有自己的序号管理。一个流的丢包不会影响其他流的传输。

3. 拥塞控制和流量控制

   • QUIC 实现了与 TCP 类似的拥塞控制机制（如基于带宽、RTT 计算）以及流量控制机制，防止网络过载。

4. 确认机制

   • QUIC 使用 ACK 报文确认接收的数据分片，并允许接收端汇报丢失的分片，帮助发送端快速恢复丢包。

5. 传输加密

   • QUIC 内置了 TLS 1.3 协议，确保数据传输的完整性和安全性，防止丢包导致的数据篡改。

通过这些设计，QUIC 在 UDP 的基础上实现了类似 TCP 的可靠性，同时解决了 TCP 的部分缺陷（如连接延迟和队头阻塞问题）。

进程和线程聊一下new

进程和线程是操作系统中的两种基本运行单位：

• 进程：是程序的一个独立运行实例，拥有独立的内存空间和系统资源。进程之间相互独立，通信需要通过进程间通信（IPC）。

  • 特点：资源隔离、启动和切换开销较大。

• 线程：是进程中的一个执行单元，多个线程共享进程的内存和资源。线程之间通信简单，但需要注意同步和互斥问题。

  • 特点：切换开销小，但线程间共享资源可能引发竞争。

简单对比：

• 隔离性：进程更独立，线程共享内存。
• 性能：线程比进程轻量，创建和切换更快。
• 适用场景：进程适合独立任务，线程适合并发计算。

操作系统给进程分配的空间结构什么样（32系统1g内核，堆栈，.bss .data那些）new

在 32 位操作系统中，典型的进程内存布局如下（以 1GB 内核空间为例）：

1. 内核空间（1GB）

   • 高地址部分（通常从 0xC0000000 到 0xFFFFFFFF）是为操作系统内核保留的，用户态进程无法直接访问。

2. 用户空间（3GB）

   • 从低地址到高地址，划分为以下主要区域：
     • 栈（Stack）：用于函数调用、局部变量等，地址向下增长（从高地址向低地址）。
     • 堆（Heap）：用于动态分配的内存，地址向上增长（从低地址向高地址）。
     • BSS 段：存放未初始化的全局变量，初始值为 0，占用实际内存。
     • 数据段（.data）：存放已初始化的全局变量和静态变量。
     • 代码段（.text）：存放可执行程序的指令，通常是只读的。

简单表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

0xFFFFFFFF | 内核空间（1GB）
           | ---------------------
           | 栈（动态局部变量、函数调用）
           | ---------------------
           | 堆（动态分配内存）
           | ---------------------
           | BSS 段（未初始化全局/静态变量）
           | ---------------------
           | 数据段（已初始化全局/静态变量）
           | ---------------------
0x00000000 | 代码段（程序指令）
```  

**注意**：堆和栈之间有一段未使用空间，当两者增长时，可能发生冲突（内存不足）。
## 2g的物理空间，但是给进程分配了4g空间发生什么（从虚拟内存原理那块说明）new
简单：当物理内存只有 2GB，但为进程分配了 4GB 虚拟内存，操作系统通过 **虚拟内存** 技术实现。虚拟内存将虚拟地址映射到物理地址，活跃的页面保存在物理内存中，不活跃的页面则存储在磁盘的交换区（swap）。当需要访问不在内存的页面时，触发缺页中断，从磁盘加载页面。这种机制使进程认为自己有完整的 4GB 空间，但频繁的磁盘操作可能导致性能下降。 
   
复杂：当物理内存为 2GB，但给进程分配了 4GB 的虚拟内存时，操作系统利用了 **虚拟内存（Virtual Memory）** 的机制，通过地址映射和分页技术，使每个进程可以认为自己有一片完整的独立内存空间。以下是工作原理的简要说明：  

---

### **1. 虚拟内存的概念**
- **虚拟地址空间**：进程使用的是虚拟地址，通常为 4GB（在 32 位系统中），这并不与实际的物理内存直接对应。  
- **物理内存**：操作系统通过一部分物理内存（如 2GB）和 **磁盘（如交换分区/文件）** 提供虚拟内存的支持。  

---

### **2. 地址映射（分页机制）**
- **页（Page）**：虚拟内存被划分成固定大小的页（如 4KB）。  
- **页表（Page Table）**：操作系统为每个进程维护一个页表，记录虚拟地址和物理地址的映射关系。  
- 当进程访问某个虚拟地址时：
  1. 通过 **页表** 找到该虚拟地址对应的物理地址。
  2. 如果数据在物理内存中，直接访问。
  3. 如果数据不在物理内存中（即发生 **缺页中断**），则操作系统从磁盘加载对应页到内存，并更新页表。

---

### **3. 物理内存不足时的策略**
- 当物理内存（2GB）无法同时容纳所有活跃进程的页面时，操作系统采用 **页面置换算法**，将暂时不用的页写入磁盘交换区（swap），腾出空间存储新的页面。  
- 常见的页面置换算法：
  - **LRU（最近最少使用）**：替换最近最少被访问的页面。
  - **FIFO（先进先出）**：替换最早加载的页面。

---

### **4. 用户视角**
- 每个进程仍然认为自己有完整的 4GB 虚拟地址空间，因为地址转换和缺页处理对用户透明。  
- 但实际受限于物理内存和磁盘速度：
  - 如果进程需要大量的内存，频繁的缺页中断会导致性能下降（**抖动**）。  

---

### **总结**
通过虚拟内存机制，操作系统在 2GB 物理内存的情况下，仍然能为每个进程分配 4GB 虚拟地址空间。地址映射、页表和磁盘交换的结合，保证了进程的内存访问需求，但过度依赖磁盘会导致性能问题。
## C++ volatile关键字有什么用new
在 C++ 中，**`volatile`** 关键字用于告诉编译器一个变量的值可能会被程序外部（如硬件或其他线程）修改，因此编译器在优化代码时不能对该变量的访问进行假设或优化。  

### **主要作用：**
1. **防止编译器优化**  
   - 对 `volatile` 变量的每次访问，编译器都会直接从内存中读取，而不是使用寄存器中的缓存值。  
   - 避免因编译器优化导致的访问问题。

2. **适用于特殊场景**  
   - **硬件寄存器**：与硬件设备通信时，某些寄存器的值可能随时变化。  
   - **多线程**：一个线程中修改的变量，另一个线程需要及时读取（但仅用 `volatile` 不能完全解决多线程问题，需要结合同步机制如 `std::atomic`）。

---

### **示例代码：**
```cpp
volatile int flag = 0;

// 示例：等待某硬件状态改变
while (flag == 0) {
    // 因为 `flag` 是 volatile，每次循环都会重新读取它的值
    // 而不会使用寄存器中的缓存值
}

注意事项：

1. 不是线程安全工具

   • volatile 仅防止优化，不解决数据竞争问题。多线程访问需配合 std::atomic 或锁。

2. 主要用于特殊硬件场景

   • 在现代 C++ 中，volatile 的使用较少，更多依赖其他同步和内存模型工具。

总结：
volatile 关键字用于告诉编译器防止优化变量访问，适合硬件编程或处理随时可能被外部修改的变量，但在多线程中需配合更高级的同步工具来保障线程安全。

C++函数调用约定了解过吗 new

C++ 的函数调用约定决定了函数参数的传递方式、栈的清理责任以及返回值的处理规则。主要有以下几种：

1. cdecl：默认调用约定，参数从右到左入栈，调用方清理栈，可支持可变参数。
2. stdcall：参数从右到左入栈，被调用方清理栈，常用于 Windows API。
3. fastcall：优先通过寄存器传递参数，其余参数按 cdecl 入栈，被调用方清理栈，用于性能优化。
4. thiscall：用于类的非静态成员函数调用，通过寄存器传递 this 指针，其余参数从右到左入栈。
5. vectorcall：优化用于传递浮点和向量类型参数，通过寄存器处理更多参数。

调用约定的选择可以影响性能或确保与不同平台、语言间的兼容性。

C++ 中 std::string 是如何管理字符串的？它和 C 风格字符串（char*）的区别是什么？

std::string 的管理方式

• 动态分配内存：std::string 使用动态分配的方式来存储字符串，可以根据需要自动调整大小。
• 内部封装：它封装了内存管理、长度管理等细节，并且提供了一系列操作字符串的接口，如拼接、查找、切片等。
• 自动清理：std::string 在作用域结束时会自动释放内存，避免内存泄漏。

与 C 风格字符串（char*）的区别

1. 内存管理：

   • **std::string**：自动管理内存，无需手动分配或释放。
   • **char***：需要手动分配和释放内存，易出错。

2. 长度管理：

   • **std::string**：内部保存字符串长度，访问时间复杂度为 O(1)。
   • **char***：长度需要通过遍历字符串计算（如 strlen），时间复杂度为 O(n)。

3. 功能性：

   • **std::string**：提供丰富的成员函数，如拼接、比较、查找、替换等。
   • **char***：只能使用标准库函数（如 strcpy、strcmp），操作不方便。

4. 安全性：

   • **std::string**：处理越界、内存分配失败等问题更安全。
   • **char***：容易出现越界访问或未释放内存的问题。

简单总结：
std::string 更安全、更方便、功能更强大，适合现代 C++ 编程；char* 较底层，效率高但容易出错，适合对性能有极高要求的特定场景。

C++ 中如何高效地拼接字符串？

总结：
小规模拼接：直接用 += 或 append。
大规模拼接：使用 std::ostringstream 或预分配内存提高效率。
性能极限场景：考虑使用 std::vector 或其他自定义优化方法。

在多线程环境下，如何安全地操作 std::string？是否需要额外的同步机制？

总结
多线程只读：无需额外同步。
多线程读写：必须使用同步机制，如互斥锁（std::mutex）。
独立副本：使用 thread_local 避免共享数据。

std::vector 和 std::list 的底层实现和使用场景有什么区别？请具体说明插入、删除和随机访问的性能差异。

底层实现

• **std::vector**：动态数组，元素连续存储。
• **std::list**：双向链表，元素通过指针连接，非连续存储。

性能差异

1. 插入/删除

   • **std::vector**：
     • 末尾插入/删除：时间复杂度 O(1)。
     • 中间插入/删除：时间复杂度 O(n)，需要移动后续元素。
   • **std::list**：
     • 任意位置插入/删除：时间复杂度 O(1)，只需调整指针。

2. 随机访问

   • **std::vector**：支持随机访问，时间复杂度 O(1)。
   • **std::list**：不支持随机访问，需从头或尾遍历，时间复杂度 O(n)。

使用场景

• **std::vector**：

  • 需要高效的随机访问或末尾插入/删除。
  • 元素数量较少，插入/删除操作较少。

• **std::list**：

  • 需要频繁的中间插入/删除操作。
  • 不需要随机访问。

简单总结：

• **选择 std::vector**：需要随机访问，插入/删除主要在末尾。
• **选择 std::list**：需要频繁的中间插入/删除操作，不关心随机访问。

如何在 C++ 中选择合适的容器（如 std::vector、std::list）来存储和操作数据？举一个具体的应用场景。

选择容器的原则

1. 数据访问需求：

   • 需要随机访问：选择 std::vector。
   • 只需顺序遍历：std::list 或 std::deque 均可。

2. 插入/删除频率：

   • 频繁在中间插入/删除：选择 std::list。
   • 插入/删除主要在末尾：选择 std::vector 或 std::deque。

3. 存储结构要求：

   • 元素数量动态变化且连续存储：选择 std::vector。
   • 需要高效管理头部或尾部：选择 std::deque。

具体应用场景

场景：文本编辑器的字符存储

• 需求：

  • 插入和删除字符频繁。
  • 不需要随机访问。

• 选择容器：

  • 使用 std::list，因为链表的插入/删除效率高，避免因频繁操作引发的大量内存移动。

总结：根据操作模式选择合适的容器能显著提高效率。

std::vector 的容量增长是如何管理的？扩容机制的时间复杂度是什么？

std::vector 的容量增长管理

• 容量增长策略：
  • 当 std::vector 的大小超过当前容量时，会自动扩容，通常容量会按 倍数增长（一般是 1.5 倍或 2 倍，具体依赖于实现）。
  • 扩容时，会分配一块更大的连续内存，并将原有元素拷贝到新内存中。

扩容机制的时间复杂度

• 单次扩容：需要拷贝所有元素到新内存，时间复杂度为 **O(n)**，其中 n 是当前元素数量。
• 均摊复杂度：由于扩容频率较低，插入操作的 **均摊时间复杂度为 O(1)**。

总结

• std::vector 通过倍数扩容减少内存分配次数。
• 单次扩容复杂度为 O(n)，但大多数情况下，插入操作的 **均摊复杂度为 O(1)**，因此性能较优。

std::unordered_map 的底层实现原理是什么？如何处理哈希冲突？

std::unordered_map 的底层实现原理

• 基于 哈希表 实现，通过哈希函数将键映射到对应的桶（bucket）。
• 每个桶存储一组键值对（key-value），用于快速查找。

哈希冲突的处理方式

• 使用 链地址法（chaining）：
  • 每个桶存储一个链表（或其他容器，如 std::forward_list），哈希冲突时，将多个键值对存储在同一个桶中链表的不同节点上。

简单总结

• 快速查找：依赖哈希函数，平均时间复杂度为 **O(1)**。
• 冲突处理：通过链地址法解决冲突，冲突严重时性能可能退化为 **O(n)**。
• 适合用于需要快速查找或插入的场景。

std::unordered_map 的时间复杂度是什么？在什么情况下可能退化到O（n）？

std::unordered_map 的时间复杂度

• 查找、插入、删除：平均时间复杂度是 **O(1)**，因为哈希表通过哈希函数直接定位桶的位置。

退化为 O(n) 的情况

当哈希冲突严重时，std::unordered_map 的性能可能退化到 **O(n)**。
具体情况包括：

1. 哈希函数质量差：

   • 哈希函数分布不均匀，大量键被映射到同一个桶中，链表长度增大。

2. 大量数据插入：

   • 如果桶的数量不足且未及时扩容，大量元素集中在少数桶中，导致链表变长。

3. 恶意输入：

   • 攻击者设计输入，使所有键的哈希值相同（例如，使用简单或弱的哈希函数），所有键都落入同一个桶。

解决办法

1. 使用高质量的哈希函数（默认的 std::hash 一般足够）。
2. 定期调整负载因子（Load Factor），避免桶过于拥挤。
3. 如果性能要求严格，可使用 **std::map**（红黑树实现，时间复杂度稳定在 O(log n)）。

总结

std::unordered_map 在正常情况下具有 O(1) 的性能，但在哈希冲突严重时可能退化为 O(n)。选择合适的哈希函数和控制负载因子可以减少退化风险。

C++ 中 std::unordered_map 是线程不安全的，如果要在多线程环境中使用哈希表，你会如何设计一个线程安全的版本？

在多线程环境下，设计一个线程安全的 std::unordered_map 需要考虑并发访问的场景。以下是常见的解决方案：

1. 全局锁保护

• 方法：使用一个 std::mutex 对整个哈希表加锁，所有操作（插入、删除、查找）都串行化。
• 优点：实现简单，适合小规模并发场景。
• 缺点：高并发时性能较低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <unordered_map>
#include <mutex>

template <typename K, typename V>
class ThreadSafeUnorderedMap {
private:
    std::unordered_map<K, V> map;
    std::mutex mtx;

public:
    void insert(const K& key, const V& value) {
        std::lock_guard<std::mutex> lock(mtx);
        map[key] = value;
    }

    bool find(const K& key, V& value) {
        std::lock_guard<std::mutex> lock(mtx);
        auto it = map.find(key);
        if (it != map.end()) {
            value = it->second;
            return true;
        }
        return false;
    }

    void erase(const K& key) {
        std::lock_guard<std::mutex> lock(mtx);
        map.erase(key);
    }
};

2. 分段锁（分桶锁）

• 方法：对哈希表的不同桶（bucket）分别加锁，每个桶使用独立的锁，只加锁访问的桶。
• 优点：减少锁的粒度，提高并发性能。
• 缺点：实现复杂，需手动管理桶锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <vector>
#include <unordered_map>
#include <mutex>
#include <shared_mutex>

template <typename K, typename V>
class ThreadSafeUnorderedMap {
private:
    static const size_t BUCKET_COUNT = 16;
    std::vector<std::unordered_map<K, V>> buckets{BUCKET_COUNT};
    std::vector<std::shared_mutex> locks{BUCKET_COUNT};

    size_t getBucketIndex(const K& key) const {
        return std::hash<K>{}(key) % BUCKET_COUNT;
    }

public:
    void insert(const K& key, const V& value) {
        size_t index = getBucketIndex(key);
        std::unique_lock<std::shared_mutex> lock(locks[index]);
        buckets[index][key] = value;
    }

    bool find(const K& key, V& value) {
        size_t index = getBucketIndex(key);
        std::shared_lock<std::shared_mutex> lock(locks[index]);
        auto it = buckets[index].find(key);
        if (it != buckets[index].end()) {
            value = it->second;
            return true;
        }
        return false;
    }

    void erase(const K& key) {
        size_t index = getBucketIndex(key);
        std::unique_lock<std::shared_mutex> lock(locks[index]);
        buckets[index].erase(key);
    }
};

3. 使用现成的线程安全容器

• 方法：使用第三方库，如 tbb::concurrent_hash_map 或 **boost::unordered_map**，它们提供高性能的线程安全哈希表。
• 优点：性能优化较好，无需自己实现。
• 缺点：需依赖外部库。

总结

• 小规模并发：使用全局锁保护。
• 高并发场景：分段锁（分桶锁）方案更高效。
• 复杂项目：优先选择成熟的第三方线程安全容器。

线程安全如何解决排查应对，sync和reen区别（换成cpp考察），乐观悲观锁（cpp考察）

线程安全的解决和排查

1. 解决线程安全问题：

   • 锁机制：使用 std::mutex 或 std::shared_mutex 控制对共享资源的访问。
   • 原子操作：使用 std::atomic 提供无锁操作支持。
   • 线程安全容器：如 concurrent_unordered_map（TBB 库）或自实现的分段锁机制。

2. 排查线程安全问题：

   • 工具检测：使用工具如 Valgrind（Helgrind 模块）、ThreadSanitizer 检测数据竞争。
   • 代码审查：明确共享资源的访问范围和生命周期，检查潜在的竞争条件。

synchronized 和 ReentrantLock 的区别（C++ 对应考察）

Java 中的 synchronized 和 ReentrantLock 对应 C++ 中的以下机制：

1. **std::mutex**（类似 synchronized）：

   • 特性：
     • 非递归锁，简单易用。
     • 线程需要显式加锁和解锁（可以用 std::lock_guard 简化）。
   • 缺点：不支持重入（递归锁）。

2. **std::recursive_mutex**（类似 ReentrantLock）：

   • 特性：
     • 支持同一线程多次获取同一锁（递归锁）。
     • 可解决递归调用时的死锁问题，但需谨慎使用，避免滥用递归锁导致复杂性增加。

乐观锁和悲观锁（C++ 对应考察）

1. 悲观锁：

   • 含义：假定操作会发生冲突，先加锁再操作，保证安全性。
   • 实现：使用 std::mutex 或 std::shared_mutex 实现。
   • 适用场景：高冲突的多线程场景，需要强一致性。
   • 示例：

     1 2 3 4 5

     std::mutex mtx; void critical_section() { std::lock_guard<std::mutex> lock(mtx); // 操作共享资源 }

2. 乐观锁：

   • 含义：假定操作不会发生冲突，直接操作资源，若检测到冲突则重试。
   • 实现：使用 std::atomic 或 CAS（Compare-And-Swap）。
   • 适用场景：低冲突、高性能需求的场景。
   • 示例：

     1 2 3 4 5 6

     std::atomic<int> value{0}; void optimistic_update(int expected, int new_value) { while (!value.compare_exchange_weak(expected, new_value)) { expected = value.load(); } }

总结考察点

1. 线程安全的基本手段：锁、原子操作、线程安全容器。
2. 悲观锁：使用 std::mutex，确保强一致性。
3. 乐观锁：使用 std::atomic 和 CAS，追求高性能但需处理冲突。
4. 递归锁：考察 std::recursive_mutex 的应用场景和限制。

Redis为什么快 Redis数据类型和结构 MySQL存储引擎 和 隔离级别

Redis 为什么快

1. 全内存操作：
   • Redis 将所有数据存储在内存中，读写操作不涉及磁盘 I/O，极大提升了速度。
2. 单线程模型：
   • 使用事件驱动的单线程架构，避免了多线程上下文切换和锁争用问题。
3. 高效的数据结构：
   • 采用优化的数据结构（如跳表、压缩列表），能快速处理大量操作。
4. 异步非阻塞 I/O：
   • 使用 I/O 多路复用（如 epoll），同时处理多个客户端连接，响应迅速。
5. 持久化优化：
   • 写时日志（AOF）和定期快照（RDB）让持久化对性能影响最小化。

Redis 数据类型和结构

1. 字符串（String）：

   • 最基本的数据类型，支持普通键值存储、计数器等场景。
   • 底层实现：简单动态字符串（SDS）。

2. 哈希（Hash）：

   • 存储键值对集合，适合对象表示，如用户信息。
   • 底层实现：压缩列表或哈希表（取决于数据规模）。

3. 列表（List）：

   • 有序字符串列表，支持队列、栈等操作。
   • 底层实现：压缩列表或双向链表。

4. 集合（Set）：

   • 无序集合，支持快速去重、交集、并集操作。
   • 底层实现：哈希表或整数数组。

5. 有序集合（Sorted Set）：

   • 带分数的有序集合，适合排行榜等场景。
   • 底层实现：跳表和哈希表组合。

6. 位图（BitMap）、HyperLogLog、GEO 等扩展类型。

MySQL 存储引擎

1. InnoDB（默认引擎）：

   • 支持事务、外键、MVCC，适合高并发场景。
   • 索引：聚簇索引（Clustered Index）。

2. MyISAM：

   • 轻量级引擎，不支持事务和外键，适合只读或低并发场景。
   • 索引：非聚簇索引（Non-Clustered Index）。

3. Memory：

   • 数据存储在内存中，速度快但不持久化，适合临时数据。

4. 其他引擎：

   • CSV：存储为 CSV 文件。
   • NDB：适合分布式集群场景（MySQL Cluster）。

MySQL 隔离级别

1. 读未提交（Read Uncommitted）：
   • 事务可以读取未提交的数据，可能导致脏读。
2. 读已提交（Read Committed）：
   • 只能读取已提交的数据，避免脏读，但可能出现不可重复读。
3. 可重复读（Repeatable Read）（InnoDB 默认）：
   • 保证事务中多次读取的结果一致，避免脏读和不可重复读，但可能出现幻读。
4. 可串行化（Serializable）：
   • 最高级别，事务按顺序执行，完全避免脏读、不可重复读和幻读，但性能最低。

总结

1. Redis 快的原因：全内存操作、单线程、I/O 多路复用等优化。
2. Redis 数据类型：支持多种高效结构（String、List、Set 等），灵活满足业务需求。
3. MySQL 存储引擎：InnoDB 支持事务和高并发，MyISAM 更轻量。
4. MySQL 隔离级别：从低到高，依次是 读未提交、读已提交、可重复读、可串行化，需根据业务需求选择。

HTTP 1.1->2.0->3.0（详细讲解从1.1到3.0） HTTPS 状态码

HTTP 1.1 → 2.0 → 3.0 演进详细讲解

HTTP/1.1

1. 核心特性：

   • 持久连接：默认使用 Connection: keep-alive，避免每次请求都重新建立 TCP 连接。
   • 管道化（Pipeline）：支持在同一个连接中同时发送多个请求，但需要按顺序接收响应。
   • 缓存控制：引入了 Cache-Control 和 ETag 等头部，提升缓存管理能力。
   • 虚拟主机支持：通过 Host 头部允许同一 IP 地址支持多个域名。

2. 主要问题：

   • 队头阻塞（Head-of-Line Blocking）：一个请求未完成会阻塞后续请求，即便在管道化模式下依然存在。
   • 单请求-响应模型：每次请求需带完整头部信息，导致冗余。
   • 高延迟：受限于 TCP 握手和慢启动机制，延迟较高。

HTTP/2.0

1. 核心改进：

   • 二进制分帧：将数据分为帧传输，帧内包含标识信息，减少了头部解析的复杂性。
   • 多路复用：在单个 TCP 连接中并行处理多个请求和响应，解决了队头阻塞问题（应用层队头阻塞）。
   • 头部压缩：使用 HPACK 算法压缩 HTTP 头部，减少带宽消耗。
   • 服务器推送（Server Push）：服务器可主动向客户端推送资源，减少请求延迟。

2. 局限性：

   • TCP 队头阻塞仍存在：虽然多路复用解决了应用层问题，但 TCP 连接本身依然受队头阻塞影响。
   • 复杂性增加：二进制分帧和流的管理增加了实现难度。

HTTP/3.0

1. 核心改进：

   • 基于 QUIC 协议：使用 UDP 代替 TCP，QUIC 提供可靠性和加密支持，解决了 TCP 的队头阻塞问题。
   • 无队头阻塞：QUIC 每个流独立处理，避免了因一个流阻塞而影响其他流。
   • 更快的连接建立：
     • 使用 0-RTT 和 1-RTT 的握手机制，首次连接延迟低。
     • TLS 1.3 集成在 QUIC 中，无需额外握手。
   • 内置加密：QUIC 协议默认加密，保证数据传输安全。

2. 优点：

   • 低延迟：减少握手次数和队头阻塞。
   • 高效传输：流量控制粒度更细，适合高并发场景。

3. 不足：

   • 兼容性问题：依赖底层 UDP，部分防火墙或 NAT 设备可能限制。
   • 实现复杂：QUIC 的逻辑比 TCP 和 HTTP/2.0 更复杂。

HTTPS

1. 定义：

   • HTTPS 是 HTTP + TLS（或 SSL），通过加密层保护数据传输的安全性。

2. 核心功能：

   • 加密：防止数据被窃听。
   • 认证：验证服务器身份（通过证书）。
   • 完整性：确保数据未被篡改。

3. 握手流程（TLS 1.3 简化）：

   • 客户端发送 ClientHello 包，附带加密算法列表。
   • 服务端返回 ServerHello，确认加密算法并附上证书。
   • 客户端验证证书，生成会话密钥。
   • 双方使用密钥加密通信。

HTTP 状态码

1xx 信息响应：

• 100 Continue：客户端应继续请求。
• 101 Switching Protocols：协议切换（如 WebSocket）。

2xx 成功响应：

• 200 OK：请求成功。
• 201 Created：资源已创建。
• 204 No Content：请求成功，无内容返回。

3xx 重定向响应：

• 301 Moved Permanently：永久重定向。
• 302 Found：临时重定向。
• 304 Not Modified：资源未修改，使用缓存。

4xx 客户端错误：

• 400 Bad Request：请求有误。
• 401 Unauthorized：未认证。
• 403 Forbidden：拒绝访问。
• 404 Not Found：资源未找到。
• 429 Too Many Requests：请求过多。

5xx 服务端错误：

• 500 Internal Server Error：服务器内部错误。
• 502 Bad Gateway：网关错误。
• 503 Service Unavailable：服务不可用。
• 504 Gateway Timeout：网关超时。

总结

• HTTP/1.1 → HTTP/2.0 → HTTP/3.0 演进解决了效率、队头阻塞、延迟问题，但实现复杂性逐渐增加。
• HTTPS 提供加密、认证和完整性保障。
• 状态码 表示请求响应的结果和错误类别，需熟练掌握常见状态码的含义。

TCP 拥塞控制流量控制

TCP 拥塞控制与流量控制

流量控制（Flow Control）

流量控制是为了避免接收端被发送端数据压垮，确保发送端不会发送超过接收端处理能力的数据量。

机制：

1. 滑动窗口（Sliding Window）：

   • 每个 TCP 连接都有一个接收窗口 (Receive Window)，表示接收端当前能接收的数据量。
   • 发送端根据接收端的窗口大小决定发送数据的数量。

2. 动态调整：

   • 接收端通过 ACK 包中的窗口大小字段通知发送端最新的接收能力。
   • 如果接收窗口大小为 0，发送端暂停发送，周期性发送探测包询问接收端是否恢复。

目标：
让发送速度与接收速度匹配，避免接收端被压垮。

拥塞控制（Congestion Control）

拥塞控制是为了避免网络因过载而性能下降，通过控制发送端流量来防止网络拥塞。

机制：

1. 慢启动（Slow Start）：

   • 初始发送速度较低，拥塞窗口 (Congestion Window) 从小值开始。
   • 每收到一个 ACK，窗口加倍（指数增长）。
   • 当达到阈值 (ssthresh) 后进入拥塞避免。

2. 拥塞避免（Congestion Avoidance）：

   • 窗口增长变为线性增长，每次收到 ACK 增加一个固定值。
   • 通过逐步提高发送速率观察网络状态。

3. 快速重传（Fast Retransmit）：

   • 如果收到多个重复的 ACK，认为某个数据包丢失，立即重传丢失的数据包，而无需等待超时。

4. 快速恢复（Fast Recovery）：

   • 当检测到丢包时，将 ssthresh 设置为当前窗口的一半，重传丢失包，并进入线性增长阶段。

关键点：

• 拥塞控制通过动态调整 拥塞窗口 (cwnd) 来适应网络状况。
• 丢包或延迟增加被认为是拥塞的信号，触发窗口收缩。

流量控制与拥塞控制的对比

总结

• 流量控制 侧重于发送端和接收端的配合，确保数据不会过载接收端。
• 拥塞控制 关注网络层，动态调整发送速率以避免网络拥塞。
• 两者结合使用，保证数据传输的效率和稳定性。

前端到后端会经历什么过程，过程涉及什么协议，协议有什么字段

前端到后端的通信过程

1. 用户发起请求：用户在浏览器中访问网站，前端向后端发送 HTTP 或 HTTPS 请求。

详细过程

1. DNS 解析

• 浏览器根据用户输入的 URL，通过 DNS 协议解析出目标服务器的 IP 地址。
• 协议：DNS（基于 UDP，默认端口 53）。
• 重要字段：
  • 请求字段：
    • 查询类型（A、AAAA、CNAME 等）。
    • 查询名（如 www.example.com）。
  • 响应字段：
    • 查询结果（目标 IP 地址）。
    • TTL（缓存时间）。

2. TCP 连接建立

• 浏览器通过 TCP 与后端服务器建立连接。
• 协议：TCP（三次握手）。
• 重要字段：
  • SYN、ACK 标志：三次握手标志。
  • 序列号（Sequence Number）：数据包的编号。
  • 窗口大小（Window Size）：流量控制相关。

3. TLS 握手（如果使用 HTTPS）

• 如果是 HTTPS，建立加密连接。
• 协议：TLS（默认端口 443）。
• 重要字段：
  • ClientHello：客户端支持的加密算法、随机数等。
  • ServerHello：服务器选择的加密算法、证书、公钥等。
  • Finished：双方确认加密通道建立完成。

4. HTTP 请求

• 浏览器向服务器发送 HTTP 请求，后端接收并处理。
• 协议：HTTP（或 HTTPS）。
• 重要字段：
  • 请求字段：
    • 方法：GET、POST、PUT、DELETE 等。
    • URL：请求的资源路径。
    • Headers（头部）：附加信息（如 User-Agent、Authorization 等）。
    • Body：请求体，通常包含数据（如 JSON）。
  • 响应字段：
    • 状态码：200、404、500 等。
    • Headers：附加信息（如 Content-Type、Set-Cookie）。
    • Body：返回的内容（如 HTML、JSON）。

5. 数据传输

• 数据在传输层中分片，通过 IP 协议在网络中路由。
• 协议：IP（默认 IPv4 或 IPv6）。
• 重要字段：
  • 源 IP 地址、目标 IP 地址。
  • 数据包大小、校验和。

总结

这些协议协同工作，确保前端请求能成功到达后端，后端响应能准确返回到前端。

抽象类和接口的区别 单元测试怎么写，是如何执行的 冒泡排序空间复杂度会不会随数据量变大而变大 冒泡排序和快速排序对比

C++ 抽象类和接口的区别

1. 抽象类：

   • 含有至少一个纯虚函数的类称为抽象类。
   • 可以包含普通函数和成员变量。
   • 允许部分实现，但不能直接实例化。

2. 接口：

   • 在 C++ 中没有专门的接口定义，但可以通过纯抽象类模拟接口。
   • 纯抽象类：所有成员函数都是纯虚函数，且不包含任何成员变量。
   • 只能定义方法，不提供任何实现。

区别总结：

• 抽象类可以包含成员变量和部分实现；接口（纯抽象类）完全没有实现，只定义方法。
• 抽象类更适合实现通用功能的基类，接口更适合定义标准化行为。

单元测试怎么写，如何执行

1. 编写单元测试：

   • 使用 C++ 单元测试框架（如 Google Test、Catch2）。
   • 为每个函数或模块编写独立的测试用例。
   • 测试用例包括输入、期望输出和实际结果的比较。

2. 单元测试的结构：

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   #include <gtest/gtest.h> // 被测试函数 int add(int a, int b) { return a + b; } // 测试用例 TEST(AdditionTest, HandlesPositiveInput) { EXPECT_EQ(add(1, 2), 3); } int main(int argc, char **argv) { ::testing::InitGoogleTest(&argc, argv); return RUN_ALL_TESTS(); }

3. 执行单元测试：

   • 编译测试代码生成可执行文件。
   • 运行测试，框架会输出每个测试用例的通过或失败信息。

单元测试流程：

• 编写测试用例。
• 使用框架运行测试。
• 分析失败用例并修复代码。
• 重复执行，确保所有测试通过。

冒泡排序空间复杂度是否随数据量变大而增加

• 冒泡排序的空间复杂度为 ( O(1) )：

  • 只需要常数级的额外空间（用于临时变量交换数据）。
  • 数据存储在原数组中，不需要额外分配内存。

• 数据量变大不会增加额外空间需求：

  • 冒泡排序的空间需求不依赖于输入数据量，只依赖于排序算法本身。

冒泡排序和快速排序对比

总结：

• 冒泡排序适合小规模数据、教学场景。
• 快速排序是高效的通用排序算法，在大数据量时表现更好。

智力题：140g的盐 各有2g和7g的砝码 只能用三次天平，如何称出50g 和 90 g

7*7g砝码得到49g盐，2g砝码得到2g盐，2g盐自己对半秤到平衡得到两份1g的盐。
于是有了49+1=50g

线程池、参数配置、默认线程池、Atomic类、synchronized、volatile、JVM结构、GC、可达性分析、GC Root、finalize，进程线程、三次握手四次挥手、TCPUDP，okhttp

C++版回答：

线程池

• 作用：线程池用于高效地管理线程，避免频繁创建和销毁线程，提高并发性能。
• 实现：
  • C++ 标准库没有直接提供线程池，可以使用开源库（如 Boost::ThreadPool）或自行实现。
  • 自己实现时通常包括一个任务队列和固定数量的工作线程，工作线程不断从任务队列中取任务执行。
• 参数配置：
  • 核心线程数：线程池初始化时的线程数量。
  • 最大线程数：线程池能够扩展的最大线程数量。
  • 任务队列：存放待执行任务的队列。
  • 超时时间：线程空闲超过设定时间后销毁。
• 默认线程池：C++20 中引入 std::async 时可以使用默认线程池，但无法直接配置线程池参数。

Atomic 类

• 作用：提供线程安全的原子操作，避免竞争条件。
• 实现：
  • C++ 提供 std::atomic，支持基本数据类型（如整数、指针等）的原子操作。
  • 使用 CAS（Compare-And-Swap）保证无锁操作。
• 常用方法：
  • std::atomic<int>：原子整型变量。
  • load()、store()：安全读取和写入。
  • fetch_add()、fetch_sub()：原子加减操作。

synchronized（C++的替代方案）

• C++ 没有 synchronized 关键字，常用以下方式实现线程同步：
  • 互斥锁：std::mutex 或 std::recursive_mutex。
  • 条件变量：std::condition_variable。
  • 读写锁：std::shared_mutex。

volatile

• 作用：volatile 告诉编译器不要优化对变量的访问，确保每次读取或写入都直接操作内存。
• 局限性：在多线程环境中，volatile 无法保证线程安全，只能确保变量的可见性。

JVM结构（替换为C++内存模型）

• C++ 内存模型由以下区域组成：
  • 代码段：存放可执行指令。
  • 数据段：
    • .bss：未初始化的全局变量和静态变量。
    • .data：已初始化的全局变量和静态变量。
  • 堆：动态分配内存区域（如 new 操作分配的内存）。
  • 栈：每个线程独有，用于函数调用和局部变量存储。

GC（垃圾回收）

• C++ 没有自动垃圾回收，内存管理由开发者负责。
• RAII（Resource Acquisition Is Initialization）是常见的内存管理方式，依赖对象的生命周期和智能指针（如 std::unique_ptr 和 std::shared_ptr）来管理资源。

可达性分析与 GC Root

• C++ 没有 Java 的可达性分析机制，但智能指针的引用计数类似于 GC。
  • std::shared_ptr：使用引用计数判断对象是否需要销毁。
  • 循环引用问题可以用 std::weak_ptr 解决。

finalize

• C++ 使用析构函数代替 finalize。
  • 析构函数在对象销毁时调用，用于资源释放。
  • 避免显式调用析构函数，以确保资源正确释放。

进程与线程

• 进程：操作系统分配资源的最小单位。
• 线程：CPU 调度的最小单位。
• 对比：
  • C++ 使用 std::thread 创建线程。
  • 线程共享进程的内存空间，适合多任务协作。
  • 进程之间通过 IPC（如管道、共享内存）通信。

三次握手与四次挥手

• 三次握手：TCP 建立连接。
  1. 客户端发送 SYN。
  2. 服务端返回 SYN+ACK。
  3. 客户端发送 ACK，连接建立。
• 四次挥手：TCP 断开连接。
  1. 客户端发送 FIN。
  2. 服务端返回 ACK。
  3. 服务端发送 FIN。
  4. 客户端返回 ACK。

TCP 和 UDP

• TCP：面向连接，可靠传输，支持流量控制、拥塞控制和数据重传。
• UDP：无连接，低延迟，适合实时通信（如视频直播）。

okhttp 的 C++ 替代

• C++ 中没有直接等价的 OkHttp，但可以使用以下库：
  • libcurl：功能强大的 HTTP 客户端库，支持多种协议。
  • Boost.Beast：基于 Boost.Asio 的 HTTP 和 WebSocket 实现。
  • cpp-httplib：轻量级的单头文件 HTTP 库。

需要进一步详细解释某一部分，欢迎指出！

在使用 Qt 时，很多功能可以通过其内置的模块和工具来实现。以下是结合 Qt 框架对这些概念的适配和实现：

线程池（Qt 的实现方式）

• Qt 提供了 QThreadPool 和 QRunnable 类，可以方便地创建和管理线程池。
  • 使用方法：
    1. 创建一个 QRunnable 对象（表示一个任务）。
    2. 将其加入 QThreadPool 进行管理和调度。

       1 2 3

       QThreadPool *pool = QThreadPool::globalInstance(); QRunnable *task = new MyTask(); // MyTask 继承 QRunnable pool->start(task);

  • 参数配置：
    • QThreadPool::setMaxThreadCount(int count)：设置线程池的最大线程数。
    • 默认的全局线程池使用硬件线程数（std::thread::hardware_concurrency()）作为线程数。

Atomic 类（Qt 的实现方式）

• Qt 提供了 QAtomicInt 和 **QAtomicPointer**，类似于 std::atomic，用于线程安全的原子操作。
  • 用法：

    1 2 3

    QAtomicInt counter = 0; counter.fetchAndAddRelaxed(1); // 原子递增 counter.fetchAndSubRelaxed(1); // 原子递减

synchronized 替代（Qt 中的锁机制）

• Qt 提供了多种同步机制，适配多线程编程：
  • 互斥锁：QMutex

    1 2 3 4

    QMutex mutex; mutex.lock(); // Critical section mutex.unlock();

  • 读写锁：QReadWriteLock
    • 用于读多写少场景，类似 std::shared_mutex。
  • 信号量：QSemaphore
    • 控制对共享资源的访问数量。

volatile（Qt 的实现）

• Qt 中没有直接的 volatile 替代，但大部分线程安全操作可通过 QMutex 或 QAtomic* 实现。
• volatile 的语义在 Qt 中通常使用信号槽机制确保内存的可见性。

JVM 结构（Qt 中内存管理）

• Qt 的内存管理依赖于 父子对象机制：
  • 一个对象销毁时会自动销毁其子对象，减少内存泄漏风险。
  • 示例：

    1 2 3

    QWidget *parent = new QWidget; QPushButton *button = new QPushButton(parent); // 父子关系 delete parent; // button 会自动销毁

GC（垃圾回收）

• Qt 没有自动垃圾回收，但通过以下方式管理内存：
  • 父子对象机制：自动销毁子对象。
  • QSharedPointer 和 QScopedPointer：智能指针管理对象生命周期。

    1	QSharedPointer<MyObject> obj = QSharedPointer<MyObject>::create();

finalize（Qt 的替代）

• Qt 中没有类似 Java finalize 的功能，资源释放依赖于：
  • 析构函数（如手动释放资源）。
  • 智能指针（自动回收动态分配的内存）。

三次握手与四次挥手（Qt 网络模块）

• Qt 提供 QTcpSocket 和 **QTcpServer**，隐藏了 TCP 的握手和挥手细节：
  • 三次握手：QTcpSocket 的 connectToHost 方法实现连接。
  • 四次挥手：disconnectFromHost 方法实现断开连接。

TCP 和 UDP（Qt 网络模块）

• TCP：使用 QTcpSocket 和 QTcpServer 实现可靠的点对点通信。
• UDP：使用 QUdpSocket 进行无连接的数据报通信。
  • 示例：

    1 2 3

    QUdpSocket udpSocket; QByteArray data = "Hello, UDP!"; udpSocket.writeDatagram(data, QHostAddress::LocalHost, 12345);

okhttp 替代（Qt 网络请求模块）

• Qt 提供了 **QNetworkAccessManager**，用于发送 HTTP 请求：
  • 示例：

    1 2 3 4 5 6 7 8 9

    QNetworkAccessManager manager; QNetworkRequest request(QUrl("http://example.com")); QNetworkReply *reply = manager.get(request); QObject::connect(reply, &QNetworkReply::finished, [&]() { QByteArray data = reply->readAll(); qDebug() << "Response:" << data; reply->deleteLater(); });

Qt 的模块化设计和跨平台支持，使其可以高效地处理网络通信和线程池任务。对于更复杂的需求，可以结合 Qt 提供的机制自行实现！

计网有哪些层

计算机网络分为 五层模型 或 七层模型，具体如下：

五层模型

1. 物理层

   • 负责比特流的传输，即将数据转化为电信号、光信号或无线信号在传输介质上传输。
   • 设备：网线、光纤、网卡、集线器等。

2. 数据链路层

   • 负责将比特流组装成帧，提供可靠的数据传输。包括差错检测、流量控制等。
   • 协议：以太网、Wi-Fi (802.11)。
   • 设备：交换机。

3. 网络层

   • 负责路由和寻址，将数据从源主机传输到目标主机。
   • 协议：IP (IPv4/IPv6)、ICMP、ARP。
   • 设备：路由器。

4. 传输层

   • 提供端到端的数据传输，分为面向连接的 TCP 和无连接的 UDP。
   • 协议：TCP、UDP。
   • 主要功能：流量控制、可靠传输、错误检测。

5. 应用层

   • 面向用户，提供网络服务，例如文件传输、邮件、浏览网页等。
   • 协议：HTTP/HTTPS、FTP、DNS、SMTP。

七层模型（OSI 模型）

将五层模型的 应用层 细化为三层，更精确描述网络功能：

1. 物理层
2. 数据链路层
3. 网络层
4. 传输层
5. 会话层
   • 管理会话的建立、维护和终止。
6. 表示层
   • 负责数据的编码、解码、压缩、加密、解密。
7. 应用层
   • 直接为用户提供服务。

总结

• 五层模型是简化版，常用于实际网络描述。
• 七层模型（OSI）更详细，常用于教学或理论分析。

一个网址从回车到解析出网页的全过程

当你在浏览器地址栏输入一个网址并按下回车，解析出网页的全过程可以分为以下几个步骤：

1. DNS 解析（域名解析）

• 作用：将人类易读的域名（如 www.example.com）转换为计算机可识别的 IP 地址（如 93.184.216.34）。
• 过程：
  1. 浏览器检查本地 DNS 缓存是否有对应的 IP 地址。
  2. 如果本地没有，查询操作系统的 DNS 缓存。
  3. 如果操作系统没有，向配置的 DNS 服务器（如本地网络的 DNS 或 ISP 提供的 DNS）发起查询。
  4. DNS 服务器递归查询，逐级从根域名服务器、顶级域名服务器（如 .com）、权威域名服务器获取 IP 地址。

2. TCP 连接建立

• 作用：通过 TCP 协议在客户端（浏览器）与服务器之间建立连接。
• 过程：
  1. 三次握手：
     • 客户端向服务器发送一个 SYN 数据包，表示发起连接请求。
     • 服务器回复一个 SYN-ACK 数据包，表示同意连接。
     • 客户端再回复一个 ACK 数据包，确认连接已建立。

3. HTTP/HTTPS 请求

• 作用：浏览器向服务器发送具体的资源请求。
• 过程：
  1. 浏览器构造 HTTP 请求头，包含以下内容：
     • 请求方法（如 GET、POST）。
     • 请求的资源路径（如 /index.html）。
     • Host（主机名，如 www.example.com）。
     • 用户代理（User-Agent，标明浏览器类型）。
  2. 如果是 HTTPS，先进行 TLS 握手：
     • 确认加密算法，交换密钥，建立安全连接。
  3. 请求发送到服务器。

4. 服务器处理请求

• 作用：服务器接收请求并返回相应的资源内容。
• 过程：
  1. 服务器根据请求的资源路径（如 /index.html）查找对应文件或动态生成内容。
  2. 返回 HTTP 响应，包含：
     • 响应状态码（如 200、404）。
     • 响应头（如 Content-Type, Cache-Control）。
     • 响应体（网页内容或数据）。

5. 浏览器接收响应并渲染页面

• 作用：将服务器返回的 HTML 内容解析并呈现为网页。
• 过程：
  1. 解析 HTML：
     • 浏览器解析 HTML 文档，生成 DOM 树。
  2. 解析 CSS：
     • 下载 CSS 文件，解析样式规则，生成 CSSOM 树。
  3. 解析 JavaScript：
     • 下载并执行 JavaScript 脚本，可能动态修改 DOM。
  4. 加载资源：
     • 加载图片、字体、视频等资源。
  5. 渲染：
     • 将 DOM 树和 CSSOM 树合并成渲染树，绘制到屏幕上。

6. 后续优化和用户交互

• 作用：优化加载速度和用户体验。
• 过程：
  • 浏览器可能使用缓存机制减少重复请求。
  • 与服务器保持连接，处理后续的 AJAX 请求或动态更新。

总结

1. DNS 解析：将域名转换为 IP 地址。
2. TCP 连接：三次握手建立连接。
3. HTTP/HTTPS 请求：发送资源请求。
4. 服务器处理：生成响应并返回数据。
5. 浏览器渲染：解析 HTML、CSS、JS，显示网页内容。
6. 用户交互：通过 AJAX 或 WebSocket 实现动态更新和交互。

整个过程依赖多个协议（DNS、TCP、HTTP/HTTPS）协同完成。

网络五元组是什么

网络五元组 是用于唯一标识网络通信中的一个数据流（如 TCP 连接）的五个关键属性，通常包括以下内容：

1. 源IP地址（Source IP Address）

   • 数据流的发送方 IP 地址。

2. 目标IP地址（Destination IP Address）

   • 数据流的接收方 IP 地址。

3. 源端口号（Source Port）

   • 发送方的端口号，用于标识应用进程。

4. 目标端口号（Destination Port）

   • 接收方的端口号，用于标识接收方的应用服务（如 80 表示 HTTP）。

5. 协议类型（Protocol）

   • 使用的传输层协议类型，如 TCP 或 UDP。

示例

假设有一个 TCP 数据包：

• 源IP地址：192.168.1.1
• 目标IP地址：10.0.0.1
• 源端口号：12345
• 目标端口号：80
• 协议类型：TCP

那么它的五元组表示为：
<192.168.1.1, 10.0.0.1, 12345, 80, TCP>

用途

1. 标识唯一的网络连接
   五元组是区分多个数据流的核心依据。例如，多个客户端同时访问同一台服务器，五元组可用于区分它们各自的连接。

2. 防火墙规则
   防火墙可以根据五元组规则来过滤特定的流量。

3. 负载均衡
   负载均衡设备可基于五元组分配流量到不同的服务器。

4. 网络监控与分析
   用于记录和分析网络通信行为，帮助定位问题或检测攻击行为。

注意

• 五元组中的协议类型是传输层协议（如 TCP、UDP），而不涉及应用层协议（如 HTTP）。

https和http区别

HTTP 和 HTTPS 的主要区别在于数据传输的安全性。以下是两者的对比：

1. HTTP（HyperText Transfer Protocol）

• 简介：超文本传输协议，用于在客户端（浏览器）和服务器之间传输数据。
• 特性：
  • 数据明文传输，缺乏加密，容易被窃听或篡改。
  • 默认使用 80 端口。
• 缺点：
  • 数据在网络中以明文形式传递，存在安全隐患（如敏感信息泄露）。

2. HTTPS（HyperText Transfer Protocol Secure）

• 简介：基于 HTTP 加入了 SSL/TLS 协议，用于加密通信，增强安全性。
• 特性：
  • 数据加密：通过 SSL/TLS 加密数据，防止被窃听。
  • 数据完整性：确保传输数据未被篡改。
  • 身份验证：使用数字证书验证服务器身份，防止伪装攻击。
  • 默认使用 443 端口。
• 安全机制：
  1. 加密：使用对称加密算法（如 AES）保护传输数据的机密性。
  2. 认证：使用非对称加密（如 RSA）和数字证书确保通信双方身份。
  3. 握手过程：通过 SSL/TLS 协商会话密钥。

3. HTTP 和 HTTPS 的主要区别

4. HTTPS 的优点

• 防止敏感信息泄露（如登录密码、银行卡号）。
• 提高网站可信度，增强用户信任。
• 对搜索引擎优化（SEO）更友好，部分搜索引擎优先 HTTPS 网站。

5. HTTPS 的不足

• 需要证书，可能增加部署成本。
• 加密和握手过程会增加计算开销，略微影响速度。

总结

HTTPS 是 HTTP 的安全版本，采用加密通信、防止窃听和篡改，特别适合需要保护敏感数据的网站。

mysql索引底层用的什么数据结构

MySQL 的索引底层主要使用了 B+ 树 和 哈希表 数据结构，根据索引的类型和存储引擎不同，使用的结构也有所不同。

1. B+ 树索引（主要结构）

• 使用场景：MySQL 中最常用的索引结构，尤其是 InnoDB 存储引擎的主索引和辅助索引。
• 特性：
  1. 有序性：B+ 树中的节点按照顺序存储，支持范围查询。
  2. 叶子节点链表：B+ 树的所有数据存储在叶子节点，并通过双向链表相连，便于顺序访问。
  3. 平衡性：B+ 树高度平衡，查询效率稳定。
• 适用索引类型：
  • 主键索引（聚簇索引，InnoDB 特有）。
  • 辅助索引（二级索引）。

B+ 树的优点

1. 快速定位：B+ 树的时间复杂度为 **O(log N)**。
2. 磁盘访问优化：每个节点存储多个键值，减少磁盘 I/O 次数。
3. 范围查询高效：有序存储，支持范围和排序操作。

2. 哈希表索引

• 使用场景：MyISAM 引擎的哈希索引或 Memory 引擎的唯一哈希索引。
• 特性：
  1. 直接定位：通过哈希函数计算键值的存储位置，查找速度非常快，时间复杂度接近 **O(1)**。
  2. 无序性：哈希表索引不支持范围查询或排序。
  3. 冲突处理：通过链地址法或开放地址法解决冲突。
• 适用索引类型：
  • 精确查找，尤其是等值查询。

哈希表的优点

1. 等值查询速度快。
2. 内存占用相对较小。

哈希表的缺点

1. 不支持范围查询和排序。
2. 哈希冲突会降低查询性能。
3. 索引值变化频繁时，重建成本高。

3. 空间索引（R-Tree）

• 使用场景：适用于地理空间数据（如二维坐标点、矩形范围）。
• 底层结构：R-Tree（多维数据索引结构）。
• 适用场景：GIS 数据库中的空间查询（如范围查询、最近邻查询）。

4. 索引类型和存储引擎的关系

1. InnoDB 存储引擎（默认引擎）
   • 主索引（聚簇索引）：B+ 树。
   • 辅助索引：B+ 树。
2. MyISAM 存储引擎
   • 主索引：B+ 树。
   • 不支持聚簇索引。
3. Memory 存储引擎
   • 默认使用哈希表索引，支持 B+ 树索引。
4. 其他引擎
   • NDB：哈希索引。
   • CSV：不支持索引。

总结

• B+ 树 是 MySQL 索引的主要数据结构，适合范围查询和排序。
• 哈希表 用于快速等值查询，但不支持范围操作。
• 根据业务需求和存储引擎选择合适的索引类型，可以显著提高查询性能。

讲一下b树，b+树，为什么用b+树

B 树和 B+ 树概述

B 树 和 B+ 树 是两种平衡树数据结构，广泛用于数据库和文件系统的索引结构中。

1. B 树

• 定义：
  B 树是一种多叉平衡树，所有节点按照一定规则存储键值，支持快速查找、插入和删除。
• 特性：
  1. 每个节点可以存储多个键值（关键字），每个键值有指向子节点的指针。
  2. 所有键值在节点内按升序排列。
  3. 非叶子节点也存储实际数据，且可以终止查找。
  4. 树高度平衡。

2. B+ 树

• 定义：
  B+ 树是 B 树的一种改进版本，所有数据都存储在叶子节点，非叶子节点仅存储索引信息。
• 特性：
  1. 所有键值按升序排列，数据只存储在叶子节点。
  2. 叶子节点通过双向链表相连，支持顺序遍历。
  3. 非叶子节点不存储数据，仅存储索引，用于导航。
  4. 树高度平衡。

3. B 树与 B+ 树的区别

4. 为什么选择 B+ 树？

4.1 顺序访问更高效

• B+ 树的叶子节点通过链表相连，支持高效的范围查询和顺序遍历，非常适合数据库的区间查询、排序等操作。

4.2 磁盘 I/O 友好

• 非叶子节点只存储索引信息，节点更小，一次可以加载更多节点到内存中，减少磁盘 I/O 次数，提升性能。

4.3 查询性能稳定

• 所有查找都需要到达叶子节点，查询路径一致，性能更稳定。

4.4 更高的存储利用率

• 非叶子节点只存索引，占用空间小，同样高度下，B+ 树能存储更多数据，提高磁盘利用率。

4.5 更适合范围查询

• B+ 树通过链表顺序遍历叶子节点即可实现范围查询，而 B 树需要中序遍历整棵树，效率较低。

5. 应用场景

• 数据库索引：MySQL 的 InnoDB 存储引擎索引就是基于 B+ 树。
• 文件系统：如 NTFS 文件系统中使用 B+ 树存储目录项。
• 键值存储：如 LevelDB 的索引部分使用 B+ 树。

总结

• B+ 树是对 B 树的优化版本，叶子节点链表、索引与数据分离等特性，使其更加适合数据库的高效查询、范围查询和磁盘存储场景。

线程和进程区别和其通信方式

线程和进程的区别

1. 基本概念

• 进程：操作系统分配资源的基本单位，每个进程有独立的地址空间、堆、栈等资源。
• 线程：CPU 调度的基本单位，是进程中的一个执行流，线程共享进程的资源。

2. 区别对比

进程间通信方式

1. 管道（Pipe）

   • 特点：单向通信，父子进程间使用。
   • 适用场景：简单的数据传输。
   • 缺点：只能在有亲缘关系的进程间使用。

2. 命名管道（FIFO）

   • 特点：支持无亲缘关系的进程间通信。
   • 适用场景：跨进程通信需要唯一标识。

3. 共享内存（Shared Memory）

   • 特点：在多个进程间共享一块内存区域。
   • 优点：通信速度最快。
   • 缺点：需加锁同步，复杂性较高。

4. 消息队列（Message Queue）

   • 特点：消息形式传递数据，支持无亲缘关系的进程通信。
   • 优点：顺序保证。
   • 缺点：性能较低。

5. 信号（Signal）

   • 特点：用来通知进程的异步事件。
   • 适用场景：事件触发的简单通信。

6. 套接字（Socket）

   • 特点：跨主机通信，基于网络协议（TCP/UDP）。
   • 适用场景：分布式通信。

7. 信号量（Semaphore）

   • 特点：用于多进程对共享资源的同步访问。
   • 适用场景：进程间的资源竞争控制。

线程间通信方式

1. 共享内存

   • 特点：线程共享进程的全局变量、堆等资源。
   • 优点：效率高。
   • 缺点：需要加锁（如 std::mutex 或 std::atomic）来保护数据一致性。

2. 条件变量（Condition Variable）

   • 特点：用于线程间的等待和通知机制。
   • 适用场景：线程同步（例如生产者-消费者模型）。

3. 信号量（Semaphore）

   • 特点：线程之间的同步工具。
   • 适用场景：资源数量有限的情况下（如线程池管理）。

4. 事件（Event）

   • 特点：用于通知线程事件发生。

5. 消息队列

   • 特点：通过队列传递消息（如 std::queue + 加锁）。
   • 适用场景：线程间数据解耦。

总结

• 线程是轻量级的执行单位，通信方式主要依赖共享内存和同步工具，性能高但需注意同步问题。
• 进程是独立的执行单位，通信方式较多，但大多开销较高，适用于隔离性更高的任务场景。

linux常用命令有哪些 要查内存占用是哪个命令 要查端口占用情况要用哪个命令

Linux 常用命令分类

1. 文件和目录操作

• ls：列出目录内容。
• cd：切换目录。
• pwd：显示当前目录路径。
• mkdir：创建目录。
• rm：删除文件或目录。
• cp：复制文件或目录。
• mv：移动文件或重命名文件。
• touch：创建空文件。
• find：查找文件。
• cat：查看文件内容。
• more / less：分页查看文件内容。

2. 系统信息查看

• uname -a：查看操作系统信息。
• who：查看当前登录用户。
• uptime：查看系统运行时间和负载。
• hostname：查看主机名。
• df -h：查看磁盘空间使用情况。
• du -sh：查看指定文件或目录大小。
• top：实时查看系统性能、进程。
• htop：增强版的 top（需手动安装）。

3. 内存占用查看

• free -h：查看内存使用情况（-h 以人类可读的格式显示）。
• top：实时查看内存占用。
• htop：交互式查看内存、CPU占用。
• cat /proc/meminfo：显示详细内存信息。

4. 网络操作

• ifconfig：查看网络接口信息（现代系统使用 ip addr 替代）。
• ping：测试网络连接。
• curl：发送 HTTP 请求。
• wget：下载文件。
• netstat -tunlp：查看网络连接和端口占用情况。
• ss -tunlp：netstat 的现代替代，查看端口占用更高效。

5. 端口占用查看

• netstat -tunlp：查看占用端口的进程及其 PID。
• ss -tunlp：类似于 netstat，性能更高。
• lsof -i :<port>：查看指定端口的占用情况。
  • 示例：lsof -i :8080。

6. 用户管理

• whoami：显示当前用户。
• id：显示用户和组信息。
• adduser / useradd：添加用户。
• passwd：修改密码。
• su：切换用户。
• chmod：修改文件权限。
• chown：修改文件所有者。

7. 进程管理

• ps：查看当前进程。
• top / htop：实时监控进程。
• kill：终止进程。
  • 示例：kill -9 <PID>。
• pkill：通过进程名称终止。
  • 示例：pkill nginx。

重点命令

1. 查看内存占用：
   • free -h 或 top / htop。
2. 查看端口占用：
   • netstat -tunlp 或 ss -tunlp。
   • lsof -i :<port> 查看特定端口。

cpp的常用数据结构哪些是引用类型，map的底层数据结构是什么

C++ 常用数据结构中哪些是引用类型？

在 C++ 中，标准库（STL）的常用数据结构主要以值语义为主（拷贝、移动语义），没有内置的引用类型数据结构。但你可以通过指针或 std::reference_wrapper 来实现引用类型的效果。

常用 STL 容器

实现引用类型的方式

1. 使用 指针：容器存储对象的指针（如 std::vector<T*>），间接实现引用语义。
2. 使用 **std::reference_wrapper**：包装引用类型，例如 std::vector<std::reference_wrapper<T>>。

std::map 的底层数据结构

1. 数据结构

• std::map 的底层实现基于 红黑树（Red-Black Tree）。
  • 红黑树是一种自平衡二叉搜索树，能在最坏情况下提供对数时间复杂度的操作。

2. 性能特点

• 插入、删除、查找：
  • 时间复杂度为 ( O(\log n) )，因为红黑树的高度是对数级别。
• 有序性：
  • std::map 保证键值是有序的，按键值的升序存储。

3. 红黑树的特点

• 每个节点为红或黑。
• 根节点始终为黑色。
• 红节点的子节点必须为黑色（红色节点不能连续出现）。
• 从任意节点到叶子节点的路径，黑色节点数量必须相同。

4. 使用场景

• 需要对键值进行 排序 或 范围查询 的场景，适合使用 std::map。

总结

1. C++ STL 容器本身以值语义为主，但可以通过存储指针或 std::reference_wrapper 实现引用语义。
2. std::map 的底层是红黑树，提供 ( O(\log n) ) 的插入、删除、查找性能，且保持键值有序。

项目为什么用多线程不用多进程

在项目中选择多线程还是多进程，取决于性能需求、资源分配、开发复杂度等因素。以下是 为什么更倾向于使用多线程而不是多进程 的几点核心原因：

1. 内存共享效率更高

• 多线程：线程共享同一个进程的内存空间，包括全局变量、堆、代码段等，线程之间可以直接读写共享数据而无需额外的进程间通信（IPC）。
• 多进程：每个进程都有独立的内存空间，进程间通信需要通过管道、消息队列、共享内存或套接字等方式，增加了开发复杂度和性能开销。

示例

• 适合需要频繁共享数据的场景（如日志记录、共享缓存）时，多线程更高效。

2. 上下文切换开销更小

• 多线程：线程的上下文切换比进程轻量级，因为线程共享相同的地址空间，不需要切换虚拟内存页表和内核资源。
• 多进程：进程切换时，操作系统需要切换整个虚拟地址空间，开销更大。

示例

• 适合需要快速响应、实时性较高的场景（如网络服务器或 GUI 应用）。

3. 资源占用更少

• 多线程：线程使用的资源更少，因为它们共用进程的资源（如打开的文件描述符）。
• 多进程：进程需要独立分配系统资源（如文件句柄、内存、CPU 时间），资源占用更高。

示例

• 高并发场景下（如 Web 服务器或游戏引擎），多线程比多进程更能降低系统资源消耗。

4. 开发和调试复杂度

• 多线程：由于线程共享内存，数据同步需要加锁处理（如 mutex、condition_variable 等），这增加了一定的调试难度。
• 多进程：进程间通信（IPC）复杂，调试时需要跟踪多个独立的进程，难以管理和维护。

示例

• 对复杂任务分解、资源共享需求高的项目，多线程开发更简单。

5. 使用场景

多线程适合：

• 高并发处理，如 Web 服务器、网络爬虫。
• CPU 密集型任务的并行计算。
• GUI 应用程序（主线程负责 UI，子线程负责后台任务）。

多进程适合：

• 高隔离性需求，如运行不可信的插件或沙箱环境。
• 大型分布式系统，每个模块独立运行。
• 内存泄漏或崩溃隔离需求高的场景。

总结

使用多线程而不是多进程的主要原因是：多线程共享内存空间，通信效率高，上下文切换开销小，资源占用少，更适合需要频繁数据共享、高并发、性能要求较高的场景。但在需要高隔离性或安全性的场景下，仍然会选择多进程。

共享内存的底层原理

共享内存的底层原理

共享内存（Shared Memory）是进程间通信（IPC）的一种高效方式，它允许多个进程直接访问同一块内存区域。这种机制避免了进程间通过管道、消息队列等进行数据复制的开销。

以下是共享内存的底层原理和关键概念：

1. 共享内存的基础

• 虚拟地址映射：每个进程都有独立的虚拟地址空间。共享内存的核心是将同一块物理内存区域映射到多个进程的虚拟地址空间中，使它们可以访问相同的物理内存。
• 操作系统支持：共享内存通常由操作系统内核管理，通过提供系统调用（如 POSIX 标准的 shmget、shmat）或内存映射（如 mmap）接口实现。

2. 共享内存的工作机制

2.1 创建共享内存

• 一个进程使用系统调用（如 shmget 或 mmap）创建共享内存段。
• 操作系统分配一块物理内存并将其标识符（shmid）返回给调用进程。

2.2 进程附加共享内存

• 使用 shmat 或 mmap 将共享内存段映射到自己的虚拟地址空间。
• 此时，多个进程的虚拟地址空间中有相同的物理内存映射。

2.3 读写共享内存

• 共享内存直接通过指针操作读写，访问速度非常快，无需经过内核的中转。
• 写入的数据对所有附加该共享内存段的进程立即可见。

2.4 分离与删除

• 当一个进程不再需要访问共享内存时，可以调用 shmdt（POSIX）或取消映射。
• 所有进程分离后，创建共享内存的进程可以调用 shmctl 删除共享内存段。

3. 操作系统如何实现共享内存

3.1 内存映射

• 操作系统为共享内存分配一块 物理页框（Page Frame），并将其虚拟地址映射到多个进程的页表中。
• 虚拟内存到物理内存的映射表（Page Table）是共享内存的核心机制。

3.2 标志和权限

• 操作系统通过共享内存的标识符（如 POSIX 的 shmid）来管理内存段，并设置读写权限。
• 权限控制可以防止未授权的进程访问共享内存。

3.3 同步机制

• 操作系统本身不提供数据同步功能。多个进程同时访问共享内存时，可能会发生数据竞争。
• 用户需要使用互斥锁（mutex）、信号量（semaphore）或条件变量（condition variable）来同步访问。

4. 常见的共享内存实现

4.1 POSIX 共享内存

• 函数：shm_open、mmap。
• 共享内存段在内核中维护，命名空间由文件系统挂载点 /dev/shm 管理。

4.2 System V 共享内存

• 函数：shmget、shmat、shmdt、shmctl。
• 通过 IPC 机制分配和管理，支持较大的共享内存。

4.3 内存映射文件（Memory-Mapped Files）

• 使用 mmap 将文件内容直接映射到虚拟内存空间。
• 进程间可以通过映射同一文件实现共享内存。

5. 优点与缺点

优点

• 高性能：无需内核中转，直接读写物理内存。
• 低延迟：相比管道、消息队列，数据不需要复制。
• 灵活性：适合大规模数据共享。

缺点

• 需要手动同步：多个进程同时访问可能导致竞争，需要用户实现同步机制。
• 资源管理复杂：共享内存需要显式分配、附加、分离和删除。
• 内存分配受限：共享内存大小受系统配置限制。

6. 应用场景

• 高性能服务器：如 Redis 使用共享内存技术优化性能。
• 视频或图像处理：多个进程需要快速共享大规模数据。
• 实时通信：进程间需要共享实时状态或数据流。

共享内存是高性能 IPC 的关键技术，但它需要额外的同步机制来确保线程安全和数据一致性。

数组越界一定会崩溃吗

在C++中，数组越界不一定会导致程序崩溃，但它是一种未定义行为。具体表现取决于以下因素：

1. 内存布局的影响

• 访问越界的内存未被使用：如果越界的内存地址尚未被分配给其他变量或程序，可能会读取到意外的数据或写入成功，但不会立刻崩溃。
• 访问越界的内存已被占用：如果越界的内存地址属于其他变量、堆栈或其他程序，可能会导致数据破坏，程序逻辑出错，甚至崩溃。

2. 运行时环境的影响

• Debug模式：在某些编译器的调试模式下，可能会对数组的边界进行检查。一旦越界，程序可能会抛出错误或崩溃。
• Release模式：通常没有边界检查，越界行为可能直接表现为读取垃圾数据或覆盖其他内存。

3. 操作系统的保护机制

• 如果越界访问的地址超出了当前程序的地址空间（如访问非法内存页），操作系统会触发段错误（Segmentation Fault），导致程序崩溃。
• 如果越界的地址仍在程序的合法地址范围内（但属于其他变量或堆栈），操作系统不会干预，程序行为不可预测。

4. 编译器优化的影响

在高优化级别下，编译器可能假设数组不会越界，因此可能忽略一些潜在的越界错误，导致更难发现问题。

5. 实际案例

1. 越界未崩溃：

1
2
3
4
5
6

#include <iostream>
int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    std::cout << arr[6] << std::endl; // 越界访问，但可能不会崩溃
    return 0;
}

结果：程序可能输出垃圾值，但不会崩溃。

2. 越界导致崩溃：

1
2
3
4
5
6

#include <iostream>
int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    arr[10000] = 42; // 写入超出数组范围的地址
    return 0;
}

结果：可能导致程序崩溃，触发段错误。

总结

数组越界是一种未定义行为，可能的后果包括：

• 读取垃圾数据或覆盖其他变量。
• 程序逻辑错误，表现为难以预测的行为。
• 触发段错误，程序崩溃。

因此，尽量避免数组越界，可以使用**std::array** 或 **std::vector**，它们在调试模式下提供越界检查，有助于提高程序的安全性。

c++的new和malloc有什么区别

C++ 中的 new 和 C 语言中的 malloc 都是用于动态内存分配的，但它们在功能、用法和底层实现上有显著区别：

1. 功能差异

new

• 调用构造函数：new 不仅分配内存，还会调用对象的构造函数（如果是类类型）。
• 返回类型安全：返回的指针是分配类型的正确指针，不需要强制类型转换。

malloc

• 仅分配内存：malloc 只负责分配内存，不会调用构造函数。
• **返回 void***：需要手动强制转换为目标类型指针。

2. 用法差异

new

1
2

int* ptr = new int(5);        // 分配一个整型并初始化为 5
MyClass* obj = new MyClass(); // 分配一个 MyClass 对象并调用其构造函数

malloc

1
2

int* ptr = (int*)malloc(sizeof(int));       // 分配一个整型，未初始化
MyClass* obj = (MyClass*)malloc(sizeof(MyClass)); // 分配 MyClass 对象，但不会调用构造函数

3. 释放内存

• new 分配的内存必须用 delete 释放，同时调用对象的析构函数。
• malloc 分配的内存必须用 free 释放，不调用析构函数。

示例：

1
2
3
4
5

int* ptr = new int(5);
delete ptr; // 调用析构函数并释放内存

int* ptr2 = (int*)malloc(sizeof(int));
free(ptr2); // 仅释放内存

4. 内存分配方式

• **new**：由 C++ 的运行时库实现，底层通常依赖 malloc 或类似机制，同时添加了构造函数的调用逻辑。
• **malloc**：直接调用 C 的标准库函数，分配内存时只考虑字节数。

5. 错误处理

• **new**：分配失败会抛出 std::bad_alloc 异常（也可以用 nothrow 版本避免异常）。

  1	int* ptr = new(std::nothrow) int; // 返回 nullptr 而不是抛出异常

• **malloc**：分配失败返回 nullptr，需要显式检查。

  1 2 3 4

  int* ptr = (int*)malloc(sizeof(int)); if (ptr == nullptr) { // 处理分配失败 }

6. 类型安全

• new 是类型安全的，不需要类型转换。
• malloc 返回 void*，需要显式强制类型转换。

总结

推荐：在 C++ 中优先使用 new 和 delete，因为它们与对象的构造和析构配合得更好，而 malloc 更适用于纯 C 风格的程序。

free 释放 new 会怎么样，free 两次呢

1. 用 free 释放 new 分配的内存

如果用 free 释放由 new 分配的内存，会导致未定义行为。可能的后果包括：

• 程序崩溃。
• 内存泄漏。
• 内存损坏，导致后续操作不稳定。

原因

• new 分配的内存由 C++ 运行时管理，它不仅分配内存，还调用构造函数。
• delete 不仅释放内存，还调用析构函数，用于正确清理资源。
• free 是 C 的内存管理函数，不知道如何处理 C++ 的构造函数和析构函数。

示例：

1
2

int* ptr = new int(10); 
free(ptr); // 未定义行为，可能崩溃

正确做法：

1
2

int* ptr = new int(10);
delete ptr; // 调用析构函数并释放内存

2. 用 free 两次

用 free 两次释放同一块内存是严重错误，也会导致未定义行为。

可能的后果：

• 程序崩溃：访问已释放的内存可能触发段错误（Segmentation Fault）。
• 内存损坏：双重释放可能破坏内存分配器的状态，影响后续内存分配和释放。
• 难以调试：这种错误通常不容易被立即发现，可能在后续代码中表现为随机错误。

示例：

1
2
3

int* ptr = (int*)malloc(sizeof(int));
free(ptr);
free(ptr); // 未定义行为，可能崩溃

防御措施：

1. 将指针置空：释放内存后，将指针设为 nullptr，避免重复释放。

   1 2 3

   int* ptr = (int*)malloc(sizeof(int)); free(ptr); ptr = nullptr; // 避免双重释放

2. 使用智能指针（C++）：如 std::unique_ptr 或 std::shared_ptr，自动管理内存，避免手动释放。

   1	auto ptr = std::make_unique<int>(10); // 内存会自动释放

总结

1. 用 free 释放 new 的内存，或者用 delete 释放 malloc 的内存，都会导致未定义行为。
2. 重复调用 free 或 delete 释放内存是错误的，可能导致程序崩溃或内存损坏。
3. 在现代 C++ 中，推荐使用智能指针来管理内存，减少手动释放的风险。

tcp和udp的区别

TCP 和 UDP 的区别

具体区别详解

1. 可靠性

   • TCP 提供可靠的传输：通过校验和、序列号、确认应答和超时重传机制，确保数据准确到达。
   • UDP 不提供可靠传输：数据包可能丢失、重复或乱序。

2. 连接机制

   • TCP 是面向连接的，需要通过三次握手建立连接，四次挥手断开连接。
   • UDP 是无连接的，直接发送数据，无需连接建立和断开。

3. 性能与速度

   • TCP 为了保证可靠性，引入了确认、重传、流量控制等机制，增加了延迟。
   • UDP 简单直接，开销小，适合对实时性要求高的场景。

4. 使用场景

   • TCP：文件传输（FTP）、电子邮件（SMTP）、网页浏览（HTTP/HTTPS）等。
   • UDP：在线游戏、视频直播、语音通话、DNS 查询等。

总结

• 选择 TCP：需要可靠性和数据完整性，比如文件传输或网页访问。
• 选择 UDP：追求低延迟和实时性，可以容忍丢包，比如语音、视频流或实时游戏。

tcp怎么实现可靠传输

TCP 实现可靠传输的机制

TCP 通过以下机制实现可靠传输，确保数据从发送端准确无误地传递到接收端：

1. 数据分段和序列号

• 数据分段：将应用层的大数据分割为多个小段（称为 TCP 段）。
• 序列号：每个段都有唯一的序列号，用于标记数据的顺序，确保接收端能够按正确顺序组装数据。

2. 确认应答（ACK）

• 每接收到一个 TCP 段，接收端都会发送一个确认应答（ACK），告诉发送端该数据已正确接收。
• ACK 包中包含下一个期望接收的数据的序列号。

3. 超时重传

• 发送端在发送每个数据段后会启动一个计时器，等待 ACK。
• 如果在超时时间内没有收到 ACK，则认为数据丢失或损坏，会重新发送该段。

4. 校验和

• 每个 TCP 段包含一个校验和字段，用于验证数据的完整性。
• 接收端通过校验和检测数据在传输过程中是否发生损坏，若发现错误会丢弃该段。

5. 流量控制

• TCP 使用滑动窗口机制控制发送端的数据量，避免发送过多数据导致接收端缓存溢出。
• 接收端通过 ACK 包中的窗口大小字段（Window Size）告诉发送端当前可接收的缓冲区大小。

6. 拥塞控制

• TCP 通过算法（如慢启动、拥塞避免、快速重传和快速恢复）动态调整数据发送速率，避免网络拥塞。
• 拥塞控制通过检测网络状况（如丢包或延迟）来调整发送窗口大小。

7. 数据有序性

• TCP 接收端会按序列号重组数据，即使数据包乱序到达，也能按照正确顺序交付给应用层。

8. 重复数据处理

• 如果接收端收到重复的数据段，会丢弃这些重复段，并重新确认（ACK）已接收的数据，确保数据无冗余。

总结

TCP 通过 序列号、确认应答、超时重传、校验和、流量控制、拥塞控制等机制，实现了数据的可靠传输，确保数据完整、按顺序到达，并能应对数据丢失、乱序或网络拥塞等问题。

三次握手和四次挥手可以少一次吗

三次握手和四次挥手是否可以少一次？

1. 三次握手

   • 不可以少一次。
     因为三次握手的主要目的是确保通信双方的发送和接收能力均正常。如果减少一次，无法完全确认通信链路的可靠性，可能导致问题。

   详细原因

   • 第一次握手：客户端发送 SYN，告诉服务端“我要建立连接”。
     服务端此时只知道客户端想建立连接，但无法确定自己的回应是否能被客户端收到。
   • 第二次握手：服务端发送 SYN+ACK，告诉客户端“我收到了你的请求，并且我也准备好了”。
     客户端此时可以确认服务端已准备好，但服务端仍无法确认客户端是否准备好。
   • 第三次握手：客户端发送 ACK，告诉服务端“我收到了你的回应，现在可以开始通信了”。
     这一步后，服务端才能确认客户端准备好了。

   如果省略第三次握手，服务端可能错误地认为客户端准备好了，而客户端可能未收到服务端的响应，导致通信失败。

2. 四次挥手

   • 也不可以少一次。
     因为四次挥手的主要目的是确保双方都能正确关闭连接，并且双方的数据传输都已完成。如果减少一次，会导致资源无法正确释放，或者一方未完全关闭连接。

   详细原因

   • 第一次挥手：客户端发送 FIN，表示“我已经没有数据要发送了”。
     服务端收到后，知道客户端数据已发送完，但自己还有数据要发。
   • 第二次挥手：服务端发送 ACK，表示“我知道了，但我还没发完数据”。
   • 第三次挥手：服务端发送 FIN，表示“我也没有数据要发了”。
     客户端收到后，知道服务端也完成了数据发送。
   • 第四次挥手：客户端发送 ACK，表示“我知道了，连接可以关闭了”。

   如果省略最后一次 ACK，服务端可能不知道客户端是否已收到关闭信号，从而保持连接，浪费资源。

总结

• 三次握手和四次挥手都不能少一次，因为它们设计的目的是为了确保连接的建立与关闭都能够双向确认，减少次数会破坏协议的可靠性和一致性。

四次挥手过程

TCP 四次挥手的详细过程

四次挥手是 TCP 协议中断开连接的过程，用于确保双方的数据传输已完成，连接可以安全关闭。

阶段和步骤

1. 第一次挥手：客户端发送 FIN

   • 客户端主动发起断开连接，向服务端发送一个 FIN 标志的数据包。
   • 表示客户端已经没有数据要发送了，但仍可以接收来自服务端的数据。
   • 客户端状态变为：FIN-WAIT-1。

2. 第二次挥手：服务端发送 ACK

   • 服务端接收到 FIN 后，发送一个 ACK 确认包，表示“已收到你的请求”。
   • 此时，服务端可能还有数据需要发送。
   • 服务端状态变为：CLOSE-WAIT。
   • 客户端状态变为：FIN-WAIT-2。

3. 第三次挥手：服务端发送 FIN

   • 当服务端完成数据发送后，主动向客户端发送 FIN 标志的数据包，表示“我也没有数据要发送了”。
   • 服务端状态变为：LAST-ACK。

4. 第四次挥手：客户端发送 ACK

   • 客户端接收到服务端的 FIN 后，发送一个 ACK 确认包，表示“我知道了，连接可以关闭了”。
   • 客户端进入TIME-WAIT状态，等待一段时间（通常是 2 个最大报文段寿命，2MSL），以确保服务端收到 ACK。
   • 客户端超时后，连接正式关闭。
   • 服务端接收到 ACK 后，直接进入关闭状态（CLOSED）。

状态变化总结

重要细节

1. TIME-WAIT 的作用：

   • 确保最后一个 ACK 被服务端成功接收。
   • 防止旧连接的重复数据包干扰新连接。

2. 为何需要四次？

   • TCP 是全双工通信，双方需要分别关闭自己的发送方向。
   • 第一次和第二次挥手完成客户端到服务端的关闭，第三次和第四次挥手完成服务端到客户端的关闭。

tcp数据到达是有序的还是乱序的，交给上层是有序的还是乱序的

TCP 数据到达的顺序性和交付给上层的顺序性

1. 数据到达的顺序性
   • 可能是乱序的：
     在实际的网络传输中，TCP 数据包（段）可能会因为路由不同、网络拥塞或其他原因乱序到达接收端。
     比如，发送的序列号为 1、2、3 的三个段，可能接收端先收到序列号为 3 的段，再收到 1 和 2。

2. 交付给上层的顺序性
   • 一定是有序的：
     TCP 在接收端通过 序列号 和 重组缓冲区 来确保将数据按正确顺序交付给上层应用。
     如果接收端发现数据乱序，会将数据暂存在重组缓冲区中，直到缺失的数据段被重传并接收到，再将完整且有序的数据交付给上层。

关键机制

1. 序列号
   每个 TCP 数据段都有唯一的序列号，用于标记数据的顺序。

2. 确认应答（ACK）
   接收端通过 ACK 告知发送端已成功接收的数据段，并通知下一个期望的序列号。

3. 重传机制
   如果某个数据段丢失或超时，发送端会根据接收端的重复 ACK 或超时机制重新发送数据段。

4. 重组缓冲区
   接收端会将乱序到达的数据存入重组缓冲区，等待缺失数据到达后再按照正确顺序组装。

总结

• 到达顺序：TCP 数据包可能乱序到达接收端。
• 交付顺序：TCP 使用序列号、重组缓冲区等机制，确保交付给上层的数据是有序的。

浏览器输入网址过程（吟唱）

浏览器输入网址到显示网页的全过程

1. 用户输入 URL

   • 用户在浏览器地址栏中输入网址（如 https://example.com）。

2. DNS 解析

   • 浏览器先检查缓存（浏览器缓存、本地系统缓存、路由器缓存、ISP 缓存）中是否有目标域名的 IP 地址。
   • 如果缓存中没有，向 DNS 服务器发起查询，将域名解析为目标服务器的 IP 地址。

3. 建立 TCP 连接

   • 使用目标服务器的 IP 地址，浏览器通过 TCP 协议与服务器建立连接（三次握手）。

4. 发起 HTTPS 请求（若使用 HTTPS）

   • 浏览器与服务器协商 SSL/TLS 加密协议，完成安全连接的建立。
   • 双方通过握手交换密钥后，开始加密通信。

5. 发送 HTTP 请求

   • 浏览器通过 TCP 连接向服务器发送 HTTP 请求：
     • 请求行：指定请求方法（如 GET）、目标资源路径等。
     • 请求头：包含浏览器信息、支持的压缩格式、缓存等。
     • 请求体：用于 POST 请求时发送数据。

6. 服务器处理请求

   • 服务器接收请求后，根据请求的路径和参数，处理业务逻辑（如查询数据库、加载资源等）。
   • 将生成的响应（HTML、CSS、JS、图片等）打包成 HTTP 响应并返回。

7. 浏览器接收响应

   • 浏览器接收服务器的 HTTP 响应，解析响应头和响应体。
   • 如果是重定向响应（如 301 或 302 状态码），浏览器根据 Location 头字段访问新的 URL。

8. 解析 HTML

   • 浏览器开始解析 HTML 文档，构建 DOM 树。
   • 解析过程中发现 CSS 文件、JS 脚本、图片等资源时，启动并发请求加载这些资源。

9. 加载和执行 CSS、JS

   • CSS：加载后解析生成 CSSOM 树，与 DOM 树合并为渲染树。
   • JS：加载后执行。JS 可能修改 DOM 和 CSSOM。

10. 布局和绘制

    • 布局（Layout）：根据渲染树计算元素的大小和位置。
    • 绘制（Painting）：将渲染树的内容绘制到屏幕上。

11. 显示页面

    • 浏览器将绘制的页面显示在用户屏幕上。
    • 如果有异步资源（如图片或动态加载的数据），页面会更新并重新绘制。

涉及的协议和技术

1. DNS（域名解析协议）：将域名解析为 IP 地址。
2. TCP/IP：建立通信连接，传输数据。
3. HTTPS（HTTP over TLS/SSL）：提供加密通信和数据完整性。
4. HTTP/1.1、HTTP/2、HTTP/3：定义请求和响应的格式与行为。
5. 浏览器渲染：HTML 解析、CSS 样式应用、JS 执行、页面绘制。

总结

整个过程是从用户输入网址开始，经过域名解析、建立连接、发送请求、接收响应、页面渲染，最终将网页显示在浏览器中。

数据链路层工作原理

数据链路层的工作原理

数据链路层是 OSI 模型中的第二层，负责在同一网络中的直接节点之间传输数据，并确保数据的正确传输。以下是其主要工作原理：

1. 数据链路层的职责

• 封装成帧：将网络层传递下来的数据（IP 数据报）封装为帧（Frame），并附加帧头和帧尾。
• 流量控制：通过控制数据发送速率，防止发送端过快而接收端处理不过来。
• 差错检测：通过帧尾的校验和（如 CRC），检测数据在传输过程中是否出错。
• 物理寻址：通过 MAC 地址（硬件地址）标识网络设备。
• 数据传输：负责节点之间的直接数据传输。

2. 工作原理

2.1 封装与解封装

• 发送端：

  1. 接收来自网络层的数据包。
  2. 在数据包前面加上帧头（包含源 MAC 地址、目的 MAC 地址等信息）。
  3. 在数据包后面加上帧尾（通常包含校验和 CRC，用于错误检测）。
  4. 将完整的帧传递到物理层。

• 接收端：

  1. 从物理层接收帧。
  2. 验证帧尾的校验和，检查数据是否完整。
  3. 去掉帧头和帧尾，将数据包传递给网络层。

2.2 差错检测

• 数据链路层使用校验和（如 循环冗余校验 CRC）检测传输中的错误。
• 如果接收到的帧有错误，可能会直接丢弃或请求重新发送（在可靠链路中，如 PPP）。

2.3 流量控制

• 数据链路层通过机制（如停止-等待协议）来控制发送端的发送速度。
• 防止发送端的数据传输速率超过接收端的处理能力。

2.4 物理寻址

• 每个网络设备都有唯一的 MAC 地址。
• 数据链路层在帧头中使用源 MAC 和目的 MAC 地址，确保帧能够正确传递到目标设备。

2.5 数据传输方式

• 数据链路层支持三种传输方式：
  1. 单播（Unicast）：一对一传输。
  2. 广播（Broadcast）：将数据发送到同一网络中的所有设备。
  3. 多播（Multicast）：将数据发送到一个特定的设备组。

3. 数据链路层协议

常见的协议包括：

• 以太网（Ethernet）：最广泛使用的局域网协议。
• 点对点协议（PPP）：主要用于点对点通信，如拨号网络。
• 令牌环（Token Ring）：一种通过令牌控制传输权的局域网技术。

4. 数据链路层的分层

在部分协议中（如以太网），数据链路层还可进一步划分为两个子层：

1. 逻辑链路控制（LLC）子层：负责帧的多路复用和差错检测。
2. 介质访问控制（MAC）子层：负责物理地址控制和介质访问。

总结

数据链路层通过封装帧、差错检测、流量控制和物理寻址等机制，为网络层提供可靠的直接通信服务。它在局域网和广域网环境中均起到关键作用。

单例模式和缺点

单例模式简介

单例模式（Singleton Pattern） 是一种设计模式，用于确保一个类在整个程序运行期间只有一个实例，并提供全局访问点。

实现方式

1. 懒汉模式（延迟初始化）
   实例在第一次被访问时创建。

   1 2 3 4 5 6 7 8 9 10 11

   class Singleton { public: static Singleton& getInstance() { static Singleton instance; // C++11线程安全 return instance; } Singleton(const Singleton&) = delete; Singleton& operator=(const Singleton&) = delete; private: Singleton() {} };

2. 饿汉模式（提前初始化）
   实例在程序启动时创建。

   1 2 3 4 5 6 7 8 9 10 11 12

   class Singleton { public: static Singleton& getInstance() { return instance; } Singleton(const Singleton&) = delete; Singleton& operator=(const Singleton&) = delete; private: Singleton() {} static Singleton instance; }; Singleton Singleton::instance;

单例模式的优点

1. 唯一性：保证一个类只有一个实例，节省系统资源。
2. 全局访问点：提供了全局访问该实例的方式，便于管理共享资源。
3. 延迟加载（针对懒汉模式）：实例只在需要时创建，节省内存。

单例模式的缺点

1. 不易扩展：

   • 单例类的代码高度耦合，难以继承和修改。
   • 测试难度大，因为单例的全局状态会对测试产生干扰。

2. 多线程问题（在非线程安全环境下）：

   • 如果没有适当的锁机制或 C++11 的 static 特性，懒汉模式的实例化可能出现竞争问题。

3. 隐藏依赖性：

   • 使用单例模式会隐藏类之间的依赖关系，使代码的可读性和可维护性下降。

4. 可能导致资源泄漏：

   • 单例类的生命周期与程序一致，不会被垃圾回收，可能会占用不必要的资源。

5. 违背单一职责原则：

   • 单例类不仅负责管理自身实例，还承担全局访问的功能，增加了类的职责。

总结

单例模式适合用在全局唯一的资源管理场景（如配置管理器、日志系统等）。但需注意其局限性，尤其是对代码的可扩展性和测试的影响。

虚拟内存

虚拟内存简介

虚拟内存是计算机系统中用来扩展物理内存能力的一种机制，它通过将物理内存和磁盘存储结合，向每个进程提供一个连续、独立的地址空间。

虚拟内存的主要概念

1. 地址空间：
   每个进程有独立的虚拟地址空间，通常被划分为用户空间和内核空间。例如，32 位系统中，用户空间是 0x00000000 到 0xBFFFFFFF（3GB），内核空间是 0xC0000000 到 0xFFFFFFFF（1GB）。

2. 页（Page）：
   虚拟内存被划分为固定大小的块，称为页，典型大小是 4KB。

3. 页表（Page Table）：
   维护虚拟地址到物理地址的映射关系。

虚拟内存的工作原理

1. 地址转换：

   • CPU 访问数据时产生一个虚拟地址（逻辑地址）。
   • 使用页表将虚拟地址映射到物理地址。
   • 页表缓冲区（TLB，Translation Lookaside Buffer）缓存常用的页表项，提升转换效率。

2. 分页机制：

   • 如果访问的虚拟地址所对应的物理内存不存在（页面未加载到物理内存），会触发缺页中断。
   • 操作系统会将对应页面从磁盘加载到内存。

3. 交换（Swapping）：

   • 当内存不足时，操作系统会将一些不常用的页面保存到磁盘（称为交换区或页面文件），腾出内存空间。

虚拟内存的优点

1. 进程隔离：
   每个进程拥有独立的地址空间，互相不会干扰，提升了安全性。

2. 内存扩展：
   虚拟内存提供的地址空间可以大于物理内存（例如 2GB 物理内存可提供 4GB 虚拟地址空间）。

3. 高效内存利用：
   仅在需要时才将页面加载到内存中，减少了内存浪费。

4. 简化编程：
   程序员可以假设有一段连续的内存，而不需要关心实际的物理内存布局。

虚拟内存的缺点

1. 性能开销：
   页表查找和缺页中断处理会导致性能下降，尤其是频繁的页面交换（Thrashing）会显著降低性能。

2. 内存占用：
   页表本身需要占用一定的内存（多级页表减少占用）。

3. 复杂性：
   实现虚拟内存需要硬件支持（MMU）和操作系统的复杂管理。

总结

虚拟内存通过地址映射、分页和页面交换机制，让每个进程感知到一个连续的、独立的内存空间，极大地提升了系统的灵活性和稳定性。但它也带来了性能和管理上的开销。

LRU、LFU

LRU（Least Recently Used）与 LFU（Least Frequently Used）简介

LRU 和 LFU 是常见的缓存替换算法，用于管理有限容量缓存中的数据，当缓存满时决定哪些数据需要被淘汰。

1. LRU（最近最少使用）

LRU 原理

• 基于“最近使用的数据更有可能再次使用”的原则。
• 淘汰最近最少被访问的数据。

实现方法

1. 数据结构：
   通常使用一个 双向链表 + 哈希表。

   • 双向链表维护数据访问的顺序（最早访问的数据在链表头，最近访问的数据在链表尾）。
   • 哈希表用于快速查找缓存中的数据是否存在。

2. 操作时间复杂度：

   • 查找：O(1)（通过哈希表）。
   • 插入/更新：O(1)（调整链表）。

适用场景

• 适用于访问具有时间局部性的数据场景，例如网页缓存。

2. LFU（最少使用）

LFU 原理

• 基于“使用频率越高的数据越有可能再次使用”的原则。
• 淘汰使用频率最少的数据。

实现方法

1. 数据结构：
   使用一个 哈希表 + 频率链表。

   • 哈希表存储键值对及其访问频率。
   • 频率链表维护所有数据按使用频率排序。

2. 操作时间复杂度：

   • 查找：O(1)（通过哈希表）。
   • 插入/更新：O(log n) 或 O(1)（维护频率链表）。

适用场景

• 适用于访问具有频率局部性的数据场景，例如推荐系统的缓存。

LRU 与 LFU 的对比

总结

• LRU：适合短期访问热点数据。
• LFU：适合长期访问高频数据。
• 结合策略：可以结合两者，例如 LRU-K（基于 K 次最近使用）和 LFU-LRU 混合策略，根据具体场景优化缓存性能。

说一下二分查找

二分查找（Binary Search）

二分查找是一种在有序数组中快速查找目标值的算法。通过每次将搜索范围缩小一半，可以显著降低查找的时间复杂度。

原理

• 前提条件：数组或数据结构必须是有序的（升序或降序）。
• 步骤：
  1. 定义左边界 left 和右边界 right。
  2. 计算中间位置 mid = (left + right) / 2。
  3. 比较 nums[mid] 和目标值 target：
     • 如果 nums[mid] == target，返回索引 mid。
     • 如果 nums[mid] < target，目标值在右半部分，将左边界更新为 mid + 1。
     • 如果 nums[mid] > target，目标值在左半部分，将右边界更新为 mid - 1。
  4. 重复以上步骤，直到找到目标值或 left > right（未找到目标值）。

代码实现（C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <vector>
using namespace std;

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止溢出
        if (nums[mid] == target) {
            return mid; // 找到目标值
        } else if (nums[mid] < target) {
            left = mid + 1; // 缩小到右半部分
        } else {
            right = mid - 1; // 缩小到左半部分
        }
    }
    return -1; // 未找到
}

时间复杂度

• 最佳情况：O(1)（目标值恰好是中间值）。
• 最坏情况：O(log n)（每次范围缩小一半，最多需对数次比较）。
• 平均情况：O(log n)。

空间复杂度

• 迭代版：O(1)。
• 递归版：O(log n)（递归调用栈深度）。

优缺点

• 优点：

  1. 时间复杂度低，适合在大规模有序数据中查找。
  2. 实现简单，逻辑清晰。

• 缺点：

  1. 只能用于有序数据。
  2. 不适合频繁插入/删除操作的动态数据。

扩展应用

1. 查找第一个等于目标值的元素。
2. 查找最后一个等于目标值的元素。
3. 查找第一个大于等于目标值的元素。
4. 查找最后一个小于等于目标值的元素。

示例（查找第一个大于等于目标值的元素）：

1
2
3
4
5
6
7
8
9
10
11
12

int lowerBound(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1; // target 在右半部分
        } else {
            right = mid; // mid 可能是答案，继续向左缩小范围
        }
    }
    return left;
}

总结

二分查找是搜索有序数据的高效方法，在算法设计中经常作为子模块使用，如解决旋转数组问题、查找插入位置等。理解并掌握其变种（如上下界查找）是算法学习的重要内容。

protobuf的优势 如何自定义数据格式解决粘包问题

Protocol Buffers（Protobuf）的优势

1. 高效性：

   • Protobuf 使用紧凑的二进制格式，占用更少的带宽和存储空间。
   • 序列化和反序列化速度快。

2. 跨语言支持：

   • Protobuf 支持多种编程语言（如 C++、Java、Python 等），便于多平台开发和数据交互。

3. 易扩展性：

   • 通过字段编号（field number）实现版本兼容性，新增字段不会影响旧版本的解析。

4. 结构化数据支持：

   • 支持嵌套消息、枚举、数组等复杂数据结构，适用于复杂应用场景。

5. 工具链完善：

   • 提供强大的工具（如 protoc 编译器）生成高效的代码。

如何自定义数据格式解决粘包问题（C++）

粘包问题：
在 TCP 通信中，由于 TCP 是流式协议，多个数据包可能会在接收端合并成一个，或者一个数据包会被拆分成多个小段，这就是粘包问题。

解决方案：
通过设计自定义数据格式，明确消息边界，以便正确地解析消息。

自定义数据格式设计

1. 固定长度消息头：

   • 包含消息的长度（比如 4 字节）和消息类型（比如 2 字节）。
   • 消息头固定长度，便于接收端解析消息大小。

2. 消息体：

   • 消息体包含实际的数据内容，可以是序列化后的 Protobuf 数据或其他格式。

示例数据格式：

1

| Length (4 bytes) | Type (2 bytes) | Data (variable length) |

实现示例

1. 发送端

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
#include <cstring>
#include <vector>
#include <cstdint>
#include <arpa/inet.h> // 用于 htonl/htons

void sendMessage(int socket, uint16_t type, const std::vector<uint8_t>& data) {
    uint32_t length = data.size();
    uint32_t networkLength = htonl(length); // 转为网络字节序
    uint16_t networkType = htons(type);     // 转为网络字节序

    // 构建消息
    std::vector<uint8_t> buffer(4 + 2 + data.size());
    memcpy(buffer.data(), &networkLength, 4); // 写入长度
    memcpy(buffer.data() + 4, &networkType, 2); // 写入类型
    memcpy(buffer.data() + 6, data.data(), data.size()); // 写入数据

    // 发送消息
    send(socket, buffer.data(), buffer.size(), 0);
}

2. 接收端

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include <vector>
#include <cstdint>
#include <unistd.h>
#include <arpa/inet.h>

void receiveMessage(int socket) {
    uint32_t length = 0;
    uint16_t type = 0;

    // 读取消息头
    if (recv(socket, &length, 4, MSG_WAITALL) != 4) {
        std::cerr << "Failed to read message length.\n";
        return;
    }
    if (recv(socket, &type, 2, MSG_WAITALL) != 2) {
        std::cerr << "Failed to read message type.\n";
        return;
    }

    // 转为主机字节序
    length = ntohl(length);
    type = ntohs(type);

    // 读取消息体
    std::vector<uint8_t> data(length);
    if (recv(socket, data.data(), length, MSG_WAITALL) != static_cast<ssize_t>(length)) {
        std::cerr << "Failed to read message body.\n";
        return;
    }

    // 处理消息
    std::cout << "Received message of type " << type << " and length " << length << ".\n";
}

如何结合 Protobuf 使用

• 消息体部分使用 Protobuf 序列化后的数据。
• 在解析消息时，使用 Protobuf 的反序列化工具解析消息体数据。

总结

1. Protobuf 提供了高效、结构化的数据序列化方式，非常适合网络通信。
2. 自定义数据格式解决粘包问题，通过消息头明确边界。
3. 结合 Protobuf 和自定义数据格式，可以构建高效、可靠的网络通信系统。

模版元编程实现编译期计算斐波那契数列

模板元编程是 C++ 的一种强大特性，可以在编译期进行计算。下面是用模板元编程实现斐波那契数列的示例代码。

编译期计算斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>

// 递归模板实现斐波那契数列
template<int N>
struct Fibonacci {
    static constexpr int value = Fibonacci<N - 1>::value + Fibonacci<N - 2>::value;
};

// 模板特化用于递归终止
template<>
struct Fibonacci<0> {
    static constexpr int value = 0;
};

template<>
struct Fibonacci<1> {
    static constexpr int value = 1;
};

int main() {
    constexpr int n = 10;
    std::cout << "Fibonacci<" << n << ">::value = " << Fibonacci<n>::value << '\n';
    return 0;
}

代码解析

1. 递归模板：

   • Fibonacci<N> 的 value 定义为 Fibonacci<N - 1>::value + Fibonacci<N - 2>::value。
   • 这类似于递归函数调用，但发生在编译期。

2. 模板特化：

   • 特化 Fibonacci<0> 和 Fibonacci<1>，分别定义为 0 和 1，用于终止递归。

3. 编译期计算：

   • Fibonacci<10>::value 的结果将在编译期计算完成，运行时直接输出值，性能极高。

结果

运行上述代码，输出结果：

1

Fibonacci<10>::value = 55

优势

• 编译期完成计算，无运行时开销。
• 可用于生成编译期常量，优化性能。

注意事项

• 递归深度受模板递归层次限制（通常为 1024），超出时会引发编译错误。
• 对于大规模计算，可以结合 C++17 的 constexpr 函数实现更灵活的编译期计算。

智能指针 完美转发

智能指针

智能指针是 C++ 提供的一种内存管理工具，负责自动管理动态分配的内存，避免手动调用 delete 造成的内存泄漏或重复释放问题。主要的智能指针包括：

1. std::unique_ptr

• 特点：独占所有权，不能共享。
• 用途：用于一个对象的所有权明确属于单个指针的场景。
• 优点：轻量且安全，生命周期明确。
• 示例：

  1 2 3 4 5

  #include <memory> #include <iostream> std::unique_ptr<int> ptr = std::make_unique<int>(10); std::cout << *ptr << std::endl;

2. std::shared_ptr

• 特点：共享所有权，多方共享同一个对象。
• 用途：适用于需要多个指针共享同一资源的场景。
• 优点：通过引用计数实现共享，最后一个持有者销毁时释放内存。
• 示例：

  1 2 3 4 5 6

  #include <memory> #include <iostream> std::shared_ptr<int> sp1 = std::make_shared<int>(20); std::shared_ptr<int> sp2 = sp1; // 共享所有权 std::cout << *sp2 << std::endl;

3. std::weak_ptr

• 特点：弱引用，不影响引用计数。
• 用途：用于打破循环引用，常与 std::shared_ptr 配合使用。
• 示例：

  1 2 3 4 5 6 7 8

  #include <memory> #include <iostream> std::shared_ptr<int> sp = std::make_shared<int>(30); std::weak_ptr<int> wp = sp; // 弱引用 if (auto sp_from_wp = wp.lock()) { // 检查是否有效 std::cout << *sp_from_wp << std::endl; }

完美转发

完美转发是 C++ 中使用 右值引用 和 模板 将函数参数精确地转发给目标函数的一种技术。

核心要点

• 利用 模板类型推导 和 **std::forward**，保留参数的值类别（左值或右值）。
• 适用于需要构造对象或调用其他函数时避免不必要拷贝的场景。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <utility> // std::forward

void print(int& x) {
    std::cout << "Lvalue: " << x << std::endl;
}

void print(int&& x) {
    std::cout << "Rvalue: " << x << std::endl;
}

template <typename T>
void forward_example(T&& arg) {
    print(std::forward<T>(arg)); // 完美转发，保持值类别
}

int main() {
    int a = 10;

    forward_example(a);       // 转发左值
    forward_example(20);      // 转发右值
    return 0;
}

运行结果

1
2

Lvalue: 10
Rvalue: 20

原理

1. T&& 是万能引用：

   • 当传入左值时，T 推导为 int&，T&& 实际上是 int& &，按规则折叠为 int&。
   • 当传入右值时，T 推导为 int，T&& 保持为 int&&。

2. **std::forward**：

   • 左值会被保持为左值，右值保持为右值。
   • 防止传参过程中发生拷贝或移动。

智能指针与完美转发结合

在构造函数中，利用完美转发构造智能指针：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <memory>
#include <iostream>

class MyClass {
public:
    template <typename T>
    MyClass(T&& value) : ptr(std::make_unique<T>(std::forward<T>(value))) {}

    void display() {
        std::cout << *ptr << std::endl;
    }

private:
    std::unique_ptr<int> ptr;
};

int main() {
    MyClass obj(42);
    obj.display();
    return 0;
}

排序算法 （如果将数据结构变成链表 哪几种排序算法时间复杂度提高）

排序算法及链表场景下时间复杂度变化

在数组和链表两种数据结构中，排序算法的效率会受到结构特性的影响。链表的随机访问性能较差，但插入和删除操作效率较高。这种特性会导致某些排序算法在链表上表现不佳，时间复杂度发生变化。

排序算法的分析

1. 冒泡排序（Bubble Sort）

• 数组时间复杂度：( O(n^2) )
• 链表时间复杂度：( O(n^2) )
  原因：冒泡排序依赖于相邻元素的交换，链表无法快速访问相邻节点，每次比较需要遍历链表到指定位置，性能没有提升。

2. 选择排序（Selection Sort）

• 数组时间复杂度：( O(n^2) )
• 链表时间复杂度：( O(n^2) )
  原因：选择排序需要找到未排序部分的最小值，链表需要遍历未排序区域，因此时间复杂度不变。

3. 插入排序（Insertion Sort）

• 数组时间复杂度：( O(n^2) )
• 链表时间复杂度：( O(n^2) )
  原因：虽然链表插入的性能较高，但查找插入位置仍需要遍历链表，时间复杂度保持为 ( O(n^2) )。

4. 快速排序（Quick Sort）

• 数组时间复杂度：平均 ( O(n \log n) )，最差 ( O(n^2) )
• 链表时间复杂度：平均 ( O(n^2) )，最差 ( O(n^2) )
  原因：快速排序对数组通过随机访问进行划分，效率较高；但链表中随机访问需要遍历，划分效率降低。

5. 归并排序（Merge Sort）

• 数组时间复杂度：( O(n \log n) )
• 链表时间复杂度：( O(n \log n) )
  原因：归并排序可以天然适配链表的结构，通过拆分链表为子链表再合并，无需随机访问，时间复杂度不变。

6. 堆排序（Heap Sort）

• 数组时间复杂度：( O(n \log n) )
• 链表时间复杂度：( O(n^2) )
  原因：堆排序依赖数组的随机访问来维护堆的性质，链表不支持高效随机访问，导致操作复杂度显著增加。

结论

在将数据结构从数组替换为链表后：

1. 时间复杂度显著提高的排序算法：

   • 快速排序：随机访问的高效性被链表的顺序访问特性限制。
   • 堆排序：链表无法有效维护堆结构。

2. 时间复杂度保持不变或适配链表的排序算法：

   • 归并排序：无需随机访问，天然适配链表。
   • 插入排序、冒泡排序、选择排序：时间复杂度本身较高，链表仅会影响常数时间开销。

实际建议

对于链表排序，推荐使用 归并排序，其分治思想与链表特性完美结合，效率最高且实现简单。

二叉树节点多出一个指向父节点的指针 问N个结点的时候有多少个指向空的指针

在一个二叉树中，每个节点可能有以下三个指针：

• 左子节点指针
• 右子节点指针
• 父节点指针

我们需要计算这些指针中有多少个是空的。

分析

1. 二叉树节点数：共有 ( N ) 个节点。

2. 左子指针和右子指针：

   • 每个节点可能有一个左子节点指针或右子节点指针。
   • 整棵树中，非空的左右子指针的总数等于 ( N-1 )（因为二叉树中有 ( N-1 ) 条边连接父节点和子节点）。
   • 因此，空的左右子指针数为：
     [
     空的左右子指针数 = 2N - (N-1) = N+1
     ]

3. 父节点指针：

   • 每个节点有一个指向父节点的指针，除了根节点的父节点指针为空，其余 ( N-1 ) 个节点的父节点指针非空。
   • 因此，空的父节点指针数为 ( 1 )。

总计空指针数

总空指针数为：
[
空指针总数 = 空的左右子指针数 + 空的父节点指针数 = (N+1) + 1 = N+2
]

结论

对于一个有 ( N ) 个节点的二叉树，如果每个节点多了一个指向父节点的指针，则总共有 ( N+2 ) 个空指针。

两个字符串 分别有添加 删除 更新操作 用伪代码实现一个变成另一个

以下是一个基于 动态规划 的伪代码，用于将一个字符串转换为另一个字符串，支持 添加、删除、更新 三种操作。这个问题对应经典的 编辑距离（Levenshtein Distance）。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

function minEditDistance(s1, s2):
    m = length of s1
    n = length of s2

    // 创建一个 (m+1) x (n+1) 的二维数组 dp，用于存储子问题的最优解
    dp = 2D array of size (m+1, n+1)

    // 初始化边界条件
    for i from 0 to m:
        dp[i][0] = i  // 从 s1 的前 i 个字符变成空字符串，需删除 i 次
    for j from 0 to n:
        dp[0][j] = j  // 从空字符串变成 s2 的前 j 个字符，需添加 j 次

    // 填充 dp 表
    for i from 1 to m:
        for j from 1 to n:
            if s1[i-1] == s2[j-1]:  // 当前字符相同，无需操作
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i-1][j] + 1,    // 删除操作
                    dp[i][j-1] + 1,    // 添加操作
                    dp[i-1][j-1] + 1   // 更新操作
                )

    // 返回将 s1 变为 s2 的最小编辑距离
    return dp[m][n]

示例执行过程

假设输入：

• ( s1 = “kitten” )
• ( s2 = “sitting” )

初始化 dp 表：

• dp[0][0] = 0
• dp[i][0] = i
• dp[0][j] = j

填表过程：

根据状态转移方程依次填充表格，最后返回 dp[m][n]。

操作路径追踪

为了获得具体的操作步骤，可以在填表的过程中记录路径，例如：

1. 如果当前选择了 删除操作，记录 delete s1[i-1]。
2. 如果选择了 添加操作，记录 insert s2[j-1]。
3. 如果选择了 更新操作，记录 update s1[i-1] to s2[j-1]。

通过从 dp[m][n] 回溯，可以生成一个完整的操作序列。

时间复杂度

• 时间复杂度：( O(m \times n) )，双层循环计算 dp 表。
• 空间复杂度：( O(m \times n) )，存储 dp 表（可优化为 ( O(\min(m, n)) )）。

lambda表达式和bind的区别，lambda表达式引用捕获有什么风险(没答上来，面试官引导往多线程的角度考虑)

Lambda 表达式和 std::bind 的区别

1. 语法和可读性：

   • Lambda 表达式：
     • 是一种匿名函数，语法简洁，直接内联定义，易于阅读。
     • 支持捕获外部变量（值捕获或引用捕获）。
   • **std::bind**：
     • 用于创建一个函数对象，将一个已有的函数与某些参数绑定，形成一个新的可调用对象。
     • 相对较冗长，可读性较差。

2. 功能：

   • Lambda 表达式更灵活，可以直接访问外部变量。
   • **std::bind**不支持捕获变量，仅能绑定已有函数的参数。

3. 性能：

   • Lambda 表达式通常性能更好，编译器可以对其内联优化。
   • **std::bind**会生成额外的函数对象，可能有较小的性能开销。

4. 使用场景：

   • Lambda 表达式适合简单、局部的回调或计算。
   • std::bind适合需要生成多次调用、固定绑定参数的场景。

Lambda 表达式引用捕获的风险

在多线程场景中，引用捕获（[&]）可能带来以下风险：

1. 捕获的引用在生命周期内失效：

   • 如果线程异步运行，捕获的引用可能指向了已经销毁的对象，导致 悬空引用 问题。
   • 例如：引用了一个局部变量，而局部变量在主线程中作用域结束后被释放，异步线程访问时会出错。

2. 数据竞争：

   • 如果多个线程通过引用捕获访问同一个变量，没有同步机制，则会发生数据竞争，导致未定义行为。

示例

生命周期问题

1
2
3
4
5
6
7
8

void example() {
    int x = 10;
    std::thread t([&]() {
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        std::cout << x << std::endl;  // x 可能已经被销毁
    });
    t.detach();
} // x 离开作用域，线程可能访问已销毁的 x