很多人在學(xué)數(shù)據(jù)結(jié)構(gòu)的時(shí)候會(huì)把查找這一章當(dāng)成一堆零散算法的集合順序查找、折半查找、哈希、二叉排序樹……背完ASL公式就扔到一邊。但我在實(shí)際做開(kāi)發(fā)之后回頭看這一章恰恰是全書最容易和工程經(jīng)驗(yàn)掛鉤的地方——你寫的每一條SQL、每一次Map.get()、每一個(gè)索引設(shè)計(jì)本質(zhì)上都在做查找。這篇文章我想把第7章的脈絡(luò)重新捋一遍不只是講怎么做題也想講清楚這些算法為什么這么設(shè)計(jì)真實(shí)項(xiàng)目里應(yīng)該怎么選最后還會(huì)補(bǔ)上一些教材不寫、但你在代碼里遲早會(huì)踩的坑。1. 先從根上理解查找考的不是找是數(shù)據(jù)怎么組織1.1 最小模型關(guān)鍵字、記錄與命中任何查找問(wèn)題都可以抽成一個(gè)非常樸素的三件套一堆數(shù)據(jù)、一條目標(biāo)記錄、一個(gè)用來(lái)判斷是不是它的關(guān)鍵字。數(shù)據(jù)怎么擺、關(guān)鍵字怎么比決定了查找是快還是慢。舉個(gè)例子你現(xiàn)在有一張兩萬(wàn)行的用戶表想查出某個(gè)用戶名對(duì)應(yīng)的注冊(cè)時(shí)間。最直觀的辦法是從頭到尾逐條比對(duì)運(yùn)氣好第一條就命中運(yùn)氣差要掃完兩萬(wàn)條。當(dāng)數(shù)據(jù)量漲到兩千萬(wàn)條時(shí)這個(gè)挨個(gè)找的方案就要掃幾千萬(wàn)次響應(yīng)時(shí)間立刻變得不可接受。此時(shí)你是去優(yōu)化比較次數(shù)還是去換一種數(shù)據(jù)組織方式答案是后者這才是查找章節(jié)真正要教的東西同樣的數(shù)據(jù)換一種存放方式查找的性能可以差出幾個(gè)數(shù)量級(jí)。只有把查找抽象成這樣一個(gè)模型你才能繼續(xù)往下談平均查找長(zhǎng)度、談不同結(jié)構(gòu)之間的優(yōu)劣。沒(méi)有這個(gè)抽象后面所有復(fù)雜算法的動(dòng)機(jī)都不成立。1.2 平均查找長(zhǎng)度是照妖鏡衡量查找算法最核心的指標(biāo)叫平均查找長(zhǎng)度ASLAverage Search Length定義為查找過(guò)程中關(guān)鍵字比較次數(shù)的期望值分為查找成功和查找失敗兩種?？荚囈闼鉇SL工程上你要估算接口耗時(shí)本質(zhì)上用的是同一套方法。舉個(gè)例子順序查找在等概率的情況下成功查找的平均比較次數(shù)是 (n1)/2。這個(gè)公式怎么來(lái)的一條一條找第1條需要1次比較第2條需要2次……第n條需要n次加起來(lái)除以n正好是(n1)/2。而失敗查找就比較慘烈了你得完整掃完整個(gè)表才能確認(rèn)不存在所以要比較n1次。很多人在算ASL時(shí)會(huì)把成功和失敗混在一起這是做這章題目最冤枉的丟分點(diǎn)成功ASL和失敗ASL針對(duì)的是兩種不同的查找過(guò)程分母也不一定一樣。成功ASL的分母是表中實(shí)際存在的記錄數(shù)失敗ASL的分母是可能失敗的位置數(shù)這個(gè)概念在后面哈希表部分尤其重要。1.3 三種基本存儲(chǔ)形態(tài)決定了三類查找策略數(shù)據(jù)在物理上怎么組織直接決定了你能用哪種查找方法。大致可以分成三條路線順序表數(shù)據(jù)連續(xù)存放在內(nèi)存里支持隨機(jī)訪問(wèn)。正因?yàn)槟躉(1)地跳到任意下標(biāo)折半查找這種需要跳來(lái)跳去的算法才成立。鏈表只能順著指針走。不管你怎么折騰想找中間元素必須從頭遍歷所以鏈表上談?wù)郯氩檎一臼菬o(wú)稽之談。散列/索引結(jié)構(gòu)數(shù)據(jù)與存儲(chǔ)位置之間建立一個(gè)映射函數(shù)目標(biāo)是直接算出位置一步到位。后面的內(nèi)容全部圍繞這三條路線展開(kāi)。每當(dāng)你看到一道查找題先別急著套算法先問(wèn)自己一句數(shù)據(jù)現(xiàn)在是以什么形式存在的這個(gè)前提直接決定答案。2. 線性結(jié)構(gòu)上的查找順序、折半與分塊2.1 順序查找不要小看挨個(gè)找順序查找是所有查找算法里最沒(méi)有智商的方案但從工程角度看它有一個(gè)其他算法都比不了的優(yōu)勢(shì)對(duì)數(shù)據(jù)組織沒(méi)有任何額外要求。數(shù)組能找鏈表也能找有序行無(wú)序也行甚至你只有一張正在源源不斷追加數(shù)據(jù)的日志表沒(méi)法建索引、沒(méi)法排序那順序掃描就是唯一選擇。它的成功ASL是(n1)/2失敗ASL是n1時(shí)間復(fù)雜度O(n)。表面上看這是一個(gè)慢的算法但慢不等于沒(méi)用。很多分布式的日志檢索、數(shù)據(jù)倉(cāng)庫(kù)的全表掃描底層就是順序查找的思路——因?yàn)闆](méi)法對(duì)全量數(shù)據(jù)提前維護(hù)索引只能靠并行掃描一堆數(shù)據(jù)分片來(lái)把時(shí)間壓下來(lái)。所以不要帶著鄙視鏈看順序查找它是兜底方案是所有更優(yōu)方案的比較基準(zhǔn)。在實(shí)際寫代碼時(shí)順序查找還有一個(gè)容易忽略的優(yōu)化把目標(biāo)關(guān)鍵字當(dāng)作哨兵放在表的末尾這樣每次循環(huán)都不需要額外判斷下標(biāo)是否越界比較次數(shù)沒(méi)變但分支減少了數(shù)據(jù)量大時(shí)也能省下不少時(shí)間。這種小技巧在算法競(jìng)賽和底層庫(kù)實(shí)現(xiàn)里很常見(jiàn)是典型不求復(fù)雜度變好、只求常數(shù)變小的思路。2.2 折半查找O(log n)的前提條件與邊界魔鬼折半查找也叫二分查找是線性結(jié)構(gòu)查找里最重要的一個(gè)算法。它有一個(gè)硬性前提數(shù)據(jù)必須存儲(chǔ)在順序表上并且按關(guān)鍵字有序。存儲(chǔ)前提前面說(shuō)過(guò)支持隨機(jī)訪問(wèn)才能跳。有序前提則是二分策略正確性的根基。它的核心思想是每次把查找區(qū)間切成兩半用中間位置的關(guān)鍵字和目標(biāo)比小了去左半邊大了去右半邊。理想情況下每次排除一半的數(shù)據(jù)復(fù)雜度O(log n)n100萬(wàn)時(shí)最多比較20次比順序查找的50萬(wàn)次平均比較有數(shù)量級(jí)的優(yōu)勢(shì)。把查找過(guò)程畫成二叉樹你會(huì)看到一棵判定樹樹的高度就是最大比較次數(shù)。比如7個(gè)有序元素的判定樹第一層1個(gè)結(jié)點(diǎn)第二層2個(gè)第三層4個(gè)樹高3層成功ASL(1×12×24×3)/717/7≈2.43。這個(gè)值和log2(8)-12非常接近說(shuō)明二分查找確實(shí)把比較次數(shù)壓到了對(duì)數(shù)級(jí)別。但二分查找的代碼非常容易寫錯(cuò)我見(jiàn)過(guò)太多人在邊界條件上翻車。這里必須說(shuō)幾個(gè)關(guān)鍵點(diǎn)循環(huán)條件用low high退出時(shí)low和high的交叉位置就是目標(biāo)應(yīng)該插入的位置計(jì)算中間點(diǎn)要用low (high - low) / 2不要用(low high) / 2因?yàn)閮蓚€(gè)大整數(shù)相加可能溢出每次移動(dòng)邊界時(shí)low mid 1或high mid - 1而不是low mid否則會(huì)出現(xiàn)死循環(huán)。我個(gè)人的習(xí)慣是先寫出判定樹在心里過(guò)一遍mid取到哪里、數(shù)組下標(biāo)是否越界再寫循環(huán)。這個(gè)習(xí)慣幫我擋掉過(guò)很多次線上事故。2.3 分塊查找靜態(tài)數(shù)據(jù)里的折中方案分塊查找索引順序查找是順序查找和折半查找之間的一個(gè)折中方案把數(shù)據(jù)分成若干塊塊與塊之間按最大值有序塊內(nèi)可以完全無(wú)序。另外維護(hù)一個(gè)索引表記錄每塊的最大關(guān)鍵字和塊的起始位置。查找過(guò)程分兩步先在索引表里定位目標(biāo)可能存在的塊這一步可以用順序查找也可以對(duì)索引表做二分再在塊內(nèi)做順序查找。比如n9分成3塊每塊3個(gè)元素索引表用順序查找時(shí)成功ASL(31)/2(31)/24如果索引表用二分查找塊間部分會(huì)降到約1.6整體ASL約3.6。分塊查找最大的價(jià)值在于它引入了索引的概念建立一個(gè)規(guī)模較小的索引結(jié)構(gòu)先查索引縮小范圍再深入數(shù)據(jù)本身。數(shù)據(jù)庫(kù)的聚簇索引、文件系統(tǒng)的多級(jí)目錄玩的都是這個(gè)思路。理解分塊查找你就理解了為什么加一層索引能解決很多性能問(wèn)題。它犧牲了額外的索引存儲(chǔ)空間換來(lái)比全表掃描低得多的查找成本。3. 哈希查找空間換時(shí)間的極致也是選擇題的重災(zāi)區(qū)3.1 散列函數(shù)均勻、快速、少?zèng)_突哈希散列查找的核心思想是算不是找通過(guò)一個(gè)散列函數(shù)把關(guān)鍵字直接映射成存儲(chǔ)地址。理想情況下你要查的元素存在哪個(gè)位置一算便知時(shí)間復(fù)雜度接近O(1)。散列函數(shù)常見(jiàn)的設(shè)計(jì)方法有直接定址法、除留余數(shù)法、數(shù)字分析法、平方取中法等?？荚?yán)锍霈F(xiàn)頻率最高的是除留余數(shù)法H(key) key % p其中p是一個(gè)不大于哈希表長(zhǎng)m的質(zhì)數(shù)或素?cái)?shù)。為什么強(qiáng)調(diào)p要選質(zhì)數(shù)假設(shè)表長(zhǎng)是10關(guān)鍵字全是10的倍數(shù)那無(wú)論除幾結(jié)果都擠在0上沖突會(huì)非常嚴(yán)重。選質(zhì)數(shù)就是為了盡量避免這種由于關(guān)鍵字分布規(guī)律帶來(lái)的成族沖突。一個(gè)合格的散列函數(shù)要滿足三件事均勻各位置被映射到的概率盡量一致、快速函數(shù)計(jì)算本身不能太復(fù)雜、少?zèng)_突不同關(guān)鍵字盡量映射到不同位置。但少?zèng)_突是理想實(shí)際中沖突不可能完全避免所以下一節(jié)的內(nèi)容就來(lái)了。3.2 處理沖突線性探測(cè)、平方探測(cè)與鏈地址法的取舍當(dāng)兩個(gè)關(guān)鍵字算出同一個(gè)地址時(shí)就需要處理沖突。教材里給的方法主要分兩類開(kāi)放定址法的思路是沖突了那就往下一個(gè)空閑位置放。具體又分線性探測(cè)法、平方探測(cè)法二次探測(cè)法和偽隨機(jī)探測(cè)法。線性探測(cè)沖突后依次探測(cè)下一個(gè)位置(H(key)i) % mi1,2,3,...。問(wèn)題非常明顯——容易產(chǎn)生聚集現(xiàn)象一旦某一段被占滿后續(xù)的關(guān)鍵字會(huì)像排隊(duì)一樣擠在一起查找失敗的代價(jià)大幅上升。平方探測(cè)探測(cè)序列變成(H(key) i^2) % m能有效緩解線性探測(cè)的聚集問(wèn)題但有個(gè)前提表長(zhǎng)必須取適合的質(zhì)數(shù)否則可能探測(cè)不全所有位置。鏈地址法則簡(jiǎn)單粗暴每個(gè)哈希表位置不存數(shù)據(jù)而是存一條鏈表的頭指針沖突的元素鏈在后面。查找時(shí)要沿著鏈表往后掃但每個(gè)鏈子通常都很短所以整體仍然很快。工程上最常用的是鏈地址法的變體——每個(gè)桶放一個(gè)鏈表鏈表過(guò)長(zhǎng)時(shí)再升級(jí)為樹結(jié)構(gòu)這是很多哈希表實(shí)現(xiàn)處理極端沖突的辦法。鏈地址法還有一個(gè)好處刪除元素特別方便直接把結(jié)點(diǎn)從鏈表里摘掉就行。而開(kāi)放定址法刪除時(shí)要小心不能直接置空否則會(huì)把后面探測(cè)路徑中斷掉通常得打一個(gè)已刪除標(biāo)記。這一點(diǎn)我在紙上推演時(shí)覺(jué)得無(wú)所謂寫代碼才發(fā)現(xiàn)非常煩人。3.3 裝填因子α才是哈希的命門開(kāi)始講哈希表時(shí)很多人誤以為沖突處理方式?jīng)Q定了性能上限其實(shí)真正決定哈希查找性能的是一個(gè)看似不起眼的參數(shù)裝填因子 α 表中記錄數(shù) / 表長(zhǎng)。為什么說(shuō)它是命門因?yàn)楣１淼腁SL并不直接依賴記錄數(shù)n而是依賴α。α越大表越滿沖突概率越高查找代價(jià)上升α越小表越空沖突少但空間浪費(fèi)嚴(yán)重。教材給過(guò)線性探測(cè)法成功查找的近似ASL1/2 * (1 1/(1-α))鏈地址法成功查找的近似ASL1 α/2。你把這個(gè)近似公式帶進(jìn)去算一下就會(huì)發(fā)現(xiàn)同樣是鏈地址法α從0.5漲到0.9ASL從1.25漲到1.45其實(shí)還能接受但線性探測(cè)在α接近0.9時(shí)已經(jīng)明顯惡化了。所以工程上的哈希表基本都會(huì)做一件事擴(kuò)容。當(dāng)α超過(guò)某個(gè)閾值常見(jiàn)的是0.75就把表擴(kuò)大一倍把所有元素重新散列一遍。很多人對(duì)擴(kuò)容有疑慮擴(kuò)容要重新插入所有元素那不是O(n)嗎沒(méi)錯(cuò)但均攤到每次插入上代價(jià)仍然很低。這是理解哈希表工程實(shí)現(xiàn)的關(guān)鍵。3.4 一個(gè)典型題目的完整ASL計(jì)算光說(shuō)公式容易虛我們算一道比較典型的題目。設(shè)關(guān)鍵字序列為{19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}表長(zhǎng)m13散列函數(shù)H(key)key%13用線性探測(cè)法處理沖突計(jì)算查找成功時(shí)的ASL。先把每個(gè)關(guān)鍵字的散列地址算出來(lái)然后逐個(gè)插入19%136無(wú)沖突比較1次14%131無(wú)沖突比較1次23%1310無(wú)沖突比較1次1%131沖突線性探測(cè)到2比較2次68%133無(wú)沖突比較1次20%137無(wú)沖突比較1次84%136沖突探測(cè)到7被20占、8比較3次27%131依次探測(cè)2、3、4比較4次55%133依次探測(cè)4、5比較3次11%1311無(wú)沖突比較1次10%1310沖突探測(cè)11被11占、12比較3次79%131依次探測(cè)2到9比較9次。成功找完所有12個(gè)關(guān)鍵字的總比較次數(shù)是 11121134313930成功ASL30/122.5。你可以對(duì)比一下如果數(shù)據(jù)能均勻散列每個(gè)關(guān)鍵字都在自己的初始地址上ASL就是1因?yàn)闆_突平均代價(jià)到了2.5。這個(gè)例子同時(shí)演示了兩個(gè)關(guān)鍵意識(shí)先算初始地址、再模擬探測(cè)過(guò)程每個(gè)關(guān)鍵字的比較次數(shù)是從它的初始位置出發(fā)到實(shí)際落位所經(jīng)歷的探測(cè)步數(shù)。4. 樹形查找讓動(dòng)態(tài)數(shù)據(jù)集保持有序且平衡4.1 二叉排序樹插入、查找、刪除全流程二叉排序樹BST的核心定義很簡(jiǎn)單左子樹所有結(jié)點(diǎn)的關(guān)鍵字小于根結(jié)點(diǎn)右子樹所有結(jié)點(diǎn)的關(guān)鍵字大于根結(jié)點(diǎn)且左右子樹也分別是二叉排序樹。這個(gè)結(jié)構(gòu)有個(gè)特性——中序遍歷得到一個(gè)升序序列所以它本質(zhì)上是一個(gè)動(dòng)態(tài)維護(hù)有序集的工具。插入操作不復(fù)雜從根開(kāi)始比當(dāng)前結(jié)點(diǎn)小就往左走大就往右走走到空位就掛上新結(jié)點(diǎn)。查找同理。真正麻煩的是刪除分三種情況刪除葉子結(jié)點(diǎn)直接摘掉不影響樹結(jié)構(gòu)刪除只有一個(gè)孩子的結(jié)點(diǎn)讓孩子頂替自己的位置刪除有兩個(gè)孩子的結(jié)點(diǎn)這是最關(guān)鍵的場(chǎng)景通常用它的直接前驅(qū)或直接后繼來(lái)替換它。直接后繼就是右子樹中最小的結(jié)點(diǎn)也就是右子樹一路向左走到最底部的那個(gè)節(jié)點(diǎn)直接前驅(qū)是左子樹中最大的結(jié)點(diǎn)即左子樹一路向右走到最底部的節(jié)點(diǎn)。為什么必須用前驅(qū)/后繼替換因?yàn)橹挥羞@樣才能保持左小右大的性質(zhì)不被破壞。稍微練過(guò)一道題就會(huì)發(fā)現(xiàn)很多人在這一步忘記替換后要遞歸處理前驅(qū)/后繼的刪除導(dǎo)致樹中出現(xiàn)重復(fù)結(jié)點(diǎn)或者丟失子樹。BST的致命弱點(diǎn)是它可能長(zhǎng)歪。如果按有序序列依次插入BST會(huì)退化成一條鏈表查找復(fù)雜度從O(log n)惡化到O(n)。這也是AVL樹、紅黑樹這些平衡結(jié)構(gòu)存在的根本原因。4.2 AVL平衡調(diào)整LL、RR、LR、RL的識(shí)別和旋轉(zhuǎn)AVL樹給BST加了一個(gè)平衡條件任意結(jié)點(diǎn)的左、右子樹高度差絕對(duì)值不超過(guò)1這個(gè)高度差稱為平衡因子。一旦某次插入后打破了平衡就需要通過(guò)旋轉(zhuǎn)來(lái)恢復(fù)。四種失衡情況必須熟練掌握只看名字也能猜個(gè)大概LL型插到了某個(gè)失衡結(jié)點(diǎn)的左孩子的左子樹。解決辦法是右旋一次把左孩子提上來(lái)當(dāng)根。RR型插到了右孩子的右子樹。解決辦法是左旋一次。LR型插到了左孩子的右子樹。先對(duì)左孩子做一次左旋把它變成LL型再對(duì)失衡結(jié)點(diǎn)做一次右旋。RL型插到了右孩子的左子樹。先對(duì)右孩子做一次右旋再對(duì)失衡結(jié)點(diǎn)做一次左旋。每次旋轉(zhuǎn)后要重新計(jì)算涉及的幾個(gè)結(jié)點(diǎn)的平衡因子。這里我說(shuō)一個(gè)容易讓人暈的地方旋轉(zhuǎn)操作只改變局部位置不會(huì)破壞BST的左小右大性質(zhì)。因?yàn)樾D(zhuǎn)的本質(zhì)是把孩子提上來(lái)、自己退下去所有子樹的相對(duì)大小關(guān)系不變。做題時(shí)如果你覺(jué)得旋轉(zhuǎn)后順序亂了多半是把誰(shuí)左誰(shuí)右搞混了可以拿三個(gè)結(jié)點(diǎn)畫一張小圖驗(yàn)證。含n個(gè)結(jié)點(diǎn)的AVL樹最大深度約1.44log2(n2)近似公式。這意味著AVL的查找復(fù)雜度能穩(wěn)定保證在O(log n)。但代價(jià)是插入和刪除時(shí)可能需要多次旋轉(zhuǎn)所以AVL一般用于查找頻率遠(yuǎn)高于插入刪除的場(chǎng)景。而紅黑樹放寬了平衡限制插入刪除代價(jià)更低因此被大量用在通用容器的底層實(shí)現(xiàn)里。4.3 從內(nèi)存到磁盤為什么大場(chǎng)面需要B樹和B樹AVL和BST解決的是內(nèi)存場(chǎng)景的問(wèn)題但數(shù)據(jù)量一旦大到要放磁盤問(wèn)題就變了。磁盤訪問(wèn)一次的時(shí)間大概是內(nèi)存訪問(wèn)的幾十萬(wàn)倍所以你必須把比較次數(shù)換成磁盤訪問(wèn)次數(shù)來(lái)優(yōu)化。B樹和B樹就是為這個(gè)場(chǎng)景設(shè)計(jì)的多路平衡查找樹。先看B樹的幾個(gè)硬性規(guī)定設(shè)階數(shù)為m每個(gè)結(jié)點(diǎn)最多有m棵子樹、m-1個(gè)關(guān)鍵字根結(jié)點(diǎn)至少有兩棵子樹除根以外所有非葉結(jié)點(diǎn)的子樹個(gè)數(shù)至少是?m/2?意思是每個(gè)結(jié)點(diǎn)最少半滿所有葉子結(jié)點(diǎn)在同一層保證樹高絕對(duì)平衡。因?yàn)橐粋€(gè)結(jié)點(diǎn)能裝很多關(guān)鍵字B樹的樹高遠(yuǎn)低于BST。假設(shè)一個(gè)磁盤頁(yè)能存幾百個(gè)關(guān)鍵字幾百萬(wàn)條數(shù)據(jù)可能只要三四層的樹就能索引完每次查找只讀幾次磁盤這是BST做不到的。B樹在B樹基礎(chǔ)上做了兩處關(guān)鍵改動(dòng)內(nèi)部結(jié)點(diǎn)不保存記錄數(shù)據(jù)只做索引所有關(guān)鍵字和數(shù)據(jù)都落在葉子結(jié)點(diǎn)上并且葉子結(jié)點(diǎn)用指針鏈成有序鏈表。這兩個(gè)改動(dòng)帶來(lái)三個(gè)好處內(nèi)部結(jié)點(diǎn)能存更多關(guān)鍵字進(jìn)一步降低樹高范圍查詢非常自然——從最小關(guān)鍵字順著葉子鏈表往后掃即可不需要反復(fù)回溯到上層所有查找都必須走到葉子結(jié)點(diǎn)每次查找的路徑長(zhǎng)度穩(wěn)定更利于預(yù)測(cè)IO開(kāi)銷。所以在真實(shí)的數(shù)據(jù)庫(kù)索引、文件系統(tǒng)索引里B樹幾乎是標(biāo)配。你說(shuō)它是查找章節(jié)的盡頭也不為過(guò)從線性表到哈希再到平衡樹、B樹這條線就是如何在大規(guī)模數(shù)據(jù)上快速定位這個(gè)問(wèn)題的完整答案鏈。5. 實(shí)際項(xiàng)目中的查找選型復(fù)雜度之外的教訓(xùn)5.1 不同場(chǎng)景的算法選型速查學(xué)了這么多算法落到實(shí)際項(xiàng)目里該怎么選我先給一張我常用的速查表它比任何概念都直接場(chǎng)景特征推薦方案理由數(shù)據(jù)量小、幾乎不變、無(wú)隨機(jī)訪問(wèn)需求順序查找實(shí)現(xiàn)簡(jiǎn)單無(wú)額外空間靜態(tài)數(shù)據(jù)、可排序、支持隨機(jī)訪問(wèn)折半查找查得快無(wú)鏈?zhǔn)浇Y(jié)構(gòu)也能用大量靜態(tài)數(shù)據(jù)、需要范圍查詢B樹索引磁盤IO友好范圍查詢順暢高頻精確查找、內(nèi)存容量允許哈希表平均O(1)但注意擴(kuò)容和控制α數(shù)據(jù)動(dòng)態(tài)插入刪除、保持有序遍歷平衡樹AVL/紅黑樹有序性保持得好范圍遍歷方便緩存淘汰、排行榜等特殊場(chǎng)景哈希鏈表組合兼顧O(1)定位和順序維護(hù)注意這張表有一列很容易被人忽略空間成本。哈希需要額外的桶和可能的內(nèi)存浪費(fèi)B樹需要大量索引結(jié)點(diǎn)折半查找則完全不需要額外內(nèi)存。如果你的數(shù)據(jù)量小到可以在內(nèi)存里全量裝下但內(nèi)存又很緊張那一個(gè)有序數(shù)組加二分查找往往比你去搞一棵樹和一個(gè)哈希表更劃算。5.2 工程實(shí)現(xiàn)里那些教材沒(méi)寫的細(xì)節(jié)教材教算法但工程里寫代碼會(huì)遇到很多教材不會(huì)提的細(xì)枝末節(jié)。我挑幾個(gè)印象最深的第一個(gè)是哈希函數(shù)的輸入類型問(wèn)題。很多教材只討論整數(shù)關(guān)鍵字但真實(shí)項(xiàng)目里關(guān)鍵字經(jīng)常是字符串、復(fù)合對(duì)象。你會(huì)遇到一個(gè)很現(xiàn)實(shí)的問(wèn)題直接把字符串的hashCode拿來(lái)用分布很可能不理想。這時(shí)候要給散列函數(shù)補(bǔ)一些位運(yùn)算把高位信息混到低位里否則哈希表的很多桶可能是空的而另一些桶擠成一堆裝填因子明明不高性能卻已經(jīng)爛了。第二個(gè)是二分查找的適用場(chǎng)景比想象中窄。工程上索引結(jié)構(gòu)大多是B樹或者哈希表很少有人手動(dòng)搞二分查找因?yàn)榫S護(hù)一個(gè)動(dòng)態(tài)有序數(shù)組的代價(jià)太高。但反過(guò)來(lái)在一次性加載全部配置、運(yùn)行期只讀這種場(chǎng)景里有序數(shù)組加二分查找的性能不但優(yōu)秀而且內(nèi)存效率極高。我見(jiàn)過(guò)某個(gè)配置服務(wù)就是這么干的啟動(dòng)時(shí)加載幾千條配置排序一次之后每次查找都是log級(jí)別的耗時(shí)比拍腦袋上一套緩存簡(jiǎn)單多了。第三個(gè)是擴(kuò)容和抖動(dòng)問(wèn)題。哈希表擴(kuò)容在并發(fā)場(chǎng)景下特別容易出問(wèn)題——擴(kuò)容過(guò)程中所有線程都嘗試rehash如果沒(méi)處理好輕則性能劇烈波動(dòng)重則數(shù)據(jù)錯(cuò)亂。這也是為什么真實(shí)系統(tǒng)里哈希表要么做分段、要么在擴(kuò)容時(shí)加鎖。這類工程細(xì)節(jié)教材不會(huì)考但做線上系統(tǒng)一定會(huì)遇到。5.3 高流量場(chǎng)景下哈希表劣化的真實(shí)經(jīng)歷最后講一個(gè)我印象很深的排查經(jīng)歷。某次接手一個(gè)內(nèi)部查詢服務(wù)接口平時(shí)響應(yīng)都是個(gè)位數(shù)毫秒某天突然有人反饋某些key的查詢要幾百毫秒甚至超時(shí)。一開(kāi)始我以為是數(shù)據(jù)量漲了導(dǎo)致機(jī)器扛不住看了監(jiān)控發(fā)現(xiàn)CPU不高、內(nèi)存也充足非常詭異。后來(lái)把調(diào)用鏈打成火焰圖才發(fā)現(xiàn)熱點(diǎn)全在哈希表里——不是哈希表本身慢了而是某個(gè)類別下的key數(shù)量特別大且它們的散列結(jié)果高度集中在少數(shù)的桶里。當(dāng)桶里的鏈表變得很長(zhǎng)查找從O(1)退化成了O(n)。那時(shí)候才意識(shí)到教科書里講的沖突極端情況不是理論是真實(shí)會(huì)在生產(chǎn)環(huán)境出現(xiàn)的。后續(xù)的修復(fù)方案也不難換一個(gè)分布更均勻的散列函數(shù)同時(shí)給底層哈希表加上桶內(nèi)元素超過(guò)閾值時(shí)自動(dòng)轉(zhuǎn)為樹結(jié)構(gòu)的機(jī)制。修復(fù)之后那些極端key的查詢時(shí)間立刻降了下來(lái)。這件事給我的教訓(xùn)是學(xué)查找算法時(shí)公式要背但更重要的是建立起數(shù)據(jù)結(jié)構(gòu)決定性能上限的敏感度。當(dāng)系統(tǒng)出現(xiàn)莫名性能問(wèn)題時(shí)最先懷疑的往往不是機(jī)器而是數(shù)據(jù)組織方式?；仡^再看第7章你會(huì)發(fā)現(xiàn)這一章的每一節(jié)都不是孤立的。順序查找是最樸素的基線分塊查找引入了索引思想哈希利用散列函數(shù)把定位變成計(jì)算BST和AVL讓動(dòng)態(tài)數(shù)據(jù)保持有序B樹把這一切擴(kuò)展到海量數(shù)據(jù)和磁盤場(chǎng)景。每套方案都有自己的適用邊界沒(méi)有銀彈。能把選型時(shí)知道自己在為什么買單這層功夫練出來(lái)這一章才算真正學(xué)會(huì)了。