C++ 面试高频题精简精校版（按面试频次分类）

按面试出现频次分为 🔥 高频题（97题）、📌 中频题（66题）、💡 低频题（34题），建议按优先级复习。

📊 频次分布总览

一、C/C++ 基础

🔥 高频题（32题）

面试中最常出现，核心知识点，建议重点掌握，能熟练默写。

1. C++ 程序的内存由哪几个部分组成？各有什么作用和特点？

C++ 程序内存分为 5 大区域：

2. 重写、重载、重定义的区别？

关键点：

• 重载看参数，不看返回值。
• 重写要求函数签名完全一致（C++11 可用 override 关键字检查）。
• 重定义会隐藏基类同名函数，需用 using Base::func; 引入。

3. strlen 和 sizeof 的区别？

char str[] = "hello";
strlen(str);  // 5
sizeof(str);  // 6（含末尾 '\0'）

char *p = "hello";
strlen(p);    // 5
sizeof(p);    // 8（64位系统指针大小）

4. C++ 中 const 关键字的作用？

1. 修饰变量：定义常量，不可修改。const int x = 10;
2. 修饰指针：
   • const int *p：指向常量的指针，不能通过 p 修改所指内容。
   • int *const p：常量指针，指针本身不可改指向。
   • const int *const p：两者都不可改。
3. 修饰函数参数：防止函数内部修改参数，常用于引用/指针传参。void func(const string &s)
4. 修饰函数返回值：返回值不可被修改。
5. 修饰成员函数：void func() const; 承诺不修改成员变量（mutable 变量除外），const 对象只能调用 const 成员函数。
6. 修饰引用：const int &r = x; 不可通过引用修改对象，可绑定临时对象。

编译期常量：C++11 起 constexpr 可用于编译期求值，比 const 更强。

5. C++ 中 static 关键字的作用？

注意：

• 静态成员变量在类内声明，类外定义（C++17 可用 inline static 直接初始化）。
• 静态成员函数不能声明为 const、virtual、volatile。
• 局部静态变量的初始化在 C++11 后是线程安全的（Magic Statics）。

6. C++ 中 class 和 struct 的区别？

本质相同：C++ 中 class 和 struct 几乎没有区别，都可以有成员函数、构造函数、析构函数、继承、多态等。唯一区别就是默认访问权限和默认继承方式。

使用惯例：

• struct：用于纯数据结构（POD），成员都是 public，无复杂行为。
• class：用于封装行为和数据，有明确的访问控制。

7. C++ 中类型转换有哪几种？

C++ 有 4 种显式类型转换运算符，比 C 风格强制转换更安全、更明确：

C 风格转换：(type)expr 会依次尝试 static_cast → const_cast → reinterpret_cast，不够明确，不推荐。

8. 简述 malloc / free 的实现原理。

malloc 实现（以 glibc ptmalloc 为例）：

1. 内存池管理：维护多个 bin（空闲块链表），按大小分类：
   • fast bin：小内存块（≤64B），LIFO 单链表，快速分配。
   • unsorted bin：刚释放的大块，未分类。
   • small bin / large bin：按大小排序的双向链表。
2. 分配流程：先查 fast bin → unsorted bin → small/large bin → 都不够则通过 brk() 扩展堆或 mmap() 映射新内存。
3. 块头信息：每个分配块前有 chunk header，记录块大小、是否使用、前一块大小等。
4. 内存对齐：返回的指针按 16 字节（64 位）对齐。

free 实现：

1. 根据传入指针找到 chunk header。
2. 标记为空闲，加入对应 bin。
3. 合并相邻空闲块（除 fast bin 外），减少外部碎片。
4. 若顶部空闲块足够大，通过 sbrk() 归还给 OS。

9. new / delete 与 malloc / free 的异同？

相同点：都在堆上分配内存，都需要手动释放，不能混用（new 的对象不能用 free，malloc 的内存不能用 delete）。

配对使用：new ↔ delete，new[] ↔ delete[]，malloc ↔ free。

10. 指针和引用的区别？

使用建议：

• 能用引用就用引用（更安全、更高效）。
• 需要表示"无对象"或需要改变指向时用指针。
• 函数参数优先用 const T&，避免拷贝且不修改。

11. 引用作为函数返回时为什么不能返回局部变量？

因为局部变量在函数返回时生命周期结束，栈空间被回收，返回的引用成为悬垂引用 (dangling reference)，访问它是未定义行为。

int& bad() {
    int x = 10;  // 局部变量，栈上
    return x;     // 错误：返回局部变量的引用
}  // x 在这里被销毁

int& r = bad();  // r 指向已销毁的栈内存
cout << r;       // 未定义行为！

可以返回引用的情况：

1. 返回传入的引用参数：int& func(int& x) { return x; }
2. 返回静态变量：int& func() { static int x; return x; }
3. 返回堆上对象：int& func() { return *new int; }（但需手动释放，不推荐）
4. 返回成员变量：int& get() { return m_x; }（对象生命周期内有效）

12. extern "C" 的用法？

extern "C" 告诉 C++ 编译器以 C 语言的方式进行链接，即不进行名字修饰 (name mangling)。

主要用途：

1. C++ 调用 C 代码：在 C++ 中包含 C 头文件时。
2. C 调用 C++ 代码：在 C++ 中导出可被 C 调用的函数。

// C++ 头文件
#ifdef __cplusplus
extern "C" {
#endif

void c_function(int x);
int another_func(const char *s);

#ifdef __cplusplus
}
#endif

注意事项：

• extern "C" 内不能有函数重载、默认参数、模板等 C++ 特性。
• 变量也可以用 extern "C" 声明。
• 只能在全局命名空间使用，不能在类内或命名空间内使用。
• 一个 extern "C" 块可以包含多个声明。

13. 内联函数和宏定义的区别？

// 宏的副作用问题
#define SQUARE(x) ((x)*(x))
int a = 5;
SQUARE(++a);  // 展开为 ((++a)*(++a))，a 被加两次！

// 内联函数安全
inline int square(int x) { return x * x; }
square(++a);   // a 只加一次

C++ 建议：优先用内联函数或 constexpr，避免宏。宏仅用于条件编译和 include guard。

14. 拷贝构造函数的调用时机？

拷贝构造函数在以下情况被调用：

1. 用一个对象初始化另一个对象：

   A a1;
   A a2 = a1;   // 拷贝构造（不是赋值！）
   A a3(a1);    // 拷贝构造
   

2. 函数参数按值传递：

   void func(A a);  // 调用时实参拷贝给形参
   func(a1);
   

3. 函数返回值按值返回（未被 RVO/NRVO 优化时）：

   A func() { A a; return a; }  // 返回时拷贝构造临时对象
   

4. 异常处理中按值抛出/捕获异常对象。

注意：

• A a2 = a1; 是拷贝构造，不是赋值运算符。赋值是对已存在对象：a2 = a1;
• C++11 起，返回值优化 (RVO/NRVO) 和移动语义可减少拷贝构造调用。
• 拷贝构造函数参数必须是 const 引用（见下题）。

15. 为什么拷贝构造函数必须传引用不能传值？

如果拷贝构造函数按值传参，会导致无限递归：

// 错误！按值传参
A(const A other) {  // 调用拷贝构造时，实参需要拷贝给形参 other
    // ...          // 而拷贝给形参又需要调用拷贝构造函数
}                    // → 无限递归，栈溢出

原理：按值传递参数本身就需要调用拷贝构造函数来创建形参副本。如果拷贝构造函数自己也按值传参，那么为了创建形参就需要再次调用拷贝构造函数，形成无限递归。

正确写法：

A(const A& other) {  // 传引用，不需要拷贝
    // 深拷贝成员
}

参数加 const 是因为：

• 不修改源对象。
• 可以接受 const 对象和临时对象（右值）作为参数。

16. 构造函数初始化和列表初始化的区别？

这里指构造函数体内赋值和初始化列表的区别：

// 方式1：构造函数体内赋值
A(int x, const string& s) {
    m_x = x;       // 先默认构造 m_x，再赋值
    m_s = s;       // 先默认构造 m_s，再赋值
}

// 方式2：初始化列表
A(int x, const string& s) : m_x(x), m_s(s) {
    // 直接构造，无默认构造步骤
}

初始化列表顺序：按成员在类中声明的顺序初始化，不是按列表书写顺序。析构顺序与构造顺序相反。

17. 虚函数表的作用和存储的地址？

虚函数表 (vtable) 是 C++ 实现动态多态的核心数据结构。

作用：存储类中所有虚函数的地址，实现运行时动态绑定。

存储内容：

• 每个有虚函数的类有一张虚函数表，存储在程序的只读数据段。
• 表中按虚函数声明顺序存放各虚函数的函数指针。
• 派生类重写的虚函数，在表中对应位置替换为派生类函数地址。
• 多重继承时，派生类可能有多个虚函数表。

对象中的 vptr：

• 每个有虚函数的对象包含一个虚函数表指针 (vptr)，指向对应类的虚函数表。
• vptr 在构造函数中初始化，指向当前类的 vtable。
• vptr 占用对象内存（64 位系统 8 字节）。

对象内存          类的虚函数表（只读数据段）
┌──────────┐     ┌──────────────────┐
│  vptr ───┼────→│ &Base::func1     │
│ 成员变量  │     │ &Base::func2     │
└──────────┘     └──────────────────┘

调用过程：obj.func() → 通过 vptr 找到 vtable → 根据函数索引找到函数地址 → 调用。

18. 构造函数可以设置成虚函数吗？为什么？

不可以，构造函数不能声明为虚函数。

原因：

1. 虚函数依赖 vptr：虚函数调用需要通过对象的 vptr 找到 vtable。但构造函数执行时，对象正在构造中，vptr 尚未正确初始化（构造函数中 vptr 指向当前类的 vtable，而非最终派生类的）。
2. 类型未确定：构造函数的作用是创建对象，在构造完成前对象的动态类型尚未确定，虚函数的动态绑定没有意义。
3. 语义矛盾：虚函数的目的是通过基类指针调用派生类实现，但构造函数是从基类到派生类依次执行的，构造基类部分时派生类还不存在。

相关概念：

• 构造函数中调用虚函数，会调用当前类的版本，不是派生类版本（因为派生类还没构造）。
• 析构函数可以且应该声明为虚函数（多态基类），确保通过基类指针删除派生类对象时正确调用派生类析构函数。

19. 虚函数和纯虚函数的区别？

class Base {
public:
    virtual void func1() { /* 默认实现 */ }  // 虚函数
    virtual void func2() = 0;                  // 纯虚函数
};

class Derived : public Base {
public:
    void func2() override { /* 必须实现 */ }  // 不实现则 Derived 也是抽象类
};

注意：

• 纯虚函数也可以在类外提供实现（void Base::func2() {}），派生类可通过 Base::func2() 调用。
• 析构函数可以是纯虚函数，但必须提供实现（否则派生类析构时链接错误）。
• 接口类（只有纯虚函数）相当于 Java 的 interface。

20. 为什么析构函数一般写成虚函数？

为了在多态场景下正确释放资源。

问题场景：

class Base {
public:
    ~Base() { /* 非虚析构 */ }
};
class Derived : public Base {
public:
    ~Derived() { /* 释放派生类资源 */ }
};

Base* p = new Derived();
delete p;  // 只调用 Base::~Base()，不调用 Derived::~Derived()！
           // → 派生类资源泄漏，未定义行为

将基类析构函数声明为 virtual 后：

class Base {
public:
    virtual ~Base() { }  // 虚析构
};
Base* p = new Derived();
delete p;  // 通过 vtable 动态绑定，先调用 Derived::~Derived()，再调用 Base::~Base()

规则：

• 基类有虚函数时，析构函数必须是虚函数（多态基类）。
• 不作为基类、不涉及多态的类，析构函数不必是虚函数（虚函数表指针会增加对象大小）。
• 析构函数可以是纯虚函数，但必须提供实现。

21. 动态多态和静态多态的实现过程？

静态多态（编译期多态）：

• 在编译期确定调用哪个函数。
• 实现方式：函数重载、模板、运算符重载。
• 优点：无运行时开销，性能好。
• 缺点：灵活性低，编译后固定。

// 函数重载
void func(int x);
void func(double x);  // 编译期根据参数类型决定调用哪个

// 模板
template<typename T>
T add(T a, T b) { return a + b; }  // 编译期实例化

动态多态（运行期多态）：

• 在运行期根据对象的实际类型决定调用哪个函数。
• 实现方式：继承 + 虚函数。
• 实现过程：基类指针/引用指向派生类对象 → 通过 vptr 找到 vtable → 根据函数索引找到派生类函数地址 → 调用。
• 优点：灵活，运行时可切换行为。
• 缺点：有运行时开销（vptr 查找、间接调用），对象体积增大。

class Base { virtual void func(); };
class Derived : public Base { void func() override; };
Base* p = new Derived();
p->func();  // 运行时确定调用 Derived::func()

C++17 补充：std::variant + std::visit 可实现类型安全的静态多态替代方案。

22. STL 中 vector 删除元素，迭代器如何变化？

erase 方法：

iterator erase(iterator pos);           // 删除单个元素，返回指向被删元素下一个元素的迭代器
iterator erase(iterator first, iterator last);  // 删除范围，返回 last 的下一个位置

迭代器变化：

• 被删除元素及其之后的所有迭代器、引用、指针全部失效。
• 删除点之前的迭代器仍然有效。
• erase 返回指向被删元素下一个位置的新有效迭代器。

正确的遍历删除方式：

// 方式1：使用 erase 返回值
for (auto it = vec.begin(); it != vec.end(); ) {
    if (should_delete(*it)) {
        it = vec.erase(it);  // 更新迭代器
    } else {
        ++it;
    }
}

// 方式2：C++20 std::erase / erase_if
std::erase_if(vec, [](int x){ return x % 2 == 0; });

错误写法：

for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (should_delete(*it)) {
        vec.erase(it);  // 错误：it 已失效，++it 是未定义行为
    }
}

23. map、set 是怎么实现的？红黑树怎么同时实现这两种容器？

map 和 set 底层都是红黑树 (red-black tree)，具体是 STL 中的 _Rb_tree。

红黑树的性质：

1. 节点非红即黑。
2. 根节点是黑色。
3. 叶子节点（NIL）是黑色。
4. 红色节点的子节点必须是黑色（不能有连续红节点）。
5. 从任一节点到其每个叶子的所有路径包含相同数量的黑节点。

保证树高 ≤ 2log(n+1)，插入/删除/查找都是 O(log n)。

map 和 set 的区别：

• set：键就是值，红黑树节点只存储键。
• map：键值对，红黑树节点存储 pair<const Key, Value>，按键排序。

同一棵红黑树实现两种容器：

• STL 的 _Rb_tree 是一个通用的红黑树模板，通过模板参数区分：
  • set 的 _Rb_tree 节点值类型就是 Key，比较器比较 Key。
  • map 的 _Rb_tree 节点值类型是 pair<const Key, Value>，比较器只比较 pair 的 first（Key）。
• 通过 _Select1st（取 pair 的 first）和 _Identity（取自身）等萃取器提取键。

multimap/multiset：也是红黑树，但允许重复键（插入时不做唯一性检查）。

24. C++11 的新特性有哪些？

核心语言特性：

1. auto：类型推导，编译器根据初始化表达式推导类型。
2. decltype：推导表达式的类型。
3. 范围 for 循环：for (auto& x : container)。
4. nullptr：类型安全的空指针常量，替代 NULL。
5. 右值引用 &&：支持移动语义和完美转发。
6. 移动构造/移动赋值：转移资源所有权，避免深拷贝。
7. std::move：将左值转为右值引用。
8. std::forward：完美转发，保持值类别。
9. lambda 表达式：匿名函数，支持捕获。
10. 智能指针：unique_ptr、shared_ptr、weak_ptr。
11. 统一初始化 {}：列表初始化，防止窄化转换。
12. =default / =delete：显式控制默认/删除特殊成员函数。
13. override / final：显式标记重写/禁止继承和重写。
14. constexpr：编译期常量表达式。
15. 委托构造函数：构造函数调用同类另一个构造函数。
16. 继承构造函数：using Base::Base; 继承基类构造函数。
17. 可变参数模板：template<typename... Args>。
18. 静态断言 static_assert：编译期断言。
19. 强类型枚举 enum class：有作用域、不会隐式转换。
20. 线程支持：std::thread、std::mutex、std::condition_variable。
21. 原子操作 std::atomic。
22. std::function / std::bind：可调用对象封装。
23. std::array：固定大小数组容器。
24. std::unordered_map / unordered_set：哈希表容器。
25. std::tuple：元组。

25. lambda 函数的全部知识？

基本语法：

[capture-list](params) mutable -> return-type { body }

1. 捕获列表：

• []：不捕获任何变量。
• [x]：按值捕获 x。
• [&x]：按引用捕获 x。
• [=]：按值捕获所有用到的外部变量。
• [&]：按引用捕获所有用到的外部变量。
• [=, &x]：默认按值，x 按引用。
• [&, x]：默认按引用，x 按值。
• [this]：捕获 this 指针。
• C++14：[x = expr] 初始化捕获（广义捕获）。

2. 参数列表：和普通函数一样，C++14 起可用 auto（泛型 lambda）。

3. mutable：允许修改按值捕获的变量（默认按值捕获的变量在 lambda 内是 const）。

4. 返回类型：可省略，编译器自动推导（单 return 语句时）。复杂情况需显式指定 -> type。

5. 函数体：执行逻辑。

本质：lambda 是编译器生成的匿名类（闭包类型）的对象，捕获的变量成为类的成员变量，operator() 是函数调用。

注意事项：

• 按引用捕获时，需确保被引用变量的生命周期长于 lambda。
• lambda 可赋值给 std::function。
• 无捕获的 lambda 可隐式转换为函数指针。
• 递归 lambda 需要用 std::function 或 Y-combinator。

26. C++ 中的智能指针？

C++11 引入三种智能指针，在 <memory> 头文件中：

1. unique_ptr（独占所有权）：

• 同一时间只能有一个 unique_ptr 指向对象。
• 不可拷贝，只能移动（std::move）。
• 轻量，无额外开销（和裸指针一样大）。

auto p = std::make_unique<int>(42);  // C++14
auto p2 = std::move(p);  // 所有权转移，p 变为 nullptr

2. shared_ptr（共享所有权）：

• 多个 shared_ptr 可指向同一对象，通过引用计数管理生命周期。
• 引用计数为 0 时自动释放对象。
• 有额外开销（控制块，包含引用计数、删除器等）。
• 线程安全：引用计数的增减是原子操作，但对象本身的访问不是线程安全的。

auto p1 = std::make_shared<int>(42);
auto p2 = p1;  // 引用计数 +1
p1.use_count(); // 2

3. weak_ptr（弱引用）：

• 不拥有对象，不增加引用计数。
• 用于解决 shared_ptr 的循环引用问题。
• 通过 lock() 获取 shared_ptr（对象已释放则返回空）。
• 通过 expired() 检查对象是否已释放。

auto sp = std::make_shared<int>(42);
std::weak_ptr<int> wp = sp;
if (auto p = wp.lock()) { /* 对象还在 */ }

循环引用问题：

struct A { std::shared_ptr<B> b; };
struct B { std::shared_ptr<A> a; };  // 循环引用，内存永远不释放
// 解决：将其中一个改为 weak_ptr

选择建议：

• 默认用 unique_ptr，需要共享时用 shared_ptr。
• 观察者模式、打破循环引用用 weak_ptr。
• 避免用裸指针管理内存，优先用 make_unique / make_shared。

27. 面向对象的三大特性？

1. 封装 (Encapsulation)：

   • 将数据和操作数据的方法绑定在类中，隐藏内部实现细节。
   • 通过访问控制符（public/private/protected）限制外部访问。
   • 目的：降低耦合、保护数据安全、便于维护。

2. 继承 (Inheritance)：

   • 派生类（子类）继承基类（父类）的成员和接口。
   • 实现代码复用和层次化设计。
   • C++ 支持单继承、多继承、虚继承。
   • 派生类可扩展新成员，也可重写（override）基类虚函数。

3. 多态 (Polymorphism)：

   • 同一接口，不同实现。
   • 静态多态：编译期确定，如函数重载、模板。
   • 动态多态：运行期确定，通过继承 + 虚函数实现，基类指针/引用指向派生类对象时调用派生类方法。
   • 目的：提高代码灵活性和可扩展性，符合开闭原则（对扩展开放，对修改关闭）。

28. 什么是多态？

多态（Polymorphism）指同一接口具有多种不同的实现形式，即"一个接口，多种方法"。

C++ 中的多态分为两类：

1. 静态多态（编译期多态）：

• 在编译时就确定调用哪个函数。
• 实现方式：函数重载、运算符重载、模板。
• 优点：无运行时开销。

void print(int x);
void print(double x);  // 重载，编译期根据参数决定
print(3);    // 调用 print(int)
print(3.14); // 调用 print(double)

2. 动态多态（运行期多态）：

• 在运行时根据对象的实际类型决定调用哪个函数。
• 实现条件：继承 + 虚函数 + 基类指针/引用。
• 实现机制：虚函数表 (vtable) + 虚函数表指针 (vptr)。

class Animal { virtual void speak(); };
class Dog : public Animal { void speak() override { cout << "汪汪"; } };
class Cat : public Animal { void speak() override { cout << "喵喵"; } };

Animal* a = new Dog();
a->speak();  // 运行时确定调用 Dog::speak()，输出"汪汪"
a = new Cat();
a->speak();  // 运行时确定调用 Cat::speak()，输出"喵喵"

多态的意义：提高代码的可扩展性和灵活性，新增功能只需新增派生类，不需修改原有代码（开闭原则）。

29. C++ 的多态如何实现？

C++ 动态多态通过 继承 + 虚函数 + 虚函数表 (vtable) 实现。

实现机制：

1. 虚函数表 (vtable)：

   • 每个有虚函数的类，编译器为其生成一张虚函数表，存储在只读数据段。
   • 表中按虚函数声明顺序存放各虚函数的函数指针。
   • 派生类重写的虚函数，在表中对应位置替换为派生类函数地址。

2. 虚函数表指针 (vptr)：

   • 每个有虚函数的对象包含一个隐藏的 vptr，指向其类的 vtable。
   • vptr 在构造函数中初始化，在析构函数中调整。
   • vptr 占用对象内存（64 位系统 8 字节）。

3. 动态绑定过程：

   Base* p = new Derived();
   p->virtualFunc();
   ① 通过 p 找到对象的 vptr
   ② 通过 vptr 找到 Derived 类的 vtable
   ③ 根据函数在 vtable 中的索引，找到 Derived::virtualFunc 的地址
   ④ 调用该函数
   

必要条件：

• 必须通过指针或引用调用虚函数（对象直接调用会静态绑定）。
• 函数必须声明为 virtual。
• 派生类必须重写该虚函数（函数签名一致）。

静态多态：通过模板和函数重载在编译期实现，无运行时开销。

30. 基类和派生类的构造函数和析构函数的执行顺序？

构造顺序（从内到外）：

1. 基类构造函数（多继承时按继承声明顺序，虚继承优先）。
2. 成员变量构造（按声明顺序，不是初始化列表顺序）。
3. 派生类构造函数体。

析构顺序（从外到内，与构造相反）：

1. 派生类析构函数体。
2. 成员变量析构（按声明逆序）。
3. 基类析构函数。

class Base {
public:
    Base() { cout << "Base 构造\n"; }
    ~Base() { cout << "Base 析构\n"; }
};

class Member {
public:
    Member() { cout << "Member 构造\n"; }
    ~Member() { cout << "Member 析构\n"; }
};

class Derived : public Base {
    Member m_;
public:
    Derived() { cout << "Derived 构造\n"; }
    ~Derived() { cout << "Derived 析构\n"; }
};

