面试问题：进程和线程，编译步骤，const，map和unordered_map，深入理解unordered

进程和线程的区别

const修饰指针(左边内容，右边指向)

1. const 修饰指针指向的内容（指向常量）

2. const 修饰指针本身（常量指针）

3. const 同时修饰指针本身和指向的内容（指向常量的常量指针）

一句话速答版（面试用）

编译的四个步骤

map和unordered_map的区别

底层实现

元素有序性与遍历

性能与时间复杂度

内存占用

unordered_map的深入理解

前言

unordered_map的结构

复杂度问题

哈希冲突问题

rehash(重新构建哈希表) 和负载因子

看似不起波澜的日复一日，相信总有一天会让我看到坚持的意义。

——2025/9/2

进程和线程的区别

进程是操作系统资源分配的基本单位，而线程是CPU调度的基本单位。

资源分配与调度

进程：它拥有独立的内存地址空间、文件句柄、I/O设备等资源。操作系统为每个进程分配这些资源。
线程：它不拥有独立的资源，而是共享其所属进程的资源。比如，同一个进程内的所有线程都共享该进程的内存空间和文件句柄。线程是CPU调度的最小单位，也就是CPU真正执行的实体。

通信机制

进程间通信（IPC）：管道、消息队列、共享内存、信号、socket 等，开销较大。

线程间通信：共享进程的内存空间，可以直接读写，但需要加锁保证同步。

适用场景

多进程：适合于隔离性要求高的任务，比如浏览器中的不同标签页，或者服务器中处理不同用户请求的进程。一个标签页崩溃了，不会影响其他标签页。
多线程：适合于需要高并发，频繁通信和共享数据的任务，比如图形界面（UI）的响应、高并发的网络服务器（如 Web 服务器中的线程池）。在服务器中，一个进程可以创建多个线程来处理不同的客户端连接，效率更高。

const修饰指针(左边内容，右边指向)

const 在修饰指针时主要有三种修饰方式，理解它们关键在于弄清楚 const 关键字修饰的是什么。

👉 const 在星号左边：修饰指针所指的内容；在星号右边：修饰指针本身。

想想也对，因为 int* const p中const紧贴着p，const自然是修饰p的p又是一个指针变量，那么指针变量的值不可变，const自然修饰的是指针本身。

1. const 修饰指针指向的内容（指向常量）

在这种情况下，const 位于星号（*）的左侧，无论是紧挨着类型名还是紧挨着星号，效果都是一样的。

示例：const int *p; 或 int const *p;

int a = 10, b = 20;
const int* p = &a;
*p = 20; // ❌ 错误
p = &b; // ✅ 合法

含义：p 是一个指向“常量整型”的指针。

特点：

*p 不可修改（不能通过 p 改变所指对象的值）。
p 本身可以修改（可以指向别的地址）。

2. const 修饰指针本身（常量指针）

含义：p 是一个“常量指针”，一旦初始化，就不能再指向别的对象。

示例：int *const p = &a;

int a = 10, b = 20;
int* const p = &a;
*p = 30; // ✅ 合法
p = &b; // ❌ 错误

特点：

p 不可修改（指向固定）。
*p 可修改（能通过 p 改变所指对象的值）。

3. const 同时修饰指针本身和指向的内容（指向常量的常量指针）

含义：p 是一个指向“常量整型”的常量指针。

示例：const int *const p = &a;

int a = 10, b = 20;
const int* const p = &a;
*p = 20; // ❌ 错误
p = &b; // ❌ 错误

特点：

p 不可修改（指针不能改变指向）。
*p 不可修改（指向的值也不能通过它改）。

一句话速答版（面试用）

const 修饰指针有三种情况：

const int* p：指向的值不能改，指针能改；
int* const p：指针不能改，指向的值能改；
const int* const p：指针和值都不能改。

编译的四个步骤

从源代码到可执行文件一般分为四步：预处理(4种处理)、编译(又可进一步分成多个阶段)、汇编(汇编代码转化成机器码)、链接(两种链接方式)。编译阶段内部又可以细分为词法分析、语法分析、语义分析、中间代码生成、优化和目标代码生成。

详细介绍请看文章：

编译过程详解，库的介绍，静态库的制作与运用，动态库的制作与运用，库中的符号冲突问题和库相互依赖问题_库文件编译-CSDN博客

关于什么时候使用静态链接什么时候用动态链接也要知道，一般涉及到系统移植建议用静态链接，可执行文件中包含了一切需要的库文件，部署打包更加方便。

map和unordered_map的区别

底层实现

map：底层通常由红黑树实现。红黑树是一种自平衡二叉查找树，它能确保在插入、删除和查找操作后，树的结构依然保持平衡。

