聊到 C 里出鏡率最高的數(shù)據(jù)結(jié)構(gòu)哈希表絕對排得進前三。刷題、寫游戲服務(wù)器、做緩存中間件甚至寫個詞頻統(tǒng)計的小工具都逃不過它的身影。而鏈式地址法也叫拉鏈法、鏈地址法就是理解哈希表最經(jīng)典的一張地圖沖突了就往鏈表上掛簡單、直觀、沒有任何高深技巧。但恰恰是這種“簡單”里藏著不少值得掰開揉碎講透的東西。堆內(nèi)存怎么管理負載因子怎么定擴容時鏈表怎么處理自定義 key 怎么哈希這些細節(jié)決定了你手寫的是一個能用的玩具還是一個能上工程的容器。這篇文章我會從零開始把鏈式地址法哈希表的原理、C 實現(xiàn)、性能調(diào)優(yōu)和常見坑位一次性講清楚。適合正在學數(shù)據(jù)結(jié)構(gòu)的同學、準備面試的人以及想真正搞懂 unordered_map 底層邏輯的工程黨。全文代碼可直接編譯運行你可以邊看邊敲領(lǐng)會一下“哈希函數(shù) 沖突解決”這兩個核心環(huán)節(jié)是如何配合的。1. 為什么要用鏈式地址法先搞清楚哈希表到底在解決什么1.1 哈希表的核心思想用空間換時間哈希表的目標很簡單把“查找”這件事從 O(n) 降到 O(1)。數(shù)組之所以快是因為下標和元素位置天然一一對應(yīng)你可以直接算出地址不需要比較。但現(xiàn)實中我們的大多數(shù) key 不是非負整數(shù)而是字符串、對象、自定義結(jié)構(gòu)體。哈希函數(shù)就是那個“翻譯官”把任意類型的 key 壓縮成一個整數(shù)下標。問題是key 的集合往往遠大于下標的集合。比如你有一萬個不同的字符串但桶數(shù)組只有 16 個格子那必然有多個 key 映射到同一個下標。Hash 桶的長度確定不了 key 在不在桶里這就是“哈希沖突”。鏈式地址法的思路簡單粗暴每個桶不是一個元素而是一條鏈表沖突的鍵全塞進同一條鏈表里。這跟你在學校儲物柜存放東西是一個道理。假設(shè)柜子只有 16 格有一百個學生的書包要存。如果每個柜子只能放一個包沖突時就得去別的樓層找空柜子這就是開放地址法的思路線性探測就是去隔壁柜子找。而鏈式地址法相當于每個柜子后面接了一個傳送帶不管多少書包都能掛在同一條傳送帶上找的時候先定位到柜子再沿傳送帶一個個找過去。1.2 哈希函數(shù)一切性能的前提鏈式地址法本身不解決哈希函數(shù)質(zhì)量差的問題。如果哈希函數(shù)把所有 key 都映射到同一個下標那么哈希表退化成一個鏈表所有操作變成 O(n)。所以哈希函數(shù)的第一要求是分布均勻讓每個桶里的鏈表盡量短。C 里最簡單的哈希實現(xiàn)是std::hashT。對于整數(shù)它通常直接返回數(shù)值本身對于字符串std::stringlibstdc 的實現(xiàn)會對每個字符做多項式哈希BKDR 哈希的變體。如果你需要自定義類型最常見的做法是把內(nèi)部字段組合成一個尺寸足夠大的哈希值再對桶數(shù)取模。struct Student { int id; std::string name; bool operator(const Student other) const { return id other.id name other.name; } }; namespace std { template struct hashStudent { size_t operator()(const Student s) const noexcept { // 把多個字段的哈希值混合成一個避免簡單拼接帶來的碰撞 size_t h1 hashint{}(s.id); size_t h2 hashstring{}(s.name); return h1 ^ (h2 1); // 或使用 boost::hash_combine 的寫法 } }; }這里有一個容易被忽略的坑std::hash對很多內(nèi)置類型只是轉(zhuǎn)了一下質(zhì)量并不高。比如你有一批整數(shù) key恰好都是 4 的倍數(shù)直接對 16 取模的話它們的桶下標永遠是 0、4、8、12 四個值其他桶全空。這就是“哈希聚集”現(xiàn)象。最穩(wěn)妥的做法是在hash(key) % bucket_count之前做一個位混合例如splitmix64讓輸入的微小變化擴散到整個哈?？臻g。代碼量不大但對分布質(zhì)量的影響是決定性的。1.3 鏈式地址法與開放地址法的對比既然聊到?jīng)_突解決就繞不開另一個大流派開放地址法。線性探測、二次探測、雙重散列都屬于開放地址法。它們的共同點是所有元素都放在桶數(shù)組本身里沖突時按規(guī)則繼續(xù)找下一個空位。鏈式地址法的優(yōu)勢在于第一對加載因子不敏感加載因子到 1.0 甚至更高都能正常工作無非鏈表長一點第二刪除操作是真正的常數(shù)時間不需要像線性探測那樣刪除后還得標記“已刪除”墓碑節(jié)點后續(xù)查找才能繼續(xù)走第三鏈表節(jié)點的內(nèi)存是動態(tài)分配在堆上的元素數(shù)量劇烈變化時回收靈活。缺點也很明顯每個節(jié)點多一個 next 指針內(nèi)存占用比緊湊的開放地址法大而且節(jié)點散落在堆上對現(xiàn)代 CPU 的緩存非常不友好。面試時如果被問到為什么很多語言的標準庫默認用鏈式地址法可以往“實現(xiàn)簡單、刪除友好、加載因子容忍度高”這幾個方向答。C 的std::unordered_map在 libstdc 和 MSVC STL 里本質(zhì)上都是鏈式結(jié)構(gòu)都是這個道理。2. 從零手寫一個可用的鏈式地址法哈希表核心實現(xiàn)2.1 先定數(shù)據(jù)結(jié)構(gòu)桶數(shù)組與鏈表節(jié)點寫代碼之前先在心里搭一張結(jié)構(gòu)圖。鏈式地址法哈希表由兩層組成第一層是桶數(shù)組動態(tài)數(shù)組每個位置是一個鏈表頭。第二層是鏈表節(jié)點存放 key、value 和指向下一個節(jié)點的指針。這里有個設(shè)計取舍直接用vectorlistpairK, V是最省事的寫法但工程上為了性能和內(nèi)存可控我建議手寫節(jié)點結(jié)構(gòu)。因為標準庫的list是雙向鏈表每一個節(jié)點多一個prev指針對于哈希表這種“每個桶只需要單向遍歷”的場景單鏈表就夠了。少一個指針就是每個節(jié)點省 8 字節(jié)。template typename K, typename V class HashMap { private: struct Node { K key; V value; Node* next; Node(const K k, const V v) : key(k), value(v), next(nullptr) {} }; std::vectorNode* buckets_; // 桶數(shù)組每個桶是一個單鏈表頭指針 size_t size_ 0; // 當前元素個數(shù) size_t bucket_count_; // 桶數(shù)量 float load_factor_threshold_; // 觸發(fā)擴容的裝載因子閾值 public: explicit HashMap(size_t init_buckets 16, float threshold 0.75f) : bucket_count_(init_buckets), load_factor_threshold_(threshold) { buckets_.resize(bucket_count_, nullptr); } ~HashMap() { clear(); } // ... 后續(xù)實現(xiàn) insert / find / erase / rehash };buckets_初始化為全nullptr空桶就是空鏈表。size_負責記錄元素個數(shù)用來計算裝載因子元素個數(shù) / 桶數(shù)量。這個值在每次插入后檢查超過閾值就觸發(fā)擴容。2.2 哈希函數(shù)的選型與取模優(yōu)化核心哈希邏輯就一行先拿到std::hash的散列值再對桶數(shù)取模得到桶下標。size_t hash_index(const K key) const { size_t h std::hashK{}(key); // 教科書里會寫 h % bucket_count_工程上如果桶數(shù)是 2 的冪 // 可以用 h (bucket_count_ - 1) 代替取模位運算更快。 return h % bucket_count_; }這里我要特意說一下“桶數(shù)量”的選擇。如果桶數(shù)是 2 的冪比如 16、32、64取模可以替換成位運算理論上有細微的性能優(yōu)勢。但代價是哈希函數(shù)的低幾位決定了桶的分布容易產(chǎn)生聚集。C 標準庫實際實現(xiàn)里unordered_map的默認桶數(shù)策略不太一樣libstdc 用的是質(zhì)數(shù)序列_Prime_rehash_policy寧愿多花一次取模也要換更均勻的分布。個人建議如果你只是學習或中小型應(yīng)用直接取模即可簡單、安全、可讀性強。等你想壓榨性能再考慮把桶數(shù)量設(shè)為 2 的冪并配合一個高質(zhì)量的位混合哈希函數(shù)。這個順序不要顛倒否則踩坑了都不知道問題出在哈希函數(shù)還是取模方式上。2.3 插入、查找、刪除三大核心操作插入操作插入的邏輯分三步走算桶下標、遍歷鏈表找 key、找到了更新 value沒找到就頭插一個新節(jié)點。void insert(const K key, const V value) { if (static_castfloat(size_ 1) / bucket_count_ load_factor_threshold_) { rehash(bucket_count_ * 2); } size_t idx hash_index(key); Node* cur buckets_[idx]; while (cur) { if (cur-key key) { cur-value value; // key 已存在更新并返回 return; } cur cur-next; } Node* new_node new Node(key, value); new_node-next buckets_[idx]; buckets_[idx] new_node; size_; }頭插法的好處是 O(1) 完成鏈表插入不需要遍歷鏈表末尾。有些人習慣寫尾插其實在哈希表這個場景下沒有必要維護插入順序頭插既快又簡潔。注意插入前先檢查裝載因子避免本次插入后超額再默默擴容。這個“先檢查、后插入”的順序很關(guān)鍵最小化擴容次數(shù)。查找操作查找的邏輯更簡單算下標、遍歷鏈表、比較 key命中就返回 value 指針。返回值用指針而不是值是為了讓調(diào)用方能夠區(qū)分“找到了”和“沒找到”兩種情況返回nullptr表示不存在。V* find(const K key) { size_t idx hash_index(key); Node* cur buckets_[idx]; while (cur) { if (cur-key key) { return cur-value; } cur cur-next; } return nullptr; } const V* find(const K key) const { // 邏輯同上返回 const 指針 }刪除操作刪除是鏈式地址法里最有“手感”的地方因為你要維護前驅(qū)節(jié)點。這里有一個很容易寫錯的細節(jié)如果待刪除節(jié)點恰好是鏈表頭則直接把桶指針指向next否則把前驅(qū)的next指向待刪除節(jié)點的next。無論哪種情況最后都要delete那個節(jié)點并--size_。bool erase(const K key) { size_t idx hash_index(key); Node* cur buckets_[idx]; Node* prev nullptr; while (cur) { if (cur-key key) { if (prev nullptr) { buckets_[idx] cur-next; // 刪除的是頭節(jié)點 } else { prev-next cur-next; // 刪除的是中間或尾節(jié)點 } delete cur; --size_; return true; } prev cur; cur cur-next; } return false; // key 不存在 }對比開放地址法的刪除操作需要墓碑標記復雜且影響查詢效率鏈式地址法的刪除如此自然簡潔這是它最吸引人的工程優(yōu)點。2.4 完整代碼的簡潔整合整合上面幾個方法一個基礎(chǔ)的模塊就出來了。核心結(jié)構(gòu)不到 150 行可以放進單文件里跑。這個版本沒有實現(xiàn)迭代器、沒有支持重復 key、也沒有移動語義的完整處理但作為教學和大多數(shù)內(nèi)部工具已經(jīng)夠用。注意上面的rehash(bucket_count_ * 2)還沒有定義下面單獨講。不要急先跑通上面的邏輯再一步步補擴容這是理解哈希表最好的節(jié)奏。3. 性能細節(jié)與擴容策略別讓你的哈希表悄悄退化3.1 裝載因子性能的“溫度計”裝載因子load factor是元素個數(shù)和桶個數(shù)的比值記作 α。在鏈式地址法中每個桶的平均鏈表長度正好就是 α。查找一個隨機 key 的平均比較次數(shù)大約是1 α / 2命中時也就是說哈希表從理論上講不是嚴格 O(1)而是 O(1 α)。當 α 0.75 時平均比較次數(shù)約 1.4 次當 α 2.0 時平均比較次數(shù)約 2 次仍然可以接受。所以鏈式地址法對裝載因子比較寬容這也是它相對于開放地址法的優(yōu)勢之一。但 α 過大就意味著鏈表太長CPU 緩存命中率下降實際耗時曲線會比理論值更陡。C 標準庫unordered_map的默認最大裝載因子就是 1.0超過才擴容。這不是拍腦袋定的而是在內(nèi)存和性能之間折中。下面是我的建議按場景分讀多寫少、追求查詢速度α 設(shè) 0.5~0.6桶多一些鏈表普遍短一點。內(nèi)存緊張、寫多讀少α 設(shè) 1.0~1.2空間友好但鏈路更長。高頻插入導致頻繁擴容的場景可以把 α 設(shè)小一點比如 0.6減少觸發(fā)擴容的次數(shù)與攤還成本。3.2 擴容與 rehash怎么動最劃算當裝載因子超過閾值就要擴容。擴容不是簡單地把桶數(shù)組變大而是要把所有已存在的節(jié)點重新計算哈希值掛到新桶里。因為桶數(shù)量變了key % old_bucket_count的余數(shù)和key % new_bucket_count完全不同所以必須重新散列這個過程叫rehash。void rehash(size_t new_bucket_count) { std::vectorNode* new_buckets(new_bucket_count, nullptr); for (size_t i 0; i bucket_count_; i) { Node* cur buckets_[i]; while (cur) { Node* next cur-next; // 先保存下一個節(jié)點 size_t new_idx std::hashK{}(cur-key) % new_bucket_count; // 把當前節(jié)點頭插到新桶 cur-next new_buckets[new_idx]; new_buckets[new_idx] cur; cur next; } } buckets_.swap(new_buckets); bucket_count_ new_bucket_count; }這段代碼有一個非常必要的細節(jié)遍歷舊鏈表時必須先保存cur-next再移動節(jié)點。因為移動之后舊鏈表的指針鏈就斷了不保存的話就丟節(jié)點了。這個內(nèi)存野指針的坑新手幾乎必踩一遍。擴容的代價是 O(n) 的但平攤到每個插入操作上就是 O(1)這就是攤還分析的概念。擴容策略的經(jīng)典做法是每次擴容為原來的兩倍。以倍增的方式總擴容成本是元素總數(shù)的線性級別均攤成本可控。如果你一次只擴容一個桶那會頻繁觸發(fā) rehash插入效率會非常糟糕。擴容時機上還有一個容易被忽視的點縮容。很多簡潔實現(xiàn)的哈希表只擴不縮導致刪除了大量元素后桶數(shù)組依舊占著大內(nèi)存。工程上如果你實現(xiàn)一個長期運行的服務(wù)端容器建議設(shè)置一個“縮容閾值”。當元素數(shù)量小于桶數(shù)量的 25% 時可以考慮縮容到一半。注意縮容同樣要 rehash不能直接改個值就完事。3.3 優(yōu)化方向內(nèi)存池與節(jié)點復用鏈式地址法有一個天生的性能短板每個節(jié)點都是獨立new出來的插入刪除頻繁時分攤的內(nèi)存分配開銷很大而且節(jié)點在堆上分散分布遍歷鏈表時 CPU 緩存命中率低。一種常見的優(yōu)化是用內(nèi)存池memory pool批量分配節(jié)點。預先分配一塊大緩沖區(qū)節(jié)點從緩沖區(qū)里切釋放時回收到空閑鏈表而不是還給操作系統(tǒng)。這樣既減少了malloc/free的系統(tǒng)調(diào)用又讓鏈表節(jié)點在物理上連續(xù)分布遍歷時緩存友好。你不需要一上來就上內(nèi)存池但要知道它是鏈式哈希表工業(yè)化的一個有效方向。std::unordered_map的節(jié)點分配方式其實也允許通過自定義分配器來控制這就是std::allocator參數(shù)的用武之地。4. 常見問題與排查實錄這些坑我替你踩過了4.1 野指針與 Access Violation很多人在寫完哈希表后運行時報出0xC0000005訪問沖突錯誤。這個錯誤在 Windows 上用 C 寫哈希表時非常經(jīng)典。十有八九是訪問了已經(jīng)刪除的節(jié)點。我來還原一下典型的錯誤場景// 錯誤示例刪除過程中繼續(xù)訪問 Node* cur buckets_[idx]; while (cur) { if (cur-key key) { delete cur; // 把 cur 銷毀了 // 但下面循環(huán)可能繼續(xù)訪問 cur-next } cur cur-next; }正確做法是刪除節(jié)點之前先保存next刪除后再用保存的next繼續(xù)遍歷或者按前面的寫法在erase里提前return。類似的錯誤也發(fā)生在clear()里遍歷刪除所有節(jié)點時必須先存next。另一個導致 Access Violation 的常見原因是桶數(shù)組在擴容時銷毀了舊數(shù)組但某些指針還指向舊鏈表上的節(jié)點導致雙重釋放或懸空訪問。解決辦法是保證rehash期間不要對容器做任何其他操作先完成所有節(jié)點的遷移再swap替換桶數(shù)組舊節(jié)點的所有權(quán)轉(zhuǎn)移到新容器不能提前釋放節(jié)點。4.2 自定義 key 忘了提供哈希與相等判定當你把自定義結(jié)構(gòu)體作為 key 插入哈希表編譯器會抱怨std::hash不可用系統(tǒng)找不到對operator()的匹配。此時需要為你的類型特化std::hashT見前面的示例。確保類型重載了operator因為哈希表查找時找到同一個桶后是用逐一比較判斷 key 是否相等的。一個值得注意的規(guī)范是如果兩個對象a b那么hash(a)必須等于hash(b)。反過來不要求兩個不同對象可以擁有相同的哈希值這是合法且必然的。違反這個約束會導致哈希表里同一個 key 在查找時命中不了同一桶容器行為直接錯亂。如果你使用了std::unordered_map這些規(guī)則同樣適用。這也是為什么定義一個類作為 key 時要同時重寫operator和特化std::hash。4.3 迭代器失效問題如果手寫容器想提供迭代器要注意失效規(guī)則。對于鏈式地址法哈希表插入操作如果在擴容邊界附近觸發(fā)了 rehash那么所有迭代器全部失效因為底層桶數(shù)組被替換了。插入操作如果沒有 rehash那么已有節(jié)點的內(nèi)存地址不變指向已有節(jié)點的迭代器仍然有效。刪除操作會使指向被刪節(jié)點的迭代器失效但其他迭代器不受影響因為刪除只動了一個節(jié)點。這跟std::unordered_map官方的迭代器失效規(guī)則基本一致。你在寫容器時如果支持多線程訪問還要考慮并發(fā)問題——鏈式哈希表并不天然線程安全加載因子檢查和 rehash 期間必須互斥否則讀線程會看到半遷移狀態(tài)的表。4.4 哈希碰撞攻擊與隨機化鏈式地址法有一個經(jīng)典的安全隱患如果哈希函數(shù)是確定性的攻擊者可以精心構(gòu)造大量哈希值相同的 key把所有數(shù)據(jù)塞進同一條鏈表讓哈希表查詢退化成 O(n)這就是哈希碰撞拒絕服務(wù)攻擊。C 標準庫的unordered_map不同實現(xiàn)對此有不同的抵御策略。有的在哈希函數(shù)里加入隨機種子在每個進程啟動時初始化讓攻擊者無法提前預測桶分布有的在鏈表長度超標時把鏈表轉(zhuǎn)換成一棵紅黑樹這個策略在 Java 的 HashMap 里更著名。如果你在寫高并發(fā)的服務(wù)端組件至少應(yīng)當考慮在哈希函數(shù)的位混合中引入一個進程級的隨機種子這樣攻擊者就無法構(gòu)造出穩(wěn)定的碰撞序列。這里的隨機數(shù)不需要密碼學強度夠用來打亂分布即可。5. 鏈式地址法在工業(yè)界的影子從手寫容器到 std::unordered_map5.1 unordered_map 的底層長什么樣很多人以為std::unordered_map的實現(xiàn)就是“vector list”實際上沒那么簡單。libstdc 的實現(xiàn)里每個元素節(jié)點不僅參與所在桶的單向鏈表還有一條貫穿整個容器的雙向鏈表用于維護全局迭代順序。查找時先定位桶再在桶內(nèi)通遍歷單向鏈表遍歷容器時則從全局鏈表頭一路走過去。這個設(shè)計讓迭代器在大多數(shù)情況下保持穩(wěn)定代價是每個節(jié)點額外占用一個雙向鏈表的指針。從使用角度來說unordered_map是 C 標準庫最常用的字典容器之一。絕大多數(shù)場景下你不需要手寫哈希表直接用標準庫即可。但理解鏈式地址法的底層機制對你調(diào)試性能問題、理解迭代器失效、選擇合適的初始桶數(shù)和max_load_factor都大有幫助。比如你可以通過下面這段代碼控制容器的空間和時間平衡std::unordered_mapint, int table; table.reserve(1000); // 預分配桶減少重復 rehash table.max_load_factor(0.7f); // 提前擴容讓查找更快reserve在 STL 里就是提前擴容到一個足夠容納 n 個元素的桶數(shù)量而不是只預留數(shù)組空間。這個細節(jié)值得記住它能讓你在插入大量元素之前就做好空間規(guī)劃避免插入過程中反復 rehash 的開銷。5.2 哈希表與字典別把概念和實現(xiàn)搞混經(jīng)常有人問“哈希表和字典有什么區(qū)別”。從抽象層次來看字典dictionary是一個接口概念描述鍵值對映射關(guān)系不限定底層實現(xiàn)哈希表是一種具體的數(shù)據(jù)結(jié)構(gòu)用哈希函數(shù)和沖突解決來實現(xiàn)字典接口。Python 的 dict、C 的std::map、Java 的 HashMap 都是在實現(xiàn)“字典”這個抽象但底層機制各不相同std::map用紅黑樹std::unordered_map用哈希表Python 的 dict 早期用開放地址法探測。面試的時候如果被問到區(qū)別可以這樣回答字典強調(diào)的是“能干什么”哈希表強調(diào)的是“怎么干”。前者是邏輯結(jié)構(gòu)后者是物理實現(xiàn)?？荚嚴镞€會考察哈希表能否保持有序遍歷——鏈式地址法的哈希表天然無序如果你想按 key 有序遍歷請改用平衡樹不要在哈希表上做文章。5.3 真實場景游戲排行榜、緩存與詞頻統(tǒng)計聊點看得見摸得著的應(yīng)用。鏈式地址法哈希表最適合的場景是元素數(shù)量大、讀多寫少、不要求順序、key 分布未知但整體隨機。游戲開發(fā)中根據(jù)玩家 ID 查分數(shù)、根據(jù)物品 ID 查屬性這種 ID 到數(shù)據(jù)的映射非常適合哈希表如果你用數(shù)組按 ID 下標存ID 范圍一大就浪費內(nèi)存動態(tài)擴容哈希表就特別香。詞頻統(tǒng)計也是一個典型練習。讀入一篇長文統(tǒng)計每個單詞出現(xiàn)了多少次標準解法就是哈希表。key 為單詞字符串value 為計數(shù)。插入時已存在的 key 的計數(shù)器加一新 key 初始化為 1。C 里可以這樣寫std::unordered_mapstd::string, int freq; std::string word; while (std::cin word) { freq[word]; // operator[] 在 key 不存在時自動插入并默認初始化 }另一個工具型場景是緩存系統(tǒng)。比如 LRU 緩存的經(jīng)典實現(xiàn)就是“哈希表 雙向鏈表”哈希表負責 O(1) 查找 key雙向鏈表負責維護訪問順序。鏈式地址法在其中依然扮演著查找主力的角色。寫在最后我在實際玩哈希表的時候印象最深的一件事是調(diào)試一個由哈希函數(shù)導致的死循環(huán)。那個哈希函數(shù)對某個特殊字符串返回了恒定的 0相當于所有元素都掛在第一個桶的鏈表上查找大量 key 時耗時長到像死循環(huán)一樣。從那以后我養(yǎng)成了一個習慣寫哈希表一定先打印哈希分布再測性能直覺和理論都不如實際分布截圖可靠。鏈式地址法本身沒有太多玄學核心就是三個數(shù)字——哈希函數(shù)、桶數(shù)量、裝載因子。把這三樣調(diào)對整個容器就穩(wěn)了一大半。最后再分享一個小技巧如果你懷疑擴容拖累了整體性能不要急著寫復雜的縮容策略先在構(gòu)造函數(shù)里用reserve預分配足夠的桶。這一步在很多場景下能直接省掉 90% 的 rehash 開銷。哈希表好不好用往往在于你愿不愿意在動手之前多想一步。