// 输出：
// Base 构造
// Member 构造
// Derived 构造
// Derived 析构
// Member 析构
// Base 析构

注意：

• 构造函数中调用虚函数，会调用当前类的版本（派生类还未构造）。
• 多态基类的析构函数必须是虚函数，否则通过基类指针删除派生类对象时不会调用派生类析构函数。
• 虚继承时，虚基类的构造函数由最派生类负责调用，且只调用一次。

31. 深拷贝和浅拷贝？如何实现？

浅拷贝 (Shallow Copy)：

• 只拷贝对象的成员变量的值，包括指针的值（地址）。
• 拷贝后两个对象的指针指向同一块内存。
• 问题：一个对象释放内存后，另一个对象的指针成为野指针；析构时 double free。
• 编译器默认生成的拷贝构造函数和赋值运算符就是浅拷贝。

深拷贝 (Deep Copy)：

• 不仅拷贝成员变量，还为指针指向的资源分配新的内存并拷贝内容。
• 拷贝后两个对象拥有独立的资源，互不影响。
• 需要自定义拷贝构造函数和赋值运算符。

class String {
    char* data_;
    int size_;
public:
    // 深拷贝构造函数
    String(const String& other) {
        size_ = other.size_;
        data_ = new char[size_ + 1];  // 分配新内存
        strcpy(data_, other.data_);     // 拷贝内容
    }

    // 深拷贝赋值运算符（Copy-and-Swap 惯用法）
    String& operator=(String other) {  // 按值传参，自动拷贝
        swap(*this, other);
        return *this;
    }

    ~String() { delete[] data_; }
};

什么时候需要深拷贝：类中包含指针成员且拥有该指针指向的资源时。

C++11 替代方案：用智能指针（unique_ptr 独占、shared_ptr 共享）管理资源，避免手动深拷贝。

32. virtual() = 0 是什么意思？

这是纯虚函数 (pure virtual function) 的声明语法。

virtual void func() = 0;  // 纯虚函数

含义：

• 声明了一个虚函数，但在基类中不提供实现（也可以提供，见下）。
• = 0 告诉编译器该函数是纯虚的。
• 包含纯虚函数的类是抽象类 (abstract class)，不能实例化。
• 派生类必须实现所有纯虚函数，否则派生类也是抽象类。

class Shape {
public:
    virtual double area() const = 0;  // 纯虚函数，定义接口
    virtual ~Shape() = default;
};

class Circle : public Shape {
public:
    double area() const override { return 3.14 * r_ * r_; }  // 必须实现
};

Shape s;  // 错误：抽象类不能实例化
Shape* p = new Circle();  // 正确

注意：

• 纯虚函数也可以在类外提供实现：void Shape::func() {}，派生类可通过 Shape::func() 调用。
• 纯虚析构函数必须提供实现（否则链接错误）。
• 接口类（所有函数都是纯虚函数）相当于 Java 的 interface。

📌 中频题（24题）

比较常见，部分公司会问到，建议理解并能口述要点。

1. 浮点数的编码方式是什么？简述原理。

遵循 IEEE 754 标准，将实数表示为科学计数法形式：

V = (-1)^S × (1 + M) × 2^(E - bias)

关键特性：

• 尾数隐含前导 1（hidden bit），节省 1 bit 提高精度。
• 指数用偏移码表示，避免负指数。
• 特殊值：E 全 0 表示非规格化数/0；E 全 1 表示 ∞ 或 NaN。
• 浮点数精度有限，比较时应使用容差（如 fabs(a-b) < 1e-6）。

2. 可执行程序是如何生成的？

四个步骤：预处理 → 编译 → 汇编 → 链接

1. 预处理：展开头文件（#include）、宏替换（#define）、去掉注释、处理条件编译（#ifdef）。生成 .i 文件。
2. 编译：将预处理后的代码翻译成汇编代码，进行语法/语义检查、优化。生成 .s 文件。
3. 汇编：将汇编代码翻译成机器码（二进制目标文件）。生成 .o / .obj 文件。
4. 链接：将多个目标文件和库文件合并，解析符号引用、分配地址，生成可执行文件（.exe / ELF）。

链接又分为静态链接（库代码嵌入可执行文件）和动态链接（运行时加载共享库 .so/.dll）。

3. 可执行程序是如何变成进程的？

1. 加载：OS 将可执行文件从磁盘读入内存，通过缺页中断按需加载代码段和数据段。
2. 创建进程控制块 (PCB)：OS 为进程分配 PID，创建 task_struct，记录进程状态、寄存器、内存映射、文件描述符等。
3. 建立虚拟地址空间：创建页表，将进程的虚拟地址映射到物理内存。
4. 设置运行上下文：初始化程序计数器（PC）指向入口函数（_start → main），设置栈指针。
5. 调度执行：进程进入就绪队列，OS 调度器分配 CPU 时间片后开始执行。

4. 在 C 语言中如何调用 C++ 函数？

C 不能直接调用 C++ 函数，因为 C++ 有名字修饰 (name mangling)（支持函数重载），而 C 没有。

方法：在 C++ 中用 extern "C" 声明需要被 C 调用的函数，禁止名字修饰：

// C++ 文件
#ifdef __cplusplus
extern "C" {
#endif

void my_function(int x);  // 以 C 方式链接

#ifdef __cplusplus
}
#endif

/* C 文件 */
extern void my_function(int x);
my_function(42);

注意：extern "C" 内不能有函数重载、默认参数等 C++ 特性。对于成员函数，需提供非成员包装函数。

5. 常见的 C/C++ 缺陷和陷阱有哪些？

1. 内存管理：野指针、悬垂指针、内存泄漏、重复释放、越界访问。
2. 未定义行为 (UB)： signed 整数溢出、移位越界、取消引用空指针、访问已释放内存等，结果不可预测。
3. 全局/静态变量初始化顺序：不同编译单元间的全局变量初始化顺序未定义（static initialization order fiasco）。
4. 隐式类型转换：整型提升、有符号/无符号比较、精度丢失（如 float 转 int 截断）。
5. 运算符优先级：如 << 低于 +，== 高于 &，易写错。
6. 数组越界：C/C++ 不做边界检查，缓冲区溢出可导致安全漏洞。
7. 头文件重复包含：需用 #ifndef 或 #pragma once 保护。
8. 临时对象生命周期：返回局部变量的引用/指针、绑定临时对象的引用延长生命周期的误用。

6. 二维数组是什么？函数指针是什么？

二维数组：数组的数组，在内存中按行优先连续存储。

int arr[3][4];  // 3行4列，arr 是 int[4] 类型的数组
// arr[i][j] 等价于 *(*(arr+i)+j)

• 二维数组名退化为指向第一行的指针（int (*)[4]），不是 int**。
• 作为函数参数时，第二维大小必须指定：void func(int arr[][4], int rows)。

函数指针：指向函数的指针，存储函数的入口地址。

// 声明：返回值类型 (*指针名)(参数类型列表)
int (*fp)(int, int);  // fp 是指向"返回int、接受两个int参数"的函数的指针

// 赋值与调用
fp = add;
int result = fp(3, 4);  // 等价于 (*fp)(3, 4)

函数指针常用于回调函数、策略模式、跳转表等场景。

7. 函数指针和指针函数的区别？

// 函数指针：返回值类型 (*指针名)(参数列表)
int (*fp)(int, int);   // fp 是指向函数的指针

// 指针函数：返回值类型 *函数名(参数列表)
int *func(int x);       // func 是返回 int* 的函数

记忆技巧：看 * 和谁结合——*fp() 中 () 优先级高，fp 先和 () 结合是函数；(*fp)() 中 * 先和 fp 结合是指针。

8. void* 的大小是多少？

void* 是指针类型，其大小等于系统的地址总线宽度：

• 32 位系统：4 字节
• 64 位系统：8 字节

注意：

• void* 可以指向任意类型的数据，但不能直接解引用（*p 非法），需先转换为具体类型指针。
• C++ 中不允许 void* 隐式转换为其他类型指针（C 可以），需用 static_cast 显式转换。
• 函数指针不能直接用 void* 存储（POSIX 允许但标准不保证）。

9. 为何 free(p) 时只需传递堆空间地址？

因为 malloc 分配时在返回指针的前面存储了块的元信息（chunk header），包含块大小等。

┌──────────────┬─────────────────────┐
│ chunk header │ 用户数据区           │
│ (大小/标志)  │ p 指向这里          │
└──────────────┴─────────────────────┘

free(p) 时：

1. 通过 p - sizeof(header) 找到块头。
2. 从块头读取块大小，知道要释放多少内存。
3. 标记为空闲，插入空闲链表，合并相邻块。

注意：

• 必须释放 malloc 返回的原始指针，不能释放偏移后的指针。
• 同一块不能重复 free（double free）。
• 栈上内存不能用 free 释放。

10. malloc 申请内存后，怎么保证一定申请到了？

malloc 分配失败时返回 NULL，因此必须检查返回值：

int *p = (int*)malloc(sizeof(int) * 100);
if (p == NULL) {
    // 分配失败，处理错误
    perror("malloc failed");
    exit(EXIT_FAILURE);
}

C++ new 的区别：

• new 失败默认抛 std::bad_alloc 异常（不会返回 NULL）。
• new (nothrow) 失败返回 nullptr。

注意事项：

• 不要假设 malloc 一定成功，尤其是分配大块内存或内存紧张时。
• malloc(0) 的行为由实现定义，可能返回 NULL 或唯一指针。
• Linux 下 malloc 可能出现"过度承诺"（overcommit），分配成功不代表物理内存真的可用，写入时才可能 OOM。

11. 静态变量什么时候初始化？

分两种情况：

1. 全局/命名空间/类静态变量：

• 编译期确定初始值的（常量初始化）：在程序加载时初始化，早于 main。
• 需要动态初始化的（如调用构造函数）：在 main 函数之前，按同一编译单元内定义顺序初始化；不同编译单元间顺序未定义。
• 程序结束时按初始化逆序销毁。

2. 局部静态变量：

• 在第一次执行到定义处时初始化（懒初始化）。
• C++11 起，初始化是线程安全的（Magic Statics），多个线程同时首次访问时只有一个线程执行初始化。
• 程序结束时销毁（在全局变量之后）。

注意：

• 静态变量只初始化一次，后续调用跳过初始化。
• 不同编译单元全局静态变量的初始化顺序问题称为 "static initialization order fiasco"，可用局部静态变量或 Meyers Singleton 规避。

12. inline 函数的使用？

inline 建议编译器在调用点直接展开函数体，消除函数调用开销。

使用场景：

• 函数体短小（通常 1-3 行），调用频繁。
• 类内定义的成员函数默认是 inline。
• 头文件中定义的函数需加 inline，避免多重定义错误。

注意事项：

1. inline 只是建议：编译器可以忽略，函数体过大、有循环、递归、虚函数、取地址等情况通常不会内联。
2. 定义必须可见：inline 函数的定义必须放在头文件中，每个编译单元都能看到。
3. 不能和 virtual 共存：虚函数需要运行时绑定，一般不会内联（通过对象直接调用时可能内联）。
4. 调试困难：内联后没有独立函数符号，断点可能不生效。
5. 代码膨胀：过度内联会增大可执行文件体积，导致指令缓存命中率下降。

C++17 补充：inline 也可用于变量，解决头文件中全局变量的多重定义问题。

13. 虚函数表里存放的内容是什么时候写进去的？

虚函数表在编译期确定内容，在程序加载时写入内存（只读数据段）。

具体过程：

1. 编译期：编译器分析每个类的虚函数，为每个有虚函数的类生成一张虚函数表，表中填入各虚函数的地址。
   • 基类的 vtable 填基类虚函数地址。
   • 派生类的 vtable：未重写的填基类地址，重写的填派生类地址，新增的虚函数追加在表后。
2. 链接期：符号解析，确定虚函数的最终地址。
3. 程序加载时：OS 将 vtable 加载到内存的只读数据段，之后不再修改。

vptr 的设置时机：

• 对象的 vptr 在构造函数执行时被设置为指向对应类的 vtable。
• 构造过程中，vptr 会随构造层次变化：基类构造时指向基类 vtable，派生类构造时指向派生类 vtable。
• 析构时反向变化。

14. 模板和实现可不可以不写在一个文件里？

可以，但需要特殊处理。默认情况下，模板的定义和实现必须放在同一个文件（通常是头文件）中，因为模板是编译期实例化的，编译器需要看到完整定义才能生成具体类型的代码。

分离的方法：

方法1：显式实例化 (Explicit Instantiation)

// template.h - 声明
template<typename T>
class MyClass {
public:
    void func();
};

// template.cpp - 实现 + 显式实例化
#include "template.h"
template<typename T>
void MyClass<T>::func() { /* 实现 */ }

// 显式实例化只支持指定类型
template class MyClass<int>;
template class MyClass<double>;

缺点：只能用于已知类型，无法支持任意类型。

方法2：包含模型 (Inclusion Model) - 最常用
将实现写在头文件中，或在头文件末尾 #include "template_impl.hpp"。

方法3：C++11 extern template
在头文件中用 extern template class MyClass<int>; 阻止隐式实例化，在某个 cpp 中显式实例化。减少编译时间。

为什么默认不能分离：模板不是具体代码，是"代码生成蓝图"，编译器在实例化时才生成具体代码，需要看到完整定义。

15. 假设有一个指针，如何做到多次使用，一次释放？

使用 shared_ptr 实现共享所有权，引用计数归零时自动释放。

#include <memory>

auto sp = std::make_shared<MyClass>();

// 多次使用，每次拷贝 shared_ptr，引用计数 +1
void use1(std::shared_ptr<MyClass> p) { /* 使用 */ }
void use2(std::shared_ptr<MyClass> p) { /* 使用 */ }

use1(sp);  // 拷贝，引用计数 +1，函数结束后 -1
use2(sp);  // 同上

// 所有 shared_ptr 都销毁时，引用计数为 0，自动释放

其他方案：

1. 资源获取即初始化 (RAII)：用类管理资源，构造时获取，析构时释放。
2. 所有权转移：用 unique_ptr + move，明确唯一所有者。
3. 引用计数自定义实现：自己管理引用计数（不推荐，shared_ptr 已实现）。

注意：

• shared_ptr 不是线程安全的（对象访问需加锁），但引用计数增减是原子的。
• 避免循环引用，必要时用 weak_ptr。
• 不要用同一个裸指针初始化多个 shared_ptr（会导致 double free），应用 shared_ptr 拷贝。

16. 32 位/64 位系统具体指什么？对系统有何影响？

32 位/64 位指的是 CPU 的通用寄存器宽度和数据总线宽度，即一次能处理的数据位数。

对系统的影响：

1. 内存寻址能力：64 位可支持远超 4GB 的内存，适合大内存需求（数据库、科学计算）。
2. 性能：64 位寄存器可一次处理更多数据，部分运算更快；但指针变大导致内存占用增加、缓存压力增大。
3. 兼容性：64 位系统通常可运行 32 位程序（需安装 32 位库），反之不行。
4. 数据模型：注意 long 在 Windows 64 位仍是 4 字节 (LLP64)，在 Linux/Mac 是 8 字节 (LP64)。
5. 文件大小：64 位原生支持大文件（>2GB），32 位需用 off64_t 等扩展。

17. 虚拟内存和物理内存的区别？

虚拟内存的核心机制：

1. 分页：将虚拟地址空间和物理内存都划分为固定大小的页（通常 4KB）。
2. 页表：维护虚拟页到物理页的映射。
3. 缺页中断：访问的页不在物理内存时，OS 将其从磁盘加载到内存。
4. 页面置换：物理内存不足时，将不常用的页换出到磁盘（LRU 等算法）。
5. TLB：快表，缓存页表项，加速地址翻译。

优势：进程隔离、安全保护、内存超卖（overcommit）、简化编程模型（每个进程认为自己独占内存）。

18. 面向过程和面向对象的区别？

面向对象三大特性：

1. 封装：隐藏内部实现，对外提供接口，降低耦合。
2. 继承：子类复用父类代码和接口，实现代码复用和层次结构。
3. 多态：同一接口不同实现，运行时根据对象类型调用对应方法（动态多态）。

C++ 的特点：C++ 是多范式语言，同时支持面向过程、面向对象、泛型编程、函数式编程等，不强制使用 OOP。

19. 空类里有什么函数？

一个空类 class Empty {}; 中，编译器会隐式生成以下成员函数（在需要时才生成）：

1. 默认构造函数：Empty()
2. 拷贝构造函数：Empty(const Empty&)
3. 移动构造函数（C++11）：Empty(Empty&&)
4. 拷贝赋值运算符：Empty& operator=(const Empty&)
5. 移动赋值运算符（C++11）：Empty& operator=(Empty&&)
6. 析构函数：~Empty()

注意：

• 这些函数只有在被使用时才会被编译器生成（not declared until used）。
• sizeof(Empty) = 1（空类大小不为 0，确保不同对象有不同地址）。
• 如果用户声明了任何构造函数，编译器不再生成默认构造函数。
• C++11 可用 =default 显式要求生成，=delete 禁止生成。

20. public/private/protected 继承的关系及应用场景？

应用场景：

1. public 继承（最常用）：

   • 表示 "is-a" 关系，派生类是基类的一种。
   • 基类接口对外可见，符合里氏替换原则。
   • 例：class Dog : public Animal。

2. protected 继承：

   • 基类的 public 成员在派生类中变为 protected，对外不可见，但对派生类的子类可见。
   • 用于希望继承基类实现，但不暴露基类接口，且允许进一步派生的场景。
   • 较少使用。

3. private 继承：

   • 表示 "根据...实现"（is-implemented-in-terms-of），不是 is-a 关系。
   • 基类所有成员在派生类中变为 private，完全隐藏。
   • 用于复用基类实现但不继承接口的场景。
   • 通常优先用组合（包含一个基类对象）替代 private 继承，因为组合更灵活、耦合更低。

// private 继承 vs 组合
class Timer { public: void start(); };

// private 继承
class Widget : private Timer { /* 复用 Timer 实现 */ };

// 组合（推荐）
class Widget {
private:
    Timer timer_;  // 包含一个 Timer 对象
};

21. string 的赋值操作是深拷贝还是浅拷贝？

深拷贝。std::string 的赋值运算符会分配新的内存并拷贝字符串内容，两个 string 对象拥有独立的内存。

std::string s1 = "hello";
std::string s2 = s1;   // 深拷贝，s2 有自己的内存
s2[0] = 'H';           // 修改 s2 不影响 s1
cout << s1;  // "hello"
cout << s2;  // "Hello"

注意：

• 历史上某些标准库实现过写时复制 (COW, Copy-On-Write)，即拷贝时先共享内存，修改时才深拷贝。但 C++11 标准后，COW 实现因线程安全问题被禁止（至少 libstdc++ 和 libc++ 都不再使用 COW）。
• std::string 内部有 SSO（小字符串优化），短字符串直接存在对象内部，连堆分配都不需要。
• C++17 引入 std::string_view，是浅拷贝（只拷贝指针和长度，不拥有数据），用于只读视图，需注意源字符串的生命周期。

22. 什么时候重载赋值运算符与拷贝构造函数？

需要自定义拷贝构造函数和赋值运算符的情况：类中包含指针成员或管理动态分配的资源（如文件句柄、网络连接、互斥锁等），且需要深拷贝语义时。

规则三 (Rule of Three)：如果需要自定义析构函数、拷贝构造函数、拷贝赋值运算符中的任何一个，通常三个都需要自定义。

规则五 (Rule of Five, C++11)：在规则三基础上，加上移动构造函数和移动赋值运算符。

class Resource {
    int* data_;
public:
    Resource() : data_(new int[100]) {}
    ~Resource() { delete[] data_; }  // 1. 自定义析构

    Resource(const Resource& other)          // 2. 拷贝构造
        : data_(new int[100]) {
        std::copy(other.data_, other.data_+100, data_);
    }

    Resource& operator=(const Resource& other) {  // 3. 拷贝赋值
        if (this != &other) {
            delete[] data_;
            data_ = new int[100];
            std::copy(other.data_, other.data_+100, data_);
        }
        return *this;
    }

    Resource(Resource&& other) noexcept           // 4. 移动构造
        : data_(other.data_) {
        other.data_ = nullptr;
    }

    Resource& operator=(Resource&& other) noexcept {  // 5. 移动赋值
        if (this != &other) {
            delete[] data_;
            data_ = other.data_;
            other.data_ = nullptr;
        }
        return *this;
    }
};

不需要自定义的情况：类的成员都是值类型（如 int、double、std::string、智能指针），编译器默认生成的浅拷贝就足够（因为这些成员自己管理资源）。

零规则 (Rule of Zero)：优先使用智能指针和标准容器，让它们管理资源，自己不需要写任何特殊成员函数。

23. 什么地方需要用到拷贝构造函数？

拷贝构造函数在以下场景被自动调用：

1. 用一个对象初始化另一个新对象：

   A a1;
   A a2 = a1;   // 拷贝构造（注意：不是赋值！）
   A a3(a1);    // 拷贝构造
   A a4 = A(a1); // 拷贝构造（可能被优化）
   

2. 函数参数按值传递：

   void func(A a);  // 形参 a 是实参的拷贝
   func(a1);        // 调用拷贝构造
   

3. 函数返回值按值返回（未被 RVO/NRVO 优化时）：

   A func() {
       A a;
       return a;  // 用 a 拷贝构造返回值临时对象
   }
   

4. 异常处理：按值抛出异常对象、按值捕获异常对象时。

5. STL 容器操作：如 vector.push_back()、容器扩容时元素拷贝、insert 等。

注意：

• A a2 = a1; 是拷贝构造，a2 = a1;（a2 已存在）是赋值运算符。
• C++11 起，移动构造函数在右值场景下优先于拷贝构造。
• 拷贝构造函数的参数必须是 const 引用，否则会无限递归。

24. sizeof(A) 是多少？（空类/含虚函数类等）

需要根据类的具体成员来计算，遵循内存对齐规则：

常见情况：

// 1. 空类
class Empty {};
sizeof(Empty);  // 1（空类大小不为0，确保不同对象地址不同）

// 2. 只有一个 int 成员
class A { int x; };
sizeof(A);  // 4

// 3. 有虚函数
class B { virtual void func(); };
sizeof(B);  // 8（64位）/ 4（32位），只有 vptr，没有成员变量

// 4. 有成员变量和虚函数
class C {
    int x;        // 4
    virtual void func();  // vptr 8
};
sizeof(C);  // 16（vptr 8 + int 4 + 对齐填充 4）

// 5. 继承
class D : public C {
    int y;  // 4
};
sizeof(D);  // 16（C 的 16 + int 4 → 对齐到 16？实际是 24，取决于布局）

内存对齐规则：

1. 每个成员的偏移量必须是其自身大小的整数倍。
2. 结构体总大小必须是最大成员大小的整数倍。
3. 可通过 #pragma pack(n) 或 alignas 修改对齐方式。

影响 sizeof 的因素：

• 非静态成员变量（按声明顺序排列，受对齐影响）。
• 虚函数表指针 vptr（有虚函数时）。
• 虚基类表指针 vbtbl（虚继承时）。
• 对齐填充字节。
• 静态成员、成员函数不占对象大小。

💡 低频题（9题）

较少出现或较偏，时间充裕时了解即可。

1. 什么时候分配内存会产生内存碎片？

内存碎片分为内部碎片和外部碎片，主要产生场景：

1. 频繁动态分配/释放小块内存：释放的内存块大小各异、位置分散，无法有效合并成连续大块，形成外部碎片。
2. 内存分配算法的对齐需求：为满足内存对齐，分配比实际需要更大的块，导致内部碎片。
3. 多进程/多线程并发分配：不同执行流交错申请释放，使空闲块分散。
4. 长期运行程序：长时间运行后，小块分配释放累积，碎片问题加剧。

缓解方法：内存池、对象池、减少小块频繁分配、使用 slab 分配器等。

