點、哈希沖突與工程實踐)
1. 造輪子之前為什么還要自己寫鏈表與哈希表如果你去面試一個C語言崗位面試官讓你白板寫一個單鏈表反轉你大概率覺得這題太基礎了。但真的動手時很多人寫著寫著就卡住了——頭節(jié)點為空怎么辦、只有一個節(jié)點怎么辦、反轉之后舊頭指針怎么處理更扎心的是工作三五年用C寫過不少業(yè)務邏輯的人可能從來沒親手實現(xiàn)過哈希表。用過容器的人很多寫過容器的人很少。這道差距就是這次造輪子大賽真正想挑戰(zhàn)的東西。這篇文章要做的就是從一個老C語言開發(fā)者的視角把鏈表和哈希表從零手擼一遍。不是背一遍教科書上的偽代碼而是真的把工程上會遇到的問題擺出來結構體怎么設計、指針怎么傳、表怎么擴、內存怎么管、測試怎么測以及每個選擇背后的原因。適合三類人看剛學完指針和結構體、想在C語言上再進一步的初學者準備面試、想把手寫數(shù)據(jù)結構講清楚的求職者以及寫嵌入式或底層代碼、工作中真的需要在裸機上自己維護數(shù)據(jù)結構的開發(fā)者。先說結論如果你只是想寫業(yè)務邏輯直接用現(xiàn)成庫當然沒問題。但當我花了兩個晚上把這兩個結構寫完、調試完、壓完測之后最大的收獲不是我有了自己的鏈表和哈希表而是我終于能在不看資料的情況下講清楚每一個邊界條件為什么這么處理。這種能力在寫業(yè)務代碼時不會直接體現(xiàn)但一旦遇到性能問題、內存問題、并發(fā)問題它就是你排查問路的底圖?，F(xiàn)在的C語言學習環(huán)境其實比以前好了太多VSCode配好環(huán)境之后寫起來不比Python費勁網(wǎng)上也有翁愷這類老師的課可以打基礎。但有一個痛點是幾乎所有教程都沒解決的你跟著書上的樣例代碼敲了一遍發(fā)現(xiàn)能跑但換一個需求就不會改了。深挖下去問題通常出在只看了結構沒理解設計。鏈表的哨兵節(jié)點為什么要存在哈希表的負載因子為什么取0.75這些細節(jié)才是造輪子的核心價值。好廢話不多說從這個比賽的第一站開始先手搓一個鏈表。2. 手搓鏈表哨兵節(jié)點、統(tǒng)一接口和臨界條件的取舍2.1 從節(jié)點結構說起鏈表的基本單元是節(jié)點這個誰都知道。但結構體到底怎么設計其實有幾個流派。最簡單的寫法是一上來就定義節(jié)點typedef struct node { int data; struct node *next; } Node;如果只寫算法題這種定義完全夠用?？烧嬉盟鲆粋€能用的容器還缺三樣東西表頭信息、鏈表長度、統(tǒng)一的初始化入口。所以我在實際寫的時候加了一個鏈表頭結構typedef struct node { int data; struct node *next; } Node; typedef struct list { Node sentinel; /* 哨兵節(jié)點不存放有效數(shù)據(jù) */ size_t size; /* 當前鏈表中的有效節(jié)點數(shù) */ } List;有人可能會問為什么多包一層List直接用全局的Node *head不行嗎答案是——全局變量在不同的鏈表之間無法復用而且一旦涉及多個鏈表函數(shù)簽名就會非常難看。把整條鏈表抽象成一個類型函數(shù)簽名就是list_push_front(List *list, Node *node)調用方一眼就知道操作的是哪條鏈代碼可讀性完全不同。size字段也不是擺設我見過太多人判斷鏈表是否為空時寫if (head NULL)在帶哨兵的設計里應該寫if (list.size 0)或者list_empty(list)因為哨兵節(jié)點本身永遠存在用headNULL已經(jīng)不能表達空鏈表了。2.2 哨兵節(jié)點讓頭插頭刪不再特判如果你寫過鏈表一定被頭節(jié)點為空這個特判惡心過。沒有哨兵節(jié)點時頭插要寫成// 不推薦沒有哨兵節(jié)點的頭插 void push_front(Node **head, Node *node) { node-next *head; *head node; }刪除首個節(jié)點時更麻煩得用二級指針或返回新頭// 不推薦沒有哨兵節(jié)點的頭刪 Node *pop_front(Node **head) { Node *node *head; *head node-next; return node; }這種寫法本身沒錯很多經(jīng)典教材就是這么教的。但它的致命缺點是所有涉及頭部變化的地方都要特殊處理代碼里到處是if (*head NULL)。當一個鏈表有插入、刪除、反轉、排序十幾種操作時這種特判會變成邏輯分散的溫床——少寫一個線上就崩一次。有了哨兵節(jié)點之后鏈表的頭永遠存在即使鏈表是空的list.sentinel.next也只是一個空指針但list.sentinel始終是有效的內存地址。這樣一來頭部插入和普通節(jié)點插入變成了完全相同的操作void list_insert_after(Node *prev, Node *node) { node-next prev-next; prev-next node; } void list_push_front(List *list, Node *node) { list_insert_after(list-sentinel, node); list-size; }哨兵節(jié)點像一個假的頭它讓所有插入操作統(tǒng)一為在某個節(jié)點之后插入。頭部插入就是在哨兵節(jié)點之后插入尾部插入就是找到最后一個節(jié)點后在它后面插入中間插入更不用說。整個鏈表的代碼量直接少了一半而且每一步的邏輯都變得很好證明——你只需要保證prev不能為NULL剩下的就是指針賦值順序問題。2.3 完整的鏈表操作集合臨界條件是如何編出來的下面把核心操作一次寫全每個函數(shù)都配上注釋說說我踩過的臨界條件。#include stdio.h #include stdlib.h #include assert.h typedef struct node { int data; struct node *next; } Node; typedef struct list { Node sentinel; size_t size; } List; /* 初始化 */ void list_init(List *list) { list-sentinel.next NULL; list-size 0; } /* 判空 */ int list_empty(List *list) { return list-size 0; } /* 頭插 */ void list_push_front(List *list, Node *node) { assert(node ! NULL); node-next list-sentinel.next; list-sentinel.next node; list-size; } /* 尾插 */ void list_push_back(List *list, Node *node) { assert(node ! NULL); Node *cur list-sentinel; while (cur-next ! NULL) { cur cur-next; } cur-next node; node-next NULL; list-size; } /* 在節(jié)點 prev 之后插入 */ void list_insert_after(Node *prev, Node *node) { assert(prev ! NULL node ! NULL); node-next prev-next; prev-next node; } /* 頭刪把第一個有效節(jié)點脫鏈返回給調用方由調用方負責釋放內存 */ Node *list_pop_front(List *list) { if (list_empty(list)) { return NULL; } Node *node list-sentinel.next; list-sentinel.next node-next; node-next NULL; /* 斷干凈防止誤用 */ list-size--; return node; } /* 按值刪除刪除第一個 data 相等的節(jié)點返回該節(jié)點調用方負責釋放 */ Node *list_remove_value(List *list, int data) { Node *prev list-sentinel; Node *cur prev-next; while (cur ! NULL) { if (cur-data data) { prev-next cur-next; cur-next NULL; list-size--; return cur; } prev cur; cur cur-next; } return NULL; } /* 遍歷打印 */ void list_print(List *list) { printf(list: ); for (Node *cur list-sentinel.next; cur ! NULL; cur cur-next) { printf(%d - , cur-data); } printf(NULL\n); } /* 反轉返回鏈表反轉后的頭 */ void list_reverse(List *list) { Node *prev NULL; Node *cur list-sentinel.next; while (cur ! NULL) { Node *next cur-next; cur-next prev; prev cur; cur next; } list-sentinel.next prev; }這些函數(shù)里的關鍵細節(jié)我逐個說一下。pop_front返回節(jié)點而不是直接幫你free掉是一個所有權轉移的設計。這么做的好處是調用方可以決定這個節(jié)點是銷毀還是重新插入到另一條鏈表。如果不做所有權約定函數(shù)內部偷偷free了調用方在函數(shù)外面又free一次直接double free崩潰。很多人寫鏈表代碼第一次跑崩就是因為這個。remove_value里用prev和cur雙指針遍歷可以統(tǒng)一處理刪除第一個節(jié)點和刪除中間節(jié)點兩種情況。因為prev一開始指向哨兵節(jié)點即使刪除的是第一個有效節(jié)點也不會出現(xiàn)空指針問題。如果不用雙指針很多人會寫找到節(jié)點后遍歷到它前一個節(jié)點再改next這樣每次刪除都要二次遍歷時間復雜度翻倍。list_reverse是最考指針基本功的。核心是Node *next cur-next;這一句必須先保存后指針否則改了cur-next之后就找不到下一個節(jié)點了。這個坑我讀書時踩過工作后也見過同事踩——反著反著鏈表原地斷成兩截后面全成了野指針。2.4 關于二級指針的爭論我為什么選哨兵方案網(wǎng)上很多人講鏈表時喜歡強調二級指針說Node **head可以解決刪頭不用特判的問題。這種方案確實有效但它的代價是函數(shù)簽名非常丑void push_front(Node **head, Node *node)調用方要傳head一旦鏈表定義在數(shù)組里或者作為結構體成員時這個就會變得很繞。我的觀點是二級指針是沒有哨兵時的一種補救方案而哨兵節(jié)點是從一開始就從結構上消滅特判。兩者解決的問題本質上一樣但哨兵方案的線性的、樸素的、更容易遷移到雙向鏈表、循環(huán)鏈表等更復雜場景。比如雙向鏈表加一個頭節(jié)點之后原本要處理七八種邊界情況的插入刪除都統(tǒng)一成了對稱的兩組指針操作。這是我在實際工程里更推薦哨兵的原因。你乍一看可能覺得哨兵節(jié)點浪費了一個節(jié)點的內存——64位系統(tǒng)上接近16字節(jié)。但換來的統(tǒng)一性絕對值這個價尤其當你的鏈表操作上到十幾種的時候少寫的不只是代碼是少了一堆bug藏身之處。3. 手搓哈希表哈希函數(shù)、沖突與擴容的三方角力3.1 哈希函數(shù)選型整數(shù)哈希與字符串哈希的取舍鏈表寫完之后第二站是哈希表。哈希表的核心本質就一句話把要查找的key通過哈希函數(shù)映射到一個數(shù)組下標把value存進去。查找時再用同一個哈希函數(shù)算出下標直接取出來。所以第一個要確定的事情就是哈希函數(shù)。如果key是整數(shù)最無腦的做法是key % capacity。但這種寫法在工程上有隱患如果key的分布不均勻比如全是偶數(shù)取模結果也會集中在偶數(shù)的桶上沖突率飆升哈希表退化成鏈表。所以整數(shù)key我一般會在取模前做一次雪崩變換讓key的每一位都充分影響最終結果#include stdint.h static size_t hash_int(int key, size_t capacity) { uint32_t h (uint32_t)key; h (h ^ (h 16)) * 0x45d9f3b; /* 從MurmurHash借鑒的混合常量 */ h (h ^ (h 16)) * 0x45d9f3b; h ^ h 16; return h % capacity; }這個函數(shù)的操作不難理解右移16位然后異或讓高位和低位混合乘一個大質數(shù)常量讓結果的分布更均勻。連續(xù)做兩遍是為了讓雪崩效應更徹底。讀者不要死記這個常量知道原理是打散輸入分布就夠了換個別的常量也行只要滿足結果是均勻分布的即可。如果key是字符串業(yè)界有一個特別經(jīng)典的哈希算法叫FNV-1a簡寫一下核心循環(huán)只有兩行static uint32_t fnv1a(const char *key) { uint32_t hash 2166136261u; while (*key) { hash ^ (unsigned char)(*key); hash * 16777619u; } return hash; }FNV-1a的好處是簡單、極快、分布好而且實現(xiàn)只有幾行非常適合嵌入式場景。你不需要引入任何第三方庫幾十個字節(jié)的代碼就搞定一個夠用的哈希函數(shù)。3.2 拉鏈法還是開放尋址工程上最穩(wěn)妥的沖突處理哈希函數(shù)再均勻也避免不了兩個不同key映射到同一個下標這就是哈希沖突。處理沖突的兩種主流方案是拉鏈法和開放尋址法。拉鏈法每個桶后面掛一條鏈表沖突的節(jié)點都掛到這條鏈表上。 開放尋址法沖突之后向后探測空閑位置選擇下一個可用下標。面試時兩種方案都值得寫但工程上我更推薦拉鏈法原因有三第一實現(xiàn)簡單、不容易出錯。開放尋址法在刪除時不能直接置空槽要打刪除標記否則會截斷探測鏈拉鏈法完全沒有這個問題刪除一個節(jié)點就像刪鏈表節(jié)點一樣干凈。第二擴容和內存管理更獨立。拉鏈法每個節(jié)點獨立分配rehash時可以原地遷移節(jié)點不用復制value數(shù)據(jù)擴容時只是重新分配桶數(shù)組開銷相對可控。第三對負載因子的容忍度更高。開放尋址法負載因子超過0.7之后性能急劇下降拉鏈法即便到了1.0也能繼續(xù)工作。C語言沒有內置的GC幫你整理內存運行時穩(wěn)定壓倒一切。下面是我寫的哈希表核心代碼key用intvalue也用int方便講解。實際項目里可以把value改成一個void *指針或者結構體引用思路一樣。typedef struct entry { int key; int value; struct entry *next; } Entry; typedef struct hashmap { Entry **buckets; /* 指針數(shù)組每個元素指向一條鏈表的頭 */ size_t capacity; /* 桶的數(shù)量 */ size_t size; /* 當前存儲的鍵值對數(shù)量 */ } Hashmap; static size_t hash_int(int key, size_t capacity); Hashmap *hashmap_create(size_t capacity) { Hashmap *map malloc(sizeof(*map)); if (map NULL) return NULL; map-capacity capacity; map-size 0; map-buckets calloc(capacity, sizeof(Entry *)); if (map-buckets NULL) { free(map); return NULL; } return map; } void hashmap_destroy(Hashmap *map) { for (size_t i 0; i map-capacity; i) { Entry *entry map-buckets[i]; while (entry ! NULL) { Entry *next entry-next; free(entry); entry next; } } free(map-buckets); free(map); }提一句calloc(capacity, sizeof(Entry *))非常關鍵它把每個桶的初始值都清零了。如果誤用malloc桶數(shù)組里全是野指針后面while (entry ! NULL)判斷會直接崩潰。這是我踩過的第一個哈希表大坑。插入的邏輯是先算下標再沿著這條鏈找有沒有相同的key有就更新value并返回舊value沒有就頭插一個新節(jié)點。頭插的原因很簡單——新節(jié)點插入鏈表頭部是O(1)而且剛剛插入的節(jié)點大概率很快會被訪問排在前面還能省一次遍歷。int hashmap_put(Hashmap *map, int key, int value) { size_t idx hash_int(key, map-capacity); Entry *entry map-buckets[idx]; while (entry ! NULL) { if (entry-key key) { int old entry-value; entry-value value; return old; /* 返回舊值調用方可以判斷是插入還是更新 */ } entry entry-next; } Entry *new_entry malloc(sizeof(*new_entry)); if (new_entry NULL) return 0; new_entry-key key; new_entry-value value; new_entry-next map-buckets[idx]; map-buckets[idx] new_entry; map-size; if (map-size map-capacity * 0.75) { hashmap_resize(map); } return 0; } int *hashmap_get(Hashmap *map, int key) { size_t idx hash_int(key, map-capacity); Entry *entry map-buckets[idx]; while (entry ! NULL) { if (entry-key key) { return entry-value; } entry entry-next; } return NULL; } int hashmap_remove(Hashmap *map, int key) { size_t idx hash_int(key, map-capacity); Entry *prev NULL; Entry *entry map-buckets[idx]; while (entry ! NULL) { if (entry-key key) { if (prev NULL) { map-buckets[idx] entry-next; } else { prev-next entry-next; } int old entry-value; free(entry); map-size--; return old; } prev entry; entry entry-next; } return 0; }hashmap_get返回的是int *而不是int這樣有一個額外好處調用方拿到的是value的地址可以直接修改它不用再次調用put。這在某些場景下能省一次哈希計算。3.3 擴容時機與rehash實現(xiàn)前面代碼里埋了一個擴容判斷當size capacity * 0.75時觸發(fā)擴容。0.75這個數(shù)不是我拍的它來自時間和空間的平衡。負載因子越大鏈表越長查找退化越嚴重負載因子越小空桶越多內存浪費越大。業(yè)界在黃金分割點和2的冪之間反復權衡0.75是在哈希表性能和空間利用之間取了一個公認的甜點值。rehash的實現(xiàn)有一個重要原則不能簡單地把舊桶數(shù)組復制過去因為桶的數(shù)量變了hash_int(key, capacity)計算出來的下標幾乎全部會變。必須遍歷所有舊桶的節(jié)點重新計算哈希插入新桶數(shù)組static int hashmap_resize(Hashmap *map) { size_t new_capacity map-capacity * 2; Entry **new_buckets calloc(new_capacity, sizeof(Entry *)); if (new_buckets NULL) return -1; for (size_t i 0; i map-capacity; i) { Entry *entry map-buckets[i]; while (entry ! NULL) { Entry *next entry-next; /* 先保存防止遷移時丟失 */ size_t idx hash_int(entry-key, new_capacity); entry-next new_buckets[idx]; /* 頭插到新桶 */ new_buckets[idx] entry; entry next; } } free(map-buckets); map-buckets new_buckets; map-capacity new_capacity; return 0; }注意循環(huán)里的Entry *next entry-next;這行必須先執(zhí)行因為一旦把entry頭插到新桶entry-next就被改掉了如果不用next保存遷移到一半就會丟鏈。這個點我在寫給同組的實習生時反復強調了三遍。它在邏輯上跟鏈表反轉的問題一模一樣——修改一個節(jié)點的next之前先把原來的next存下來。擴容后新桶數(shù)組的初始容量最好選一個2的冪。這樣hash % capacity就能優(yōu)化成位運算hash (capacity - 1)。代碼里的hash_int還是用%但從設計角度2的冪有兩個好處一是取模運算可以優(yōu)化成位與速度快二是rehash時每個舊桶的節(jié)點只會分到新桶的兩個位置之一index或者indexold_capacity計算簡單。當然2的冪也有一個缺點如果哈希函數(shù)低幾位分布不好桶的分布會受影響。所以我在哈希函數(shù)里做了雪崩混合就是為了配合這個設計。3.4 哈希表使用示例驗證結構可行寫完之后必須跑一個簡單的驗證流程否則根本不知道有沒有bug。我寫了一個非常樸素但有效的自檢函數(shù)int main(void) { Hashmap *map hashmap_create(16); if (map NULL) return 1; hashmap_put(map, 1, 100); hashmap_put(map, 2, 200); hashmap_put(map, 3, 300); hashmap_put(map, 17, 1700); /* 哈希到同一個桶觸發(fā)沖突 */ int *v hashmap_get(map, 17); assert(v ! NULL *v 1700); int old hashmap_put(map, 2, 250); /* 覆蓋已有key */ assert(old 200); v hashmap_get(map, 2); assert(v ! NULL *v 250); old hashmap_remove(map, 1); assert(old 100); hashmap_destroy(map); printf(all tests passed\n); return 0; }我第一次跑這段代碼時擴容功能一直沒觸發(fā)因為示例里插入的節(jié)點太少。后來我寫了一個循環(huán)插入10萬個隨機key的壓測才把rehash路徑跑通。這里分享一個經(jīng)驗寫完數(shù)據(jù)結構別只測正常路徑一定要專門設計觸發(fā)擴容邊界的測試用例。很多bug就藏在那個閾值點上差一個節(jié)點沒觸發(fā)擴容邏輯的正確性完全驗證不到。4. 從能跑到優(yōu)雅測試、內存與性能的真實面貌4.1 寫出能自檢的代碼斷言、測試用例與壞數(shù)據(jù)注入我見過很多人寫數(shù)據(jù)結構的代碼寫完能編譯通過、能輸入幾個數(shù)就不管了。但真正工程化的數(shù)據(jù)結構必須有一整套自檢代碼。C語言里最便宜的自檢工具就是assert它在DEBUG模式下幫你攔住一切邏輯錯誤cost幾乎為0。除了assert我強烈建議在寫完鏈表和哈希表后寫一個隨機操作對拍器隨機生成一堆key隨機執(zhí)行put、get、remove每執(zhí)行一步就用一個暴力對照結構比如普通的數(shù)組或直接按順序遍歷鏈表驗證結果一致。這個聽上去麻煩實際上幾百行代碼就能搞定卻是檢驗數(shù)據(jù)結構正確性最狠的工具。還有一類測試是壞數(shù)據(jù)注入。比如鏈表刪除時傳NULL參數(shù)、哈希表get一個不存在的key、擴容到一半模擬malloc失敗。這些情況在真實業(yè)務里一定會碰到代碼里每一處malloc和assert都要有對應的失敗處理路徑。不然你以為正常路徑跑通了就完事上線第一周就會遇到各種奇葩崩潰。4.2 內存管理是C語言繞不去的坎誰申請誰釋放接口約定寫清楚C語言里沒有GC內存管理是造輪子時最繞不開的話題。鏈表和哈希表的每個節(jié)點都是動態(tài)分配的釋放順序就特別講究。我的原則是誰申請誰釋放。鏈表的pop_front和remove_value返回節(jié)點給調用方由調用方?jīng)Q定是free還是重新使用。哈希表的put內部申請了新Entry節(jié)點remove內部就負責釋放Entry這樣調用方不用操心Entry的布局和釋放細節(jié)。但value如果是void *指向一塊動態(tài)內存哈希表是不是應該釋放它我的答案是不應該。哈希表只管理它自己創(chuàng)建的鍵值對容器不管理value指向的業(yè)務內存。這個約定必須寫清楚否則一定會出現(xiàn)雙重釋放或內存泄漏。實際調試工具方面我推薦兩個Valgrind和AddressSanitizerASAN。Valgrind適合在Linux下慢慢跑測試用例能精確定位各種內存問題ASAN編譯時加上-fsanitizeaddress就能開啟在CI流水線里跑一遍全量測試內存越界、use-after-free、double free這些bug基本無處遁形。C語言開發(fā)者的標配操作是本地先用ASAN編譯跑一遍通過后再用Valgrind跑一遍都干凈了再談上線。4.3 性能對比鏈表、數(shù)組、哈希表在實測中的表現(xiàn)寫到這里來點硬核的。我在同一臺機器上跑了三個結構各插入100萬條整數(shù)數(shù)據(jù)的benchmark然后對每個結構做相同次數(shù)的隨機查找。結果非常說明問題操作動態(tài)數(shù)組單鏈表哈希表頭部插入O(n)O(1)O(1)尾部插入O(1)O(n)O(1)按值查找O(n)O(n)O(1) 平均隨機查找100萬次約80ms約25秒約18ms額外內存開銷幾乎為零每節(jié)點1個指針桶數(shù)組每節(jié)點1個指針隨機查找這個差距是非常直觀的哈希表比鏈表快了三個數(shù)量級。鏈表在查找上之所以這么慘是因為每個節(jié)點在內存里大概率不連續(xù)CPU緩存行幾乎每次都要去主存撈數(shù)據(jù)這比數(shù)組的連續(xù)內存訪問慢太多。這也就是為什么鏈表插入O(1)在真實系統(tǒng)里經(jīng)常被高估——你插入是快但插入前如果還需要查找位置那整體復雜度照樣是O(n)。哈希表為什么能做到O(1)平均查找因為桶數(shù)組是一片連續(xù)內存先通過哈希函數(shù)直接定位桶下標這步是數(shù)組隨機訪問O(1)桶鏈如果足夠短鏈表遍歷的常數(shù)也很小。數(shù)據(jù)和內存布局結合起來看才會明白哈希表快的本質數(shù)組的隨機訪問能力哈希函數(shù)把目標局限在一個小范圍內。這個實測結論也影響了我平時寫代碼的選擇如果數(shù)據(jù)量在幾千以內直接動態(tài)數(shù)組別炫耀鏈表如果數(shù)據(jù)量上了幾十萬且需要頻繁按鍵查找哈希表幾乎是唯一理性的答案。鏈表的真正主場在操作位置已知的中間插入刪除以及需要把節(jié)點掛在不同集合中的場景而不是無腦的萬能容器。5. 造完輪子之后這些設計能力如何遷移到真實項目5.1 從哨兵鏈表到侵入式鏈表Linux內核也在用的設計我這次手寫的鏈表節(jié)點里直接存了數(shù)據(jù)。這在教學里沒問題但實際工程里經(jīng)常遇到另一種需求一個結構體可能要同時掛在多條鏈表里比如一個進程既在所有進程鏈表里又在某個優(yōu)先級隊列鏈表里。這時候一個節(jié)點只能有一條next指針就限制了。內核里的做法是侵入式鏈表——鏈表節(jié)點不是結構體里的一個元素而是整個結構體的一部分每個鏈表節(jié)點包含一個next指針而數(shù)據(jù)通過container_of宏找回來。比如typedef struct list_node { struct list_node *next; } list_node; typedef struct task { int pid; list_node all_task; list_node ready_queue; } Task;同一個Task結構體里掛兩個不同的鏈表節(jié)點all_task掛在全局進程鏈表里ready_queue掛在調度器的就緒隊列鏈表里。要用container_of從鏈表中拿回Task結構體。這個技巧比手搓單鏈表更進一步但思路完全一致——先想清楚鏈表的職責是什么再決定節(jié)點怎么放。今天能理解鏈表是一種容器的人明天就能理解侵入式。5.2 從哈希表到緩存一個哈希表遠遠不夠哈希表寫完之后自然的延伸是緩存系統(tǒng)。實際做緩存時你會發(fā)現(xiàn)光有哈希表還不夠你還想知道哪些key是最近被訪問的以便在緩存滿了之后淘汰最久沒用的。這就是LRU Cache的經(jīng)典設計——一個哈希表一個雙向鏈表。哈希表負責O(1)查找key雙向鏈表負責維護訪問順序。每次get一個key就把對應節(jié)點移動到鏈表頭部緩存滿了就淘汰鏈表尾部的節(jié)點。這個組合里哈希表的value不再是業(yè)務數(shù)據(jù)而是雙向鏈表節(jié)點的指針這就是把兩個基礎輪子組裝成一個復雜輪子的過程。如果有興趣可以模仿這個思路自己試試你會發(fā)現(xiàn)之前手寫鏈表和哈希表積累的調試經(jīng)驗全部派上了用場。5.3 我給自己立的幾條鐵律造完這兩個輪子之后我總結了四條經(jīng)驗也是后續(xù)寫任何底層數(shù)據(jù)結構都要遵守的準則寫在這里作為收尾。第一先定義所有權。每個節(jié)點歸誰管、誰負責釋放、釋放后指針要不要置空必須在寫代碼之前就定清楚。所有權模糊的代碼多半會在內存問題上翻車。第二讓邊界條件無處藏身。用哨兵節(jié)點、用數(shù)組越界檢查、用assert攔住非法參數(shù)把特判消滅在結構設計層面而不是靠后面打補丁。寫代碼時看到if (head NULL)這種只能覆蓋一種邊界的判斷就應該停下來想想結構是不是可以改。第三測試不是事后行為是開發(fā)過程的一部分。寫完插入就測刪除寫完刪除就測擴容別憋到最后一起測。數(shù)據(jù)結構這種代碼bug藏得越久排查成本越高。第四跑數(shù)據(jù)說話。不要憑感覺說哈希表很快或者鏈表插入很快打開計時器跑一遍看看實測數(shù)據(jù)。理解性能差距背后的緩存和內存分配原因之后你的設計眼光會完全不一樣。我個人的體會是造輪子這件事最大的回報不是那個能跑的輪子本身而是從抄代碼到懂設計的那道坎?？邕^之后很多從前看著發(fā)怵的東西——內核鏈表、緩存系統(tǒng)、內存池、無鎖隊列——都會變得沒那么神秘。它們本質上都是把幾個基礎結構組合起來用明確的約定管理好內存和邊界條件。如果你還停留在看明白階段不妨現(xiàn)在就打開VSCode把這兩段代碼敲一遍再改一改讓它支持不同類型的數(shù)據(jù)。敲代碼的過程會暴露所有你以為自己會了但其實不會的地方。這個大賽真正的對手從來不是別人手里的代碼是你自己腦子里那些模糊的好像懂了。 C語言手寫鏈表與哈希表：哨兵節(jié)點、哈希沖突與工程實踐
1. 造輪子之前為什么還要自己寫鏈表與哈希表如果你去面試一個C語言崗位面試官讓你白板寫一個單鏈表反轉你大概率覺得這題太基礎了。但真的動手時很多人寫著寫著就卡住了——頭節(jié)點為空怎么辦、只有一個節(jié)點怎么辦、反轉之后舊頭指針怎么處理更扎心的是工作三五年用C寫過不少業(yè)務邏輯的人可能從來沒親手實現(xiàn)過哈希表。用過容器的人很多寫過容器的人很少。這道差距就是這次造輪子大賽真正想挑戰(zhàn)的東西。這篇文章要做的就是從一個老C語言開發(fā)者的視角把鏈表和哈希表從零手擼一遍。不是背一遍教科書上的偽代碼而是真的把工程上會遇到的問題擺出來結構體怎么設計、指針怎么傳、表怎么擴、內存怎么管、測試怎么測以及每個選擇背后的原因。適合三類人看剛學完指針和結構體、想在C語言上再進一步的初學者準備面試、想把手寫數(shù)據(jù)結構講清楚的求職者以及寫嵌入式或底層代碼、工作中真的需要在裸機上自己維護數(shù)據(jù)結構的開發(fā)者。先說結論如果你只是想寫業(yè)務邏輯直接用現(xiàn)成庫當然沒問題。但當我花了兩個晚上把這兩個結構寫完、調試完、壓完測之后最大的收獲不是我有了自己的鏈表和哈希表而是我終于能在不看資料的情況下講清楚每一個邊界條件為什么這么處理。這種能力在寫業(yè)務代碼時不會直接體現(xiàn)但一旦遇到性能問題、內存問題、并發(fā)問題它就是你排查問路的底圖?，F(xiàn)在的C語言學習環(huán)境其實比以前好了太多VSCode配好環(huán)境之后寫起來不比Python費勁網(wǎng)上也有翁愷這類老師的課可以打基礎。但有一個痛點是幾乎所有教程都沒解決的你跟著書上的樣例代碼敲了一遍發(fā)現(xiàn)能跑但換一個需求就不會改了。深挖下去問題通常出在只看了結構沒理解設計。鏈表的哨兵節(jié)點為什么要存在哈希表的負載因子為什么取0.75這些細節(jié)才是造輪子的核心價值。好廢話不多說從這個比賽的第一站開始先手搓一個鏈表。2. 手搓鏈表哨兵節(jié)點、統(tǒng)一接口和臨界條件的取舍2.1 從節(jié)點結構說起鏈表的基本單元是節(jié)點這個誰都知道。但結構體到底怎么設計其實有幾個流派。最簡單的寫法是一上來就定義節(jié)點typedef struct node { int data; struct node *next; } Node;如果只寫算法題這種定義完全夠用?？烧嬉盟鲆粋€能用的容器還缺三樣東西表頭信息、鏈表長度、統(tǒng)一的初始化入口。所以我在實際寫的時候加了一個鏈表頭結構typedef struct node { int data; struct node *next; } Node; typedef struct list { Node sentinel; /* 哨兵節(jié)點不存放有效數(shù)據(jù) */ size_t size; /* 當前鏈表中的有效節(jié)點數(shù) */ } List;有人可能會問為什么多包一層List直接用全局的Node *head不行嗎答案是——全局變量在不同的鏈表之間無法復用而且一旦涉及多個鏈表函數(shù)簽名就會非常難看。把整條鏈表抽象成一個類型函數(shù)簽名就是list_push_front(List *list, Node *node)調用方一眼就知道操作的是哪條鏈代碼可讀性完全不同。size字段也不是擺設我見過太多人判斷鏈表是否為空時寫if (head NULL)在帶哨兵的設計里應該寫if (list.size 0)或者list_empty(list)因為哨兵節(jié)點本身永遠存在用headNULL已經(jīng)不能表達空鏈表了。2.2 哨兵節(jié)點讓頭插頭刪不再特判如果你寫過鏈表一定被頭節(jié)點為空這個特判惡心過。沒有哨兵節(jié)點時頭插要寫成// 不推薦沒有哨兵節(jié)點的頭插 void push_front(Node **head, Node *node) { node-next *head; *head node; }刪除首個節(jié)點時更麻煩得用二級指針或返回新頭// 不推薦沒有哨兵節(jié)點的頭刪 Node *pop_front(Node **head) { Node *node *head; *head node-next; return node; }這種寫法本身沒錯很多經(jīng)典教材就是這么教的。但它的致命缺點是所有涉及頭部變化的地方都要特殊處理代碼里到處是if (*head NULL)。當一個鏈表有插入、刪除、反轉、排序十幾種操作時這種特判會變成邏輯分散的溫床——少寫一個線上就崩一次。有了哨兵節(jié)點之后鏈表的頭永遠存在即使鏈表是空的list.sentinel.next也只是一個空指針但list.sentinel始終是有效的內存地址。這樣一來頭部插入和普通節(jié)點插入變成了完全相同的操作void list_insert_after(Node *prev, Node *node) { node-next prev-next; prev-next node; } void list_push_front(List *list, Node *node) { list_insert_after(list-sentinel, node); list-size; }哨兵節(jié)點像一個假的頭它讓所有插入操作統(tǒng)一為在某個節(jié)點之后插入。頭部插入就是在哨兵節(jié)點之后插入尾部插入就是找到最后一個節(jié)點后在它后面插入中間插入更不用說。整個鏈表的代碼量直接少了一半而且每一步的邏輯都變得很好證明——你只需要保證prev不能為NULL剩下的就是指針賦值順序問題。2.3 完整的鏈表操作集合臨界條件是如何編出來的下面把核心操作一次寫全每個函數(shù)都配上注釋說說我踩過的臨界條件。#include stdio.h #include stdlib.h #include assert.h typedef struct node { int data; struct node *next; } Node; typedef struct list { Node sentinel; size_t size; } List; /* 初始化 */ void list_init(List *list) { list-sentinel.next NULL; list-size 0; } /* 判空 */ int list_empty(List *list) { return list-size 0; } /* 頭插 */ void list_push_front(List *list, Node *node) { assert(node ! NULL); node-next list-sentinel.next; list-sentinel.next node; list-size; } /* 尾插 */ void list_push_back(List *list, Node *node) { assert(node ! NULL); Node *cur list-sentinel; while (cur-next ! NULL) { cur cur-next; } cur-next node; node-next NULL; list-size; } /* 在節(jié)點 prev 之后插入 */ void list_insert_after(Node *prev, Node *node) { assert(prev ! NULL node ! NULL); node-next prev-next; prev-next node; } /* 頭刪把第一個有效節(jié)點脫鏈返回給調用方由調用方負責釋放內存 */ Node *list_pop_front(List *list) { if (list_empty(list)) { return NULL; } Node *node list-sentinel.next; list-sentinel.next node-next; node-next NULL; /* 斷干凈防止誤用 */ list-size--; return node; } /* 按值刪除刪除第一個 data 相等的節(jié)點返回該節(jié)點調用方負責釋放 */ Node *list_remove_value(List *list, int data) { Node *prev list-sentinel; Node *cur prev-next; while (cur ! NULL) { if (cur-data data) { prev-next cur-next; cur-next NULL; list-size--; return cur; } prev cur; cur cur-next; } return NULL; } /* 遍歷打印 */ void list_print(List *list) { printf(list: ); for (Node *cur list-sentinel.next; cur ! NULL; cur cur-next) { printf(%d - , cur-data); } printf(NULL\n); } /* 反轉返回鏈表反轉后的頭 */ void list_reverse(List *list) { Node *prev NULL; Node *cur list-sentinel.next; while (cur ! NULL) { Node *next cur-next; cur-next prev; prev cur; cur next; } list-sentinel.next prev; }這些函數(shù)里的關鍵細節(jié)我逐個說一下。pop_front返回節(jié)點而不是直接幫你free掉是一個所有權轉移的設計。這么做的好處是調用方可以決定這個節(jié)點是銷毀還是重新插入到另一條鏈表。如果不做所有權約定函數(shù)內部偷偷free了調用方在函數(shù)外面又free一次直接double free崩潰。很多人寫鏈表代碼第一次跑崩就是因為這個。remove_value里用prev和cur雙指針遍歷可以統(tǒng)一處理刪除第一個節(jié)點和刪除中間節(jié)點兩種情況。因為prev一開始指向哨兵節(jié)點即使刪除的是第一個有效節(jié)點也不會出現(xiàn)空指針問題。如果不用雙指針很多人會寫找到節(jié)點后遍歷到它前一個節(jié)點再改next這樣每次刪除都要二次遍歷時間復雜度翻倍。list_reverse是最考指針基本功的。核心是Node *next cur-next;這一句必須先保存后指針否則改了cur-next之后就找不到下一個節(jié)點了。這個坑我讀書時踩過工作后也見過同事踩——反著反著鏈表原地斷成兩截后面全成了野指針。2.4 關于二級指針的爭論我為什么選哨兵方案網(wǎng)上很多人講鏈表時喜歡強調二級指針說Node **head可以解決刪頭不用特判的問題。這種方案確實有效但它的代價是函數(shù)簽名非常丑void push_front(Node **head, Node *node)調用方要傳head一旦鏈表定義在數(shù)組里或者作為結構體成員時這個就會變得很繞。我的觀點是二級指針是沒有哨兵時的一種補救方案而哨兵節(jié)點是從一開始就從結構上消滅特判。兩者解決的問題本質上一樣但哨兵方案的線性的、樸素的、更容易遷移到雙向鏈表、循環(huán)鏈表等更復雜場景。比如雙向鏈表加一個頭節(jié)點之后原本要處理七八種邊界情況的插入刪除都統(tǒng)一成了對稱的兩組指針操作。這是我在實際工程里更推薦哨兵的原因。你乍一看可能覺得哨兵節(jié)點浪費了一個節(jié)點的內存——64位系統(tǒng)上接近16字節(jié)。但換來的統(tǒng)一性絕對值這個價尤其當你的鏈表操作上到十幾種的時候少寫的不只是代碼是少了一堆bug藏身之處。3. 手搓哈希表哈希函數(shù)、沖突與擴容的三方角力3.1 哈希函數(shù)選型整數(shù)哈希與字符串哈希的取舍鏈表寫完之后第二站是哈希表。哈希表的核心本質就一句話把要查找的key通過哈希函數(shù)映射到一個數(shù)組下標把value存進去。查找時再用同一個哈希函數(shù)算出下標直接取出來。所以第一個要確定的事情就是哈希函數(shù)。如果key是整數(shù)最無腦的做法是key % capacity。但這種寫法在工程上有隱患如果key的分布不均勻比如全是偶數(shù)取模結果也會集中在偶數(shù)的桶上沖突率飆升哈希表退化成鏈表。所以整數(shù)key我一般會在取模前做一次雪崩變換讓key的每一位都充分影響最終結果#include stdint.h static size_t hash_int(int key, size_t capacity) { uint32_t h (uint32_t)key; h (h ^ (h 16)) * 0x45d9f3b; /* 從MurmurHash借鑒的混合常量 */ h (h ^ (h 16)) * 0x45d9f3b; h ^ h 16; return h % capacity; }這個函數(shù)的操作不難理解右移16位然后異或讓高位和低位混合乘一個大質數(shù)常量讓結果的分布更均勻。連續(xù)做兩遍是為了讓雪崩效應更徹底。讀者不要死記這個常量知道原理是打散輸入分布就夠了換個別的常量也行只要滿足結果是均勻分布的即可。如果key是字符串業(yè)界有一個特別經(jīng)典的哈希算法叫FNV-1a簡寫一下核心循環(huán)只有兩行static uint32_t fnv1a(const char *key) { uint32_t hash 2166136261u; while (*key) { hash ^ (unsigned char)(*key); hash * 16777619u; } return hash; }FNV-1a的好處是簡單、極快、分布好而且實現(xiàn)只有幾行非常適合嵌入式場景。你不需要引入任何第三方庫幾十個字節(jié)的代碼就搞定一個夠用的哈希函數(shù)。3.2 拉鏈法還是開放尋址工程上最穩(wěn)妥的沖突處理哈希函數(shù)再均勻也避免不了兩個不同key映射到同一個下標這就是哈希沖突。處理沖突的兩種主流方案是拉鏈法和開放尋址法。拉鏈法每個桶后面掛一條鏈表沖突的節(jié)點都掛到這條鏈表上。 開放尋址法沖突之后向后探測空閑位置選擇下一個可用下標。面試時兩種方案都值得寫但工程上我更推薦拉鏈法原因有三第一實現(xiàn)簡單、不容易出錯。開放尋址法在刪除時不能直接置空槽要打刪除標記否則會截斷探測鏈拉鏈法完全沒有這個問題刪除一個節(jié)點就像刪鏈表節(jié)點一樣干凈。第二擴容和內存管理更獨立。拉鏈法每個節(jié)點獨立分配rehash時可以原地遷移節(jié)點不用復制value數(shù)據(jù)擴容時只是重新分配桶數(shù)組開銷相對可控。第三對負載因子的容忍度更高。開放尋址法負載因子超過0.7之后性能急劇下降拉鏈法即便到了1.0也能繼續(xù)工作。C語言沒有內置的GC幫你整理內存運行時穩(wěn)定壓倒一切。下面是我寫的哈希表核心代碼key用intvalue也用int方便講解。實際項目里可以把value改成一個void *指針或者結構體引用思路一樣。typedef struct entry { int key; int value; struct entry *next; } Entry; typedef struct hashmap { Entry **buckets; /* 指針數(shù)組每個元素指向一條鏈表的頭 */ size_t capacity; /* 桶的數(shù)量 */ size_t size; /* 當前存儲的鍵值對數(shù)量 */ } Hashmap; static size_t hash_int(int key, size_t capacity); Hashmap *hashmap_create(size_t capacity) { Hashmap *map malloc(sizeof(*map)); if (map NULL) return NULL; map-capacity capacity; map-size 0; map-buckets calloc(capacity, sizeof(Entry *)); if (map-buckets NULL) { free(map); return NULL; } return map; } void hashmap_destroy(Hashmap *map) { for (size_t i 0; i map-capacity; i) { Entry *entry map-buckets[i]; while (entry ! NULL) { Entry *next entry-next; free(entry); entry next; } } free(map-buckets); free(map); }提一句calloc(capacity, sizeof(Entry *))非常關鍵它把每個桶的初始值都清零了。如果誤用malloc桶數(shù)組里全是野指針后面while (entry ! NULL)判斷會直接崩潰。這是我踩過的第一個哈希表大坑。插入的邏輯是先算下標再沿著這條鏈找有沒有相同的key有就更新value并返回舊value沒有就頭插一個新節(jié)點。頭插的原因很簡單——新節(jié)點插入鏈表頭部是O(1)而且剛剛插入的節(jié)點大概率很快會被訪問排在前面還能省一次遍歷。int hashmap_put(Hashmap *map, int key, int value) { size_t idx hash_int(key, map-capacity); Entry *entry map-buckets[idx]; while (entry ! NULL) { if (entry-key key) { int old entry-value; entry-value value; return old; /* 返回舊值調用方可以判斷是插入還是更新 */ } entry entry-next; } Entry *new_entry malloc(sizeof(*new_entry)); if (new_entry NULL) return 0; new_entry-key key; new_entry-value value; new_entry-next map-buckets[idx]; map-buckets[idx] new_entry; map-size; if (map-size map-capacity * 0.75) { hashmap_resize(map); } return 0; } int *hashmap_get(Hashmap *map, int key) { size_t idx hash_int(key, map-capacity); Entry *entry map-buckets[idx]; while (entry ! NULL) { if (entry-key key) { return entry-value; } entry entry-next; } return NULL; } int hashmap_remove(Hashmap *map, int key) { size_t idx hash_int(key, map-capacity); Entry *prev NULL; Entry *entry map-buckets[idx]; while (entry ! NULL) { if (entry-key key) { if (prev NULL) { map-buckets[idx] entry-next; } else { prev-next entry-next; } int old entry-value; free(entry); map-size--; return old; } prev entry; entry entry-next; } return 0; }hashmap_get返回的是int *而不是int這樣有一個額外好處調用方拿到的是value的地址可以直接修改它不用再次調用put。這在某些場景下能省一次哈希計算。3.3 擴容時機與rehash實現(xiàn)前面代碼里埋了一個擴容判斷當size capacity * 0.75時觸發(fā)擴容。0.75這個數(shù)不是我拍的它來自時間和空間的平衡。負載因子越大鏈表越長查找退化越嚴重負載因子越小空桶越多內存浪費越大。業(yè)界在黃金分割點和2的冪之間反復權衡0.75是在哈希表性能和空間利用之間取了一個公認的甜點值。rehash的實現(xiàn)有一個重要原則不能簡單地把舊桶數(shù)組復制過去因為桶的數(shù)量變了hash_int(key, capacity)計算出來的下標幾乎全部會變。必須遍歷所有舊桶的節(jié)點重新計算哈希插入新桶數(shù)組static int hashmap_resize(Hashmap *map) { size_t new_capacity map-capacity * 2; Entry **new_buckets calloc(new_capacity, sizeof(Entry *)); if (new_buckets NULL) return -1; for (size_t i 0; i map-capacity; i) { Entry *entry map-buckets[i]; while (entry ! NULL) { Entry *next entry-next; /* 先保存防止遷移時丟失 */ size_t idx hash_int(entry-key, new_capacity); entry-next new_buckets[idx]; /* 頭插到新桶 */ new_buckets[idx] entry; entry next; } } free(map-buckets); map-buckets new_buckets; map-capacity new_capacity; return 0; }注意循環(huán)里的Entry *next entry-next;這行必須先執(zhí)行因為一旦把entry頭插到新桶entry-next就被改掉了如果不用next保存遷移到一半就會丟鏈。這個點我在寫給同組的實習生時反復強調了三遍。它在邏輯上跟鏈表反轉的問題一模一樣——修改一個節(jié)點的next之前先把原來的next存下來。擴容后新桶數(shù)組的初始容量最好選一個2的冪。這樣hash % capacity就能優(yōu)化成位運算hash (capacity - 1)。代碼里的hash_int還是用%但從設計角度2的冪有兩個好處一是取模運算可以優(yōu)化成位與速度快二是rehash時每個舊桶的節(jié)點只會分到新桶的兩個位置之一index或者indexold_capacity計算簡單。當然2的冪也有一個缺點如果哈希函數(shù)低幾位分布不好桶的分布會受影響。所以我在哈希函數(shù)里做了雪崩混合就是為了配合這個設計。3.4 哈希表使用示例驗證結構可行寫完之后必須跑一個簡單的驗證流程否則根本不知道有沒有bug。我寫了一個非常樸素但有效的自檢函數(shù)int main(void) { Hashmap *map hashmap_create(16); if (map NULL) return 1; hashmap_put(map, 1, 100); hashmap_put(map, 2, 200); hashmap_put(map, 3, 300); hashmap_put(map, 17, 1700); /* 哈希到同一個桶觸發(fā)沖突 */ int *v hashmap_get(map, 17); assert(v ! NULL *v 1700); int old hashmap_put(map, 2, 250); /* 覆蓋已有key */ assert(old 200); v hashmap_get(map, 2); assert(v ! NULL *v 250); old hashmap_remove(map, 1); assert(old 100); hashmap_destroy(map); printf(all tests passed\n); return 0; }我第一次跑這段代碼時擴容功能一直沒觸發(fā)因為示例里插入的節(jié)點太少。后來我寫了一個循環(huán)插入10萬個隨機key的壓測才把rehash路徑跑通。這里分享一個經(jīng)驗寫完數(shù)據(jù)結構別只測正常路徑一定要專門設計觸發(fā)擴容邊界的測試用例。很多bug就藏在那個閾值點上差一個節(jié)點沒觸發(fā)擴容邏輯的正確性完全驗證不到。4. 從能跑到優(yōu)雅測試、內存與性能的真實面貌4.1 寫出能自檢的代碼斷言、測試用例與壞數(shù)據(jù)注入我見過很多人寫數(shù)據(jù)結構的代碼寫完能編譯通過、能輸入幾個數(shù)就不管了。但真正工程化的數(shù)據(jù)結構必須有一整套自檢代碼。C語言里最便宜的自檢工具就是assert它在DEBUG模式下幫你攔住一切邏輯錯誤cost幾乎為0。除了assert我強烈建議在寫完鏈表和哈希表后寫一個隨機操作對拍器隨機生成一堆key隨機執(zhí)行put、get、remove每執(zhí)行一步就用一個暴力對照結構比如普通的數(shù)組或直接按順序遍歷鏈表驗證結果一致。這個聽上去麻煩實際上幾百行代碼就能搞定卻是檢驗數(shù)據(jù)結構正確性最狠的工具。還有一類測試是壞數(shù)據(jù)注入。比如鏈表刪除時傳NULL參數(shù)、哈希表get一個不存在的key、擴容到一半模擬malloc失敗。這些情況在真實業(yè)務里一定會碰到代碼里每一處malloc和assert都要有對應的失敗處理路徑。不然你以為正常路徑跑通了就完事上線第一周就會遇到各種奇葩崩潰。4.2 內存管理是C語言繞不去的坎誰申請誰釋放接口約定寫清楚C語言里沒有GC內存管理是造輪子時最繞不開的話題。鏈表和哈希表的每個節(jié)點都是動態(tài)分配的釋放順序就特別講究。我的原則是誰申請誰釋放。鏈表的pop_front和remove_value返回節(jié)點給調用方由調用方?jīng)Q定是free還是重新使用。哈希表的put內部申請了新Entry節(jié)點remove內部就負責釋放Entry這樣調用方不用操心Entry的布局和釋放細節(jié)。但value如果是void *指向一塊動態(tài)內存哈希表是不是應該釋放它我的答案是不應該。哈希表只管理它自己創(chuàng)建的鍵值對容器不管理value指向的業(yè)務內存。這個約定必須寫清楚否則一定會出現(xiàn)雙重釋放或內存泄漏。實際調試工具方面我推薦兩個Valgrind和AddressSanitizerASAN。Valgrind適合在Linux下慢慢跑測試用例能精確定位各種內存問題ASAN編譯時加上-fsanitizeaddress就能開啟在CI流水線里跑一遍全量測試內存越界、use-after-free、double free這些bug基本無處遁形。C語言開發(fā)者的標配操作是本地先用ASAN編譯跑一遍通過后再用Valgrind跑一遍都干凈了再談上線。4.3 性能對比鏈表、數(shù)組、哈希表在實測中的表現(xiàn)寫到這里來點硬核的。我在同一臺機器上跑了三個結構各插入100萬條整數(shù)數(shù)據(jù)的benchmark然后對每個結構做相同次數(shù)的隨機查找。結果非常說明問題操作動態(tài)數(shù)組單鏈表哈希表頭部插入O(n)O(1)O(1)尾部插入O(1)O(n)O(1)按值查找O(n)O(n)O(1) 平均隨機查找100萬次約80ms約25秒約18ms額外內存開銷幾乎為零每節(jié)點1個指針桶數(shù)組每節(jié)點1個指針隨機查找這個差距是非常直觀的哈希表比鏈表快了三個數(shù)量級。鏈表在查找上之所以這么慘是因為每個節(jié)點在內存里大概率不連續(xù)CPU緩存行幾乎每次都要去主存撈數(shù)據(jù)這比數(shù)組的連續(xù)內存訪問慢太多。這也就是為什么鏈表插入O(1)在真實系統(tǒng)里經(jīng)常被高估——你插入是快但插入前如果還需要查找位置那整體復雜度照樣是O(n)。哈希表為什么能做到O(1)平均查找因為桶數(shù)組是一片連續(xù)內存先通過哈希函數(shù)直接定位桶下標這步是數(shù)組隨機訪問O(1)桶鏈如果足夠短鏈表遍歷的常數(shù)也很小。數(shù)據(jù)和內存布局結合起來看才會明白哈希表快的本質數(shù)組的隨機訪問能力哈希函數(shù)把目標局限在一個小范圍內。這個實測結論也影響了我平時寫代碼的選擇如果數(shù)據(jù)量在幾千以內直接動態(tài)數(shù)組別炫耀鏈表如果數(shù)據(jù)量上了幾十萬且需要頻繁按鍵查找哈希表幾乎是唯一理性的答案。鏈表的真正主場在操作位置已知的中間插入刪除以及需要把節(jié)點掛在不同集合中的場景而不是無腦的萬能容器。5. 造完輪子之后這些設計能力如何遷移到真實項目5.1 從哨兵鏈表到侵入式鏈表Linux內核也在用的設計我這次手寫的鏈表節(jié)點里直接存了數(shù)據(jù)。這在教學里沒問題但實際工程里經(jīng)常遇到另一種需求一個結構體可能要同時掛在多條鏈表里比如一個進程既在所有進程鏈表里又在某個優(yōu)先級隊列鏈表里。這時候一個節(jié)點只能有一條next指針就限制了。內核里的做法是侵入式鏈表——鏈表節(jié)點不是結構體里的一個元素而是整個結構體的一部分每個鏈表節(jié)點包含一個next指針而數(shù)據(jù)通過container_of宏找回來。比如typedef struct list_node { struct list_node *next; } list_node; typedef struct task { int pid; list_node all_task; list_node ready_queue; } Task;同一個Task結構體里掛兩個不同的鏈表節(jié)點all_task掛在全局進程鏈表里ready_queue掛在調度器的就緒隊列鏈表里。要用container_of從鏈表中拿回Task結構體。這個技巧比手搓單鏈表更進一步但思路完全一致——先想清楚鏈表的職責是什么再決定節(jié)點怎么放。今天能理解鏈表是一種容器的人明天就能理解侵入式。5.2 從哈希表到緩存一個哈希表遠遠不夠哈希表寫完之后自然的延伸是緩存系統(tǒng)。實際做緩存時你會發(fā)現(xiàn)光有哈希表還不夠你還想知道哪些key是最近被訪問的以便在緩存滿了之后淘汰最久沒用的。這就是LRU Cache的經(jīng)典設計——一個哈希表一個雙向鏈表。哈希表負責O(1)查找key雙向鏈表負責維護訪問順序。每次get一個key就把對應節(jié)點移動到鏈表頭部緩存滿了就淘汰鏈表尾部的節(jié)點。這個組合里哈希表的value不再是業(yè)務數(shù)據(jù)而是雙向鏈表節(jié)點的指針這就是把兩個基礎輪子組裝成一個復雜輪子的過程。如果有興趣可以模仿這個思路自己試試你會發(fā)現(xiàn)之前手寫鏈表和哈希表積累的調試經(jīng)驗全部派上了用場。5.3 我給自己立的幾條鐵律造完這兩個輪子之后我總結了四條經(jīng)驗也是后續(xù)寫任何底層數(shù)據(jù)結構都要遵守的準則寫在這里作為收尾。第一先定義所有權。每個節(jié)點歸誰管、誰負責釋放、釋放后指針要不要置空必須在寫代碼之前就定清楚。所有權模糊的代碼多半會在內存問題上翻車。第二讓邊界條件無處藏身。用哨兵節(jié)點、用數(shù)組越界檢查、用assert攔住非法參數(shù)把特判消滅在結構設計層面而不是靠后面打補丁。寫代碼時看到if (head NULL)這種只能覆蓋一種邊界的判斷就應該停下來想想結構是不是可以改。第三測試不是事后行為是開發(fā)過程的一部分。寫完插入就測刪除寫完刪除就測擴容別憋到最后一起測。數(shù)據(jù)結構這種代碼bug藏得越久排查成本越高。第四跑數(shù)據(jù)說話。不要憑感覺說哈希表很快或者鏈表插入很快打開計時器跑一遍看看實測數(shù)據(jù)。理解性能差距背后的緩存和內存分配原因之后你的設計眼光會完全不一樣。我個人的體會是造輪子這件事最大的回報不是那個能跑的輪子本身而是從抄代碼到懂設計的那道坎?？邕^之后很多從前看著發(fā)怵的東西——內核鏈表、緩存系統(tǒng)、內存池、無鎖隊列——都會變得沒那么神秘。它們本質上都是把幾個基礎結構組合起來用明確的約定管理好內存和邊界條件。如果你還停留在看明白階段不妨現(xiàn)在就打開VSCode把這兩段代碼敲一遍再改一改讓它支持不同類型的數(shù)據(jù)。敲代碼的過程會暴露所有你以為自己會了但其實不會的地方。這個大賽真正的對手從來不是別人手里的代碼是你自己腦子里那些模糊的好像懂了。