哈希表這個東西我在面試和實際工程里都吃過不少甜頭也踩過不少坑。別看它表面就“鍵值對映射”這一句話真要往深了摳里面的門道夠講一整篇。今天這篇文章就用純手寫代碼的思路從底層結(jié)構(gòu)到工程實踐把哈希表拆開揉碎講清楚。不管你是剛學(xué)算法準(zhǔn)備筆試還是工作幾年想回來補(bǔ)補(bǔ)內(nèi)功這篇應(yīng)該都能讓你對哈希表有個不一樣的認(rèn)識。1. 內(nèi)容整體設(shè)計與思路拆解1.1 哈希表到底解決了什么問題數(shù)組大家都熟按下標(biāo)訪問是 O(1) 的但它的前提是“位置語義”必須知道數(shù)據(jù)存在哪個下標(biāo)。如果現(xiàn)在場景換成“根據(jù)姓名找電話號碼”你不可能拿“張三”當(dāng)數(shù)組下標(biāo)去訪問。哈希表的核心貢獻(xiàn)就是給任意類型的“鍵”做一次映射把它轉(zhuǎn)成一個數(shù)組下標(biāo)然后把 O(n) 的線性查找直接變成 O(1) 的近似訪問。換個生活化的類比就像你去快遞驛站取件如果沒有分區(qū)編號你得在堆成山的包裹里挨個翻找自己的名字有了“貨架號層號”的編碼體系你按圖索驥直接走過去就能拿。哈希表干的就是“把客戶姓名換算成貨架號”這回事這個換算函數(shù)就叫哈希函數(shù)。1.2 哈希表數(shù)據(jù)結(jié)構(gòu)的基本構(gòu)成一張哈希表從底層看其實就三樣?xùn)|西一塊連續(xù)的內(nèi)存區(qū)域?qū)W名叫桶數(shù)組它決定了一張表能存多少“主倉位”。一個哈希函數(shù)把任意輸入的鍵換算成桶數(shù)組的下標(biāo)。一套沖突處理策略因為不同鍵映射到同一個下標(biāo)是必然的問題不是“會不會撞”而是“撞了之后怎么處理”。這個設(shè)計順序很重要。我見過不少初學(xué)者上來就背“哈希表是O(1)查找”這句話結(jié)果問他沖突是怎么解決的他一愣。其實這個問題的答案直接決定了你的哈希表是“理論快”還是“真快”。最經(jīng)典的開鏈法和開放尋址法前者是每個桶掛一個鏈表后者是沖突了就往后找空位兩種方案的性能和適用場景完全不同。1.3 手寫哈希表的整體技術(shù)選型我用 C 手寫哈希表時選型的思路是這么走的存儲載體用動態(tài)數(shù)組 vector這樣才能在擴(kuò)容時方便地重新映射。沖突處理先寫鏈地址法也就是“數(shù)組 鏈表”因為它實現(xiàn)直觀刪除操作容易不容易踩到開放尋址里“刪除后會把查找鏈斷掉”的坑。哈希函數(shù)從最簡單的取模開始但會強(qiáng)調(diào)一個關(guān)鍵細(xì)節(jié)模數(shù)不能隨便選最好用質(zhì)數(shù)因為質(zhì)數(shù)能減少哈希值的聚集現(xiàn)象。鍵類型用 int這樣你在看代碼時能把注意力完全集中在哈希表本身的邏輯上而不是被字符串哈希的邊角細(xì)節(jié)干擾。我需要先說清楚這里手寫哈希表絕不是為了讓你在工程里重復(fù)造輪子。真正的價值有兩個一是面試時你對著 map 和 unordered_map 不至于只會背“紅黑樹快還是哈希表快”這種結(jié)論而是能講清楚底層差異二是遇到性能瓶頸時你知道應(yīng)該去優(yōu)化哈希表的哪個環(huán)節(jié)而不是瞎猜。2. 哈希函數(shù)與沖突處理的核心機(jī)制解析2.1 哈希函數(shù)為什么不能太“隨便”哈希函數(shù)是整張哈希表的靈魂。它的理想狀態(tài)是把鍵均勻地撒到數(shù)組的每個桶里。但現(xiàn)實是完美均勻幾乎不可能所以我們評估一個哈希函數(shù)好不好主要看三個維度第一計算速度快不快。如果你的哈希函數(shù)本身就要跑一個復(fù)雜加密算法那即使查找次數(shù)再少時間也全花在算哈希值上了整體性能一樣難看。第二雪崩效應(yīng)夠不夠好。意思是輸入哪怕只變一點點輸出也應(yīng)該天翻地覆地變而不是只差一個數(shù)字否則兩個相近的鍵很容易聚在同一個桶。第三碰撞率低不低。碰撞率直接決定了鏈表的平均長度鏈表越長查詢效率越差。拿最基礎(chǔ)的取模法舉例。假如桶數(shù)組大小是 100哈希函數(shù)是 key % 100這看起來沒問題但實際上如果 key 的分布正好和 100 有關(guān)系比如系統(tǒng)產(chǎn)生的 ID 全是偶數(shù)你會發(fā)現(xiàn)所有數(shù)據(jù)都落到了 0、2、4、6 這些偶數(shù)桶里奇數(shù)桶全部閑置。這種分布不均說白了就是哈希函數(shù)的“自私”它有規(guī)律地偏愛某些下標(biāo)導(dǎo)致數(shù)據(jù)嚴(yán)重傾斜。2.2 沖突處理策略詳解鏈地址法與開放尋址法鏈地址法也叫拉鏈法是工程最常用的方案Java 的 HashMap 和 C 的 unordered_map 都是基于它實現(xiàn)的變種。它的做法是每個桶不直接存數(shù)據(jù)而是存一個鏈表的頭指針。當(dāng)多個鍵映射到同一個桶時就把它們依次掛到這個桶的鏈表后面。我拿這個方案練手最大的感受是它的“刪除操作”特別自然。找到桶之后在鏈表里做常規(guī)的刪除節(jié)點操作就行不需要額外標(biāo)狀態(tài)。而且只要哈希函數(shù)選得還可以每個桶的鏈表平均長度就會很短短到鏈表掃描的成本可以忽略不計。開放尋址法和鏈地址法就是兩個完全不同的思路。它不設(shè)鏈表所有元素直接躺在桶數(shù)組里。沖突發(fā)生時按照一定規(guī)則向后探測找到下一個空位放進(jìn)去。查找的時候也是按同樣的規(guī)則探測直到找到目標(biāo)或者遇到空桶。聽起來開放尋址法好像還更省內(nèi)存因為它不需要維護(hù)鏈表節(jié)點的額外指針。但它的致命弱點在于刪除操作會破壞探測鏈導(dǎo)致明明存在的元素找不到了。為了解決這個問題通常要引入“墓碑標(biāo)記”給被刪除的位置做一個特殊記號查找時看到墓碑要繼續(xù)往后探測。這就讓實現(xiàn)復(fù)雜度上了一個臺階所以新手入門我更推薦先用鏈地址法跑通整體邏輯把開放尋址當(dāng)作進(jìn)階思考題去研究。2.3 模數(shù)的選擇為什么用質(zhì)數(shù)是更好的實踐我之前說過取模的模數(shù)盡量用質(zhì)數(shù)。這話不是玄學(xué)背后是數(shù)論層面的原因。假設(shè)桶大小是 12某個鍵產(chǎn)生哈希值的規(guī)律是每隔 2 遞增比如 0、2、4、6...那么全部對 12 取模后你會驚訝地發(fā)現(xiàn)結(jié)果只在 0、2、4、6、8、10 這幾個偶數(shù)里打轉(zhuǎn)。為什么會這樣因為 2 是 12 的因子所以步長 2 和模數(shù) 12 有公因子就會不斷踩進(jìn)同一個“模數(shù)環(huán)”里跳不出來。但如果桶大小取質(zhì)數(shù)比如 132 和 13 互質(zhì)那步長 2 的遍歷就會覆蓋到 0 到 12 的每一個值數(shù)據(jù)分布就鋪開了。這就是為什么很多 STL 老鳥會說哈希表桶數(shù)量盡量取質(zhì)數(shù)。但在 C 的 STL 里這個原則常常被專門的“桶數(shù)量生成策略”替代它不一定嚴(yán)格用質(zhì)數(shù)但一定做了合理的選數(shù)避免明顯的公因子問題。2.4 擴(kuò)容機(jī)制負(fù)載因子與重新哈希哈希表不能無限往里塞數(shù)據(jù)因為桶的總數(shù)是固定的塞得越多鏈表越長哈希表退化成鏈表的風(fēng)險越大。所以每個哈希表都會有一個負(fù)載因子的概念計算方式是負(fù)載因子 存儲元素個數(shù) / 桶總數(shù)鏈地址法通常把閾值定在 0.75 到 1.0 左右。C 的 unordered_map 把這個值暴露給大家也允許開發(fā)者自己調(diào)整。負(fù)載因子超過閾值后就要執(zhí)行擴(kuò)容。擴(kuò)容的策略是重新申請一張更大的桶數(shù)組通常大小變成原來的兩倍左右然后把舊數(shù)據(jù)全部重新計算哈希值、重新插入到新桶里。這個過程叫 rehash它的時間復(fù)雜度是 O(n)單次觸發(fā)會卡頓但均攤到每次插入操作后整體復(fù)雜度依然是 O(1)。我見過不少人在手寫哈希表時忽略擴(kuò)容結(jié)果測試的時候數(shù)據(jù)量一大直接超時這不是算法問題是工程習(xí)慣問題。后面寫代碼時我會把擴(kuò)容槽位直接做進(jìn)去這才是和 STL 行為對齊的做法。3. 實戰(zhàn)C 手寫一個鏈地址法哈希表3.1 為什么用 C 寫哈希表有人可能問哈希表明明是個語言無關(guān)的數(shù)據(jù)結(jié)構(gòu)為什么這里要用 C 來演示一方面是因為很多刷題場景和面試場景默認(rèn)用的就是 C另一方面是 C 對內(nèi)存和對象生命周期的控制更顯式你在操作指針和節(jié)點時能更直觀地理解哈希表底層“每一塊內(nèi)存”是怎么被組織起來的。語言越貼底層你對數(shù)據(jù)結(jié)構(gòu)的理解就越扎實。如果換 Python很多操作都會被 dict 給遮住了你根本看不到后面發(fā)生了什么換 Java大量都封裝在 HashMap 里你看到的是方法調(diào)用。當(dāng)然這不代表 Java 不行只是從“學(xué)習(xí)原理”這個角度出發(fā)C 手寫一遍是最讓人通透的。3.2 關(guān)鍵代碼實現(xiàn)節(jié)點、哈希表類、插入、查找、刪除直接上代碼。我會按步驟拆開講不求一上來就寫成大型庫只求邏輯完整、能跑。第一步定義鏈表節(jié)點。這個節(jié)點既要存放鍵值對也要有一個指向下一個節(jié)點的指針這里我把 key 和 value 分開存后面做練習(xí)時你就可以自己擴(kuò)展成模板。為了簡單我先用整數(shù)鍵值對來演示struct Node { int key; int value; Node* next; Node(int k, int v) : key(k), value(v), next(nullptr) {} };第二步定義哈希表類主體。類的成員變量包括桶數(shù)組 vector桶數(shù)量以及當(dāng)前存儲元素個數(shù)class HashTable { private: vectorNode* buckets; int bucketCount; int size; int hashFunc(int key) { // 簡單取模桶數(shù)以質(zhì)數(shù)為主 return key % bucketCount; } void rehash(); public: HashTable(int count 13) : bucketCount(count), size(0) { buckets.resize(bucketCount, nullptr); } void insert(int key, int value); bool find(int key, int value); bool remove(int key); ~HashTable(); };第三步是插入函數(shù)。這個函數(shù)的核心邏輯是先算哈希值找到對應(yīng)的桶然后遍歷這個桶的鏈表如果發(fā)現(xiàn) key 已經(jīng)存在就更新值不存在就頭插一個新節(jié)點。頭插法比尾插法省去遍歷到鏈表末尾的過程簡潔高效void HashTable::insert(int key, int value) { int index hashFunc(key); Node* head buckets[index]; Node* cur head; while (cur ! nullptr) { if (cur-key key) { cur-value value; // 鍵已存在更新值 return; } cur cur-next; } // 鍵不存在頭插新節(jié)點 Node* newNode new Node(key, value); newNode-next buckets[index]; buckets[index] newNode; size; // 檢查負(fù)載因子決定是否擴(kuò)容 if ((double)size / bucketCount 0.75) { rehash(); } }第四步是查找函數(shù)。查找的邏輯和插入的前半部分完全一致這本身就體現(xiàn)出哈希表操作的統(tǒng)一性算下標(biāo)、遍歷鏈表、按 key 比較bool HashTable::find(int key, int value) { int index hashFunc(key); Node* cur buckets[index]; while (cur ! nullptr) { if (cur-key key) { value cur-value; return true; } cur cur-next; } return false; }第五步是刪除函數(shù)。刪除有兩種常見做法一種是用兩個指針做 prev 和 cur 的交替遍歷另一種是保存前驅(qū)節(jié)點。我建議用雙指針?biāo)悸非宄蝗菀壮霈F(xiàn)自引用問題bool HashTable::remove(int key) { int index hashFunc(key); Node* cur buckets[index]; Node* prev nullptr; while (cur ! nullptr) { if (cur-key key) { if (prev nullptr) { // 刪除的是頭節(jié)點 buckets[index] cur-next; } else { prev-next cur-next; } delete cur; size--; return true; } prev cur; cur cur-next; } return false; }第六步是析構(gòu)函數(shù)和 rehash。析構(gòu)函數(shù)要釋放所有鏈表節(jié)點防止內(nèi)存泄漏。rehash 負(fù)責(zé)在負(fù)載因子超標(biāo)時擴(kuò)容HashTable::~HashTable() { for (int i 0; i bucketCount; i) { Node* cur buckets[i]; while (cur ! nullptr) { Node* temp cur; cur cur-next; delete temp; } } } void HashTable::rehash() { int newBucketCount bucketCount * 2 1; // 盡量選一個有利于分布的奇數(shù)/質(zhì)數(shù) vectorNode* newBuckets(newBucketCount, nullptr); for (int i 0; i bucketCount; i) { Node* cur buckets[i]; while (cur ! nullptr) { Node* next cur-next; int newIndex cur-key % newBucketCount; cur-next newBuckets[newIndex]; newBuckets[newIndex] cur; cur next; } } buckets.swap(newBuckets); bucketCount newBucketCount; }這里我采用bucketCount * 2 1來生成新桶數(shù)。需要注意它不嚴(yán)格保證是質(zhì)數(shù)但在常見場景下已經(jīng)能有效避免連續(xù)公因子問題。如果你要更嚴(yán)謹(jǐn)?shù)馁|(zhì)數(shù)表策略可以參考 STL 內(nèi)部那套立體化增長策略它會維護(hù)一個預(yù)置的質(zhì)數(shù)列表并依次切換。3.3 unordered_map 的使用方式與手寫版對比工程里直接用 C STL 的 unordered_map 是最常見的操作。它的底層就是哈希表不過做了大量優(yōu)化支持任意可哈希類型比如 string。使用示例#include iostream #include unordered_map #include string int main() { std::unordered_mapstd::string, int ageMap; ageMap[Alice] 30; ageMap[Bob] 25; auto it ageMap.find(Alice); if (it ! ageMap.end()) { std::cout it-second std::endl; } return 0; }和手寫版對比unordered_map 的差異主要體現(xiàn)在三塊第一它自動管理節(jié)點內(nèi)存你不用手動 new 和 delete也就不容易泄漏第二它支持自定義哈希函數(shù)和相等比較函數(shù)適合復(fù)雜鍵類型第三它內(nèi)部采用鏈表加桶數(shù)組的組織方式還維護(hù)了節(jié)點之間的迭代順序細(xì)節(jié)工程魯棒性更強(qiáng)。但為什么仍然建議手寫一遍我打個比方你會開自動擋汽車不等于你懂發(fā)動機(jī)原理。真到車輛出故障你還是一頭霧水。手寫哈希表最大的價值就在于逼迫你在內(nèi)存層面搞清楚“每個節(jié)點怎么掛”“擴(kuò)容時數(shù)據(jù)怎么挪”這些核心問題。很多坑你只在用 unordered_map 時是永遠(yuǎn)看不到的。3.4 字符串鍵的哈希處理經(jīng)驗實際工作中更多時候用的鍵是字符串。C 里常見字符串哈希是“多項式滾動哈希”原理是把字符串每個字符當(dāng)成一個數(shù)字按位加權(quán)求和hash (hash * base str[i]) % modbase 一般取一個質(zhì)數(shù)比如 31 或 131mod 取一個大質(zhì)數(shù)比如 1e97。為什么 base 取質(zhì)數(shù)因為質(zhì)數(shù)能讓字符序列的排列組合在哈?？臻g里分布更散減少不同字符串映射到同一哈希值的概率。我在項目里也踩過字符串哈希不均導(dǎo)致查詢變慢的坑。當(dāng)時是給一批 URL 生成哈希桶base 取了 10結(jié)果所有 URL 最后幾位的數(shù)字變化被 10 的冪次反復(fù)加權(quán)放大了哈希聚集非常嚴(yán)重。后來換成 base 131問題立刻緩解。這種實際調(diào)參的經(jīng)驗比單純背公式有用得多。4. 常見問題與排查技巧實錄4.1 哈希沖突嚴(yán)重查詢退化如何排查現(xiàn)象是數(shù)據(jù)量不大的時候哈希表查詢卻明顯變慢。這時候第一反應(yīng)不是懷疑代碼寫得不對而是懷疑哈希函數(shù)的分布不均勻。排查方法很簡單寫一個統(tǒng)計腳本把所有鍵的哈希下標(biāo)分布打印出來看它是不是均勻落在各個桶里。如果發(fā)現(xiàn)大量鍵集中在某幾個桶基本可以確認(rèn)是哈希函數(shù)的問題。此時可以嘗試改 base 或 mod或者用更好的混合哈希算法來打散數(shù)據(jù)。我在實際項目里遇到過用默認(rèn)哈希函數(shù)處理一組特定字符串時大量沖突的問題換成一個帶隨機(jī)種子的哈希函數(shù)后立刻緩解。這種坑不好提前避免只能靠監(jiān)控和切換策略兜底。4.2 刪除操作找不到節(jié)點的問題如果使用開放尋址法刪除時直接“置空”會導(dǎo)致后續(xù)探測器在停止條件上誤判從而找不到那些原本還存在的元素。這是開放尋址法最經(jīng)典的坑。你明明插入了數(shù)據(jù)刪除一個不相干的鍵之后再查之前的鍵卻返回不存在就是墓碑標(biāo)記沒做好。鏈地址法雖然天然規(guī)避了這個問題但如果你在鏈表刪除時沒正確維護(hù) prev 指針也會出現(xiàn)“斷鏈”或“自引用”的 bug表現(xiàn)為刪除一個節(jié)點后整個鏈表的部分元素突然不可達(dá)了。排查這類問題我會在紙上一格一格畫鏈表結(jié)構(gòu)順著指針跑一遍很快就能定位到是哪個指針丟了。4.3 擴(kuò)容與迭代器失效問題C 中unordered_map 在擴(kuò)容后之前獲得的迭代器可能失效。這個問題在單線程里容易踩在多線程環(huán)境里更容易踩。你是不是覺得擴(kuò)容只是內(nèi)部數(shù)組搬數(shù)據(jù)迭代器應(yīng)該還在其實哈希表的迭代器內(nèi)部保存了當(dāng)前節(jié)點和桶編號的關(guān)聯(lián)信息擴(kuò)容后桶數(shù)組完全重排舊迭代器對應(yīng)的桶和節(jié)點關(guān)系全部亂了。解決辦法很簡單在循環(huán)插入擴(kuò)容的代碼里不要長期持有舊迭代器每次使用 find 重新獲取或直接通過鍵訪問。4.4 哈希表常見坑位清單問題類型現(xiàn)象主要原因解決方案哈希分布不均數(shù)據(jù)量大時查詢變慢桶數(shù)選了合數(shù)或哈希函數(shù)不均衡桶數(shù)盡量取質(zhì)數(shù)改進(jìn)哈希函數(shù)刪除后查不到明明存在卻 find 失敗開放尋址法缺少墓碑標(biāo)記改用鏈地址法或?qū)崿F(xiàn)好標(biāo)記邏輯內(nèi)存泄漏程序跑久了內(nèi)存增長析構(gòu)函數(shù)沒有釋放全部鏈表節(jié)點逐個釋放每個桶的所有節(jié)點迭代器失效循環(huán)中插入后訪問失效擴(kuò)容導(dǎo)致桶結(jié)構(gòu)重排擴(kuò)容后重新獲取迭代器負(fù)載因子過高查詢退化到 O(n)未觸發(fā)擴(kuò)容插入后檢查現(xiàn)有 size 并執(zhí)行 rehash這張表是實際開發(fā)中最常碰到的五個坑的濃縮寫在紙上貼在工位旁邊比臨時上網(wǎng)找答案要快得多。4.5 自定義哈希函數(shù)與對象鍵的擴(kuò)展心得當(dāng)你用自定義結(jié)構(gòu)體做鍵時比如一個包含兩個 int 的坐標(biāo)類C 默認(rèn)的 std::hash 是不能直接使用的需要自己提供哈希函數(shù)。常規(guī)做法是把多個字段合并成一個整數(shù)再套用一個混合函數(shù)打散。我用過最簡潔的方案是struct PointHash { size_t operator()(const Point p) const { return hashint()(p.x) ^ (hashint()(p.y) 1); } };這種“異或加移位”的組合方式比簡單相加更穩(wěn)因為如果兩個字段拼成字符串的話(1,23)和(12,3)就有撞車風(fēng)險而異或加移位能更好地區(qū)分不同字段組合。當(dāng)然它依然不是完美方案但作為自定義鍵的哈希它已經(jīng)比很多人直接用相加要嚴(yán)謹(jǐn)?shù)枚唷?. 哈希表的工程應(yīng)用與實際落地場景5.1 緩存系統(tǒng)里免密查找的價值哈希表最典型的應(yīng)用是緩存。無論是內(nèi)存級的緩存組件還是應(yīng)用內(nèi)的小緩存底層幾乎都離不開哈希表。因為緩存的核心要求就是用一個鍵快速判斷數(shù)據(jù)是否存在并把命中的數(shù)據(jù)盡快取出來。鏈表和數(shù)組在“快速定位”這件事上都力不從心只有哈希表能以近乎 O(1) 的代價完成。我自己維護(hù)過一個小的熱點數(shù)據(jù)緩存當(dāng)時用哈希表存商品 ID 和商品詳情的映射壓測下來單次查詢耗時從原來的毫秒級降到微秒級。哈希表在這個場景下的價值不是“比樹快一倍”這種程度而是質(zhì)的差距。尤其當(dāng)數(shù)據(jù)量大了以后紅黑樹的 O(log n) 在千萬級別數(shù)據(jù)下意味著單次查詢要比較二十多次而哈希表穩(wěn)定在個位數(shù)次操作性能差距非常直觀。5.2 計數(shù)與去重場景的標(biāo)準(zhǔn)答案另外兩個高頻應(yīng)用場景是計數(shù)和去重。統(tǒng)計一段文本中每個單詞出現(xiàn)的次數(shù)、計算兩個數(shù)組的交集、判斷一個元素是否已經(jīng)出現(xiàn)過這些場景全是哈希表的主場。我之前做過一個日志分析工具要統(tǒng)計海量日志中各類錯誤碼的出現(xiàn)次數(shù)直接拿 unordered_map 存錯誤碼到計數(shù)的映射代碼量不到十行就能跑出結(jié)果。同樣的事要用數(shù)組做要么你得先知道錯誤碼的范圍要么就得接受 O(n2) 的暴力查找。哈希表在這里的不可替代性非常明顯它允許你在“未知范圍”和“任意類型”的鍵上做高效聚合用空間換時間。5.3 分布式系統(tǒng)分片與哈希環(huán)的進(jìn)階話題哈希表在單機(jī)場景下已經(jīng)夠好用但在分布式系統(tǒng)里它還會升級出兩個重要變種一致性哈希和哈希分片。一致性哈希解決的是“節(jié)點變動時數(shù)據(jù)遷移量過大”的問題。傳統(tǒng)取模方案里如果后端節(jié)點數(shù)從 5 變成 6那么 5/6 的鍵都會映射到新節(jié)點上緩存命中率會瞬間崩潰。一致性哈希把哈希結(jié)果映射到一個虛擬環(huán)上每個節(jié)點負(fù)責(zé)環(huán)上的一段區(qū)間節(jié)點增刪時只會影響相鄰區(qū)間數(shù)據(jù)遷移量大幅減少。這在微服務(wù)架構(gòu)和緩存集群里是個極其重要的設(shè)計面試也愛問。哈希分片則是把一個大哈希表按哈希值范圍拆到不同的物理節(jié)點上。比如把 userId 做哈希后取前兩位把數(shù)據(jù)橫向切到不同分片。這種方案能突破單機(jī)內(nèi)存上限是很多分布式數(shù)據(jù)庫的底層思路之一。這些進(jìn)階話題不需要你現(xiàn)在就完全掌握但當(dāng)你理解了哈希函數(shù)、沖突、擴(kuò)容這些基礎(chǔ)概念之后再去讀一致性哈希的文檔你會有一種“原來如此”的感覺所有上層復(fù)雜設(shè)計底層踩的還是那幾個最原始的原則。6. 復(fù)雜度分析與選型決策6.1 時間復(fù)雜度與空間復(fù)雜度的精確定位哈希表的理想時間復(fù)雜度是 O(1) 查找但這里有個前提哈希函數(shù)均勻且負(fù)載因子控制得好。如果負(fù)載因子過高、沖突嚴(yán)重最壞情況下所有鍵都堆在一個桶里查找會退化到 O(n)這和鏈表沒什么區(qū)別了。均攤角度來說插入操作因為有偶爾的 rehash單次可能 O(n)但所有插入加起來的總成本均攤下來依然是 O(1)。這個“均攤”概念很重要我在面試中經(jīng)常會讓候選人解釋為什么哈希表說是 O(1)卻偶爾會卡一下。答案就是擴(kuò)容重哈希在作祟?？臻g復(fù)雜度方面哈希表需要為每個元素額外存儲指針和可能被浪費(fèi)的空桶所以它本質(zhì)上是“用空間換時間”的典型代表。6.2 哈希表和平衡樹怎么選擇這是程序員在選擇數(shù)據(jù)結(jié)構(gòu)時繞不開的問題。HashMap 的查找通常比 TreeMap 快但 TreeMap 有它不可替代的殺手锏有序性。需要范圍查詢、按順序遍歷、找最大值最小值前綴等場景平衡樹完勝。另外平衡樹的性能更穩(wěn)定不會出現(xiàn)哈希表那種極端情況下退化到 O(n) 的意外。我的選擇經(jīng)驗很簡單只要對順序有要求就放棄哈希表只要對查找速度有極致要求且不需要順序就上哈希表。舉個例子統(tǒng)計詞頻用哈希表最舒服但要做“按出現(xiàn)次數(shù)排序后輸出前十個單詞”那就是先哈希表統(tǒng)計再排序。兩個根本不矛盾它們是配合關(guān)系而不是對立關(guān)系。6.3 空間占用對比的細(xì)節(jié)把控同樣是存一萬個鍵值對哈希表的空間開銷其實比很多人想象的要大。首先是桶數(shù)組本身即使某個桶里沒有元素也要占據(jù)一個指針的空間其次是鏈表的每個節(jié)點還有額外指針。我在定過一個結(jié)構(gòu)體數(shù)組和哈希表做對比測試數(shù)據(jù)量 10 萬級別時哈希表的內(nèi)存占用幾乎是數(shù)組的 2 到 3 倍。所以如果內(nèi)存極度緊張、鍵的范圍又已知且連續(xù)數(shù)組永遠(yuǎn)是更合適的選擇這點要心里有數(shù)。7. 性能優(yōu)化與擴(kuò)展思路7.1 預(yù)留空間減少擴(kuò)容次數(shù)unordered_map 有一個接口叫 reserve可以提前告訴它將來大概要存多少元素它會在初始階段就分配好足夠大的桶數(shù)組。這樣后續(xù)插入就不必頻繁觸發(fā) rehash性能會大幅提升。我在處理大批量數(shù)據(jù)導(dǎo)入時習(xí)慣先根據(jù)預(yù)估數(shù)據(jù)量調(diào)用 reserve。對比測試中同樣的 100 萬條數(shù)據(jù)導(dǎo)入不調(diào)用 reserve 比調(diào)用 reserve 的耗時高出 30% 以上。這個優(yōu)化真的屬于花最小成本得到最大收益的操作建議任何批量場景都要用上。7.2 讓哈希函數(shù)調(diào)用成本更低哈希函數(shù)的計算成本很容易被忽略。很多哈希函數(shù)在底層對字符串做了逐字符遍歷字符串越長成本越高。如果能從業(yè)務(wù)上縮短鍵的長度或者把字符串鍵預(yù)編譯成整數(shù) ID 再插入哈希表性能會提升得很明顯。我以前做過一個文本索引系統(tǒng)本來直接用句子做哈希鍵后面改成預(yù)先把句子編號映射為 int ID再用 ID 做哈希鍵查詢速度提升了將近一倍。這類優(yōu)化看著不起眼但在高 QPS 場景下省下來的時間就是實實在在的機(jī)器成本。7.3 多線程環(huán)境下的哈希表使用策略多線程訪問哈希表時最容易出問題因為哈希表的寫操作涉及節(jié)點的申請、鏈表的修改、甚至整個桶數(shù)組的擴(kuò)容。最簡單粗暴的方案就是全局加鎖但這樣并發(fā)度會被鎖拖垮。推薦的做法有幾種一是用讀寫鎖讀多寫少時能提升并發(fā)二是對每個桶獨立加鎖即分段鎖不同桶的讀寫互不干擾三是使用無鎖哈希表高性能但實現(xiàn)難度高適合核心場景。我自己常用的策略是單線程寫、多線程讀。只要保證寫操作完成后再發(fā)布讀請求讀線程可以安全并發(fā)訪問哈希表不需要鎖。這個策略在許多緩存場景里已經(jīng)夠用而且避免了幾乎所有的并發(fā)復(fù)雜度。8. 哈希表學(xué)習(xí)路線與算法面試要點8.1 從零基礎(chǔ)到能手寫哈希表的路徑規(guī)劃如果你是完全零基礎(chǔ)我建議按四條線遞進(jìn)。第一條線先徹底理解數(shù)組和鏈表這是哈希表的左邊基石和右邊基石沒搞懂這兩個數(shù)據(jù)結(jié)構(gòu)就去學(xué)哈希表會一頭霧水。第二條線用 C 手寫一遍鏈地址法哈希表包含插入、查找、刪除、擴(kuò)容四個操作這是第一次真正落地。第三條線用 unordered_map 刷十道左右經(jīng)典題目包括兩數(shù)之和、字母異位詞分組、最長連續(xù)序列、LRU 緩存等目的是把標(biāo)準(zhǔn)和手寫對應(yīng)起來。第四條線研究底層實現(xiàn)和沖突優(yōu)化包括字符串哈希、一致性哈希、布隆過濾器延伸到這個階段你已經(jīng)能獨立設(shè)計哈希相關(guān)的方案了。很多同學(xué)卡在第二步覺得手寫一遍沒必要其實我自己教過的所有人里凡是能不看代碼把插入和刪除邏輯寫出來的面試時聊到哈希表都很有底氣因為他是真懂而不是背結(jié)論。8.2 面試中關(guān)于哈希表的高頻追問面試官問哈希表一般不是讓你背定義而是會連環(huán)追問幾個細(xì)節(jié)負(fù)載因子是什么為什么是 0.75哈希表和紅黑樹各自底層結(jié)構(gòu)和選擇依據(jù)是什么如果讓你設(shè)計一個存一億個 URL 的系統(tǒng)你會怎么優(yōu)化哈希如果哈希沖突很嚴(yán)重你怎么排查和解決回答這些問題的時候思路比標(biāo)準(zhǔn)答案更重要。比如被問到“為什么負(fù)載因子是 0.75”如果只是背出常數(shù)面試官不會覺得很驚艷但如果能順帶提到 0.75 是在時間與空間之間做權(quán)衡的結(jié)果桶數(shù)越密查找越快但浪費(fèi)空間越大桶數(shù)越稀省內(nèi)存但鏈表變長一個合理的負(fù)載因子就是在尋找那個均衡點面試官就會認(rèn)定你是真的理解這個設(shè)計。8.3 推薦刷題清單與場景復(fù)盤我把學(xué)哈希表后適合碰的幾道題列在這里基本覆蓋了哈希表的常見考法兩數(shù)之和最經(jīng)典的“用哈希表記歷史”思路。字母異位詞分組用排序后的詞作為哈希鍵考驗對鍵的設(shè)計。最長連續(xù)序列核心是用哈希表 O(1) 判斷數(shù)字是否存在配合跳躍掃描避免重復(fù)計算。LRU 緩存哈希表加雙向鏈表組合使用最能體現(xiàn)數(shù)據(jù)結(jié)構(gòu)聯(lián)合作戰(zhàn)的能力。找到所有消失的數(shù)字哈希表做標(biāo)記去重。這些題做完一遍你對哈希表的理解就不再停留在原理層面而是真正知道它在實際問題里是怎么用的。以后再看源碼、讀論文、做架構(gòu)選型你心里都有一根哈希表的“標(biāo)尺”知道什么場景適合它什么場景該換別的結(jié)構(gòu)。這就是把基礎(chǔ)打扎實之后帶來的長期復(fù)利。