2. 负数的编码方式是什么？简述原理。

计算机中负数采用补码表示。

原理：

• 最高位为符号位，0 表示正，1 表示负。
• 正数的原码、反码、补码相同。
• 负数补码 = 绝对值的原码 → 除符号位外取反（反码）→ 加 1。
• 补码的本质是模运算：在有限位编码中，x - y = x + (-y的补码)，减法可统一为加法。

优势：统一加减法运算、0 的表示唯一（原码中 +0 和 -0 不同）、简化硬件电路设计。

3. string 的 SSO 模式？

SSO (Small String Optimization，小字符串优化)：当字符串较短时，直接将数据存储在 string 对象内部的栈空间，避免堆分配。

原理：

• std::string 对象通常包含指针、大小、容量三个成员（共 24 字节，64 位）。
• 当字符串长度 ≤ 某个阈值（通常 15 字节）时，复用内部缓冲区存储数据，不调用 new。
• 超过阈值时，才在堆上分配内存。

优势：

• 短字符串无需堆分配，减少内存碎片和分配开销。
• 提高缓存命中率，访问更快。

不同实现：

• libstdc++ (GCC)：阈值 15 字节。
• libc++ (Clang)：阈值 22 字节（用更紧凑的表示）。
• MSVC：阈值 15 字节。

4. 动态编译与静态编译？

静态编译命令：

g++ -static main.cpp -o app  # 静态链接所有库

动态编译命令（默认）：

g++ main.cpp -o app -lmylib  # 动态链接 libmylib.so

实际选择：发布独立工具用静态编译；系统级库用动态编译节省资源。

5. 类中静态函数占用内存吗？

不占用对象的内存。静态成员函数属于类，不属于任何对象，没有 this 指针。

内存分布：

• 静态成员变量：存储在全局/静态区，所有对象共享一份，不计入 sizeof(类)。
• 静态成员函数：代码存储在程序代码区，和普通函数一样只有一份，不计入对象大小。
• 非静态成员函数：代码也只有一份，通过 this 指针区分不同对象，也不计入对象大小。

class A {
    int x;          // 4 字节
    static int y;   // 不在对象中
    void func() {}  // 不在对象中
    static void s_func() {}  // 不在对象中
};
sizeof(A);  // 4（只有非静态成员变量 x，可能有对齐填充）

对象内存只包含：非静态成员变量 + 虚函数表指针（如有虚函数）+ 对齐填充。

6. 动态指针的判空？

动态指针（new 出来的指针）判空需要注意：

C++ new 的行为：

• 默认 new 失败抛 std::bad_alloc 异常，不会返回 nullptr，所以 if (p == nullptr) 在异常模式下永远为真（除非用了 nothrow）。
• new (std::nothrow) 失败返回 nullptr，需要判空。

// 方式1：异常模式（默认）
try {
    int* p = new int[1000000];
    // p 一定非空
} catch (const std::bad_alloc& e) {
    // 分配失败处理
}

// 方式2：nothrow 模式
int* p = new (std::nothrow) int[1000000];
if (p == nullptr) {
    // 分配失败
}

其他判空场景：

• 函数返回动态指针时，调用方应判空。
• malloc 返回的指针必须判空（失败返回 NULL）。
• 智能指针 unique_ptr/shared_ptr 可用 if (ptr) 或 ptr != nullptr 判空。
• 避免野指针：delete 后应置为 nullptr，否则判空无意义。

7. 编译器的优化级别及基本优化思想？

GCC/Clang 优化级别：

基本优化思想：

1. 常量传播与折叠：编译期计算常量表达式，直接替换结果。
2. 死代码消除：删除不可达或无副作用的代码。
3. 公共子表达式消除 (CSE)：重复计算的表达式只算一次。
4. 循环优化：循环展开、循环不变量外提、循环合并、循环分块。
5. 函数内联：将小函数体展开到调用点，消除调用开销。
6. 向量化 (SIMD)：将标量循环转换为 SIMD 指令，并行处理多个数据。
7. 指令调度：重排指令减少流水线停顿和数据依赖。
8. 寄存器分配：尽量将常用变量放在寄存器，减少内存访问。
9. 缓存优化：改进数据访问模式和布局，提高缓存命中率。
10. 尾调用优化：将尾递归转为循环，避免栈溢出。

注意：优化可能改变程序行为（如浮点精度、未定义行为的表现），调试时用 -O0，发布时用 -O2。

8. A 继承 B、C 两个空类，对 A 强转成 B、C，地址空间有什么变化？

这涉及多重继承中的对象布局和指针调整。

class B {};  // 空类，sizeof(B) = 1
class C {};  // 空类，sizeof(C) = 1
class A : public B, public C {};

对象布局（典型实现）：

A 对象内存：
┌──────────┐ ← this (A*)  同时也是 B 子对象地址
│ B 子对象  │
├──────────┤ ← C 子对象地址（可能有偏移）
│ C 子对象  │
└──────────┘

指针转换时的地址变化：

• A* → B*：地址不变（B 是第一个基类，B 子对象在 A 对象起始位置）。
• A* → C*：地址增加一个偏移量（C 子对象在 B 子对象之后），编译器自动调整指针。

A a;
A* pa = &a;
B* pb = static_cast<B*>(pa);  // pb == pa，地址不变
C* pc = static_cast<C*>(pa);  // pc = pa + sizeof(B)，地址增加

反向转换：

• B* → A*：如果 B 是第一个基类，地址不变；否则需要调整。
• C* → A*：地址减去偏移量。
• dynamic_cast 可在运行时安全处理这些转换（需要虚函数支持）。

空基类优化 (EBO)：如果基类为空，编译器可能将其大小优化为 0（不占空间），此时偏移可能为 0。但多个空基类仍需区分地址。

9. 如果有一块地址空间，怎么在这个地址空间内调用构造函数？

使用定位 new (placement new)，在已分配的内存上调用构造函数。

#include <new>  // placement new

// 假设有一块已分配的内存
void* memory = malloc(sizeof(MyClass));

// 在指定地址上构造对象（不分配新内存，只调用构造函数）
MyClass* obj = new (memory) MyClass(constructor_args);

// 使用对象...
obj->doSomething();

// 销毁：显式调用析构函数（不要用 delete！因为内存不是 new 分配的）
obj->~MyClass();

// 释放内存（根据分配方式）
free(memory);

关键点：

1. placement new 语法：new (address) Type(args)，在 address 指向的已分配内存上构造对象。
2. 必须显式调用析构函数：obj->~MyClass();，因为 delete 会同时释放内存，而内存不是 new 分配的。
3. 内存对齐：确保传入的地址满足类型的对齐要求，否则是未定义行为。
4. C++17 替代：std::construct_at（更安全的 placement new 封装）和 std::destroy_at。

应用场景：内存池、对象池、自定义分配器、在共享内存中构造对象等。

二、STL

🔥 高频题（5题）

面试中最常出现，核心知识点，建议重点掌握，能熟练默写。

1. vector 底层实现？

std::vector 底层是动态数组，在堆上分配一段连续内存。

核心成员（典型实现）：

• _M_start：指向数组起始位置
• _M_finish：指向已使用元素的末尾（size 位置）
• _M_end_of_storage：指向分配内存的末尾（capacity 位置）

内存布局：
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘
  ↑           ↑               ↑
start      finish      end_of_storage
  size = 4     capacity = 8

关键特性：

1. 动态扩容：当 size == capacity 时，重新分配更大的内存（通常 1.5 倍或 2 倍），将旧元素拷贝/移动到新内存，释放旧内存。
2. 随机访问 O(1)：连续内存，支持 [] 和 at()。
3. 尾端插入 O(1) 均摊：push_back 不扩容时 O(1)，扩容时 O(n)，均摊 O(1)。
4. 中间插入/删除 O(n)：需要移动元素。
5. 迭代器失效：扩容会导致所有迭代器失效；插入/删除点之后的迭代器失效。

vs 数组：vector 自动管理内存，可动态增长；数组大小固定。

2. vector、list 在添加删除的效率方面有什么不同？

关键区别：

• vector 在已知位置插入/删除需要移动元素，但随机访问快。
• list 在已知迭代器位置插入/删除是 O(1)，但找到位置需要 O(n) 遍历。
• vector 连续内存对 CPU 缓存友好，遍历速度远快于 list。

实际选择：

• 大多数场景用 vector（即使有中间插入，缓存优势可能弥补移动开销）。
• 只有在频繁中间插入/删除且位置已知时才考虑 list。
• C++11 后，std::list 使用场景越来越少，Bjarne Stroustrup 也建议优先用 vector。

3. vector 迭代器失效的情况有哪些？

迭代器失效指迭代器不再指向有效的元素，使用失效迭代器是未定义行为。

正确的遍历删除方式：

// 使用 erase 返回值
for (auto it = vec.begin(); it != vec.end(); ) {
    if (condition(*it)) {
        it = vec.erase(it);
    } else {
        ++it;
    }
}

// C++20
std::erase_if(vec, condition);

范围 for 循环中删除元素会导致迭代器失效，不要在范围 for 中 erase。

4. map 和 unordered_map 的区别？

unordered_map 底层：

• 一个桶数组（bucket array），每个桶是一个链表（或 C++11 后链表过长时转红黑树）。
• 通过哈希函数将键映射到桶索引。
• 负载因子 = 元素数 / 桶数，超过阈值（默认 1.0）时 rehash（扩容并重新哈希）。

选择建议：

• 需要有序或范围查询用 map。
• 追求查找速度、键可哈希用 unordered_map。
• 自定义类型作为键时，map 只需定义比较器，unordered_map 需同时定义哈希和相等比较。

5. vector、list、map 在内存中的数据结构有什么区别？

内存布局示意：

vector:  [1][2][3][4][5][ ][ ][ ]  连续内存

list:    [1]↔[3]↔[5]↔[2]↔[4]       节点分散，指针相连
          ↑   节点在内存中可能不连续

map:         [3]
            /   \
          [1]   [5]
           \    /
           [2][4]                  树节点分散，父子兄弟指针相连

内存开销对比（64 位系统，存 int）：

• vector：每个元素 4 字节 + 整体 3 个指针（24 字节管理开销）。
• list：每个节点 4 + 16（前后指针）= 20 字节 → 对齐到 24 字节。
• map：每个节点 4 + 颜色(4) + 3 指针(24) = 32 字节。

对性能的影响：

• vector 连续内存，CPU 缓存命中率高，遍历极快。
• list/map 节点分散，缓存不友好，遍历慢（每次访问可能缓存未命中）。
• 这也是为什么即使有中间插入，vector 有时仍比 list 快的原因。

📌 中频题（7题）

比较常见，部分公司会问到，建议理解并能口述要点。

1. STL 包括哪些内容？

STL (Standard Template Library，标准模板库) 由六大组件组成：

核心思想：将数据结构和算法分离，通过迭代器连接，实现高度复用。算法不关心容器类型，只要迭代器满足要求即可。

2. vector 和 deque 的区别？

deque 底层：由一个 map（中控数组，存储缓冲区指针）和多个固定大小的缓冲区（通常 512 字节）组成。头部可向前扩展，尾部可向后扩展。

使用建议：

• 需要高效随机访问用 vector。
• 需要频繁在头尾插入删除用 deque。
• stack 和 queue 默认底层容器是 deque。

3. 释放 vector 内存的处理方式？

vector 析构时自动释放内存，但在以下场景需要手动处理：

1. 清空元素但不释放内存：

vec.clear();  // size 变为 0，capacity 不变，内存不释放

2. 释放多余容量（收缩到 fit）：

// C++11 方式
vec.shrink_to_fit();  // 请求释放多余容量，不保证一定执行

// 通用方式（swap 技巧）
std::vector<int>(vec).swap(vec);  // 用拷贝构造的临时 vector 交换，临时对象析构释放旧内存

3. 彻底释放内存：

// 方式1：空 vector 交换
std::vector<int>().swap(vec);

// 方式2：先 clear 再 shrink
vec.clear();
vec.shrink_to_fit();

// 方式3：直接让 vector 离开作用域，析构自动释放

注意：

• clear() 只析构元素，不释放内存（capacity 不变）。
• resize(0) 也只改变 size，不释放内存。
• vector 的内存只能在 vector 析构或 swap/shrink 时释放，不能单独释放某个元素的内存。
• 如果 vector 存储的是指针，需要先 delete 每个指针再清空 vector，否则内存泄漏。

4. unordered_map 和 unordered_set 的区别？

共同点：

• 都是无序关联容器。
• 底层都是哈希表。
• 键必须可哈希（std::hash）且可比较相等（operator==）。
• 不允许重复键（multi 版本允许）。

使用场景：

• unordered_map：字典、缓存、计数。
• unordered_set：去重、存在性检查、集合运算。

5. clear 和 erase 的区别？

// clear：删除所有
vec.clear();
map.clear();

// erase：删除单个
vec.erase(vec.begin() + 5);
map.erase(key);  // 关联容器可按键删除
auto it = map.find(key);
if (it != map.end()) map.erase(it);

// erase：删除范围 [first, last)
vec.erase(vec.begin(), vec.begin() + 3);

注意：

• clear() 等价于 erase(begin(), end())。
• 两者都不释放容器内存（capacity 不变），需用 shrink_to_fit 或 swap 释放。
• 遍历中删除元素必须用 erase 的返回值更新迭代器，不能用失效迭代器自增。

6. swap 函数的作用？

std::swap 用于交换两个对象的值。

基本用法：

int a = 1, b = 2;
std::swap(a, b);  // a=2, b=1

std::vector<int> v1 = {1,2,3}, v2 = {4,5,6};
v1.swap(v2);  // 成员函数版本，O(1) 交换内部指针
std::swap(v1, v2);  // 通用版本，通常调用成员 swap

容器 swap 的特点：

• 对于 vector、deque、map、set 等容器，swap 是 O(1) 的，只交换内部指针/句柄，不交换元素。
• 迭代器在 swap 后仍然有效，但指向对方容器。
• 对于 array，swap 是 O(n) 的（需要逐个交换元素）。

常见应用：

1. 释放 vector 内存：

   std::vector<int>().swap(vec);  // 与空 vector 交换，释放内存
   std::vector<int>(vec).swap(vec);  // 收缩到 fit
   

2. 实现拷贝赋值运算符（Copy-and-Swap 惯用法）：

   T& operator=(T other) {  // 按值传参，自动拷贝
       swap(*this, other);
       return *this;
   }  // other 析构释放旧资源
   

3. pimpl 惯用法中交换实现指针。
4. 排序算法中交换元素。

自定义类型：应为自定义类型提供 swap 成员函数或 std::swap 特化，避免默认的三次拷贝（尤其是管理资源的类）。

7. erase 的返回值？

erase 的返回值是指向被删除元素的下一个元素的迭代器（C++11 起，之前是 void）。

vector / string / deque：

iterator erase(iterator pos);
iterator erase(iterator first, iterator last);
// 返回指向被删元素下一个位置的迭代器（可能是 end()）

list / map / set / unordered_map：

iterator erase(iterator pos);           // 返回下一个迭代器
size_type erase(const key_type& key);   // 按键删除，返回删除的数量
iterator erase(iterator first, iterator last);  // 范围删除

为什么需要返回值：erase 后，被删元素的迭代器失效，需要用返回值获取下一个有效迭代器继续遍历。

正确用法：

// 遍历删除（正确）
for (auto it = vec.begin(); it != vec.end(); ) {
    if (should_delete(*it)) {
        it = vec.erase(it);  // 更新迭代器
    } else {
        ++it;
    }
}

// map 按键删除
int n = m.erase(key);  // n 为删除的元素个数（0 或 1）

// 范围删除
vec.erase(vec.begin() + 2, vec.begin() + 5);  // 删除索引 2,3,4

C++20 补充：std::erase 和 std::erase_if 非成员函数，更简洁：

std::erase(vec, value);        // 删除所有等于 value 的元素
std::erase_if(vec, pred);      // 删除满足谓词的元素

💡 低频题（1题）

较少出现或较偏，时间充裕时了解即可。

1. 自己实现 unordered_map 会考虑什么问题？

1. 哈希函数设计：

   • 选择好的哈希函数，减少碰撞（如 MurmurHash、CityHash）。
   • 对自定义类型提供哈希特化。
   • 处理哈希洪水攻击（可能需要随机化哈希种子）。

2. 冲突处理：

   • 链地址法（separate chaining）：每个桶挂链表，最常用。
   • 开放寻址法（open addressing）：线性探测、二次探测、双重哈希。
   • 链表过长时转红黑树（C++11 unordered_map 的优化）。

3. 扩容与 rehash：

   • 负载因子阈值（通常 0.75 或 1.0）。
   • 扩容时桶数通常翻倍（或取质数）。
   • rehash 过程：重新计算所有元素的桶索引，迁移到新表。
   • 渐进式 rehash（Redis 方式）：避免一次性迁移阻塞。

4. 桶数组管理：

   • 初始桶数（通常 8 或 16）。
   • 桶数取质数可减少碰撞（但现代实现常用 2 的幂，用位运算代替取模）。

5. 迭代器实现：

   • 需跟踪当前桶和桶内链表位置。
   • rehash 后迭代器失效。

6. 内存管理：

   • 节点分配（可使用内存池）。
   • 析构时正确释放所有节点和桶数组。

7. 线程安全：

   • STL 容器非线程安全，并发访问需外部加锁。
   • 读可并发，写需独占。

8. 接口设计：

   • insert、erase、find、operator[]、at、clear。
   • bucket_count、load_factor、rehash、reserve。

三、Linux

🔥 高频题（22题）

面试中最常出现，核心知识点，建议重点掌握，能熟练默写。

1. 内存泄漏怎么检查，怎么避免？

检查工具：

1. Valgrind (memcheck)：

valgrind --tool=memcheck --leak-check=full --show-leak-kinds=all ./program

• 最常用，能检测内存泄漏、越界访问、use-after-free、未初始化变量。
• 缺点：程序运行慢 10-50 倍。

2. AddressSanitizer (ASan)：

g++ -fsanitize=address -g -O1 main.cpp -o program
./program

• 编译时插入检测代码，运行速度比 Valgrind 快（慢约 2 倍）。
• 能检测越界、use-after-free、double-free、内存泄漏（需 detect_leaks=1）。

3. LeakSanitizer (LSan)：

g++ -fsanitize=leak -g main.cpp -o program

• 专门检测内存泄漏，开销很小。

4. mtrace：

• glibc 内置，mtrace() 跟踪 malloc/free，生成日志后用 mtrace 命令分析。

5. 其他工具：

• massif（Valgrind 工具，内存使用分析）
• heaptrack、Intel Inspector、Purify

避免内存泄漏的方法：

1. 使用智能指针：std::unique_ptr、std::shared_ptr，RAII 自动释放。
2. 使用标准容器：std::vector、std::string 自动管理内存。
3. RAII 惯用法：资源在构造时获取，析构时释放。
4. 配对检查：malloc/free、new/delete、new[]/delete[] 配对使用。
5. 代码审查：关注异常路径、提前 return、goto 等是否遗漏释放。
6. 静态分析：cppcheck、clang-tidy 等工具提前发现。
7. 避免裸指针：尽量用智能指针或引用代替裸指针。
8. 异常安全：用 RAII 确保异常抛出时资源也能释放。

2. 多进程和多线程的区别？

进程和线程的关系：

• 进程是资源分配的最小单位，线程是 CPU 调度的最小单位。
• 一个进程至少有一个线程（主线程）。
• 线程有自己的栈、寄存器、程序计数器，但共享进程的堆、代码段、数据段。

选择建议：

• 任务独立、需要隔离 → 多进程。
• 任务紧密、频繁共享数据 → 多线程。
• 现代 C++ 推荐用 std::thread，配合 std::mutex、std::condition_variable 同步。

3. 进程间通信方式有哪些？

对比：

• 速度：共享内存 > 内存映射 > 消息队列 > 管道 > Socket
• 是否需要内核拷贝：共享内存/mmap 不需要（直接读写），其他需要内核态拷贝。
• 同步：共享内存/mmap 需要额外同步机制（信号量/互斥锁），消息队列/管道自带同步。

POSIX vs System V：

• 消息队列、信号量、共享内存都有 POSIX 和 System V 两套 API。
• 推荐用 POSIX 版本（更现代、接口更好）。

4. 什么是同步、异步？

同步 (Synchronous)：

• 调用方发出请求后，阻塞等待结果返回，才能继续执行。
• 调用顺序和执行顺序一致。
• 例子：普通函数调用、read() 阻塞读、join() 等待线程。

int result = calculate();  // 阻塞等待 calculate 完成
print(result);             // 拿到结果后才继续

异步 (Asynchronous)：

• 调用方发出请求后，不等待结果，立即返回继续执行。
• 结果通过回调、通知、future 等方式稍后获取。
• 例子：std::async、IOCP、epoll、JavaScript 回调。

std::future<int> f = std::async(std::launch::async, calculate);
doOtherWork();           // 不等待，继续做别的
int result = f.get();    // 需要结果时再获取（可能阻塞）

对比：

相关概念：

• 阻塞/非阻塞：描述调用方是否等待，关注调用方状态。
• 同步/异步：描述结果如何通知，关注通信机制。
• 同步可以是阻塞的也可以是非阻塞的（如非阻塞 read 轮询）。
• 异步一定是非阻塞的。

5. 对多线程的理解？生产者-消费者问题？

多线程：一个进程内创建多个执行流，共享进程地址空间，通过 OS 调度在多核上并行执行，提高 CPU 利用率和程序响应性。

生产者-消费者问题 (Producer-Consumer)：经典的多线程同步问题，也叫有界缓冲区问题。

问题描述：

• 生产者线程生产数据，放入缓冲区。
• 消费者线程从缓冲区取出数据消费。
• 缓冲区大小有限。
• 生产者不能在缓冲区满时放入，消费者不能在缓冲区空时取出。

C++11 实现：

#include <queue>
#include <mutex>
#include <condition_variable>

template<typename T>
class BoundedBuffer {
    std::queue<T> queue_;
    std::mutex mutex_;
    std::condition_variable not_full_;   // 缓冲区不满，生产者可放
    std::condition_variable not_empty_;  // 缓冲区不空，消费者可取
    size_t capacity_;
public:
    BoundedBuffer(size_t cap) : capacity_(cap) {}

    void produce(const T& item) {
        std::unique_lock<std::mutex> lock(mutex_);
        not_full_.wait(lock, [this]{ return queue_.size() < capacity_; });
        queue_.push(item);
        not_empty_.notify_one();
    }

    T consume() {
        std::unique_lock<std::mutex> lock(mutex_);
        not_empty_.wait(lock, [this]{ return !queue_.empty(); });
        T item = queue_.front();
        queue_.pop();
        not_full_.notify_one();
        return item;
    }
};

关键同步原语：

• 互斥锁：保护缓冲区的并发访问。
• 条件变量 not_full：缓冲区满时生产者等待，消费者取出后通知。
• 条件变量 not_empty：缓冲区空时消费者等待，生产者放入后通知。

注意：

• 条件变量的 wait 必须用 while 循环（或 wait 的谓词版本），防止虚假唤醒。
• 多个生产者/消费者时用 notify_one，全部唤醒用 notify_all。
• 这是线程安全的经典模式，广泛用于线程池、消息队列。

6. 什么是死锁？

死锁 (Deadlock)：多个线程/进程互相等待对方持有的资源，导致都无法继续执行，永久阻塞。

死锁的四个必要条件（Coffman 条件）：

1. 互斥 (Mutual Exclusion)：资源不能被多个线程同时持有，只能独占。
2. 占有并等待 (Hold and Wait)：线程持有至少一个资源，同时等待其他线程持有的资源。
3. 不可剥夺 (No Preemption)：资源不能被强行夺走，只能由持有者主动释放。
4. 循环等待 (Circular Wait)：存在一组线程，形成循环等待链，每个线程等待下一个线程持有的资源。