unordered_map：底层由哈希表实现。它通过哈希函数将键（key）映射到哈希表中的一个桶（bucket）里，以实现快速访问。

元素有序性与遍历

有序性

map：自动按 key 排序（默认升序，可以自定义比较器）。
unordered_map：元素无序存储，不保证遍历顺序。

遍历

map：有序遍历，支持区间操作（比如 lower_bound（>=）、upper_bound（>））。

unordered_map：无序遍历，不支持按区间查找。

区间查找指的是在一个数据集合中，查找所有满足某个特定范围条件的元素。在 map 里，迭代器返回的位置就是“边界点”，它把元素分成了两部分

map 默认是按键升序排列的有序容器。lower_bound(key) 返回第一个不小于(>=) key 的元素的迭代器。

左边（begin 到返回迭代器之前）：

全部 < key → 不满足 >= key 的条件。

右边（从返回迭代器到 end）：

全部 >= key → 满足条件。

性能与时间复杂度

map：插入、删除、查找的平均时间复杂度都是 O(logN)。

优点：对于需要稳定性能（即最坏情况下的性能也能得到保证）和有序访问的场景非常合适。

unordered_map：插入、删除、查找的平均时间复杂度是 O(1)。

缺点：在最坏情况下（例如，哈希冲突严重），时间复杂度会退化到 O(N)。此外，它的性能高度依赖于哈希函数的质量和负载因子。

内存占用

map：相对较省内存（树节点开销）。

unordered_map：需要哈希表 + 桶结构，内存开销更大。

unordered_map的深入理解

前言

之前我有介绍部分关于unordered_map的深入理解，可以先看一下，主要里面介绍了扩容机制，哈希冲突的解决方式（链地址法和开放地址法）

unordered_map和哈希表的使用_map自定义哈希函数-CSDN博客

在面试的时候unordered_map真的是一个非常非常高频的考点！！！所以下面我将更深入地聊一下这个问题

unordered_map的结构

unordered_map 的哈希表 + 桶结构是其实现高效查找的基石

哈希表可以理解为unordered_map的主干，它是一个内部的数组，这个数组里的每一个元素都叫做一个桶（Bucket）。

一个桶里可能存放 0 个、1 个或多个元素。为什么会有多个？

👉 因为 哈希冲突：不同的 key 经过哈希函数后可能得到相同的下标。

所以每个桶不是只放一个元素，而是通常会用链表 / 动态数组来存放同一个哈希值的所有元素。

比如我们有 unordered_map<string,int>，桶数是 8（N=8）：

Index: 0 1 2 3 4 5 6 7
Bucket: [ ] [ ] [A] [ ] [B,C] [ ] [ ] [D]

复杂度问题

Q：为什么 unordered_map 查找是 O(1)？最坏情况为什么是 O(n)？

平均情况：哈希函数分布均匀，桶内元素少，查找是 O(1)。
最坏情况：所有元素都冲突到同一个桶 → 等价于链表查找 → O(n)。

哈希冲突问题

Q：哈希冲突是怎么解决的？

STL 实现里通常是 拉链法（separate chaining）：桶里存链表/动态数组。
也有一些实现用 开放寻址法（open addressing），不过 unordered_map 一般是拉链法。

为什么不用开放寻址法？

C++ 标准库没有强制规定必须用拉链法，但 几乎所有主流实现（GCC 的 libstdc++、Clang 的 libc++、MSVC STL）都采用拉链法。

原因是：

拉链法更容易处理删除操作（直接删链表节点即可）。

开放寻址法删除时需要“墓碑标记”，实现复杂。

拉链法在装载因子不是太高时性能更稳定。

为了解决哈希冲突（不同键有相同的哈希值），每个桶通常是一个链表（在 C++11 后，如果元素过多会转换为红黑树以提高性能）,当多个键被哈希到同一个桶时，它们会以链表的形式被连接起来。所以查找元素时，先通过哈希函数定位到桶，然后遍历该桶内的链表来找到目标元素。

C++11 引入的性能优化

哈希冲突严重的情况：

当哈希函数设计得不好，或者数据本身就存在某种规律导致大量键的哈希值相同或相近时，一个桶里的链表会变得非常长。此时，对这个桶内的元素的查找，时间复杂度会从 O(1) 退化到 O(N)（其中 N 是该链表的长度）。这会严重影响 unordered_map 的性能。

为了解决这个问题，从 C++11 开始，标准库的实现引入了一个优化机制：

当一个桶中的元素数量（即链表长度）超过一个阈值（这个阈值是编译器实现决定的，通常是 8 或 10）时，unordered_map 会自动将该桶的数据结构从链表转换为红黑树。
红黑树是一种自平衡的二叉查找树。
这样一来，在这个桶内的查找、插入和删除操作的时间复杂度就从线性的 O(N) 降到了对数的 O(logN)。