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