死锁示例：

std::mutex m1, m2;

void thread1() {
    std::lock_guard<std::mutex> l1(m1);  // 持有 m1
    std::lock_guard<std::mutex> l2(m2);  // 等待 m2（被 thread2 持有）→ 死锁
}

void thread2() {
    std::lock_guard<std::mutex> l2(m2);  // 持有 m2
    std::lock_guard<std::mutex> l1(m1);  // 等待 m1（被 thread1 持有）→ 死锁
}

预防死锁的方法（破坏四个条件之一）：

1. 破坏互斥：尽量用可共享资源（如只读数据），但很多资源必须互斥。
2. 破坏占有并等待：一次性申请所有需要的资源，申请不到就不持有任何资源。
3. 破坏不可剥夺：持锁线程申请新资源失败时，释放已持有的资源（如 try_lock）。
4. 破坏循环等待：对资源编号，所有线程按固定顺序申请资源（如总是先锁 m1 再锁 m2）。

避免死锁：

• 银行家算法：分配资源前判断是否安全。
• 用 std::lock(m1, m2) 同时加多个锁（内部按固定顺序，避免死锁）。
• 用 std::scoped_lock（C++17）同时管理多个互斥锁。

检测与恢复：

• 运行时检测死锁（如 Linux 的 lockdep、Java 的 JMX）。
• 检测到后终止一个线程或剥夺资源。

7. 线程池有什么好处？

线程池：预先创建一组线程，任务到来时从池中取一个空闲线程执行，任务完成后线程不销毁，回到池中等待下一个任务。

好处：

1. 降低资源消耗：

   • 避免频繁创建和销毁线程的开销（创建线程需分配栈、寄存器、内核对象，销毁需回收）。
   • 重复利用已有线程，减少系统调用和内存分配。

2. 提高响应速度：

   • 任务到来时无需等待线程创建，直接用已有线程执行。
   • 减少任务等待时间，提高吞吐量。

3. 控制并发数：

   • 限制同时运行的线程数量，避免线程过多导致：
     • 频繁上下文切换（CPU 开销大）。
     • 内存耗尽（每个线程有独立栈，默认 8MB）。
     • 资源竞争加剧（锁竞争、缓存失效）。
   • 根据 CPU 核心数和任务类型设置合理的线程数。

4. 统一管理：

   • 集中管理线程的生命周期、任务队列、监控统计。
   • 支持优雅关闭（等待任务完成再退出）。
   • 支持任务排队、优先级调度、拒绝策略。

5. 提高稳定性：

   • 线程池中的线程异常退出后可自动补充新线程。
   • 避免无限制创建线程导致系统崩溃（OOM）。

适用场景：

• 任务量大但每个任务执行时间短（如 Web 服务器请求处理）。
• 需要限制并发数的场景。
• 需要异步执行任务但不想每次创建线程。

不适用场景：

• 任务执行时间很长（线程池优势不明显）。
• 需要线程特定状态长期保留（如线程局部存储的复杂状态）。

线程数设置：

• CPU 密集型任务：线程数 = CPU 核心数 + 1。
• I/O 密集型任务：线程数 = CPU 核心数 × (1 + 等待时间/计算时间)，通常较多。

8. 讲一下线程池？

线程池组成：

┌─────────────────────────────────────┐
│            线程池                      │
│  ┌───────────────────────────────┐  │
│  │        任务队列 (Queue)        │  │
│  │  [task1][task2][task3]...    │  │
│  └───────────────────────────────┘  │
│                                      │
│  ┌──────┐ ┌──────┐ ┌──────┐       │
│  │worker1│ │worker2│ │worker3│ ...  │  工作线程
│  └──────┘ └──────┘ └──────┘       │
│                                      │
│  核心线程数 | 最大线程数 | 拒绝策略   │
└─────────────────────────────────────┘

核心参数（以 Java ThreadPoolExecutor 为例，C++ 类似）：

• 核心线程数 (corePoolSize)：常驻线程数，即使空闲也不销毁。
• 最大线程数 (maximumPoolSize)：线程池最多创建的线程数。
• 任务队列 (workQueue)：存放待执行任务的阻塞队列。
• 存活时间 (keepAliveTime)：非核心线程空闲超过此时间则销毁。
• 拒绝策略 (RejectedExecutionHandler)：队列满且线程数达上限时的处理策略。

工作流程：

1. 任务提交，若当前线程数 < 核心线程数，创建新核心线程执行。
2. 若核心线程都在忙，任务加入任务队列。
3. 若队列满，且当前线程数 < 最大线程数，创建非核心线程执行。
4. 若线程数已达最大，执行拒绝策略（Abort/CallerRuns/Discard/DiscardOldest）。

C++ 简单实现：

class ThreadPool {
    std::vector<std::thread> workers_;
    std::queue<std::function<void()>> tasks_;
    std::mutex mutex_;
    std::condition_variable condition_;
    bool stop_ = false;
public:
    ThreadPool(size_t n) {
        for (size_t i = 0; i < n; ++i) {
            workers_.emplace_back([this] {
                while (true) {
                    std::function<void()> task;
                    {
                        std::unique_lock<std::mutex> lock(mutex_);
                        condition_.wait(lock, [this]{ return stop_ || !tasks_.empty(); });
                        if (stop_ && tasks_.empty()) return;
                        task = std::move(tasks_.front());
                        tasks_.pop();
                    }
                    task();
                }
            });
        }
    }

    template<class F>
    auto submit(F&& f) -> std::future<decltype(f())> {
        using ReturnType = decltype(f());
        auto task = std::make_shared<std::packaged_task<ReturnType()>>(std::forward<F>(f));
        std::future<ReturnType> result = task->get_future();
        {
            std::unique_lock<std::mutex> lock(mutex_);
            tasks_.emplace([task](){ (*task)(); });
        }
        condition_.notify_one();
        return result;
    }

    ~ThreadPool() {
        {
            std::unique_lock<std::mutex> lock(mutex_);
            stop_ = true;
        }
        condition_.notify_all();
        for (auto& w : workers_) w.join();
    }
};

9. 什么是线程安全？

线程安全 (Thread Safe)：多线程环境下，代码/函数/数据结构能被多个线程同时调用而不产生错误结果（如数据竞争、状态不一致、未定义行为）。

线程不安全的原因：

• 数据竞争 (Data Race)：多个线程同时访问共享变量，且至少有一个是写操作，没有同步保护。
• 竞态条件 (Race Condition)：程序行为依赖于线程执行的时序，结果不确定。
• 状态不一致：多步操作中间状态被其他线程观察到。

实现线程安全的方法：

1. 互斥锁 (Mutex)：

   • 保护临界区，同一时刻只有一个线程执行。
   • std::mutex、std::lock_guard、std::unique_lock。

2. 原子操作 (Atomic)：

   • 不可分割的操作，硬件级保证。
   • std::atomic<int>、fetch_add、compare_exchange。
   • 适用于简单计数器、标志位。

3. 不可变对象 (Immutable)：

   • 对象创建后不可修改，多线程只读访问天然安全。
   • 如 const 对象、字符串。

4. 线程局部存储 (TLS)：

   • thread_local 变量，每个线程有独立副本，不共享。
   • 避免同步开销。

5. 消息传递：

   • 线程间通过消息队列通信，不共享可变状态。
   • 如 Actor 模型、Go channel。

6. 无锁数据结构 (Lock-Free)：

   • 用 CAS (Compare-And-Swap) 等原子操作实现，不用锁。
   • 复杂但性能高，如无锁队列。

线程安全的级别：

• 线程安全：多线程同时调用安全。
• 条件线程安全：读操作并发安全，写操作需外部同步（如大多数 STL 容器）。
• 线程不安全：多线程调用需外部加锁。

注意：

• STL 容器不是线程安全的：多线程读安全，至少一个线程写时需外部加锁。
• std::shared_ptr 的引用计数是线程安全的，但对象本身的访问不是。
• 函数内的局部变量是线程安全的（每个线程有独立栈）。

10. 多线程间共享数据，用什么方式保证安全性？

最佳实践：

1. 优先用 RAII 锁：

std::mutex mtx;
void func() {
    std::lock_guard<std::mutex> lock(mtx);  // 构造加锁，析构解锁
    // 临界区
}  // 自动解锁，即使异常也安全

2. 缩小临界区：只保护必须保护的代码，减少锁持有时间。

3. 避免死锁：

   • 按固定顺序加锁。
   • 用 std::lock(m1, m2) 同时加多个锁。
   • C++17 用 std::scoped_lock。

4. 优先用原子操作：简单的计数/标志用 std::atomic，比锁高效。

5. 减少共享：能用线程局部存储或消息传递就不用共享可变数据。

注意：

• 双重检查锁定 (DCLP) 在 C++11 前有问题，C++11 后可用 std::call_once 或原子操作实现。
• 静态局部变量的初始化在 C++11 后是线程安全的（Magic Statics）。

11. 什么是线程安全函数？工作中如何保证线程安全？

线程安全函数：可被多个线程同时调用而不产生数据竞争或错误结果的函数。

函数线程安全的条件：

• 不访问非局部的可变共享数据（全局变量、静态变量）。
• 若访问共享数据，必须有同步保护。
• 不返回指向内部静态可变数据的指针。
• 调用的其他函数也是线程安全的。

反例（线程不安全）：

// 不安全：使用静态变量
char* unsafe_itoa(int n) {
    static char buf[20];  // 多线程调用会互相覆盖
    sprintf(buf, "%d", n);
    return buf;
}

// 不安全：修改全局变量
int counter = 0;
void unsafe_increment() {
    counter++;  // 非原子操作，多线程数据竞争
}

正例（线程安全）：

// 安全：只用局部变量
void safe_func(int x) {
    int result = x * 2;  // 局部变量，每线程独立栈
    print(result);
}

// 安全：用原子操作
std::atomic<int> counter{0};
void safe_increment() {
    counter++;  // 原子操作
}

// 安全：用互斥锁保护共享数据
std::mutex mtx;
int shared_data = 0;
void safe_modify() {
    std::lock_guard<std::mutex> lock(mtx);
    shared_data++;
}

工作中保证线程安全的方法：

1. 尽量避免共享：

   • 用局部变量代替全局/静态变量。
   • 用 thread_local 存储线程私有数据。
   • 用不可变对象（创建后只读）。

2. 正确使用同步原语：

   • 互斥锁保护临界区，用 RAII（lock_guard）。
   • 原子操作处理简单计数。
   • 条件变量处理事件等待。

3. 代码审查：

   • 检查是否有未保护的共享数据访问。
   • 检查锁的获取顺序是否一致（防死锁）。
   • 检查是否有竞态条件。

4. 工具检测：

   • ThreadSanitizer (TSan)：-fsanitize=thread，检测数据竞争和死锁。
   • Helgrind（Valgrind 工具）：线程错误检测。
   • 静态分析：clang-tidy、Coverity。

5. 测试：

   • 压力测试：多线程高并发运行。
   • 长时间运行测试（偶发问题）。
   • 用不同调度顺序、不同 CPU 数测试。

6. 设计层面：

   • 明确哪些数据是共享的，哪些是线程私有的。
   • 用消息传递代替共享内存（如 Actor 模型）。
   • 单一职责，减少函数间的隐式共享。

12. 从输入 URL 到显示页面的全过程？

1. DNS 解析：

   • 浏览器检查缓存 → 系统缓存 (hosts) → 本地 DNS 服务器 → 根 DNS → 顶级域 DNS → 权威 DNS。
   • 将域名解析为 IP 地址。

2. TCP 连接建立：

   • 浏览器与服务器 IP 的 80/443 端口进行 TCP 三次握手。
   • HTTPS 还需 TLS 握手（协商加密套件、交换密钥、验证证书）。

3. 发送 HTTP 请求：

   • 浏览器构造 HTTP 请求报文（请求行、请求头、请求体）。
   • 通过 TCP 连接发送给服务器。

4. 服务器处理：

   • 反向代理（Nginx）接收请求，转发给应用服务器。
   • 应用服务器处理业务逻辑，可能查询数据库、缓存。
   • 生成 HTTP 响应报文（状态行、响应头、响应体）。

5. 返回响应：

   • 服务器将响应通过 TCP 连接发回浏览器。
   • 浏览器接收响应，根据状态码处理（200 成功、301 重定向、404 未找到等）。

6. 浏览器渲染：

   • 解析 HTML 构建 DOM 树。
   • 解析 CSS 构建 CSSOM 树。
   • 合并为渲染树 (Render Tree)。
   • 布局 (Layout/Reflow)：计算元素位置和大小。
   • 绘制 (Paint)：将像素绘制到屏幕。
   • 合成 (Composite)：多层合并显示。

7. 断开连接：

   • TCP 四次挥手断开连接（或保持长连接 Keep-Alive）。

13. select、poll、epoll 的区别？

select 的缺点：

• 连接数上限 1024。
• 每次调用都需遍历所有 fd，连接多时效率低。
• fd_set 每次调用后被修改，需重新设置。
• 用户态/内核态频繁拷贝。

epoll 的优势：

• 事件驱动：只返回就绪的 fd，不需要遍历全部。
• 内存共享：通过 mmap 共享内存，避免频繁拷贝。
• 两种触发模式：
  • LT (Level Triggered，水平触发)：只要缓冲区有数据就一直通知，类似 select，不容易出错。
  • ET (Edge Triggered，边沿触发)：只在状态变化时通知一次，需一次性读完数据（非阻塞 + 循环读），效率更高但编程复杂。
• 三个系统调用：
  • epoll_create：创建 epoll 实例。
  • epoll_ctl：注册/修改/删除 fd 及其事件。
  • epoll_wait：等待事件，返回就绪的 fd。

使用建议：高并发服务器（如 Nginx、Redis）都用 epoll。

14. epoll 边沿触发 (ET) 的具体实现方式？

ET (Edge Triggered，边沿触发)：只在 fd 状态发生变化时（如新数据到达）通知一次，之后即使缓冲区还有数据也不再通知，直到下一次状态变化。

实现要点：

1. 设置非阻塞：ET 模式必须配合非阻塞 I/O，否则 read/write 可能阻塞在单个 fd 上，导致整个事件循环卡死。

int flags = fcntl(fd, F_GETFL, 0);
fcntl(fd, F_SETFL, flags | O_NONBLOCK);

2. 注册 ET 事件：

struct epoll_event ev;
ev.events = EPOLLIN | EPOLLET;  // 加上 EPOLLET 标志
ev.data.fd = fd;
epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &ev);

3. 循环读取直到 EAGAIN：ET 只通知一次，必须一次性把缓冲区数据读完，否则剩余数据不会再触发事件。

while (1) {
    ssize_t n = read(fd, buf, sizeof(buf));
    if (n > 0) {
        // 处理数据
    } else if (n == 0) {
        // 对端关闭连接
        close(fd);
        break;
    } else {
        if (errno == EAGAIN || errno == EWOULDBLOCK) {
            // 数据已全部读完
            break;
        }
        // 真正的错误
        close(fd);
        break;
    }
}

4. 写事件同理：ET 模式下 EPOLLOUT 只在可写状态变化时通知一次，需循环写直到 EAGAIN。

ET vs LT：

注意事项：

• ET 模式下，如果 read 没有读完数据，剩余数据不会再触发 EPOLLIN，导致数据"丢失"（实际还在缓冲区，但不会通知）。
• 必须用非阻塞 I/O。
• 每次 read 要循环到 EAGAIN。
• 对端关闭连接时 read 返回 0，需处理。

15. LT 和 ET 的区别及应用场景？

应用场景：

LT 适用场景：

• 连接数较少，对性能要求不高。
• 编程简单优先，不想处理复杂的非阻塞逻辑。
• 数据量小，一次 read 就能读完。
• 初学者或快速开发。
• 写事件：LT 模式下 EPOLLOUT 只要可写就一直触发，需注意写完后及时移除 EPOLLOUT，否则 CPU 空转。

ET 适用场景：

• 高并发服务器，连接数大（上万甚至十万）。
• 性能要求高，希望减少系统调用和重复通知。
• 数据量大，需要高效处理。
• Nginx、Redis、高性能网络库（muduo、libevent 可选 ET）。

ET 编程注意：

1. 所有 fd 设为非阻塞。
2. read/write 循环到 EAGAIN。
3. 处理 EINTR（被信号中断）。
4. 注意写事件：ET 下 EPOLLOUT 只在从不可写变可写时触发一次，如果发送缓冲区一直有空间，不会重复触发。需要主动注册 EPOLLOUT，写完后移除。
5. accept 也要循环：ET 模式下新连接到达只通知一次，需循环 accept 直到 EAGAIN（多个连接同时到达时）。

选择建议：

• 大多数场景用 LT 即可，简单可靠。
• 追求极致性能、连接数巨大时用 ET。
• 很多高性能框架（如 Netty）默认用 LT，因为 ET 编程容易出错且收益不一定大。

16. TCP 的"粘包"问题？

粘包：TCP 是面向字节流的协议，没有消息边界。发送方发送的多个数据包可能被接收方当作一个包接收，或者一个包被拆成多个包接收。

产生原因：

1. 发送方 Nagle 算法：将多个小数据包合并成一个发送。
2. 接收方缓存：接收方读取不及时，多个包在缓冲区中合并。
3. TCP 分段：MSS (最大分段大小) 限制，大包被拆分成多个段。
4. 应用层写入：多次 write 的数据被 TCP 合并发送。

注意：粘包不是 TCP 的 bug，而是字节流协议的特性。UDP 是面向数据报的，不会粘包。

解决方法（应用层处理）：

1. 固定长度消息：

• 每条消息固定长度，不足补零。
• 接收方按固定长度读取。
• 缺点：浪费空间，不适合变长消息。

2. 特殊分隔符：

• 消息之间用特殊字符分隔（如 \n、\r\n、\0）。
• 接收方按分隔符切分。
• 缺点：消息内容不能包含分隔符（需转义）。
• 例：HTTP 头部用 \r\n\r\n 分隔。

3. 消息头 + 消息体（长度前缀）：

• 最常用的方法。消息头包含消息体长度（如 4 字节整数）。
• 接收方先读固定长度的头部，解析出消息体长度，再读指定长度的消息体。

┌──────────┬──────────────────┐
│ 长度(4B) │    消息体(N B)    │
└──────────┴──────────────────┘

4. 自定义协议：

• 设计完整的应用层协议，包含魔数、版本、消息类型、长度、序列化数据、校验和等。
• 例：Protobuf + 长度前缀、Thrift、gRPC。

接收方处理逻辑（以长度前缀为例）：

// 维护接收缓冲区
std::string recv_buf;

void on_data(const char* data, size_t len) {
    recv_buf.append(data, len);
    while (recv_buf.size() >= 4) {  // 至少有消息头
        uint32_t msg_len = *reinterpret_cast<const uint32_t*>(recv_buf.data());
        if (recv_buf.size() >= 4 + msg_len) {
            // 完整消息到达，处理
            handle_message(recv_buf.data() + 4, msg_len);
            recv_buf.erase(0, 4 + msg_len);
        } else {
            break;  // 消息不完整，等待更多数据
        }
    }
}

17. TCP 和 UDP 的区别？

TCP 保证可靠性的机制：

1. 序列号和确认号：每个字节都有序号，接收方确认收到的字节。
2. 超时重传：发送方在超时时间内未收到确认则重传。
3. 校验和：检测传输过程中的数据损坏。
4. 流量控制：滑动窗口，防止发送方发得太快导致接收方处理不过来。
5. 拥塞控制：根据网络状况调整发送速率。

UDP 的优势场景：

• 实时性要求高，丢一两个包不影响（视频会议、直播、游戏）。
• 网络状况好，丢包率低。
• 需要广播/组播。
• 简单请求-响应，自己实现轻量级可靠机制。

选择建议：默认用 TCP，除非明确需要 UDP 的特性。

18. TCP 三次握手建立连接的过程？

客户端 (Client)                          服务器 (Server)
     |                                        |
     |  1. SYN (seq=x)                       |
     | ────────────────────────────────────→ |
     |                                        |
     |  2. SYN+ACK (seq=y, ack=x+1)          |
     | ←──────────────────────────────────── |
     |                                        |
     |  3. ACK (seq=x+1, ack=y+1)            |
     | ────────────────────────────────────→ |
     |                                        |
     |         连接建立，开始传输数据           |

详细过程：

1. 第一次握手 (SYN)：

   • 客户端向服务器发送 SYN 报文，序列号 seq = x（随机生成）。
   • 客户端状态变为 SYN_SENT。
   • 同步位 SYN = 1，表示请求建立连接。

2. 第二次握手 (SYN+ACK)：

   • 服务器收到 SYN 后，回复 SYN+ACK 报文。
   • 确认号 ack = x + 1（表示期望收到的下一个字节序号）。
   • 服务器自己的序列号 seq = y（随机生成）。
   • 服务器状态变为 SYN_RCVD。
   • 服务器为该连接分配资源（TCB）。

3. 第三次握手 (ACK)：

   • 客户端收到 SYN+ACK 后，回复 ACK 报文。
   • 确认号 ack = y + 1。
   • 序列号 seq = x + 1。
   • 客户端状态变为 ESTABLISHED。
   • 服务器收到 ACK 后，状态也变为 ESTABLISHED。

为什么是三次而不是两次？

1. 确认双方的收发能力：三次握手能确认客户端的发送/接收能力和服务器的发送/接收能力都正常。两次握手只能确认客户端到服务器的单向能力。
2. 防止已失效的连接请求到达服务器：如果客户端的一个旧 SYN 延迟到达服务器，服务器回复 SYN+ACK 后，如果是两次握手就会建立连接，但客户端并不想建立，浪费服务器资源。三次握手中客户端可以忽略这个旧 SYN 的回复，不发送第三次 ACK，连接就不会建立。
3. 同步初始序列号：双方需要交换并确认各自的初始序列号 (ISN)，三次握手刚好完成双向同步。

第三次握手可以携带数据：TCP 标准允许第三次握手的 ACK 报文中携带数据（但有些实现可能不支持）。

19. TCP 四次挥手的过程？

客户端 (Client)                          服务器 (Server)
     |                                        |
     |  1. FIN (seq=u)                       |
     | ────────────────────────────────────→ |
     |  状态: FIN_WAIT_1                      |
     |                                        |
     |  2. ACK (ack=u+1)                     |
     | ←──────────────────────────────────── |
     |  状态: FIN_WAIT_2                      |  状态: CLOSE_WAIT
     |                                        |
     |  3. FIN (seq=w)                       |
     | ←──────────────────────────────────── |
     |                                        |  状态: LAST_ACK
     |  4. ACK (ack=w+1)                     |
     | ────────────────────────────────────→ |
     |  状态: TIME_WAIT (2MSL)               |
     |                                        |  状态: CLOSED
     |  等待 2MSL 后 → CLOSED                 |

详细过程：

1. 第一次挥手 (FIN)：

   • 客户端发送 FIN 报文，序列号 seq = u。
   • 表示客户端没有数据要发送了，请求关闭连接。
   • 客户端状态变为 FIN_WAIT_1。

2. 第二次挥手 (ACK)：

   • 服务器收到 FIN 后，回复 ACK，确认号 ack = u + 1。
   • 服务器状态变为 CLOSE_WAIT。
   • 客户端收到 ACK 后，状态变为 FIN_WAIT_2。
   • 此时客户端到服务器的方向关闭了（半关闭），但服务器可能还有数据要发送。

3. 第三次挥手 (FIN)：

   • 服务器数据发送完毕后，发送 FIN 报文，序列号 seq = w。
   • 服务器状态变为 LAST_ACK。

4. 第四次挥手 (ACK)：

   • 客户端收到 FIN 后，回复 ACK，确认号 ack = w + 1。
   • 客户端状态变为 TIME_WAIT。
   • 服务器收到 ACK 后，状态变为 CLOSED。
   • 客户端等待 2MSL（最长报文寿命的两倍）后，状态变为 CLOSED。

