面試問題：進程和線程，編譯步驟，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)。