數(shù)組和鏈表是這個(gè)行業(yè)里最老生常談的數(shù)據(jù)結(jié)構(gòu)也是我在代碼評(píng)審里最愿意花時(shí)間摳細(xì)節(jié)的東西。兩者的核心差異用一句話能說(shuō)清數(shù)組用連續(xù)內(nèi)存換來(lái)了像閃電一樣的隨機(jī)訪問(wèn)鏈表用指針把錢(qián)都花在增刪靈活性上。但“一句話”只適合面試背答案到了真實(shí)項(xiàng)目里你會(huì)發(fā)現(xiàn)很多結(jié)論是反的——鏈表的插入未必快數(shù)組的復(fù)制也未必是罪過(guò)。這篇文章會(huì)把數(shù)組與鏈表的核心差異從結(jié)構(gòu)、性能、內(nèi)存、場(chǎng)景四個(gè)維度完整拆解并給出一套我在若干模擬項(xiàng)目里反復(fù)驗(yàn)證過(guò)的實(shí)戰(zhàn)選型指南。適合剛?cè)胄械拈_(kāi)發(fā)者在做數(shù)據(jù)結(jié)構(gòu)選型時(shí)參考也適合準(zhǔn)備技術(shù)面試、想把這個(gè)經(jīng)典問(wèn)題講透的朋友。1. 先把底賬算清楚數(shù)組和鏈表的結(jié)構(gòu)差異要聊選型不能只停留在“數(shù)組查詢(xún)快、鏈表增刪快”這種口訣層面。先看清楚它們?cè)趦?nèi)存里到底長(zhǎng)什么樣后續(xù)所有性能優(yōu)劣判斷才有依據(jù)。1.1 數(shù)組連續(xù)內(nèi)存和隨機(jī)訪問(wèn)的根源數(shù)組的本質(zhì)是在內(nèi)存里申請(qǐng)一整塊地址連續(xù)的空間每個(gè)元素緊挨著排布。比如定義一個(gè)保存 5 個(gè)整數(shù)的數(shù)組系統(tǒng)會(huì)分配一塊能裝下 5 個(gè)int的內(nèi)存塊元素之間沒(méi)有縫隙。正因?yàn)榈刂愤B續(xù)數(shù)組的隨機(jī)訪問(wèn)才能算得這么快。我訪問(wèn)arr[2]CPU 不需要遍歷前兩個(gè)元素它直接拿數(shù)組首地址base加上偏移量2 * sizeof(int)就能算出目標(biāo)地址。整個(gè)過(guò)程只有一次內(nèi)存訪問(wèn)這就是教科書(shū)里O(1)隨機(jī)訪問(wèn)的根源。int arr[5] {10, 20, 30, 40, 50}; // arr[2] 的地址 數(shù)組首地址 2 * sizeof(int) printf(%d, arr[2]); // 輸出 30這里要特別注意一個(gè)容易混淆的點(diǎn)數(shù)組分為靜態(tài)數(shù)組和動(dòng)態(tài)數(shù)組。靜態(tài)數(shù)組容量固定分配在棧上或者靜態(tài)區(qū)動(dòng)態(tài)數(shù)組則會(huì)在內(nèi)存耗盡時(shí)申請(qǐng)一塊更大的新內(nèi)存把舊元素拷貝過(guò)去再釋放舊空間。我們?nèi)粘Ｓ玫暮芏唷皠?dòng)態(tài)數(shù)組容器”其實(shí)就是后者它仍然屬于數(shù)組的范疇只是把擴(kuò)容的過(guò)程封裝起來(lái)了。后面章節(jié)討論擴(kuò)容成本時(shí)說(shuō)的就是這種動(dòng)態(tài)數(shù)組。連續(xù)內(nèi)存還給數(shù)組帶來(lái)一個(gè)額外的優(yōu)點(diǎn)內(nèi)存占用純粹。每個(gè)元素只保存數(shù)據(jù)本身沒(méi)有額外的指針元數(shù)據(jù)。對(duì)于一個(gè)包含 100 萬(wàn)條用戶(hù)記錄的列表數(shù)組方案會(huì)比同數(shù)據(jù)的鏈表方案節(jié)省大量?jī)?nèi)存這一點(diǎn)在內(nèi)存敏感的場(chǎng)景里特別值錢(qián)。1.2 鏈表指針串聯(lián)帶來(lái)的代價(jià)與便利鏈表的概念也不復(fù)雜把每個(gè)數(shù)據(jù)打包成一個(gè)節(jié)點(diǎn)節(jié)點(diǎn)之間用指針串聯(lián)起來(lái)。單向鏈表每個(gè)節(jié)點(diǎn)只保存一個(gè)next指針雙向鏈表還會(huì)多一個(gè)prev指針循環(huán)鏈表則讓鏈表尾部再次指回頭部。struct Node { int data; // 數(shù)據(jù) struct Node *next; // 指向下一個(gè)節(jié)點(diǎn) }; struct Node *head NULL;鏈表的第一個(gè)問(wèn)題就是內(nèi)存不連續(xù)。節(jié)點(diǎn)可以散落在內(nèi)存中的任意位置它們之間靠地址指針關(guān)聯(lián)。這帶來(lái)一個(gè)直接后果訪問(wèn)第i個(gè)元素沒(méi)有捷徑。我必須從頭指針head出發(fā)沿著next指針一個(gè)一個(gè)走走i步才能拿到目標(biāo)節(jié)點(diǎn)。這就是鏈表隨機(jī)訪問(wèn)是O(n)的原因。那靈活性從哪來(lái)關(guān)鍵在增刪操作。只要我手里拿著某個(gè)節(jié)點(diǎn)的指針要在這個(gè)節(jié)點(diǎn)后面插入一個(gè)新節(jié)點(diǎn)或者把它的后繼節(jié)點(diǎn)摘掉操作只涉及幾個(gè)指針的重新指向其他所有節(jié)點(diǎn)都無(wú)需移動(dòng)。這一步確實(shí)是O(1)的也是鏈表“靈活”這個(gè)標(biāo)簽的真正來(lái)源。但要注意鏈表的每個(gè)節(jié)點(diǎn)都要額外承擔(dān)指針存儲(chǔ)成本。單鏈表每個(gè)節(jié)點(diǎn)多 1 個(gè)指針雙鏈表多 2 個(gè)指針。如果數(shù)據(jù)本身只是一個(gè) 8 字節(jié)的整數(shù)單向鏈表的內(nèi)存開(kāi)銷(xiāo)就直接翻了 1 倍雙向鏈表更是翻了 2 倍。這些看似不起眼的開(kāi)銷(xiāo)在百萬(wàn)級(jí)節(jié)點(diǎn)面前會(huì)變成肉眼可見(jiàn)的巨大差異。2. 速度對(duì)比理論復(fù)雜度和真實(shí)性能差距很多人選鏈表是因?yàn)榭吹浇炭茣?shū)上寫(xiě)著“鏈表插入 O(1)數(shù)組插入 O(n)”于是像抓住救命稻草一樣撲過(guò)去。但復(fù)雜度只是理論上的游戲規(guī)則真實(shí)場(chǎng)景里硬件的緩存、內(nèi)存分配、數(shù)據(jù)規(guī)模都會(huì)改寫(xiě)結(jié)論。這一節(jié)我把兩者放到實(shí)驗(yàn)室里看看到底誰(shuí)快、為什么快。2.1 基礎(chǔ)操作復(fù)雜度的賬面對(duì)比先給一張經(jīng)典的復(fù)雜度對(duì)照表把賬面上的底牌攤開(kāi)操作數(shù)組動(dòng)態(tài)數(shù)組鏈表隨機(jī)訪問(wèn)arr[i]O(1)O(n)從頭部插入O(n)O(1)從尾部插入O(1) 均攤O(1) 需知道尾節(jié)點(diǎn)從中間插入O(n)O(1)前提已經(jīng)定位到位置查找某個(gè)值O(n)O(n)這張表單看沒(méi)問(wèn)題但它特別容易誤導(dǎo)人。比如“從中間插入鏈表 O(1)”這里有個(gè)極其重要的隱藏前提你要么已經(jīng)拿到了插入位置的節(jié)點(diǎn)指針要么定位過(guò)程不算時(shí)間復(fù)雜度。可現(xiàn)實(shí)代碼里絕大多數(shù)插入操作的前置步驟是“先找到那個(gè)位置”而這個(gè)查找動(dòng)作在數(shù)組里是 O(1) 隨機(jī)訪問(wèn)在鏈表里是 O(n) 遍歷。一旦把定位成本算進(jìn)去鏈表從中間插入的總成本往往是 O(n)并沒(méi)有想象中那么神。尾部插入也沒(méi)有全面優(yōu)勢(shì)。數(shù)組尾部追加是均攤 O(1)雖然擴(kuò)容那一刻會(huì)慢但平均下來(lái)非常穩(wěn)定鏈表尾部插入需要知道尾節(jié)點(diǎn)在哪如果不維護(hù)尾指針就得從頭遍歷那就變成 O(n) 了。2.2 硬件視角的真相緩存局部性才是分水嶺復(fù)雜度表沒(méi)有反映出來(lái)的最大變量是 CPU 緩存。計(jì)算機(jī)的內(nèi)存讀取并不是按“元素”一個(gè)個(gè)讀的而是按“緩存行”成塊讀取?，F(xiàn)代 CPU 一次能從內(nèi)存里加載 64 字節(jié)左右的數(shù)據(jù)到高速緩存。數(shù)組元素連續(xù)排列意味著當(dāng)你訪問(wèn)arr[0]時(shí)CPU 順帶把a(bǔ)rr[1]、arr[2]一直到 64 字節(jié)邊界內(nèi)的元素都塞進(jìn)緩存了。后面的循環(huán)訪問(wèn)直接在緩存里命中速度極快。這就是所謂的緩存局部性或者叫空間局部性。鏈表則是另一個(gè)極端。節(jié)點(diǎn)在內(nèi)存里各處散落你訪問(wèn)當(dāng)前節(jié)點(diǎn)node-nextCPU 必須根據(jù)指針地址跑到另一塊內(nèi)存去取而且無(wú)法預(yù)判下一塊內(nèi)存是哪里。每次跳轉(zhuǎn)都可能是一次緩存缺失甚至是一次數(shù)百納秒的內(nèi)存訪問(wèn)。一個(gè)形象的類(lèi)比是數(shù)組就像在連續(xù)書(shū)架上按編號(hào)取書(shū)一次可以抱出好幾本來(lái)鏈表則是按快遞小哥給的地址在城市不同倉(cāng)庫(kù)間來(lái)回奔波每取一件貨都要重新導(dǎo)航一次。我在一個(gè)模擬的系統(tǒng)日志存儲(chǔ)模塊里做過(guò)實(shí)測(cè)數(shù)據(jù)量約 50 萬(wàn)個(gè)日志條目分別用數(shù)組和鏈表做“按時(shí)間順序遍歷”。數(shù)組版本遍歷耗時(shí)大約只有鏈表版本的四分之一到五分之一。原因不在算法復(fù)雜度——兩者遍歷都是 O(n)差距完全來(lái)自緩存命中率。節(jié)點(diǎn)量越大、每條數(shù)據(jù)越大這個(gè)差距還會(huì)更明顯。所以速度博弈的第一準(zhǔn)則如果核心操作是遍歷和隨機(jī)讀取數(shù)組天然占優(yōu)而且優(yōu)勢(shì)會(huì)隨著數(shù)據(jù)規(guī)模擴(kuò)大被放大。3. 靈活性博弈插入、刪除與內(nèi)存管理的取舍“靈活性”這個(gè)詞在鏈表語(yǔ)境里幾乎成了政治正確。但我想先把話挑明靈活的代價(jià)也很高昂。鏈表的靈活性是一種結(jié)構(gòu)性靈活它讓你可以在準(zhǔn) O(1) 時(shí)間內(nèi)改變節(jié)點(diǎn)間的相對(duì)順序但這不代表它在所有增刪場(chǎng)景里都是最佳方案。3.1 中間頻繁增刪先搞清楚你的“定位成本”假設(shè)業(yè)務(wù)要求在一個(gè)大列表中間反復(fù)插入或刪除元素而且數(shù)據(jù)量達(dá)到幾十萬(wàn)。直覺(jué)會(huì)告訴你用鏈表因?yàn)殒湵碓鰟h節(jié)點(diǎn)只要改指針。這個(gè)說(shuō)法沒(méi)錯(cuò)但它忽略了一個(gè)細(xì)節(jié)你每次插入前都必須先遍歷到這個(gè)插入點(diǎn)。鏈表的遍歷是 O(n)數(shù)組的定位是 O(1)但數(shù)組的插入是 O(n)因?yàn)橐嵋坪罄m(xù)元素。兩邊一加總鏈表是“遍歷 O(n) 插入 O(1)”數(shù)組是“定位 O(1) 搬移 O(n)”總復(fù)雜度其實(shí)都是 O(n)。在這個(gè)層面上兩者打平了。但別忘了緩存效應(yīng)數(shù)組搬移元素是一段連續(xù)內(nèi)存的復(fù)制CPU 有專(zhuān)門(mén)的優(yōu)化指令來(lái)加速這種操作鏈表遍歷則是跨內(nèi)存地址的指針追逐。所以實(shí)際工程里在幾萬(wàn)到幾十萬(wàn)量級(jí)的數(shù)據(jù)集上數(shù)組版本往往表現(xiàn)更好甚至比鏈表快一個(gè)量級(jí)。真正能讓鏈表發(fā)揮優(yōu)勢(shì)的場(chǎng)景是那種“錨點(diǎn)明確、局部操作”的場(chǎng)景。典型的例子是 LRU 緩存淘汰算法雙向鏈表維護(hù)數(shù)據(jù)的新鮮度哈希表維護(hù) key 到節(jié)點(diǎn)的映射。當(dāng)一個(gè) key 被訪問(wèn)時(shí)我通過(guò)哈希表 O(1) 找到節(jié)點(diǎn)引用然后把它從鏈表當(dāng)前位置摘下來(lái)、掛到頭部整個(gè)過(guò)程只動(dòng)幾個(gè)指針不需要遍歷。這種“手里已經(jīng)捏著節(jié)點(diǎn)引用”的操作才是鏈表無(wú)可替代的主場(chǎng)。3.2 擴(kuò)容和內(nèi)存碎片數(shù)組的隱藏成本與鏈表的散彈槍數(shù)組也有自己的隱藏成本核心是擴(kuò)容。動(dòng)態(tài)數(shù)組在容量不夠時(shí)會(huì)申請(qǐng)新的、通常是原來(lái)的 1.5 到 2 倍大的內(nèi)存把所有舊元素拷貝過(guò)去再釋放舊內(nèi)存。擴(kuò)容那一刻會(huì)有一個(gè)明顯的性能尖峰但如果平攤到每次插入操作上復(fù)雜度仍是 O(1)。對(duì)于大多數(shù)應(yīng)用來(lái)說(shuō)這個(gè)成本可以接受。更讓人頭疼的是擴(kuò)容引發(fā)的內(nèi)存峰值。在舊數(shù)組和新數(shù)組同時(shí)存在的瞬間內(nèi)存占用會(huì)短暫翻倍。如果數(shù)組本身就占了 1 GB擴(kuò)容時(shí)就需要額外 1 GB 可用內(nèi)存這在內(nèi)存緊張的嵌入式或高并發(fā)服務(wù)里可能是致命的。規(guī)避方法是提前預(yù)留容量用容器的reserve類(lèi)接口在構(gòu)建階段把容量一次到位盡量避免中途反復(fù)擴(kuò)容。鏈表沒(méi)有擴(kuò)容問(wèn)題但它的內(nèi)存碎片問(wèn)題更尖銳。每個(gè)節(jié)點(diǎn)都是一次獨(dú)立的小內(nèi)存分配在頻繁插入刪除的過(guò)程中分配器會(huì)不斷切出各種大小的內(nèi)存塊又不斷釋放最終導(dǎo)致堆內(nèi)存碎片化分配效率下降。而且節(jié)點(diǎn)之間在物理內(nèi)存里排列隨機(jī)不僅緩存不友好對(duì)內(nèi)存管理器的壓力也遠(yuǎn)大于數(shù)組的連續(xù)塊分配。3.3 內(nèi)存開(kāi)銷(xiāo)的對(duì)照表把內(nèi)存層面的差異放在一張表里更直觀維度數(shù)組鏈表數(shù)據(jù)本身占用連續(xù)整塊無(wú)額外元數(shù)據(jù)連續(xù)整塊不分散為節(jié)點(diǎn)每元素額外開(kāi)銷(xiāo)幾乎為零可能預(yù)留少量容量至少一個(gè)指針雙鏈表為兩個(gè)擴(kuò)容/縮容復(fù)制整個(gè)數(shù)組存在峰值每次操作只分配或釋放一個(gè)節(jié)點(diǎn)內(nèi)存布局高度連續(xù)緩存友好隨機(jī)分布緩存不友好碎片風(fēng)險(xiǎn)低高尤其在頻繁增刪時(shí)這張表說(shuō)明了一個(gè)反直覺(jué)的事實(shí)鏈表雖然名字里帶“靈活”但它從不省錢(qián)。它把靈活性成本轉(zhuǎn)嫁到指針存儲(chǔ)、內(nèi)存分配、緩存命中率三個(gè)賬戶(hù)上。數(shù)組的復(fù)制、擴(kuò)容看起來(lái)很笨重但它的內(nèi)存模型簡(jiǎn)單規(guī)整硬件和時(shí)間上都更可控。4. 實(shí)戰(zhàn)選型指南幾個(gè)典型場(chǎng)景下的選擇思路講完原理下面進(jìn)入真正的“實(shí)戰(zhàn)選型”。我按最常見(jiàn)的幾類(lèi)業(yè)務(wù)模式給出選擇建議每類(lèi)都說(shuō)說(shuō)我踩過(guò)的坑和最終結(jié)論。4.1 高頻讀取、構(gòu)建后基本不變無(wú)腦選數(shù)組這類(lèi)場(chǎng)景非常多。系統(tǒng)啟動(dòng)時(shí)加載一份配置表、把傳感器采集的數(shù)據(jù)序列化到內(nèi)存、把一批只讀規(guī)則載入規(guī)則引擎之后運(yùn)行期間幾乎不增刪只做高頻查詢(xún)和遍歷。數(shù)組是毫無(wú)爭(zhēng)議的最優(yōu)選。原因很簡(jiǎn)單連續(xù)內(nèi)存讓遍歷和隨機(jī)訪問(wèn)都快到極致而且沒(méi)有指針元數(shù)據(jù)內(nèi)存利用率最高。再加上這類(lèi)數(shù)據(jù)往往大小固定動(dòng)態(tài)擴(kuò)容根本不會(huì)發(fā)生數(shù)組的隱藏成本也就完全不存在。我做過(guò)一個(gè)模擬的圖片像素讀寫(xiě)模塊像素?cái)?shù)組在初始化后反復(fù)被卷積核遍歷用數(shù)組實(shí)現(xiàn)比鏈表實(shí)現(xiàn)順暢得多代碼也簡(jiǎn)潔得多一段連續(xù)的buffer一個(gè)循環(huán)完事。4.2 頻繁頭部/尾部操作別急著用鏈表先想清楚在哪一端很多人看到“頻繁頭插”就想到鏈表但最終結(jié)論還是要分端口來(lái)看。尾部追加動(dòng)態(tài)數(shù)組是天然贏家。均攤 O(1) 的尾部插入配合連續(xù)內(nèi)存帶來(lái)的緩存優(yōu)勢(shì)往往比鏈表表現(xiàn)更好。實(shí)現(xiàn)一個(gè)棧結(jié)構(gòu)標(biāo)準(zhǔn)庫(kù)提供的動(dòng)態(tài)數(shù)組容器幾乎總是首選。頭部插入鏈表在表面上確實(shí)有優(yōu)勢(shì)因?yàn)閿?shù)組頭插需要把整個(gè)數(shù)組向右搬移。但這里有個(gè)陷阱如果頭插之后很快又會(huì)被整體讀取或遍歷一次數(shù)組雖然頭插慢但讀取時(shí)緩存效率高鏈表頭插快但后續(xù)讀取緩存效率低。誰(shuí)更優(yōu)要實(shí)測(cè)才知道。比較讓我意外的是消息隊(duì)列場(chǎng)景。一個(gè)常見(jiàn)的需求是“尾部進(jìn)頭部出”很多人第一反應(yīng)是設(shè)計(jì)一個(gè)鏈表隊(duì)列。但真實(shí)項(xiàng)目中用環(huán)形數(shù)組才能做到兩端操作都是 O(1)而且內(nèi)存連續(xù)、緩存友好。我在寫(xiě)某個(gè)模擬的異步任務(wù)隊(duì)列時(shí)最開(kāi)始用的鏈表實(shí)現(xiàn)高頻入隊(duì)出隊(duì)導(dǎo)致節(jié)點(diǎn)反復(fù)分配釋放性能瓶頸明顯。換成環(huán)形數(shù)組后隊(duì)列不再每次操作都觸碰內(nèi)存分配器吞吐率提升非?？捎^。所以這里有個(gè)經(jīng)驗(yàn)高頻且端口固定的場(chǎng)景優(yōu)先考慮環(huán)形數(shù)組而不是默認(rèn)鏈表。4.3 既要有隨機(jī)訪問(wèn)又要有頻繁增刪先想清楚能不能轉(zhuǎn)換場(chǎng)景這是最讓人糾結(jié)的一類(lèi)需求。想象一個(gè)在線游戲大廳的玩家列表既要按玩家 ID 快速查找又要支持玩家中途加入或者中途退場(chǎng)。鏈表擅長(zhǎng)增刪數(shù)組擅長(zhǎng)隨機(jī)訪問(wèn)但兩者都滿(mǎn)足不了全部需求。我的建議是先別急著在數(shù)組和鏈表之間二選一而是看能不能引入輔助結(jié)構(gòu)。比如“哈希表 雙向鏈表”的組合用哈希表做 O(1) 定位用雙向鏈表做 O(1) 增刪這就是 LRU 這類(lèi)結(jié)構(gòu)的慣用思路。又比如“數(shù)組 空閑槽位復(fù)用”的方案數(shù)組保存節(jié)點(diǎn)刪除時(shí)只標(biāo)記空閑新插入時(shí)優(yōu)先復(fù)用空閑槽位既保留了數(shù)組的連續(xù)內(nèi)存和隨機(jī)訪問(wèn)又模擬出了鏈表的靈活性。很多底層系統(tǒng)內(nèi)部就是這么干的這比單純爭(zhēng)論數(shù)組好還是鏈表好更有工程價(jià)值。4.4 內(nèi)存受控、節(jié)點(diǎn)數(shù)量波動(dòng)的邊緣場(chǎng)景用池化思維彌補(bǔ)劣勢(shì)嵌入式設(shè)備、網(wǎng)絡(luò)協(xié)議棧這類(lèi)環(huán)境對(duì)內(nèi)存的穩(wěn)定性要求很高不允許隨手malloc一個(gè) 16 字節(jié)的小節(jié)點(diǎn)也不允許數(shù)組隨意擴(kuò)容導(dǎo)致峰值不可控。我見(jiàn)過(guò)的穩(wěn)定實(shí)現(xiàn)往往是“數(shù)組化鏈表”或“節(jié)點(diǎn)池鏈表”預(yù)先分配一大塊連續(xù)內(nèi)存作為節(jié)點(diǎn)池鏈表從池里取節(jié)點(diǎn)刪除時(shí)把節(jié)點(diǎn)還回池里。這樣做的好處是兩全其美節(jié)點(diǎn)地址相對(duì)集中緩存命中率有所提升分配和釋放不觸碰到系統(tǒng)級(jí)的堆管理實(shí)時(shí)性和穩(wěn)定性都大大增強(qiáng)。數(shù)組化鏈表還有個(gè)變種用數(shù)組下標(biāo)代替指針節(jié)點(diǎn)里的next字段存的是下一個(gè)節(jié)點(diǎn)的下標(biāo)而不是內(nèi)存地址序列化和調(diào)試起來(lái)都更友好。所以在邊緣場(chǎng)景里數(shù)據(jù)結(jié)構(gòu)的選型就已經(jīng)不是單純的數(shù)組 vs 鏈表而是向量化、池化、序列化這些維度疊加后的綜合權(quán)衡。5. 常見(jiàn)問(wèn)題與排查技巧實(shí)錄書(shū)本不會(huì)告訴你的那些坑通常都藏在線上事故和調(diào)優(yōu)過(guò)程里。這一節(jié)我把自己這些年遇到的高頻問(wèn)題整理成速查形式。5.1 鏈表越用越慢查一下節(jié)點(diǎn)分配模式一個(gè)很典型的現(xiàn)象代碼剛開(kāi)始跑很快跑了一會(huì)兒就開(kāi)始卡頓。如果你用的是鏈表先懷疑是不是大量小節(jié)點(diǎn)分配導(dǎo)致堆內(nèi)存碎片化。我在某個(gè)模擬的緩存淘汰模塊里就踩過(guò)這個(gè)坑節(jié)點(diǎn)被反復(fù)創(chuàng)建和釋放系統(tǒng)內(nèi)存分配器忙得不可開(kāi)交整體吞吐量掉得很厲害。后來(lái)改成預(yù)先分配節(jié)點(diǎn)池運(yùn)行穩(wěn)定度大幅提升。排查方法也簡(jiǎn)單用內(nèi)存熱點(diǎn)工具看分配曲線或者統(tǒng)計(jì)單位時(shí)間內(nèi)發(fā)生多少次malloc/free。如果單次操作都伴隨一次分配釋放那就該考慮池化或數(shù)組化改造了。5.2 循環(huán)里刪除元素怎么老是漏刪或越界這是數(shù)組和鏈表都會(huì)踩的坑。對(duì)數(shù)組做正向遍歷刪除時(shí)刪除當(dāng)前元素后所有后續(xù)元素都會(huì)前移如果不修正索引下一個(gè)要處理的元素就被跳過(guò)了。正確的寫(xiě)法是刪除后讓循環(huán)變量回退一步。對(duì)鏈表做遍歷刪除也有類(lèi)似問(wèn)題如果你直接釋放當(dāng)前節(jié)點(diǎn)再訪問(wèn)保存好的next指針就會(huì)崩潰。正確做法是先用臨時(shí)變量保存下一個(gè)節(jié)點(diǎn)指針然后再安全釋放當(dāng)前節(jié)點(diǎn)。這塊的細(xì)節(jié)代碼評(píng)審時(shí)我會(huì)格外盯著看。// 數(shù)組遍歷刪除的經(jīng)典錯(cuò)誤寫(xiě)法漏刪 for (int i 0; i n; i) { if (should_remove(arr[i])) { remove_at(arr, i, n); } } // 正確寫(xiě)法刪除后 i-- 回退一位 for (int i 0; i n; i) { if (should_remove(arr[i])) { remove_at(arr, i, n); i--; } }5.3 數(shù)組擴(kuò)容時(shí)的內(nèi)存尖峰怎么壓下去動(dòng)態(tài)數(shù)組擴(kuò)容的瞬間舊數(shù)組和新數(shù)組會(huì)同時(shí)存在內(nèi)存占用可能沖到平時(shí)的兩到三倍。我在一個(gè)模擬的大日志模塊里遇到過(guò)一次數(shù)組里存了幾百萬(wàn)條記錄某次插入觸發(fā)擴(kuò)容內(nèi)存直接飆到接近上限甚至出現(xiàn)過(guò)短暫的停頓。解決方案有兩個(gè)。一個(gè)是在數(shù)據(jù)量可預(yù)估時(shí)提前把容量預(yù)留到位另一個(gè)是設(shè)定合理的擴(kuò)容因子在內(nèi)存和時(shí)間之間取平衡。實(shí)踐中我還發(fā)現(xiàn)如果數(shù)據(jù)是先批量裝載再進(jìn)入運(yùn)行期優(yōu)先選擇一次性構(gòu)建好數(shù)組而不是在運(yùn)行期頻繁觸發(fā)擴(kuò)容這樣最穩(wěn)。5.4 性能比較的正確姿勢(shì)別拿復(fù)雜度當(dāng)結(jié)論做數(shù)組與鏈表性能對(duì)比時(shí)最容易犯的錯(cuò)誤是只看理論復(fù)雜度忽略數(shù)據(jù)規(guī)模和操作分布。比如在 100 個(gè)元素的小數(shù)據(jù)集上比較結(jié)果說(shuō)明不了任何問(wèn)題在 1000 萬(wàn)個(gè)元素上數(shù)組的緩存優(yōu)勢(shì)和鏈表的指針跳躍才會(huì)被充分放大。我的建議是寫(xiě)一個(gè)二十行左右的小基準(zhǔn)測(cè)試把“插入 N 次”“隨機(jī)讀 N 次”“遍歷 N 次”這三個(gè)典型操作分開(kāi)計(jì)時(shí)并且把數(shù)據(jù)規(guī)模設(shè)成 1 萬(wàn)、10 萬(wàn)、100 萬(wàn)三個(gè)檔位。同時(shí)注意預(yù)熱緩存避免把第一次運(yùn)行時(shí)的額外開(kāi)銷(xiāo)算進(jìn)結(jié)果。最終用一個(gè)簡(jiǎn)單的表格把耗時(shí)擺出來(lái)選型結(jié)論會(huì)清晰得多。6. 我的三點(diǎn)選型心得聊到這兒原理和場(chǎng)景都拆得差不多了。最后說(shuō)幾點(diǎn)我個(gè)人的經(jīng)驗(yàn)不保證覆蓋所有情況但至少在重大選擇面前能幫你少走彎路。第一先畫(huà)數(shù)據(jù)訪問(wèn)模式圖。動(dòng)手設(shè)計(jì)前把系統(tǒng)里的核心數(shù)據(jù)結(jié)構(gòu)拿出來(lái)列清楚它的讀多還是寫(xiě)多、隨機(jī)訪問(wèn)多還是順序遍歷多、增刪集中在哪一段、數(shù)據(jù)量級(jí)大概是多少。這些問(wèn)題的答案往往直接指向最終選擇根本不需要糾結(jié)。第二不要迷信任何一方的復(fù)雜度。數(shù)組復(fù)制、鏈表指針跳轉(zhuǎn)這些聽(tīng)起來(lái)很?chē)樔说牟僮髟谡鎸?shí)硬件上的表現(xiàn)經(jīng)常和直覺(jué)相反。只有小步驗(yàn)證才能把理論轉(zhuǎn)化為可靠結(jié)論。我見(jiàn)過(guò)太多人在鏈表和數(shù)組之間反復(fù)橫跳最后靠一個(gè)兩百行的錨點(diǎn)測(cè)試解決了爭(zhēng)執(zhí)。第三數(shù)據(jù)結(jié)構(gòu)從來(lái)不是單選題。很多時(shí)候真正高效的答案是把兩者結(jié)合或者在此基礎(chǔ)上引入哈希表、環(huán)形數(shù)組、節(jié)點(diǎn)池這些額外設(shè)施。數(shù)組和鏈表只是工具箱里的兩把錘子工程人員更重要的是判斷敲哪顆釘子、怎么敲。我的體會(huì)是把數(shù)據(jù)結(jié)構(gòu)選型的功夫花在理解業(yè)務(wù)和測(cè)量數(shù)據(jù)上比背一百道面試題都管用。