为什么是四次而不是三次？

• TCP 是全双工的，两个方向需要分别关闭。
• 服务器收到客户端的 FIN 后，可能还有数据要发送，不能立即回复 FIN，只能先回复 ACK。
• 等服务器数据发完后，再单独发送 FIN。
• 因此 ACK 和 FIN 分开发送，共四次。
• 如果服务器没有数据要发送，ACK 和 FIN 可以合并，变成三次挥手。

为什么 TIME_WAIT 需要 2MSL？

1. 确保最后一个 ACK 能到达服务器：如果客户端的最后一个 ACK 丢失，服务器会重传 FIN，客户端在 TIME_WAIT 期间可以重发 ACK。2MSL 足够让 ACK 和可能的 FIN 重传都完成。
2. 让本次连接的所有报文在网络中消失：防止旧连接的延迟报文被新连接误认为是新数据。2MSL 确保所有报文都过期。

20. 为什么 TIME_WAIT 状态需要经过 2MSL 才能返回到 CLOSED？

MSL (Maximum Segment Lifetime，最长报文寿命)：TCP 报文在网络中存活的最长时间，RFC 建议 2 分钟，Linux 实际通常为 30 秒（可通过 /proc/sys/net/ipv4/tcp_fin_timeout 调整，但实际 MSL 固定为 30 秒，TIME_WAIT 时长为 60 秒）。

2MSL 的原因：

1. 确保最后一个 ACK 能到达被动关闭方：

• 主动关闭方发送最后一个 ACK 后进入 TIME_WAIT。
• 如果这个 ACK 在网络中丢失，被动关闭方 (LAST_ACK 状态) 会超时重传 FIN。
• 主动关闭方在 TIME_WAIT 期间收到重传的 FIN 后，可以重新发送 ACK。
• 1MSL 足够 ACK 到达被动关闭方，另 1MSL 足够被动关闭方重传的 FIN 到达主动关闭方。
• 如果没有 TIME_WAIT，主动关闭方直接关闭，就无法处理被动关闭方重传的 FIN，导致被动关闭方一直停留在 LAST_ACK 无法正常关闭。

2. 确保本次连接的所有报文都在网络中消失：

• 防止旧连接的延迟报文 (wandering duplicate) 被新连接误认为是新数据。
• 2MSL 确保本次连接产生的所有报文都在网络中过期消失。
• 这样新连接（使用相同的四元组：源IP、源端口、目的IP、目的端口）不会收到旧连接的残留报文。

TIME_WAIT 的影响：

• 主动关闭方在 TIME_WAIT 期间，该四元组不能被复用（默认情况下）。
• 高并发短连接服务器（如 HTTP 服务器主动关闭连接）可能产生大量 TIME_WAIT，耗尽端口资源。

处理大量 TIME_WAIT 的方法：

1. 调整 tcp_tw_reuse：允许将 TIME_WAIT 的端口用于新的出站连接（需配合时间戳）。
2. 让客户端主动关闭：服务器保持连接，由客户端发起关闭，TIME_WAIT 在客户端。
3. 使用长连接 (Keep-Alive)：减少连接建立和关闭的频率。
4. 调整 tcp_fin_timeout：减少 FIN_WAIT_2 的时间（不直接影响 TIME_WAIT）。
5. 增加本地端口范围：ip_local_port_range 调大，可用端口更多。
6. 使用 SO_REUSEADDR：允许绑定处于 TIME_WAIT 的地址（对服务器监听端口有效）。

注意：tcp_tw_recycle 已在 Linux 4.12 中移除，因为在 NAT 环境下会导致问题，不要使用。

21. HTTP 和 HTTPS 的区别？

HTTPS 工作原理：

1. TCP 三次握手。
2. TLS 握手：
   • 客户端发送 ClientHello（支持的加密套件、随机数）。
   • 服务器回复 ServerHello（选定加密套件、随机数）+ 证书（含公钥）。
   • 客户端验证证书合法性（CA 签名、有效期、域名匹配）。
   • 客户端生成预主密钥 (Pre-Master Secret)，用服务器公钥加密后发送。
   • 双方根据预主密钥和随机数生成会话密钥 (Session Key)。
   • 发送 Finished 消息，握手完成。
3. 加密通信：之后所有 HTTP 数据用会话密钥对称加密传输。

HTTPS 的优势：

• 机密性：第三方无法窃听内容。
• 完整性：消息认证码检测数据是否被篡改。
• 身份认证：证书验证服务器身份，防止钓鱼和中间人攻击。
• SEO 友好：搜索引擎优先展示 HTTPS 网站。
• 支持 HTTP/2：主流浏览器只在 HTTPS 下支持 HTTP/2。

HTTPS 的成本：

• 证书费用（现在有 Let's Encrypt 免费证书）。
• 握手延迟（TLS 1.3 已大幅减少）。
• 加密解密的 CPU 开销（现代 CPU 有 AES-NI 硬件加速，开销很小）。

22. 什么时候产生 TIME_WAIT？大规模 TIME_WAIT 怎么处理？

什么时候产生 TIME_WAIT：

• TCP 连接中，主动关闭连接的一方在发送最后一个 ACK 后进入 TIME_WAIT 状态。
• 即四次挥手中，主动发送 FIN 的一方（客户端或服务器），在收到对方的 FIN 并回复 ACK 后，进入 TIME_WAIT。
• 持续时间为 2MSL（Linux 通常 60 秒，MSL=30 秒）。
• 之后才进入 CLOSED 状态，释放连接资源。

常见场景：

• HTTP/1.0 默认短连接，服务器发送完响应后主动关闭连接 → 服务器端产生大量 TIME_WAIT。
• 客户端主动关闭连接 → 客户端产生 TIME_WAIT。
• 高并发短连接服务（如 API 网关、反向代理）容易产生大量 TIME_WAIT。

大规模 TIME_WAIT 的危害：

1. 端口耗尽：TIME_WAIT 状态的连接占用四元组（源IP、源端口、目的IP、目的端口），客户端出站连接的本地端口有限（默认约 3 万个），大量 TIME_WAIT 会导致无法建立新连接（Cannot assign requested address）。
2. 内存占用：每个 TIME_WAIT 连接占用内核内存（tcp_timewait 结构），数量极多时消耗内存。
3. 性能下降：内核需要管理大量 TIME_WAIT 连接。

处理方法：

1. 调整内核参数：

# 允许将 TIME_WAIT 端口用于新的出站连接（需时间戳支持）
sysctl -w net.ipv4.tcp_tw_reuse=1

# 增大本地端口范围
sysctl -w net.ipv4.ip_local_port_range="1024 65535"

# 减少 FIN_WAIT_2 超时（间接减少 TIME_WAIT 产生）
sysctl -w net.ipv4.tcp_fin_timeout=15

# 增大 TIME_WAIT 最大数量（防止被攻击）
sysctl -w net.ipv4.tcp_max_tw_buckets=262144

2. 让客户端主动关闭连接：

• 服务器保持连接，由客户端发起关闭，TIME_WAIT 发生在客户端，不影响服务器端口。
• HTTP/1.1 默认 Keep-Alive，连接复用，减少关闭频率。

3. 使用长连接 (Keep-Alive)：

• 复用 TCP 连接，避免频繁建立和关闭连接。
• HTTP/1.1、HTTP/2、数据库连接池、RPC 框架都默认使用长连接。
• 设置合理的连接空闲超时，及时释放不活跃连接。

4. SO_REUSEADDR：

• 服务器端 setsockopt(sock, SOL_SOCKET, SO_REUSEADDR, &on)，允许绑定处于 TIME_WAIT 的地址。
• 对服务器监听端口有效，重启服务时不会因 TIME_WAIT 而绑定失败。

5. 负载均衡/分布式：

• 多实例部署，分散连接数。
• 四层负载均衡 (LVS)、七层负载均衡 (Nginx) 分发流量。

6. 使用 SO_LINGER（不推荐）：

• 设置 SO_LINGER 为 0，关闭连接时直接发送 RST 而不是正常的四次挥手，跳过 TIME_WAIT。
• 但这可能导致数据丢失，不推荐用于正常通信。

注意：

• tcp_tw_recycle 已在 Linux 4.12 移除，NAT 环境下会导致连接问题，不要使用。
• tcp_tw_reuse 只对出站连接（客户端）有效，对入站连接（服务器）无效。
• 最根本的解决方法是减少短连接，使用长连接。

📌 中频题（18题）

比较常见，部分公司会问到，建议理解并能口述要点。

1. Linux 中常用的命令？

文件与目录：

• ls：列出目录内容（-l 详细，-a 含隐藏，-h 人类可读）
• cd：切换目录
• pwd：显示当前路径
• mkdir：创建目录（-p 递归创建）
• rm：删除文件/目录（-r 递归，-f 强制）
• cp：复制（-r 递归目录）
• mv：移动/重命名
• touch：创建空文件/更新时间戳
• ln：创建链接（-s 软链接）

文件查看：

• cat：查看文件内容
• less/more：分页查看
• head/tail：查看文件头/尾（-f 实时跟踪）
• grep：搜索文本（-r 递归，-i 忽略大小写，-n 行号）
• find：查找文件
• wc：统计行数/字数/字节数

权限与用户：

• chmod：修改权限
• chown：修改所有者
• sudo：以管理员权限执行
• su：切换用户

进程与系统：

• ps：查看进程（aux 全格式）
• top/htop：实时系统监控
• kill：终止进程（-9 强制）
• df：磁盘使用情况
• du：目录大小（-sh 汇总）
• free：内存使用
• uname：系统信息（-a 全部）

网络：

• ifconfig/ip addr：查看网络接口
• netstat/ss：查看网络连接
• ping：测试连通性
• curl/wget：下载文件
• ssh：远程登录

其他：

• tar：打包压缩（-czf 压缩，-xzf 解压）
• gzip/zip/unzip：压缩解压
• echo：输出文本
• history：命令历史
• man：帮助手册

2. Linux 查看内存、磁盘、端口、进程、线程的命令？

3. gdb 调试工具用过哪些功能？

常用 gdb 命令：

编译要求：需加 -g 参数保留调试信息：g++ -g -O0 main.cpp -o program

4. 模块偶发崩溃如何定位？

定位步骤：

1. 保留现场：

• 确保系统生成 core dump：ulimit -c unlimited，检查 /proc/sys/kernel/core_pattern。
• 保留崩溃时的 core 文件和对应版本的可执行文件（带调试信息）。

2. 分析 core dump：

gdb ./program core.12345
bt          # 查看崩溃时的调用栈
info locals # 查看局部变量
frame N     # 切换栈帧

3. 增加日志：

• 在关键路径加详细日志（函数入口/出口、关键变量值、错误码）。
• 用日志级别控制，崩溃前的日志能缩小范围。

4. 内存错误检测：

• AddressSanitizer (ASan)：-fsanitize=address -g，检测越界、use-after-free、double-free 等。
• Valgrind：valgrind --tool=memcheck ./program，检测内存泄漏和非法访问（慢但准确）。
• UndefinedBehaviorSanitizer (UBSan)：-fsanitize=undefined，检测未定义行为。

5. 线程问题检测：

• ThreadSanitizer (TSan)：-fsanitize=thread，检测数据竞争和死锁。
• 偶发崩溃很多是竞态条件，TSan 很有效。

6. 复现：

• 压力测试：循环运行、并发测试、边界条件测试。
• 故障注入：模拟网络异常、磁盘满、内存不足等。
• 用 gdb --args + 条件断点在可疑位置停住。

7. 静态分析：

• clang --analyze、cppcheck、Coverity 等工具提前发现潜在问题。

8. 监控：

• 崩溃时记录寄存器状态、栈信息、内存映射。
• 用 backtrace() + backtrace_symbols() 在程序内部捕获崩溃栈。

5. 什么是 coredump 文件？

**core dump（核心转储）**是程序异常终止时，OS 将进程的内存映像、寄存器状态、调用栈等信息保存到一个文件中，用于事后调试。

生成条件：

• 进程收到某些信号并终止：SIGSEGV（段错误）、SIGABRT（abort）、SIGFPE（浮点异常）、SIGILL（非法指令）、SIGBUS（总线错误）等。
• 需开启 core dump：ulimit -c unlimited（默认大小为 0，不生成）。

core 文件位置：

• 由 /proc/sys/kernel/core_pattern 控制：
  • core：当前目录下生成 core 文件。
  • /tmp/core.%e.%p.%t：指定路径和命名格式（%e 程序名，%p PID，%t 时间）。
• Ubuntu 默认通过 apport 服务管理，core 文件可能在 /var/lib/apport/coredump/。

调试 core 文件：

gdb ./program core.12345
(gdb) bt          # 查看崩溃调用栈
(gdb) info locals # 查看局部变量
(gdb) frame N     # 切换栈帧
(gdb) list        # 查看源码

注意事项：

• core 文件可能很大（等于进程内存大小），注意磁盘空间。
• 可执行文件需带调试信息（-g），否则只能看到函数地址。
• 生产环境可考虑用 coredumpctl（systemd）管理 core 文件。
• 容器中需确保 ulimit -c 和 core_pattern 配置正确。

6. mmap 的应用场景？

mmap (memory map) 将文件或设备映射到进程的虚拟地址空间，通过指针直接读写，替代 read/write 系统调用。

应用场景：

1. 大文件读写：

• 映射大文件（如数据库文件、日志文件），随机访问效率高。
• 避免 read/write 的内核缓冲区拷贝开销。

2. 进程间通信 (IPC)：

• 多个进程映射同一个文件（或匿名映射），共享内存区域。
• 比消息队列、管道效率高（直接内存读写，无需内核拷贝）。
• 需配合信号量/互斥锁同步。

3. 动态库加载：

• 动态链接器用 mmap 将 .so 文件映射到进程地址空间。
• 代码段只读共享，数据段私有写时复制。

4. 零拷贝 (Zero-Copy)：

• 网络发送文件时，用 mmap + sendfile 避免数据在用户态和内核态之间拷贝。
• Kafka、RocketMQ 等消息队列用 mmap 提升性能。

5. 匿名映射分配内存：

• mmap(NULL, size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) 分配大块内存。
• malloc 在分配大块内存（>128KB）时内部用 mmap。

6. 写时复制 (COW)：

• fork() 创建子进程时，用 mmap 的写时复制机制共享父进程内存，只有写入时才拷贝。

7. 内存映射 I/O：

• 映射设备文件（如 /dev/mem），直接访问硬件寄存器（驱动开发）。

关键参数：

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
// prot: PROT_READ/PROT_WRITE/PROT_EXEC/PROT_NONE
// flags: MAP_SHARED（共享，修改写回文件）/ MAP_PRIVATE（写时复制）
//        MAP_ANONYMOUS（匿名映射，不关联文件）

注意：

• 映射大小必须是页大小（通常 4KB）的整数倍。
• 访问越界会触发 SIGSEGV。
• 需用 msync 将修改刷回磁盘，munmap 解除映射。

7. 线程间通信的方式？

线程共享进程地址空间，通信比进程简单，主要是同步与互斥：

C++11 标准库：

#include <mutex>           // std::mutex, std::lock_guard, std::unique_lock
#include <condition_variable> // std::condition_variable
#include <future>          // std::async, std::future, std::promise
#include <atomic>          // std::atomic 原子操作
#include <thread>          // std::thread

注意：

• 共享变量访问必须同步，否则是数据竞争（未定义行为）。
• 避免死锁：按固定顺序加锁、用 std::lock 同时加多个锁、设置超时。
• 优先用 std::lock_guard（RAII）代替手动 lock/unlock。

8. Linux 进程同步的机制？

POSIX 信号量：

• 命名信号量：有名字，多进程共享，sem_open。
• 无名信号量：放在共享内存中，多进程共享，sem_init。

System V 信号量：

• semget、semop、semctl，功能强大但接口复杂。

注意：

• 进程间同步必须用进程间共享的同步对象（放在共享内存中或命名对象）。
• 普通 pthread_mutex_t 默认是进程内的，需设置 PTHREAD_PROCESS_SHARED 属性才能进程间共享。
• 避免死锁：按固定顺序获取资源、设置超时、用 try 系列函数。

9. 进程的状态？

Linux 进程有以下状态：

状态转换：

创建 → 就绪(R) ↔ 运行(R)
         ↓ 等待资源
      可中断睡眠(S) ← 事件到达/信号
         ↓ 等待I/O
      不可中断睡眠(D) ← I/O完成
         ↓ 收到SIGSTOP
      停止(T) ← SIGCONT
         ↓ 执行结束/收到SIGKILL
      僵尸(Z) → 父进程wait → 死亡(X)

查看进程状态：

ps aux   # STAT 列显示状态
ps -eo pid,stat,comm  # 只看 PID、状态、命令
top      # 实时显示

僵尸进程处理：

• 父进程应调用 wait()/waitpid() 回收子进程。
• 父进程先退出，子进程被 init/systemd 收养，会自动回收。
• 僵尸进程无法用 kill 杀死（已死亡），只能杀父进程让 init 收养回收。

10. 写时拷贝 (Copy-On-Write)？

写时拷贝 (COW, Copy-On-Write)：一种延迟复制优化策略，多个对象共享同一份数据，只有当某个对象需要修改数据时，才真正复制一份。

应用场景：

1. fork() 创建子进程：

• 子进程创建时不复制父进程的物理内存，只复制页表，共享物理页。
• 页表标记为只读。
• 当子进程或父进程写入某页时，触发缺页异常，内核才复制该页（分配新物理页，拷贝内容，标记为可写）。
• 大大减少 fork 的开销（尤其是大进程）。

2. std::string（历史上）：

• 某些旧实现（如旧版 libstdc++）的 string 拷贝构造采用 COW，拷贝时共享数据，修改时才复制。
• C++11 标准后 COW 实现因线程安全问题被禁止，改为深拷贝 + SSO。

3. 虚拟内存 mmap：

• MAP_PRIVATE 映射采用写时复制，多个进程共享文件页，写入时才复制私有副本。

4. 其他：

• Git 的对象存储、Docker 的镜像层、一些数据库的 MVCC。

优点：

• 减少不必要的内存拷贝，节省内存和时间。
• fork 后子进程立即 exec 时，完全不需要复制内存。

缺点：

• 写入时触发缺页异常，有额外开销。
• 多线程环境下 COW 的引用计数管理复杂（需要原子操作）。

11. 自旋锁 (Spinlock)？

自旋锁 (Spinlock)：一种忙等待锁，当锁被占用时，等待线程循环检查锁是否可用（"自旋"），而不是睡眠阻塞。

特点：

• 不睡眠，不释放 CPU，持续轮询。
• 适用于锁持有时间极短的场景（如内核中保护几个变量的操作）。
• 避免了进程/线程上下文切换的开销（切换开销可能比锁本身还大）。

适用场景：

• 多核处理器（单核上自旋无意义，应用互斥锁）。
• 锁持有时间很短（几条指令）。
• 中断上下文（不能睡眠，只能用自旋锁）。
• 内核态同步。

不适用场景：

• 锁持有时间长（浪费 CPU）。
• 单核 CPU（自旋的线程占着 CPU，持锁线程无法运行）。
• 用户态通常用互斥锁，自旋锁用得少。

C++ 中的自旋锁：

#include <atomic>
class SpinLock {
    std::atomic<bool> flag{false};
public:
    void lock() {
        while (flag.exchange(true, std::memory_order_acquire)) {
            // 自旋等待
        }
    }
    void unlock() {
        flag.store(false, std::memory_order_release);
    }
};

自旋锁 vs 互斥锁：

优化：可在自旋中加入 cpu_relax() / pause 指令减少功耗，或设置自旋上限，超过后退化为互斥锁（自适应锁，如 Linux 内核的 mutex）。

12. 可重入函数是什么意思？为什么一定是线程安全的？

可重入函数 (Reentrant Function)：可以在执行过程中被中断（如信号、中断），然后再次被调用（重入），而不会产生错误结果的函数。

可重入的条件：

1. 不使用全局或静态的可变数据。
2. 不返回指向全局/静态可变数据的指针。
3. 只调用可重入函数。
4. 不使用不可重入的标准库函数（如 malloc、printf、strtok）。
5. 不修改自身代码（自修改代码）。

可重入 vs 线程安全：

为什么可重入函数一定是线程安全的？

• 可重入函数不使用任何全局/静态可变数据，所有数据都是局部的（在栈上）。
• 每个线程有独立的栈，因此多个线程同时调用可重入函数时，各自操作自己的局部数据，互不干扰。
• 没有共享数据，就没有数据竞争，因此天然线程安全。

线程安全但不可重入的例子：

// 线程安全（有锁），但不可重入（用了全局变量+锁）
std::mutex mtx;
int counter = 0;

int increment() {
    std::lock_guard<std::mutex> lock(mtx);
    return ++counter;
}
// 如果在信号处理函数中调用 increment()，而信号中断了正在持锁的 increment()，
// 会导致死锁（同一线程重复加锁，普通 mutex 不可重入）。

可重入的例子：

// 可重入：只用局部变量
int square(int x) {
    int result = x * x;  // 局部变量
    return result;
}

// 可重入：用调用者提供的缓冲区
void safe_itoa(int n, char* buf, int size) {
    snprintf(buf, size, "%d", n);  // 结果写入调用者的缓冲区
}

注意：

• 信号处理函数中只能调用可重入函数（POSIX 定义了 async-signal-safe 函数列表）。
• malloc、free、printf 等大多数标准库函数不可重入。

13. write 阻塞的原因有哪些？

write() 系统调用在以下情况可能阻塞：

1. 套接字发送缓冲区满：

   • TCP 套接字的发送缓冲区 (send buffer) 被数据填满，对端接收慢或网络拥塞导致数据发不出去。
   • 这是最常见的原因。

2. 对端接收窗口为 0 (Zero Window)：

   • 对端接收缓冲区满，TCP 通告窗口大小为 0，发送方不能再发送数据。
   • 需等待对端处理数据后窗口恢复。

3. 流量控制/拥塞控制：

   • 网络拥塞，TCP 拥塞窗口减小，发送速率受限。

4. 文件写入慢：

   • 写入磁盘文件时，磁盘 I/O 慢（如机械磁盘、磁盘满、I/O 等待）。
   • 写入管道 (pipe) 时，管道缓冲区满且对端未读取。

5. Nagle 算法：

   • TCP 默认启用 Nagle 算法，小数据包会等待确认或攒够一定量才发送，可能导致延迟。
   • 可用 TCP_NODELAY 选项禁用。

6. 套接字为阻塞模式：

   • 默认套接字是阻塞的，write 会一直等到有空间或出错。
   • 设为非阻塞 (O_NONBLOCK) 时，write 会立即返回 EAGAIN/EWOULDBLOCK。

7. 内核缓冲区锁竞争：

   • 多线程同时 write 同一套接字，内核需加锁保护，可能短暂阻塞。

解决方法：

• 使用非阻塞 I/O + epoll，监听 EPOLLOUT 事件。
• 应用层维护发送缓冲区，write 不全时缓存剩余数据。
• 调整发送缓冲区大小：setsockopt(sock, SOL_SOCKET, SO_SNDBUF, ...)。
• 禁用 Nagle：setsockopt(sock, IPPROTO_TCP, TCP_NODELAY, ...)。
• 检查对端是否正常接收。

14. 调用 send 发送数据不全怎么办？

send() 返回实际发送的字节数，可能小于请求发送的字节数（尤其是非阻塞套接字或发送缓冲区满时），需要处理。

原因：

• 发送缓冲区满，TCP 不能一次性接收所有数据。
• 非阻塞模式下，send 不等待，立即返回已发送的部分。
• 信号中断（EINTR）。

解决方法：循环发送：

ssize_t send_all(int sockfd, const void* buf, size_t len) {
    const char* ptr = (const char*)buf;
    size_t remaining = len;
    while (remaining > 0) {
        ssize_t sent = send(sockfd, ptr, remaining, 0);
        if (sent > 0) {
            ptr += sent;
            remaining -= sent;
        } else if (sent == 0) {
            // 对端关闭？send 返回 0 比较少见
            break;
        } else {
            if (errno == EINTR) {
                continue;  // 被信号中断，重试
            }
            if (errno == EAGAIN || errno == EWOULDBLOCK) {
                // 非阻塞模式，发送缓冲区满
                // 方法1：阻塞等待（不推荐，会卡住事件循环）
                // 方法2：注册 EPOLLOUT，等可写时继续发送剩余数据
                // 这里返回已发送的字节数，上层缓存剩余数据
                return len - remaining;
            }
            return -1;  // 真正的错误
        }
    }
    return len;  // 全部发送完成
}

非阻塞 + epoll 的完整方案：

1. 应用层维护每个连接的发送缓冲区（如 std::string 或环形缓冲区）。
2. 调用 send 时，先尝试发送，如果没发完，剩余数据存入发送缓冲区。
3. 注册 EPOLLOUT 事件。
4. epoll_wait 返回 EPOLLOUT 时，继续发送缓冲区中的数据。
5. 发送缓冲区为空时，移除 EPOLLOUT（避免一直触发空转）。

// 伪代码
class Connection {
    std::string send_buf_;
    bool writing_ = false;

    void send(const char* data, size_t len) {
        if (!writing_) {
            ssize_t n = ::send(fd_, data, len, MSG_DONTWAIT);
            if (n > 0 && n < len) {
                send_buf_.assign(data + n, len - n);
                register_epollout();
                writing_ = true;
            } else if (n < 0 && errno == EAGAIN) {
                send_buf_.assign(data, len);
                register_epollout();
                writing_ = true;
            }
        } else {
            send_buf_.append(data, len);  // 追加到缓冲区
        }
    }

    void on_writable() {  // EPOLLOUT 触发
        ssize_t n = ::send(fd_, send_buf_.data(), send_buf_.size(), MSG_DONTWAIT);
        if (n > 0) {
            send_buf_.erase(0, n);
            if (send_buf_.empty()) {
                unregister_epollout();
                writing_ = false;
            }
        }
    }
};

注意：

• 阻塞套接字下 send 通常会发送全部数据（除非出错或被信号中断），但仍建议检查返回值。
• 不要假设 send 一定发送全部数据。
• TCP 是字节流，没有消息边界，发送不全是正常现象。

15. TCP 的超时重传机制？

超时重传 (Retransmission Timeout, RTO)：TCP 发送方在发送数据后启动定时器，如果在指定时间内未收到接收方的确认 (ACK)，则重新发送该数据。

核心机制：

1. RTT 测量：

   • RTT (Round-Trip Time)：报文段从发送到收到确认的往返时间。
   • TCP 持续测量 RTT，动态调整 RTO。

2. RTO 计算（Jacobson/Karels 算法）：

   • 平滑 RTT (SRTT)：SRTT = (1 - α) × SRTT + α × RTT，α 通常为 1/8。
   • RTT 偏差 (RTTVAR)：RTTVAR = (1 - β) × RTTVAR + β × |SRTT - RTT|，β 通常为 1/4。
   • RTO：RTO = SRTT + 4 × RTTVAR。
   • RTO 至少为 1 秒（Linux 实现），最大约 120 秒。

3. 重传定时器：

   • 每个发送的报文段都有一个重传定时器。
   • 定时器超时后，重传该报文段。
   • 指数退避 (Exponential Backoff)：每次重传后，RTO 翻倍（RTO = RTO × 2），最多重传约 15 次后放弃连接。

4. 快速重传 (Fast Retransmit)：

   • 不等待 RTO 超时，收到 3 个重复的 ACK (DupACK) 就立即重传。
   • 因为重复 ACK 说明后续报文已到达，只有丢失的那个需要重传。
   • 比超时重传快得多。

5. 选择确认 (SACK, Selective Acknowledgment)：

   • 接收方在 ACK 中告知发送方哪些报文段已收到、哪些丢失。
   • 发送方只需重传丢失的报文段，不需要重传所有后续报文。
   • 提高重传效率。

超时后的行为：

• 重传丢失的报文段。
• 拥塞窗口 (cwnd) 减半（或重置为 1，取决于实现）。
• 慢启动阈值 (ssthresh) 调整为当前窗口的一半。
• RTO 翻倍（指数退避）。

注意：

• TCP 的超时重传保证了数据的可靠传输。
• 但频繁超时重传会导致性能下降，说明网络拥塞或丢包严重。
• 应用层无法直接控制 RTO，但可以通过调整 TCP 参数（如 tcp_retries1、tcp_retries2）影响重传行为。

16. TCP 通信过程的状态变化？

TCP 状态机（11 个状态）：

状态转换图：

建立连接（三次握手）：

CLOSED → (主动 connect, 发SYN) → SYN_SENT → (收SYN+ACK, 发ACK) → ESTABLISHED
CLOSED → (被动 listen) → LISTEN → (收SYN, 发SYN+ACK) → SYN_RCVD → (收ACK) → ESTABLISHED

关闭连接（四次挥手）：

主动关闭方：
ESTABLISHED → (发FIN) → FIN_WAIT_1 → (收ACK) → FIN_WAIT_2 → (收FIN, 发ACK) → TIME_WAIT → (2MSL后) → CLOSED

被动关闭方：
ESTABLISHED → (收FIN, 发ACK) → CLOSE_WAIT → (应用层close, 发FIN) → LAST_ACK → (收ACK) → CLOSED

同时关闭：
ESTABLISHED → (发FIN) → FIN_WAIT_1 → (收FIN, 发ACK) → CLOSING → (收ACK) → TIME_WAIT → CLOSED

查看连接状态：

netstat -tlnp    # 查看监听状态
netstat -tan      # 查看所有 TCP 连接状态
ss -tan           # 更现代的工具

常见状态问题：

• 大量 TIME_WAIT：主动关闭方多，高并发短连接服务器常见。可调整 tcp_tw_reuse、tcp_tw_recycle（已废弃）、tcp_fin_timeout。
• 大量 CLOSE_WAIT：被动关闭方应用层没有调用 close()，连接泄漏。需检查代码是否正确关闭连接。
• 大量 SYN_RCVD：可能遭受 SYN Flood 攻击。可启用 tcp_syncookies。

17. 网络的七层模型？

OSI 七层模型（Open Systems Interconnection Reference Model）：

数据封装过程（发送方）：

应用层数据 → 加应用层首部 → 表示层 → 会话层
→ 传输层：加 TCP/UDP 首部（含端口）→ 段 (Segment)
→ 网络层：加 IP 首部（含 IP 地址）→ 包/分组 (Packet)
→ 数据链路层：加帧首部和尾部（含 MAC 地址、FCS）→ 帧 (Frame)
→ 物理层：比特流 (Bit)

解封装过程（接收方）：从物理层到应用层，逐层去掉首部，最终得到应用层数据。

TCP/IP 四层模型（实际使用的模型，将 OSI 七层合并）：

五层模型（教学常用，在 TCP/IP 四层基础上将网络接口层拆为数据链路层和物理层）：
应用层 → 传输层 → 网络层 → 数据链路层 → 物理层。

18. HTTP 有哪些常用方法？

常用方法详解：

GET：

• 请求指定资源，参数在 URL 查询字符串中。
• 幂等：多次调用结果相同。
• 安全：不修改服务器资源。
• 长度受限（URL 长度限制，不同浏览器不同）。
• 可被缓存、收藏为书签。

POST：

• 向服务器提交数据，请求体中包含数据。
• 非幂等：多次提交可能创建多个资源。
• 常用于表单提交、创建资源、登录等。
• 数据不在 URL 中，相对安全（但仍需 HTTPS 加密）。

PUT：

• 用请求体中的数据全量替换目标资源。
• 幂等：多次 PUT 相同数据结果相同。
• 如果资源不存在，有些实现会创建。

PATCH：

• 对资源进行部分更新（只更新指定字段）。
• 非幂等（取决于补丁内容）。
• 比 PUT 更高效，不需要发送完整资源。

DELETE：

• 删除指定资源。
• 幂等：删除已删除的资源结果相同（都是不存在）。

HEAD：

• 和 GET 类似，但服务器只返回响应头，不返回响应体。
• 用于检查资源是否存在、获取元信息（如 Content-Length、Last-Modified），效率高。

OPTIONS：

• 查询服务器对指定资源支持的 HTTP 方法（响应头 Allow）。
• CORS 中的预检请求 (preflight) 使用 OPTIONS。

幂等性 (Idempotent)：多次执行相同请求，服务器状态结果相同。GET、PUT、DELETE、HEAD、OPTIONS 是幂等的；POST、PATCH 不是。

安全性 (Safe)：请求不修改服务器资源。GET、HEAD、OPTIONS 是安全的。

💡 低频题（19题）

较少出现或较偏，时间充裕时了解即可。

1. 创建软链接的命令是什么？

ln -s 源文件 链接名

示例：

ln -s /usr/local/bin/python3 /usr/bin/python  # 创建软链接
ls -l /usr/bin/python  # 查看链接指向

软链接 vs 硬链接：

常用场景：

• 创建命令快捷方式（如 /usr/bin/python → 实际安装路径）
• 配置文件管理（多版本切换）
• 库文件版本管理（lib.so → lib.so.1.2.3）

2. /proc 文件夹下放的是什么？

/proc 是虚拟文件系统 (procfs)，不占用实际磁盘空间，内容在内存中动态生成，是内核与用户空间交互的窗口。

主要内容：

1. 进程信息（每个进程一个目录，以 PID 命名）：

• /proc/[pid]/status：进程状态（名称、PID、PPID、内存、权限等）
• /proc/[pid]/cmdline：启动命令行
• /proc/[pid]/cwd：当前工作目录（符号链接）
• /proc/[pid]/exe：可执行文件路径（符号链接）
• /proc/[pid]/maps：内存映射
• /proc/[pid]/fd/：打开的文件描述符
• /proc/[pid]/environ：环境变量
• /proc/self：当前进程的符号链接

2. 系统信息：

• /proc/cpuinfo：CPU 信息
• /proc/meminfo：内存信息
• /proc/version：内核版本
• /proc/uptime：系统运行时间
• /proc/loadavg：系统负载
• /proc/filesystems：支持的文件系统
• /proc/modules：已加载内核模块
• /proc/mounts：挂载信息

3. 内核参数（可读写，sysctl 对应）：

• /proc/sys/：可修改的内核参数
  • /proc/sys/net/ipv4/ip_forward：IP 转发
  • /proc/sys/vm/swappiness：swap 使用倾向
  • /proc/sys/kernel/hostname：主机名

特点：

• 大部分文件大小为 0，读取时才由内核动态生成内容。
• 可通过 cat 查看，部分可通过 echo 修改（立即生效，重启失效）。
• 永久修改需写入 /etc/sysctl.conf。

3. Linux 下有哪些文件类型？

用 ls -l 查看，第一个字符表示文件类型：

查看文件类型的命令：

ls -l filename    # 第一个字符
file filename     # 详细描述文件类型
stat filename     # 详细信息

特殊文件：

• /dev/null：黑洞，写入丢弃，读取返回 EOF。
• /dev/zero：读取返回无限的 0 字节。
• /dev/random、/dev/urandom：随机数生成器。
• /dev/tty：当前终端。

4. gdb 堆栈信息不准怎么办？

可能原因和解决方法：

1. 编译优化级别过高：

• 优化（-O2/-O3）可能内联函数、消除变量、重排代码，导致栈帧不完整。
• 解决：用 -O0 -g 重新编译，关闭优化。

2. 缺少调试信息：

• 未加 -g 参数，或 strip 掉了符号表。
• 解决：用 -g（或 -ggdb）重新编译，不要 strip。

3. 帧指针被优化掉：

• -fomit-frame-pointer（高优化级别默认开启）消除了帧指针寄存器，gdb 无法正确回溯栈。
• 解决：加 -fno-omit-frame-pointer 编译。

4. 汇编代码/手写汇编：

• 没有正确的 CFI（Call Frame Information）调试信息。
• 解决：在汇编中添加 .cfi_* 伪指令。

5. 栈被破坏：

• 缓冲区溢出、野指针写入破坏了栈上的返回地址和帧指针。
• 解决：用 valgrind、AddressSanitizer 检测内存错误。

6. 信号处理函数中：

• 信号处理函数的栈帧可能不完整。
• 解决：bt 可能仍能显示，用 info signals 查看信号处理。

7. 多线程问题：

• 需切换到正确线程：thread apply all bt 查看所有线程栈。

手动处理：

• 用 x/100gx $rsp 查看原始栈内存，手动分析返回地址。
• 用 info symbol 地址 查看地址对应的函数。

5. 循环内出现问题，gdb 调试要等很久怎么办？

加速调试的方法：

1. 条件断点：

break file.cpp:100 if i == 9999  # 只在 i=9999 时停住
break func if ptr == nullptr      # 指针为空时停住

避免每次循环都中断。

2. 跳过前 N 次：

break file.cpp:100
continue 1000  # 跳过断点 1000 次，第 1001 次才停

3. 数据断点 (watchpoint)：

watch variable    # 变量值变化时停住
watch *address    # 内存地址内容变化时停住
rwatch variable   # 读时停住
awatch variable   # 读写时停住

直接定位变量被异常修改的位置。

4. 反向调试：

record           # 开始记录执行
reverse-step     # 反向单步
reverse-continue # 反向继续

从崩溃点往回找原因。

5. 在循环外加断点，手动修改变量：

break file.cpp:90  # 循环前
set var i = 9990   # 直接跳到接近问题的迭代
continue

6. 用日志代替断点：

• 在循环内加 printf 或日志，运行到崩溃后分析日志。
• 比反复中断快得多。

7. 缩小循环范围：

• 二分法：先跑前半段看是否崩溃，逐步缩小范围。
• 修改代码临时减少循环次数。

8. 采样分析：

• 用 perf record + perf report 采样，看程序卡在哪里。
• 不需要中断程序。

6. Linux 文件系统读入文件的过程？

以 read() 系统调用读取文件为例：

1. 路径解析：

   • 内核根据文件路径（如 /home/user/file.txt）逐级查找目录项 (dentry)。
   • 从根目录 / 开始，查找 home → user → file.txt。
   • 查找过程中可能需要从磁盘读取目录块（有 dentry cache 时可加速）。

2. 获取 inode：

   • 找到文件的目录项后，获取其 inode 编号。
   • inode 存储文件的元数据：大小、权限、所有者、时间戳、数据块指针等。
   • inode 中有 12 个直接块指针、1 个一级间接块、1 个二级间接块、1 个三级间接块，定位数据块。

3. 检查权限：

   • 检查进程是否有读权限。

4. 检查页缓存 (Page Cache)：

   • 内核先在页缓存中查找文件对应的数据页。
   • 若命中（缓存已有数据），直接从缓存拷贝到用户缓冲区，返回。
   • 若未命中，触发缺页，进入下一步。

5. 提交 I/O 请求：

   • 内核根据 inode 的数据块指针，计算文件偏移对应的磁盘块号。
   • 向块设备层提交读请求（bio 结构）。
   • I/O 调度器（如 CFQ、deadline、noop）合并、排序请求，减少磁盘寻道。

6. 磁盘读取：

   • 磁盘控制器执行读操作，将数据从磁盘读到内存缓冲区。
   • DMA 控制器直接传输数据到内存，不占用 CPU。
   • 读取完成后触发中断，通知内核 I/O 完成。

7. 填充页缓存：

   • 读取的数据页加入页缓存，后续访问可直接命中。

8. 拷贝到用户空间：

   • 内核将数据从页缓存拷贝到用户提供的缓冲区。
   • read() 返回实际读取的字节数。

优化机制：

• 预读 (readahead)：内核预测顺序读，提前读取后续页面到缓存。
• 页缓存：热点数据缓存在内存，减少磁盘 I/O。
• O_DIRECT：绕过页缓存，直接 I/O（数据库常用）。

7. Linux 程序运行找不到动态库 .so 文件的解决办法？

错误信息：error while loading shared libraries: libxxx.so: cannot open shared object file: No such file or directory

三种解决办法：

1. 设置环境变量 LD_LIBRARY_PATH：

export LD_LIBRARY_PATH=/path/to/libs:$LD_LIBRARY_PATH
./program

• 临时生效，只对当前 shell 有效。
• 适合测试和开发环境。

2. 将库路径写入 /etc/ld.so.conf 配置文件：

echo "/path/to/libs" | sudo tee /etc/ld.so.conf.d/myapp.conf
sudo ldconfig  # 更新缓存

• 永久生效，系统级配置。
• ldconfig 会扫描配置的目录，更新 /etc/ld.so.cache 缓存。

3. 编译时指定库的运行路径 (rpath)：

g++ main.cpp -o program -L/path/to/libs -lxxx -Wl,-rpath,/path/to/libs

• 编译时将库路径写入可执行文件，运行时自动查找。
• 适合发布独立应用。
• 也可用 $ORIGIN 表示可执行文件所在目录：-Wl,-rpath,'$ORIGIN/lib'。

其他方法：

• 将 .so 文件复制到系统默认库目录（/usr/lib、/usr/local/lib），然后 ldconfig。
• 创建软链接：ln -s /path/to/libxxx.so /usr/lib/libxxx.so。

查看程序依赖的库：

ldd ./program  # 列出所有依赖的动态库及其路径

8. 什么是孤儿进程？

孤儿进程 (Orphan Process)：父进程先退出，子进程还在运行，此时子进程成为孤儿进程。

处理机制：

• 孤儿进程会被 init 进程（PID 1） 或 systemd 收养。
• init 进程会成为孤儿进程的新父进程，并负责在其退出时调用 wait() 回收资源。
• 因此孤儿进程不会变成僵尸进程，没有危害。

示例：

#include <unistd.h>
#include <stdio.h>
int main() {
    pid_t pid = fork();
    if (pid == 0) {
        // 子进程
        sleep(10);  // 父进程已退出，子进程成为孤儿
        printf("Child (orphan) parent pid: %d\n", getppid());  // 父PID变为1
    } else {
        // 父进程
        printf("Parent exiting, child pid: %d\n", pid);
        // 父进程直接退出，不 wait
    }
    return 0;
}

孤儿进程 vs 僵尸进程：

应用：守护进程 (daemon) 的创建就是故意让进程成为孤儿，脱离终端控制。

9. 结束进程的方式有哪些？

1. 正常退出：

• return 从 main 返回。
• exit(status)：标准库函数，执行清理（atexit 函数、刷新缓冲区、关闭文件）后退出。
• _exit(status) / _Exit(status)：系统调用，直接退出，不执行清理。
• abort()：异常终止，产生 SIGABRT 信号，生成 core dump。

2. 信号终止：

kill <pid>          # 默认发送 SIGTERM (15)，请求进程正常终止
kill -9 <pid>       # 发送 SIGKILL (9)，强制终止，不可捕获/忽略
kill -15 <pid>      # SIGTERM，可被进程捕获做清理
kill -2 <pid>       # SIGINT，等同 Ctrl+C
kill -l             # 列出所有信号
pkill process_name  # 按名称杀进程
killall process_name # 杀死所有同名进程

常见信号：

3. 其他方式：

• xkill：图形界面点击杀死窗口。
• systemctl stop service：停止服务进程。
• 进程收到致命错误（段错误、断言失败）自动终止。

注意：

• 优先用 SIGTERM，给进程清理机会；SIGKILL 是最后手段。
• D 状态（不可中断睡眠）的进程连 SIGKILL 也杀不死，需等待 I/O 完成或重启。

10. 什么是会话 (session)？

会话 (Session) 是一个或多个进程组的集合，由会话首进程 (session leader) 创建，会话 ID 等于首进程的 PID。

相关概念：

• 进程组 (Process Group)：一个或多个进程的集合，进程组 ID 等于组长进程的 PID。
• 会话：一个或多个进程组的集合。
• 控制终端 (Controlling Terminal)：会话可以关联一个控制终端，用于输入输出和信号传递。

会话中的进程组：

• 前台进程组：接收控制终端输入的进程组，同一时刻只有一个。
• 后台进程组：不接收终端输入的进程组，可以有多个。

创建会话：

pid_t setsid(void);  // 创建新会话，调用者成为会话首进程和进程组组长

• 调用者不能是进程组组长，否则失败。
• 新会话没有控制终端。

查看会话：

ps -ejH    # 查看会话ID、进程组ID、进程树
ps -o pid,ppid,pgid,sid,comm  # 查看各进程的会话ID

应用：

• 守护进程创建：fork() → 子进程 setsid() 创建新会话脱离终端 → 再次 fork() 确保不是会话首进程。
• 终端登录：用户登录时，shell 进程创建一个新会话，关联终端。
• nohup：使进程忽略 SIGHUP 信号，终端关闭后进程继续运行。

SIGHUP 信号：当控制终端断开时，会向会话首进程发送 SIGHUP，默认终止会话内所有进程。守护进程通过脱离控制终端避免收到此信号。

11. 守护进程与后台进程的区别？

创建守护进程的步骤：

1. fork()，父进程退出，子进程继续
2. setsid()，创建新会话，脱离控制终端
3. 再次 fork()，确保不是会话首进程（防止重新获取控制终端）
4. chdir("/")，改变工作目录到根目录
5. umask(0)，清除文件权限掩码
6. 关闭 stdin/stdout/stderr，重定向到 /dev/null

后台进程：

./program &    # 后台运行，仍关联终端
nohup ./program &  # 忽略 SIGHUP，终端关闭后继续运行

关键区别：守护进程完全独立于终端和登录会话，是系统级服务；后台进程仍受当前 shell 和终端管理。

12. 信号量处理耗费多长时间？信号量同步有什么问题？

信号量操作耗时：

• P 操作 (wait/sem_wait) 和 V 操作 (post/sem_post) 本身是原子操作，耗时极短（纳秒级，几条指令）。
• 但如果信号量值为 0，P 操作会导致线程睡眠阻塞，等待时间取决于何时被 V 操作唤醒，可能很长（毫秒到秒级）。
• 睡眠/唤醒涉及内核态切换（系统调用），开销比纯用户态操作大（约几微秒）。

信号量同步的问题：

1. 优先级反转 (Priority Inversion)：

   • 低优先级线程持有信号量，高优先级线程等待，中等优先级线程抢占低优先级运行，导致高优先级等待更久。
   • 解决：优先级继承协议（PIP）、优先级天花板协议（PCP）。

2. 死锁：

   • 多个信号量的获取顺序不一致可能导致死锁。
   • 需按固定顺序获取。

3. 活锁 (Livelock)：

   • 线程都在运行但都在等待对方，不断重试但无法推进。
   • 比死锁更难检测。

4. 竞态条件：

   • 信号量使用不当（如忘记 P/V、P/V 不配对）仍会导致数据竞争。

5. 性能开销：

   • 信号量操作涉及内核态（System V 信号量）或原子操作（POSIX 无名信号量），有一定开销。
   • 对于极短的临界区，自旋锁可能更高效。

6. 调试困难：

   • 信号量相关的 bug（死锁、竞态）难以复现和调试，依赖时序。

7. 计数错误：

   • 信号量初值设置错误、V 操作次数多于 P 操作，可能导致资源过度分配。

选择建议：

• 互斥用 std::mutex（比信号量简单高效）。
• 资源计数用信号量。
• 事件通知用条件变量（比信号量更灵活）。

13. 登录 shell 进程是如何启动的？

以 Linux 文本登录为例：

1. init/systemd 启动 getty：

   • 系统启动后，init（或 systemd）为每个终端（tty）启动 getty 进程。
   • getty 打开终端设备，设置终端属性，显示登录提示符（"login:"）。

2. 用户输入用户名：

   • getty 读取用户输入的用户名。
   • getty 执行 login 程序，将用户名作为参数传入。

3. login 验证用户：

   • login 提示输入密码。
   • login 验证用户名和密码（通过 /etc/passwd、/etc/shadow、PAM 模块）。
   • 验证失败则退出，getty 重新显示登录提示符。

4. 登录成功后设置环境：

   • login 设置用户的 UID/GID、环境变量（HOME、USER、SHELL、PATH 等）。
   • login 将当前工作目录切换到用户的家目录（/etc/passwd 中指定）。
   • login 打开终端的 stdin/stdout/stderr。

5. 启动 shell：

   • login 执行用户的登录 shell（/etc/passwd 中指定，如 /bin/bash）。
   • shell 以登录 shell 模式启动（-bash，argv[0] 前加 - 表示登录 shell）。

6. shell 初始化：

   • 登录 shell 依次读取执行：
     • /etc/profile（系统级环境配置）
     • /etc/profile.d/*.sh（系统级脚本）
     • ~/.bash_profile、~/.bash_login、~/.profile（用户级，按顺序找第一个存在的）
   • 非登录 shell（如终端中开新标签）读取 ~/.bashrc。

7. shell 交互：

   • shell 显示命令提示符，等待用户输入命令。
   • 用户输入命令后，shell 解析、fork+exec 执行命令，等待命令完成后显示提示符。

图形登录：通过显示管理器（gdm、lightdm）验证用户后启动桌面环境（GNOME、KDE），桌面环境再启动终端模拟器时启动非登录 shell。

14. sleep() 调用后进程有哪些过程？sleep 过程中占用 CPU 吗？

sleep() 的执行过程：

1. 调用 sleep(seconds)：

   • 进程调用 sleep() 库函数（内部通常用 nanosleep 或 alarm + pause 系统调用实现）。

2. 进程状态切换：

   • 内核将进程状态从 运行态 (R) 改为 可中断睡眠态 (S)。
   • 进程从 CPU 运行队列中移除，加入等待队列（等待定时器到期）。
   • 内核设置一个定时器（基于 jiffies 或高精度定时器 hrtimer），在指定时间后触发。

3. 调度其他进程：

   • CPU 调度器选择另一个就绪进程运行。
   • sleep 的进程此时不占用 CPU。

4. 定时器到期：

   • 指定时间到达后，定时器中断触发。
   • 内核将 sleep 进程的状态从睡眠态改为就绪态 (R)，加入运行队列。

5. 被调度恢复运行：

   • 调度器在合适时机选中该进程，恢复上下文，继续执行。
   • sleep() 返回 0（正常结束）或剩余秒数（被信号中断）。

sleep 过程中占用 CPU 吗？

• 不占用。进程处于睡眠状态，被移出运行队列，CPU 可以执行其他进程。
• 只有在 sleep 开始（设置定时器）和结束（唤醒、调度）的瞬间有极少量 CPU 开销。
• 这和忙等待 (busy waiting) 不同：忙等待（如 while(!timeout) 循环）会持续占用 CPU。

被信号中断：

• sleep 期间进程可被信号唤醒（如 SIGINT），此时 sleep 返回剩余秒数，进程处理信号后继续执行。
• nanosleep 更精确，返回时可通过第二个参数获取剩余时间，便于循环重试。

精度：

• sleep() 以秒为单位，精度受内核定时器频率（HZ，通常 250/300/1000）影响。
• usleep() 微秒级，nanosleep() 纳秒级（高精度定时器 hrtimer 支持）。

15. 1G 文件从 A 机器发送到 B 机器，怎么发？

方案选择：

1. 简单方案：scp / rsync

scp largefile user@B:/path/
# 或 rsync（支持断点续传、增量同步）
rsync -avz --progress largefile user@B:/path/

• 优点：简单，rsync 支持压缩和断点续传。
• 缺点：单连接，速度可能受限。

2. 高性能方案：分块并行传输

• 将 1G 文件分成多个块（如 10 个 100MB 块）。
• 多线程/多连接并行发送不同块。
• B 端按序号合并。
• 充分利用带宽，比单连接快。

3. 零拷贝方案：sendfile

• 服务器端用 sendfile() 系统调用，直接将文件数据从磁盘通过内核发送到网卡，不经过用户态拷贝。
• 比传统的 read+send 快（减少两次内存拷贝和上下文切换）。

sendfile(out_fd, in_fd, &offset, count);

4. 协议选择：

• TCP：可靠传输，自动处理丢包重传，适合文件传输。
• UDP：不可靠，需自己实现可靠传输（如 UDT、QUIC），但在高延迟高丢包网络下可能比 TCP 快。
• HTTP：简单，支持 Range 请求断点续传。

5. 优化手段：

• 调大 TCP 缓冲区：setsockopt(SO_SNDBUF/SO_RCVBUF)，增大窗口。
• 启用 TCP 窗口缩放：tcp_window_scaling=1（默认开启）。
• 调整拥塞控制算法：BBR 比 cubic 在高带宽长延迟链路下更快。
• 压缩：如果文件可压缩（文本、日志），先压缩再传输（gzip、lz4）。
• 断点续传：记录已传输偏移，中断后从断点继续（HTTP Range、rsync）。
• P2P/多源下载：从多个节点同时下载不同片段（BitTorrent 方式）。

推荐方案：

• 内网、简单需求：scp 或 rsync。
• 高性能、自定义传输：TCP + sendfile + 大缓冲区 + 可能的分块并行。
• 跨公网、不稳定网络：rsync（断点续传）或 HTTP Range。

16. 如何根据 IP 获取对方的 MAC 地址？

使用 ARP (Address Resolution Protocol，地址解析协议)。

ARP 工作原理：

• ARP 用于将 IP 地址解析为对应的 MAC 地址（物理地址）。
• 工作在数据链路层，只在同一局域网 (LAN) 内有效。

ARP 解析过程：

1. 检查 ARP 缓存：

   • 主机先检查自己的 ARP 缓存表（arp -a 查看），如果有目标 IP 对应的 MAC，直接使用。

2. 发送 ARP 请求：

   • 如果缓存中没有，主机广播 ARP 请求报文：
     • 源 MAC：自己的 MAC
     • 目的 MAC：FF:FF:FF:FF:FF:FF（广播地址）
     • 源 IP：自己的 IP
     • 目的 IP：目标 IP
     • 问题："谁拥有 IP 地址 x.x.x.x？请告诉我你的 MAC 地址。"

3. 目标主机回复 ARP 响应：

   • 局域网内所有主机都收到广播，但只有目标 IP 匹配的主机会回复。
   • 目标主机单播发送 ARP 响应报文：
     • 源 MAC：目标主机的 MAC
     • 目的 MAC：请求方的 MAC
     • 内容："IP x.x.x.x 的 MAC 地址是 xx:xx:xx:xx:xx:xx"

4. 更新 ARP 缓存：

   • 请求方收到 ARP 响应后，将 IP-MAC 映射存入 ARP 缓存。
   • 之后使用该 MAC 地址封装数据帧进行通信。

查看 ARP 缓存：

arp -a           # 查看 ARP 缓存表
ip neigh show    # 更现代的命令
arp -d <ip>      # 删除指定 ARP 条目

跨网段获取 MAC：

• ARP 只能在同一局域网内工作。
• 如果目标 IP 在不同网段，主机获取的是网关 (默认路由器) 的 MAC 地址，而不是目标主机的 MAC。
• 数据包先发送到网关，由网关路由到目标网络后，再通过目标网络的 ARP 获取目标主机 MAC。

ARP 相关问题：

• ARP 欺骗 (ARP Spoofing)：攻击者发送伪造的 ARP 响应，将自己的 MAC 伪装成网关或其他主机，实现中间人攻击。可通过静态 ARP、ARP 防火墙 (arpwatch)、DAI (Dynamic ARP Inspection) 防范。
• 免费 ARP (Gratuitous ARP)：主机主动发送自己 IP 的 ARP 请求，用于检测 IP 冲突和更新其他主机的 ARP 缓存。
• 反向 ARP (RARP)：根据 MAC 获取 IP（已被 DHCP 取代）。

17. 怎样加快大文件在网络中传输？（滑动窗口与拥塞控制）

从 TCP 滑动窗口和拥塞控制角度优化：

1. 增大滑动窗口（流量控制）：

• TCP 接收窗口 (rwnd) 限制发送方的发送量。
• 增大接收缓冲区：setsockopt(sock, SOL_SOCKET, SO_RCVBUF, &size) 和 SO_SNDBUF。
• 缓冲区越大，窗口越大，在途数据越多，吞吐量越高。
• 带宽延迟积 (BDP) = 带宽 × RTT，理想窗口大小应 ≥ BDP。
  • 例：1Gbps 带宽，100ms RTT，BDP = 1Gbps × 0.1s = 12.5MB，窗口至少 12.5MB 才能跑满带宽。
• 启用窗口缩放 (Window Scaling)：tcp_window_scaling=1（默认开启），支持最大 1GB 窗口。

2. 优化拥塞控制：

• 选择合适的拥塞控制算法：
  • cubic（Linux 默认）：通用场景。
  • bbr（Bottleneck Bandwidth and RTT）：Google 开发，在高带宽长延迟 (BDP 大) 链路下比 cubic 快很多，不依赖丢包来判断拥塞。
  • 查看：sysctl net.ipv4.tcp_congestion_control
  • 修改：sysctl -w net.ipv4.tcp_congestion_control=bbr
• 增大慢启动阈值：慢启动阶段窗口指数增长，达到 ssthresh 后线性增长。初始 ssthresh 通常很大，慢启动能快速增长。
• 避免丢包：丢包会触发拥塞控制（窗口减半），严重影响吞吐量。确保网络质量，减少丢包。

3. 应用层优化：

• 分块并行传输：将大文件分成多块，多连接并行传输，充分利用带宽（单连接可能受拥塞窗口限制）。
• 零拷贝：用 sendfile() 或 splice()，避免数据在用户态和内核态之间拷贝。
• 禁用 Nagle 算法：TCP_NODELAY，减少小包延迟（对大文件传输影响不大）。
• 启用 TCP Fast Open：减少握手延迟。
• 压缩：对可压缩文件先压缩再传输（gzip、lz4、zstd）。

4. 内核参数调优：

# 增大 TCP 缓冲区范围
sysctl -w net.core.rmem_max=16777216
sysctl -w net.core.wmem_max=16777216
sysctl -w net.ipv4.tcp_rmem="4096 87380 16777216"
sysctl -w net.ipv4.tcp_wmem="4096 65536 16777216"

# 启用窗口缩放和选择确认
sysctl -w net.ipv4.tcp_window_scaling=1
sysctl -w net.ipv4.tcp_sack=1

# 使用 BBR 拥塞控制
sysctl -w net.core.default_qdisc=fq
sysctl -w net.ipv4.tcp_congestion_control=bbr

5. 协议选择：

• 高延迟高丢包网络：考虑 QUIC (基于 UDP)，比 TCP 更快建立连接、更好的拥塞控制、无队头阻塞。
• 内网稳定网络：TCP 已足够。

18. SSH 基于 TCP 还是 UDP？

SSH (Secure Shell) 基于 TCP，默认端口 22。

原因：

• SSH 需要可靠传输，保证命令和数据不丢失、不乱序。
• TCP 提供可靠的字节流传输，适合 SSH 的交互式会话和文件传输。
• SSH 的加密、认证、压缩都建立在可靠传输之上。

SSH 协议栈：

应用层：SSH 协议（远程登录、SCP、SFTP、端口转发）
    ↓
传输层：TCP（端口 22）
    ↓
网络层：IP

SSH 的组成：

1. 传输层协议 (SSH-TRANS)：提供服务器认证、机密性、完整性。基于 TCP。
2. 用户认证协议 (SSH-USERAUTH)：客户端向服务器认证用户身份（密码、公钥、键盘交互）。
3. 连接协议 (SSH-CONNECT)：在加密隧道上复用多个通道（交互式 shell、端口转发、X11 转发等）。

基于 UDP 的类似协议：

• Mosh (Mobile Shell)：基于 UDP，支持漫游、间歇性连接、低延迟，适合移动网络。但 Mosh 初始连接仍用 SSH (TCP) 建立，之后切换到 UDP。

SSH 常见用途：

• 远程登录服务器：ssh user@host
• 文件传输：scp file user@host:/path/、sftp
• 端口转发：ssh -L 8080:localhost:80 user@host（本地转发）
• 密钥认证：免密码登录
• X11 转发：运行远程图形程序

19. 网卡的中断、几级缓存、网络瓶颈怎么解决？

网卡中断：

• 网卡收到数据包后，通过硬件中断通知 CPU 处理。
• 中断处理分为两部分：
  • 硬中断 (Top Half)：快速处理，将数据包从网卡缓冲区拷贝到内核，调度软中断。
  • 软中断 (Bottom Half)：在中断上下文外处理，完成协议栈解析、将数据交给应用层。
• 中断亲和性 (IRQ Affinity)：将网卡中断绑定到特定 CPU 核心，避免中断在多核间漂移，提高缓存命中率。
  • 查看：cat /proc/interrupts
  • 设置：echo <cpu_mask> > /proc/irq/<irq_num>/smp_affinity
• RSS (Receive Side Scaling)：多队列网卡，将接收流量分散到多个队列，每个队列绑定不同 CPU 核心，并行处理。
• RPS/RFS：软件实现的接收侧扩展，在单队列网卡上将软中断分散到多核。
• 中断合并 (Interrupt Coalescing)：网卡将多个数据包合并后触发一次中断，减少中断频率，降低 CPU 开销（但增加延迟）。

CPU 缓存级别：

• L1 缓存：最小最快，每个核心独占，分为 L1i（指令）和 L1d（数据），通常 32-64KB，延迟约 1-3 个时钟周期。
• L2 缓存：每个核心独占，通常 256KB-1MB，延迟约 10-15 个时钟周期。
• L3 缓存：所有核心共享，通常几 MB 到几十 MB，延迟约 30-40 个时钟周期。
• 内存 (RAM)：延迟约 100-200 个时钟周期。
• 缓存越大越慢，越小越快。数据访问遵循局部性原理（时间局部性、空间局部性）。

网络瓶颈及解决方法：

具体优化手段：

1. 网卡多队列 (RSS)：充分利用多核。
2. 中断绑定：将网卡中断和应用线程绑定到不同核心，避免竞争。
3. 增大缓冲区：SO_RCVBUF、SO_SNDBUF、tcp_rmem、tcp_wmem。
4. 拥塞控制算法：BBR 替代 cubic。
5. 用户态协议栈：DPDK、Solarflare OpenOnload，绕过内核协议栈，极致性能。
6. io_uring：Linux 5.1+ 的异步 I/O 接口，比 epoll 更高效。
7. 零拷贝：sendfile、splice、mmap，减少内存拷贝。
8. 监控工具：sar、nstat、ss、ethtool、perf、bcc/BPF 定位瓶颈。

四、数据结构与算法

🔥 高频题（10题）

面试中最常出现，核心知识点，建议重点掌握，能熟练默写。

1. 红黑树的思想、特点？红黑树和平衡二叉树的区别？

红黑树 (Red-Black Tree) 是一种自平衡的二叉搜索树，通过节点颜色和旋转操作保持平衡。

红黑树的五条性质：

1. 每个节点非红即黑。
2. 根节点是黑色。
3. 叶子节点（NIL 空节点）是黑色。
4. 红色节点的两个子节点必须是黑色（不能有连续红节点）。
5. 从任一节点到其每个叶子的所有路径包含相同数量的黑节点（黑高相同）。

特点：

• 插入、删除、查找都是 O(log n)。
• 最长路径不超过最短路径的 2 倍（性质 4 和 5 保证）。
• 插入最多 2 次旋转，删除最多 3 次旋转，比 AVL 树的旋转次数少。
• 广泛用于 STL 的 map/set/multimap/multiset、Java 的 TreeMap、Linux 进程调度 CFS 等。

红黑树 vs AVL 树（平衡二叉树）：

为什么 STL 用红黑树而不是 AVL？

• 红黑树插入删除的旋转次数更少，性能更稳定。
• 实际应用中插入删除比纯查找更常见。
• 红黑树的实现相对简单。

2. 海量数据 Top K 问题？

问题：从海量数据（如 10 亿条）中找出出现频率最高的前 K 个。

常见场景：热搜词统计、日志分析、推荐系统。

解法：

方法1：分治 + 哈希 + 小顶堆（最常用）

1. 分治：将海量数据通过哈希取模分到 N 个小文件中（如 hash(key) % 1000），相同 key 一定在同一个文件中。
2. 哈希统计：对每个小文件，用哈希表统计每个 key 的出现次数。
3. 小顶堆求 Top K：
   • 维护一个大小为 K 的小顶堆。
   • 遍历所有文件的统计结果，如果当前元素频率 > 堆顶（最小元素），则替换堆顶并调整堆。
   • 最终堆中就是 Top K 元素。
4. 时间复杂度：O(N) 分治 + O(M log K) 堆操作（M 为不同 key 数）。
5. 空间复杂度：每个小文件可放入内存。

方法2：哈希表 + 排序（数据量可放入内存时）

• 直接用哈希表统计频率，然后按频率排序取前 K。
• 时间 O(M log M)，空间 O(M)。

方法3：位图/布隆过滤器（判断是否存在）

• 不需要精确计数时，用布隆过滤器判断元素是否出现过。
• 有一定误判率，但空间效率极高。

方法4：Trie 树（字符串场景）

• 对字符串建立 Trie 树，在节点中计数。
• 适合字符串前缀统计。

方法5：MapReduce 分布式处理

• Map 阶段分片统计，Reduce 阶段合并。
• 适合超大规模数据（Hadoop/Spark）。

注意事项：

• 哈希分治时要确保相同 key 分到同一文件。
• 小顶堆比排序更高效（O(M log K) vs O(M log M)），K 远小于 M 时优势明显。
• 内存不够时必须分治，每块能放入内存。
• 数据有倾斜时（某些 key 特别多），单个文件可能仍超内存，需二次分治。

3. 两数之和 (LeetCode 1)？

问题：给定整数数组 nums 和目标值 target，找出和为 target 的两个整数的下标。

方法1：哈希表（O(n) 时间，O(n) 空间）

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;  // 值 -> 下标
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.count(complement)) {
            return {map[complement], i};
        }
        map[nums[i]] = i;
    }
    return {};
}

• 遍历数组，对每个元素查找 target - nums[i] 是否在哈希表中。
• 找到则返回两个下标，找不到则将当前元素存入哈希表。
• 一次遍历完成，时间 O(n)，空间 O(n)。

方法2：暴力枚举（O(n²) 时间，O(1) 空间）

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (nums[i] + nums[j] == target)
            return {i, j};

• 简单但效率低，大数据量不适用。

方法3：排序 + 双指针（O(n log n) 时间）

• 先排序，然后左右指针向中间移动。
• 但排序会打乱原始下标，需要额外记录下标。
• 适合只需要返回值而不是下标的场景。

扩展：

• 三数之和：排序 + 固定一个数 + 双指针，O(n²)。
• 四数之和：排序 + 双层循环 + 双指针，O(n³)。
• 两数之和 II（有序数组）：双指针，O(n) 时间 O(1) 空间。

4. 如何判断单链表是否有环？

方法：快慢指针（Floyd 判圈算法，O(n) 时间，O(1) 空间）

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;        // 慢指针走一步
        fast = fast->next->next;  // 快指针走两步
        if (slow == fast) return true;  // 相遇则有环
    }
    return false;  // 快指针到达尾部则无环
}

原理：

• 如果链表有环，快指针一定能追上慢指针（类似操场跑步，快的一定能套圈）。
• 如果无环，快指针会先到达尾部。
• 时间 O(n)，空间 O(1)。

求环的入口节点：

ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            // 相遇后，一个指针从头开始，一个从相遇点开始，每次都走一步
            ListNode* p = head;
            while (p != slow) {
                p = p->next;
                slow = slow->next;
            }
            return p;  // 环的入口
        }
    }
    return nullptr;
}

• 数学证明：设头到入口距离为 a，入口到相遇点距离为 b，相遇点到入口距离为 c。
• 相遇时：慢指针走了 a+b，快指针走了 a+b+n(b+c)（n 圈）。
• 快指针速度是慢指针 2 倍：2(a+b) = a+b+n(b+c) → a = (n-1)(b+c)+c。
• 所以从头走 a 步 = 从相遇点走 c 步 + (n-1) 圈，刚好在入口相遇。

其他方法：

• 哈希表：遍历链表，用 set 记录访问过的节点，遇到已访问的则有环。O(n) 时间，O(n) 空间。
• 标记法：每个节点加一个访问标记（修改节点结构，不推荐）。

5. 反转单链表？

迭代法（O(n) 时间，O(1) 空间）

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* cur = head;
    while (cur) {
        ListNode* next = cur->next;  // 保存下一个节点
        cur->next = prev;             // 反转指针
        prev = cur;                   // prev 前移
        cur = next;                   // cur 前移
    }
    return prev;  // prev 指向新的头节点
}

递归法（O(n) 时间，O(n) 空间（递归栈））

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;  // 空链表或只有一个节点
    ListNode* newHead = reverseList(head->next);  // 递归反转后面的链表
    head->next->next = head;  // 将 head 接到反转后链表的尾部
    head->next = nullptr;
    return newHead;
}

反转链表的一部分（LeetCode 92，反转从 left 到 right 的节点）：

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* pre = &dummy;
    for (int i = 0; i < left - 1; i++) pre = pre->next;
    ListNode* cur = pre->next;
    for (int i = 0; i < right - left; i++) {
        ListNode* next = cur->next;
        cur->next = next->next;
        next->next = pre->next;
        pre->next = next;
    }
    return dummy.next;
}

K 个一组反转链表（LeetCode 25）：

• 每 K 个节点为一组，组内反转，不足 K 个不反转。
• 用迭代或递归实现。

6. B 树和 B+ 树的特点及应用场景？

B 树 (B-Tree) 和 B+ 树 (B+ Tree) 都是多路平衡搜索树，专为磁盘等外部存储设计，减少 I/O 次数。

B 树特点：

• 每个节点可以存储多个关键字和多个子节点（m 阶 B 树最多 m 个子节点）。
• 每个节点既存索引（关键字），也存数据（卫星信息）。
• 所有节点都可能存数据，不只是叶子节点。
• 所有叶子节点在同一层。
• 中序遍历可得到有序序列。

B+ 树特点：

• 非叶子节点只存索引（关键字），不存数据，数据只存在叶子节点。
• 叶子节点包含所有关键字和对应的数据，叶子节点之间用链表连接（双向链表）。
• 非叶子节点的关键字都在子节点中出现（是子节点中最大/最小关键字的冗余）。
• 所有叶子节点在同一层。
• 查询任何数据都要走到叶子节点（查询路径长度稳定）。

B 树 vs B+ 树：

应用场景：

为什么数据库索引用 B+ 树而不是 B 树？

1. 范围查询高效：B+ 树叶子节点链表，范围查询只需找到起点后顺序扫描，B 树需要中序遍历多次 I/O。
2. 查询更稳定：B+ 树所有查询都走到叶子节点，路径长度相同，性能稳定。
3. 树更矮：B+ 树非叶子节点不存数据，单页能存更多关键字，树的高度更低，I/O 次数更少。
4. 全表扫描快：B+ 树只需扫描叶子节点链表，B 树需要遍历整棵树。

7. Hash 表处理冲突的方式？

哈希冲突：不同关键字通过哈希函数得到相同的哈希地址。

常见处理方法：

1. 链地址法 (Separate Chaining)：

• 每个桶挂一个链表，冲突的元素放在同一个链表中。
• 链表过长时（Java 8 阈值 8）转为红黑树。
• STL unordered_map、Java HashMap 都用这种方法。
• 优点：简单，删除方便，装载因子可大于 1。
• 缺点：链表节点分散，缓存不友好；额外指针开销。

2. 开放寻址法 (Open Addressing)：

• 所有元素都存在哈希表数组中，冲突时探测下一个空位。
• 线性探测：依次检查下一个位置 (hash+1) % n、(hash+2) % n...
  • 简单，但容易产生"聚集"（primary clustering），连续占用导致探测序列变长。
• 二次探测：(hash + i²) % n，减少聚集。
• 双重哈希：用第二个哈希函数决定步长 (hash1 + i × hash2) % n，聚集最少。
• 优点：数组连续，缓存友好，无指针开销。
• 缺点：删除复杂（需标记删除或重新哈希），装载因子不能太高（通常 ≤ 0.7），聚集问题。
• 应用：Python 字典、Redis 字典（早期）、Go map。

3. 再哈希法 (Rehashing)：

• 准备多个哈希函数，冲突时换一个哈希函数。
• hash2(key)、hash3(key)...
• 优点：不易聚集。
• 缺点：计算多个哈希函数开销大，可能仍冲突。

4. 建立公共溢出区：

• 哈希表分基本表和溢出表，冲突的元素都放入溢出表。
• 简单，但溢出区查找是线性的，冲突多时效率低。

负载因子 (Load Factor)：

• α = 元素数 / 桶数。
• α 越大，冲突概率越高，查找越慢。
• 链地址法 α 可 > 1（链表变长）。
• 开放寻址法 α 通常 < 0.7，超过则 rehash（扩容）。

Rehash（扩容）：

• 当负载因子超过阈值时，创建更大的哈希表（通常 2 倍），将所有元素重新哈希到新表。
• 渐进式 rehash（Redis）：不一次性迁移，而是在后续操作中逐步迁移，避免阻塞。

选择建议：

• 通用场景用链地址法（实现简单，性能稳定）。
• 对缓存性能要求高、元素小的场景用开放寻址法。

8. 一致性哈希？

一致性哈希 (Consistent Hashing) 是一种哈希算法，解决分布式系统中节点增减时数据迁移量大的问题。

传统哈希的问题：

• hash(key) % N 分配数据到 N 个节点。
• 当节点数从 N 变为 N+1 时，几乎所有 key 的映射位置都会改变，需要大量数据迁移。

一致性哈希原理：

1. 哈希环：将哈希空间（如 0 ~ 2^32-1）组织成一个环。
2. 节点映射：将每个服务器节点（通过 IP/ID 哈希）映射到环上的某个位置。
3. 数据映射：将每个 key 哈希到环上的位置，然后顺时针找到第一个节点，该节点就是数据存储的节点。

        哈希环 (0 ~ 2^32-1)
              0
             / \
           /     \
    节点A         节点B
         \  key1 /
          \    /
           节点C

• key1 顺时针找到的第一个节点是节点 B，所以 key1 存在节点 B。

节点增减的影响：

• 新增节点：只影响新节点到其逆时针方向上一个节点之间的数据，只需迁移这部分数据到新节点。
• 删除节点：该节点的数据迁移到其顺时针下一个节点。
• 其他数据不受影响。

虚拟节点 (Virtual Nodes)：

• 问题：节点少时，数据分布可能不均匀（某些节点负责的环范围大）。
• 解决：每个物理节点对应多个虚拟节点（如 150 个），虚拟节点分布在环上。
• 数据映射到虚拟节点，虚拟节点再映射到物理节点。
• 虚拟节点越多，分布越均匀，节点增减时迁移量越小。

应用场景：

• 分布式缓存（Redis Cluster、Memcached 客户端）。
• 分布式存储（DynamoDB、Cassandra）。
• 负载均衡（需要会话保持且动态扩缩容）。
• CDN 内容路由。

优点：

• 节点增减时只影响相邻节点的数据，迁移量小。
• 可扩展性好，适合动态分布式系统。

缺点：

• 实现复杂。
• 节点少时数据可能不均（需虚拟节点解决）。
• 不支持精确的节点权重（可通过虚拟节点数量调整）。

9. LRU 实现原理？

LRU (Least Recently Used，最近最少使用) 缓存淘汰算法：当缓存满时，淘汰最久未使用的数据。

数据结构：哈希表 + 双向链表

哈希表：key -> 链表节点指针（O(1) 查找）
双向链表：按访问时间排序，头部是最近使用，尾部是最久未使用

        head ↔ [节点1] ↔ [节点2] ↔ [节点3] ↔ tail
        最近使用                          最久未使用（淘汰）

C++ 实现：

class LRUCache {
    struct Node {
        int key, value;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };

    int capacity_;
    unordered_map<int, Node*> map_;
    Node* head_;  // 哑节点，简化边界处理
    Node* tail_;

    // 将节点移到头部（最近使用）
    void moveToHead(Node* node) {
        removeNode(node);
        addToHead(node);
    }

    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void addToHead(Node* node) {
        node->next = head_->next;
        node->prev = head_;
        head_->next->prev = node;
        head_->next = node;
    }

    Node* removeTail() {
        Node* node = tail_->prev;
        removeNode(node);
        return node;
    }

public:
    LRUCache(int capacity) : capacity_(capacity) {
        head_ = new Node(0, 0);
        tail_ = new Node(0, 0);
        head_->next = tail_;
        tail_->prev = head_;
    }

    int get(int key) {
        if (!map_.count(key)) return -1;
        Node* node = map_[key];
        moveToHead(node);  // 访问后移到头部
        return node->value;
    }

    void put(int key, int value) {
        if (map_.count(key)) {
            Node* node = map_[key];
            node->value = value;
            moveToHead(node);
        } else {
            Node* node = new Node(key, value);
            map_[key] = node;
            addToHead(node);
            if (map_.size() > capacity_) {
                Node* removed = removeTail();  // 淘汰尾部
                map_.erase(removed->key);
                delete removed;
            }
        }
    }
};

操作复杂度：get 和 put 都是 O(1)。

C++ STL 简化实现：用 std::list（双向链表）+ unordered_map（存迭代器）：

class LRUCache {
    int cap;
    list<pair<int,int>> cache;  // 链表，头部最近使用
    unordered_map<int, list<pair<int,int>>::iterator> map;
public:
    LRUCache(int capacity) : cap(capacity) {}
    int get(int key) {
        if (!map.count(key)) return -1;
        auto it = map[key];
        cache.splice(cache.begin(), cache, it);  // 移到头部
        return it->second;
    }
    void put(int key, int value) {
        if (map.count(key)) {
            map[key]->second = value;
            cache.splice(cache.begin(), cache, map[key]);
        } else {
            if (cache.size() == cap) {
                map.erase(cache.back().first);
                cache.pop_back();
            }
            cache.push_front({key, value});
            map[key] = cache.begin();
        }
    }
};

其他缓存淘汰算法：

• LFU (Least Frequently Used)：淘汰使用次数最少的，需维护频率计数。
• FIFO：先进先出，淘汰最早进入的。
• ARC (Adaptive Replacement Cache)：自适应，结合 LRU 和 LFU。
• 2Q：两个队列，热数据和冷数据分离。

10. 快速排序算法思想？

快速排序 (Quick Sort) 是一种基于分治思想的排序算法。

核心思想：

1. 选择基准 (Pivot)：从数组中选择一个元素作为基准。
2. 分区 (Partition)：将数组分为两部分，小于基准的放左边，大于基准的放右边，基准在中间。
3. 递归排序：对左右两部分分别递归进行快速排序。

分区过程（Hoare 分区 / Lomuto 分区）：

int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right];  // 选最后一个元素为基准
    int i = left - 1;         // i 指向小于基准区域的末尾
    for (int j = left; j < right; j++) {
        if (nums[j] <= pivot) {
            i++;
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[i + 1], nums[right]);  // 基准放到正确位置
    return i + 1;
}

void quickSort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int pi = partition(nums, left, right);
        quickSort(nums, left, pi - 1);   // 排序左半部分
        quickSort(nums, pi + 1, right);   // 排序右半部分
    }
}

复杂度分析：

• 平均时间：O(n log n)。
• 最好时间：O(n log n)（每次分区均匀）。
• 最坏时间：O(n²)（每次选到最大/最小元素，如已排序数组选首元素为基准）。
• 空间：O(log n)（递归栈），最坏 O(n)。
• 不稳定排序：相等元素的相对顺序可能改变。

优化方法：

1. 随机化基准：随机选择基准元素，避免最坏情况（已排序数组）。
2. 三数取中：取首、中、尾三个元素的中位数作为基准。
3. 小数组用插入排序：当子数组长度 < 阈值（如 10）时，用插入排序（小数组插入排序更快）。
4. 尾递归优化：只递归较小的一半，较大的一半用循环，减少栈深度。
5. 三路快排 (Dutch National Flag)：将数组分为小于、等于、大于基准三部分，适合有大量重复元素的场景。

三路快排：

void quickSort3Way(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int pivot = nums[left + rand() % (right - left + 1)];
    int lt = left, gt = right, i = left;
    while (i <= gt) {
        if (nums[i] < pivot) swap(nums[i++], nums[lt++]);
        else if (nums[i] > pivot) swap(nums[i], nums[gt--]);
        else i++;
    }
    quickSort3Way(nums, left, lt - 1);
    quickSort3Way(nums, gt + 1, right);
}

应用：快速排序是实际应用中最快的通用排序算法之一，C 的 qsort、C++ 的 std::sort（ introsort，快排+堆排+插入排序混合）都基于快排。

📌 中频题（6题）

比较常见，部分公司会问到，建议理解并能口述要点。

1. 负载均衡算法？

负载均衡 (Load Balancing) 将请求分发到多个服务器，提高系统吞吐量和可用性。

常见算法：

选择建议：

• 服务器性能相近、无状态服务：轮询。
• 服务器性能差异大：加权轮询。
• 需要会话保持：IP Hash 或 Cookie 会话保持。
• 长连接/连接耗时差异大：最少连接。
• 动态扩缩容频繁：一致性哈希。
• 生产环境通常结合健康检查和多种算法。

2. 合并两个有序数组或链表？

合并两个有序数组（in-place，nums1 有足够空间）：

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

• 从后往前合并，避免覆盖 nums1 中未处理的元素。
• 时间 O(m+n)，空间 O(1)。

合并两个有序链表：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    cur->next = l1 ? l1 : l2;
    return dummy.next;
}

• 时间 O(m+n)，空间 O(1)。
• 用哑节点简化头节点处理。

递归版本（链表）：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

扩展：合并 K 个有序链表

• 方法1：两两合并，O(N log K)。
• 方法2：小顶堆，每次取 K 个链表头中最小的，O(N log K)。

3. 实现一个栈，O(1) 时间求最小元素？

思路：用两个栈，一个数据栈存元素，一个辅助栈存当前最小值。

class MinStack {
    stack<int> data_;   // 数据栈
    stack<int> min_;    // 最小栈，栈顶始终是当前最小值
public:
    void push(int x) {
        data_.push(x);
        if (min_.empty() || x <= min_.top()) {
            min_.push(x);  // 新元素 <= 当前最小值时，入最小栈
        }
    }

    void pop() {
        if (data_.top() == min_.top()) {
            min_.pop();  // 弹出的是当前最小值时，最小栈也弹出
        }
        data_.pop();
    }

    int top() {
        return data_.top();
    }

    int getMin() {
        return min_.top();  // O(1)
    }
};

优化：减少辅助栈空间

• 当新元素 > 当前最小值时，辅助栈重复压入当前最小值（而不是不压入），这样 pop 时两个栈同步弹出，不需要判断。

void push(int x) {
    data_.push(x);
    min_.push(min_.empty() ? x : min(x, min_.top()));
}
void pop() {
    data_.pop();
    min_.pop();  // 同步弹出
}

• 缺点：辅助栈空间始终和数据栈一样大。

另一种优化：差值法（O(1) 额外空间）

• 栈中存储元素与当前最小值的差值，用一个变量存当前最小值。
• 弹出时根据差值恢复之前的最小值。
• 空间更优但有溢出风险。

4. 怎么判断单链表是否相交？

问题：判断两个单链表是否相交，如果相交返回第一个相交节点。

方法1：双指针法（O(n+m) 时间，O(1) 空间，最优）

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    if (!headA || !headB) return nullptr;
    ListNode* pA = headA;
    ListNode* pB = headB;
    while (pA != pB) {
        pA = pA ? pA->next : headB;  // A 走完后走 B
        pB = pB ? pB->next : headA;  // B 走完后走 A
    }
    return pA;  // 相交则返回交点，不相交则返回 nullptr
}

原理：

• 指针 A 走完链表 A 后走链表 B，指针 B 走完链表 B 后走链表 A。
• 两个指针走的总长度相同（lenA + lenB）。
• 如果相交，它们会在交点相遇（因为交点之后的公共部分长度相同）。
• 如果不相交，它们会同时走到 nullptr（都走了 lenA+lenB）。

方法2：哈希集合法（O(n+m) 时间，O(n) 空间）

• 遍历链表 A，将所有节点存入哈希集合。
• 遍历链表 B，检查每个节点是否在哈希集合中。
• 第一个在集合中的节点就是交点。

方法3：尾节点法（判断是否相交，但不返回交点）

• 分别遍历到两个链表的尾节点，如果尾节点相同则相交。
• 但不能找到第一个交点。

方法4：长度差法

• 分别计算两个链表的长度 lenA、lenB。
• 长链表先走 |lenA - lenB| 步，然后两个链表同时走，第一个相同节点就是交点。

注意：

• 链表相交指的是节点引用相同（地址相同），不是节点值相同。
• 相交后的链表共享尾部，形状像 "Y" 而不是 "X"（单链表每个节点只有一个 next）。

5. 快排和堆排的应用场景？

快速排序应用场景：

• 通用的内存排序，大多数场景的首选。
• 数据量较大且内存足够。
• 对平均性能要求高，能接受极少数最坏情况（通过随机化基准基本避免）。
• C++ std::sort、Java Arrays.sort（基本类型）都用快排变体。

堆排序应用场景：

• Top K 问题：求最大/最小的 K 个元素，用小顶堆/大顶堆，O(n log K)。
• 优先队列：任务调度、Dijkstra 最短路径、哈夫曼编码。
• 内存严格受限：需要 O(1) 额外空间且保证 O(n log n) 最坏时间。
• 实时系统：不能接受快排最坏 O(n²) 的场景。
• 排序本身用得少（因为实际比快排慢），但堆数据结构应用广泛。

Top K 问题对比：

• 用快排思想（快速选择）：O(n) 平均时间，O(1) 空间，但会修改原数组。
• 用堆排序（小顶堆）：O(n log K) 时间，O(K) 空间，不修改原数组，适合流式数据。
• 海量数据 Top K：堆排序更适合（不需要全部数据放入内存）。

选择建议：

• 纯排序用快排（更快、缓存友好）。
• Top K、优先队列、动态最值用堆。
• 内存极度受限且需保证最坏性能用堆排序。

6. std::sort 的实现方法？

std::sort 是 C++ STL 的排序算法，采用 Introsort (内省排序)，是快速排序、堆排序、插入排序的混合算法。

实现原理（GCC libstdc++）：

1. 快速排序为主：

   • 默认使用快速排序，三数取中选择基准（首、中、尾的中位数）。
   • 递归分区，平均 O(n log n)。

2. 递归深度监控（防止最坏情况）：

   • 监控递归深度，当深度超过 2 × log2(n) 时，认为快排退化（遇到最坏情况）。
   • 切换到堆排序，保证最坏 O(n log n)。
   • 这就是 Introsort 的核心：快排平均快，堆排保底。

3. 小数组用插入排序：

   • 当子数组长度小于阈值（通常 16）时，切换到插入排序。
   • 小数组插入排序比快排快（常数因子小，无递归开销，缓存友好）。
   • 插入排序对近乎有序的数据效率极高。

伪代码：

void sort(first, last) {
    if (last - first <= 1) return;
    if (last - first <= 16) {
        insertion_sort(first, last);  // 小数组插入排序
        return;
    }
    if (depth_limit <= 0) {
        heap_sort(first, last);  // 递归过深，堆排序保底
        return;
    }
    depth_limit--;
    pivot = median_of_three(*first, *(mid), *(last-1));
    p = partition(first, last, pivot);  // 分区
    sort(first, p);       // 递归左半
    sort(p + 1, last);    // 递归右半
}

复杂度：

• 平均 O(n log n)，最坏 O(n log n)（Introsort 保证）。
• 空间 O(log n)（递归栈）。
• 不稳定排序。

其他 STL 排序算法：

• std::stable_sort：稳定排序，归并排序实现，O(n log n) 时间，O(n) 额外空间。
• std::partial_sort：部分排序，堆排序实现，只排序前 K 个元素，O(n log K)。
• std::nth_element：快速选择，O(n) 平均时间，找第 K 大/小元素。
• std::sort_heap：堆排序。

为什么用 Introsort？

• 纯快排最坏 O(n²)，不可接受。
• 纯堆排序常数因子大，实际比快排慢。
• Introsort 结合两者优点：平均情况快排的速度，最坏情况堆排的保证。

💡 低频题（4题）

较少出现或较偏，时间充裕时了解即可。

1. 有损压缩和无损压缩算法？

无损压缩算法：

1. Huffman 编码：

   • 根据字符出现频率构建最优二叉树，频率高的字符用短编码，频率低的用长编码。
   • 前缀编码，无歧义。
   • 广泛用于 DEFLATE、JPEG（熵编码阶段）。

2. LZ77/LZ78 (Lempel-Ziv)：

   • 用"长度-偏移"对替换重复出现的字符串。
   • LZ77 用滑动窗口，LZ78 用字典。
   • DEFLATE (gzip/zip/png) = LZ77 + Huffman。

3. LZW：

   • LZ78 的变体，动态构建字典。
   • 用于 GIF、TIFF、旧版 Unix compress。

4. 算术编码 (Arithmetic Coding)：

   • 将整个消息编码为 [0,1) 区间的一个小数。
   • 比 Huffman 更接近熵极限，但实现复杂、有专利问题（已过期）。
   • 用于 JPEG2000、H.264 的 CABAC。

5. RLE (行程编码)：

   • 将连续重复的字符表示为"计数+字符"。
   • 简单，适合有大量连续重复的数据（如位图、传真）。

有损压缩算法：

1. JPEG：

   • 图像分 8×8 块 → DCT 变换 → 系数量化（丢弃高频）→ Zigzag 扫描 → RLE + Huffman。
   • 人眼对亮度敏感、对色度不敏感，可降低色度采样率 (4:2:0)。

2. MP3/AAC：

   • 心理声学模型，丢弃人耳听不到的频率（掩蔽效应）。
   • 变换编码、量化、霍夫曼编码。

3. H.264/H.265：

   • 帧内预测（空间冗余）、帧间预测（时间冗余，运动估计/补偿）、变换、量化、熵编码。
   • H.265 (HEVC) 比 H.264 压缩率提高约 50%。

2. 三个有序序列，查找公共部分？

问题：给定三个有序数组，找出它们的公共元素（交集）。

方法1：三指针法（最优，O(n) 时间，O(1) 空间）

vector<int> intersection(vector<int>& a, vector<int>& b, vector<int>& c) {
    vector<int> result;
    int i = 0, j = 0, k = 0;
    while (i < a.size() && j < b.size() && k < c.size()) {
        if (a[i] == b[j] && b[j] == c[k]) {
            result.push_back(a[i]);
            i++; j++; k++;
        } else {
            // 移动指向最小值的指针
            int mn = min({a[i], b[j], c[k]});
            if (a[i] == mn) i++;
            if (b[j] == mn) j++;
            if (c[k] == mn) k++;
        }
    }
    return result;
}

• 时间复杂度：O(n1 + n2 + n3)，每个指针最多遍历完自己的数组。
• 空间复杂度：O(1)（不计结果）。
• 处理重复元素：如果数组有重复，找到公共元素后跳过所有相同值。

方法2：哈希集合法（O(n) 时间，O(n) 空间）

• 先用第一个数组构建哈希集合。
• 用第二个数组过滤，得到前两个的交集集合。
• 再用第三个数组过滤。
• 适合数组很大但内存足够的情况，不需要有序。

方法3：二分查找法（O(n log n) 时间）

• 遍历最短数组的每个元素，在另外两个数组中二分查找。
• 时间 O(min(n) × log(max(n)))。
• 适合一个数组特别短的情况。

选择建议：数组有序时优先用三指针法，时间空间最优。

3. 100G 文本，求重复最多的行？（多机多进程）

问题：100G 文本文件，每行 80 字符，一台机器 8G 内存，多机多进程求重复最多的行。

思路：分治 + 哈希统计 + 归并

单机方案（内存不够时）：

1. 分治（哈希分片）：

   • 遍历 100G 文件，对每行内容计算哈希值 hash(line) % N（N 如 1000）。
   • 将每行写入对应的小文件（共 N 个文件，每个约 100MB）。
   • 相同行一定在同一个小文件中。
   • 每台机器处理一部分小文件。

2. 哈希统计：

   • 对每个小文件（可放入 8G 内存），用 unordered_map<string, int> 统计每行出现次数。
   • 多进程并行处理不同的小文件。

3. 求 Top 1（或 Top K）：

   • 每个小文件统计完后，记录出现次数最多的行。
   • 所有小文件的结果归并，找出全局重复最多的行。
   • 可用小顶堆维护 Top K。

多机分布式方案（MapReduce 思想）：

1. Map 阶段：

   • 将 100G 文件切分成多个块（如 64MB/块），分发到多台机器。
   • 每台机器对自己的块进行哈希统计（局部统计）。
   • 输出 <line, count> 键值对。

2. Shuffle 阶段：

   • 按 key (line) 哈希分区，相同 line 分发到同一个 Reduce 节点。
   • 网络传输中间结果。

3. Reduce 阶段：

   • 每个 Reduce 节点对相同 line 的 count 求和，得到全局计数。
   • 所有 Reduce 结果归并，找出重复最多的行。

内存估算：

• 每行 80 字节 + 计数 4 字节 + 哈希表开销（约 40 字节/条目）≈ 124 字节/条目。
• 8G 内存可存约 6000 万条不同行。
• 如果单个分片仍超内存，增大分片数 N（二次分治）。

注意事项：

• 哈希分片要均匀，避免数据倾斜（某些行特别多导致单个文件过大）。
• 数据倾斜时对热点 key 可进一步分治或用组合 key。
• 多机间数据传输是瓶颈，需尽量减少 Shuffle 数据量（Combiner 局部合并）。
• 容错：某台机器失败时重新分配任务。

4. 将奇数放于数组前面，偶数放于后面？

方法：双指针（O(n) 时间，O(1) 空间）

void reOrderArray(vector<int>& array) {
    int left = 0, right = array.size() - 1;
    while (left < right) {
        // 左指针找偶数
        while (left < right && array[left] % 2 == 1) left++;
        // 右指针找奇数
        while (left < right && array[right] % 2 == 0) right--;
        // 交换
        if (left < right) {
            swap(array[left], array[right]);
        }
    }
}

• 左指针从左往右找偶数，右指针从右往左找奇数，找到后交换。
• 时间 O(n)，空间 O(1)。
• 不保证奇数之间和偶数之间的相对顺序。

如果要求保持相对顺序（稳定）：

void reOrderArrayStable(vector<int>& array) {
    vector<int> odd, even;
    for (int x : array) {
        if (x % 2 == 1) odd.push_back(x);
        else even.push_back(x);
    }
    array.clear();
    array.insert(array.end(), odd.begin(), odd.end());
    array.insert(array.end(), even.begin(), even.end());
}

• 时间 O(n)，空间 O(n)。
• 类似快速排序的 partition 操作，稳定版本需要额外空间。

扩展：这是快速排序中 partition 的基础操作，也可用于荷兰国旗问题（三色排序）。

五、数据库

🔥 高频题（11题）