數(shù)組這個知識點放在教科書里永遠是“基礎(chǔ)中的基礎(chǔ)”但真到了業(yè)務(wù)代碼里它反而是線上事故率最高的元兇之一。我最近接手一個訂單模塊的活跑批結(jié)果對不上從上午排查到下午最后定位到根因就是初始化一個二維數(shù)組時把行的引用復(fù)制錯了。這種經(jīng)歷多了以后我對“數(shù)組易錯點”這件事有了一個自己的判斷標準寫過半年代碼的人通常都會說自己數(shù)組很熟但你要是問他數(shù)組都踩過哪些坑他反而會卡住。這說明大多數(shù)人掌握的是語法不是陷阱。這篇內(nèi)容我想把自己在C、C、Java、JavaScript、Python這些語言里遇到的數(shù)組高頻坑完整梳理一遍重點是“為什么錯”“錯在哪一步”“怎么一眼看出來”適合正在寫業(yè)務(wù)代碼的工程師也適合準備面試、刷題時總被數(shù)組邊界和引用問題搞暈的同學(xué)。1. 索引與邊界的“差一錯誤”數(shù)組最容易翻車的地方數(shù)組的索引邊界問題在所有易錯點里屬于出場率最高的那類。很多人第一次接觸數(shù)組時記住的是“下標從0開始”但真正寫起代碼來腦子里還是會不自覺地認為“第N個元素”等于下標N。這個認知偏差導(dǎo)致的后果就是經(jīng)典的off-by-one錯誤多循環(huán)了一次或者少取了一個元素而且這類Bug在測試階段往往跑不出來只在數(shù)據(jù)量變化或邊界條件下突然爆發(fā)。1.1 循環(huán)邊界判斷為什么 i n 會越界先看一段最典型的錯誤代碼這個寫法在C語言里幾乎人人都寫過一版int arr[10]; for (int i 0; i 10; i) { arr[i] i; }數(shù)組arr的合法下標范圍是0到9一共10個元素。循環(huán)條件寫成i 10后i會一路加到10于是第11次循環(huán)寫入arr[10]這一步越界了。C語言不會主動提醒你越界它只是去訪問數(shù)組后面那塊內(nèi)存至于那塊內(nèi)存里存的是什么全看運氣。在某些編譯器布局下越界寫入可能會覆蓋相鄰變量的值表現(xiàn)出來就是“某個變量莫名其妙變了”在另一些場景下越界讀會把數(shù)組后面一段垃圾數(shù)據(jù)讀出來表現(xiàn)為“結(jié)果忽大忽小”。這個問題的根源是“長度”和“最后一個下標”兩個概念被混為一談。一個長度為n的數(shù)組合法下標的閉區(qū)間是[0, n-1]。循環(huán)變量要從0走到n-1所以條件應(yīng)該是i n不是i n-1雖然兩者等價但i n更符合思維習(xí)慣。我后來給自己定了一條規(guī)則寫循環(huán)時先問“我要循環(huán)多少次”然后直接寫成i 次數(shù)不搞任何等價變換越簡單越不容易錯。Python里也有類似的情況。很多人用range寫數(shù)組索引時會糾結(jié)range(0, n)和range(0, n-1)哪個對。這里記住range的右邊界是開區(qū)間就夠了range(0, n)取到的是0到n-1恰好覆蓋整個長度為n的數(shù)組。Python這個設(shè)計其實比閉區(qū)間友好但前提是你要把“右邊取不到”這個特性刻在腦子里否則同樣會多一位或者少一位。1.2 二分查找里的三個隱蔽邊界坑二分查找是下標計算的重災(zāi)區(qū)因為它的邊界不是寫死的而是在循環(huán)里動態(tài)變化。最常見的三個坑我一個個說。第一個坑是中間下標計算溢出。這個Bug在Java經(jīng)典面試題里出現(xiàn)率極高int mid (low high) / 2;當(dāng)low和high都很大比如low接近Integer.MAX_VALUE的一半以上時low high會溢出變成負數(shù)mid算出來就是負的數(shù)組直接下標越界。解決辦法大家現(xiàn)在都知道寫low (high - low) / 2就好。這個寫法先算差值差值一定不會溢出再加到low上結(jié)果安全。第二個坑是循環(huán)條件到底是low high還是low high。這兩種寫法其實對應(yīng)不同的區(qū)間定義low high通常配合右開區(qū)間low high配合閉區(qū)間。一旦混用要么死循環(huán)要么漏掉最后一個元素。我的建議是保持一套固定的模板別換比如始終寫low high、右邊界用high mid - 1這樣一套邏輯吃透以后不管遇到什么二分題都套同一個模板比每次現(xiàn)推邊界要穩(wěn)得多。第三個坑是相鄰元素時的死循環(huán)問題。比如low 0, high 1時如果條件寫得不好mid永遠算出來等于low然后你又執(zhí)行l(wèi)ow mid而不是low mid 1那么low永遠不變死循環(huán)就出現(xiàn)了。這類問題在“查找第一個大于等于target的位置”這類變體題里尤其常見標記一下屬于必須親手跑一遍才能記住的坑。1.3 負索引與切片邊界的特殊規(guī)則Python的負索引是另一套邊界規(guī)則它和常規(guī)下標體系的混用特別容易讓人迷糊。arr[-1]在Python里表示最后一個元素這個設(shè)計很好用但負索引和正索引混在一起做切片時就容易出亂子。比如arr [0, 1, 2, 3, 4] print(arr[1:-1]) # [1, 2, 3] print(arr[:-1]) # [0, 1, 2, 3]切片的規(guī)則是“左閉右開”也就是起始下標取得到結(jié)束下標取不到。-1做結(jié)束下標時表示的是最后一個元素的位置但不會把它包含進來。所以arr[:-1]是去掉最后一個元素這個語義一旦建立起來就很好用。容易出錯的地方在于把負索引和正索引混合用于兩步操作比如先取arr[-3:]再對結(jié)果繼續(xù)取[:-1]腦子稍微一亂就算錯了。JavaScript里沒有負索引這個語法。如果你寫arr[-1]它不會報錯但也不會返回最后一個元素而是把“-1”作為屬性名掛到數(shù)組對象上。這個行為在嚴格模式和非嚴格模式下表現(xiàn)還不一樣屬于JS數(shù)組一個很隱蔽的坑。很多從Python切到JS的同事在這里翻過車所以我專門提一句JS想要取末尾元素老老實實用arr[arr.length - 1]別用負索引的習(xí)慣。2. C/C場景的數(shù)組與指針混淆數(shù)組名退化、指針加減法與多維數(shù)組C和C的數(shù)組問題核心不在于邊界而在于“數(shù)組名到底是什么”。教科書說“數(shù)組名是首元素地址”這句話只對了一半另一半坑了無數(shù)人。數(shù)組名在大多數(shù)表達式里會退化成指向首元素的指針但在sizeof、取地址符等少數(shù)場景下它又保留了“整個數(shù)組”的語義。這兩套規(guī)則切換不熟練就會出現(xiàn)同一段代碼換個場景結(jié)果完全不同的怪事。2.1 sizeof數(shù)組名和sizeof指針的結(jié)果為什么不同先看這段代碼int arr[10]; printf(%zu\n, sizeof(arr)); // 輸出40int占4字節(jié) void func(int arr[]) { printf(%zu\n, sizeof(arr)); // 輸出8或4指針大小 }同一個arr在主函數(shù)里sizeof得到的是整個數(shù)組占用的字節(jié)數(shù)40傳到函數(shù)參數(shù)里卻變成了指針的大小。原因是函數(shù)參數(shù)列表里的int arr[]會被編譯器自動調(diào)整為int *arr數(shù)組名在傳參過程中退化成了指針數(shù)組的長度信息在這一步就丟了。所以函數(shù)內(nèi)部拿sizeof去算數(shù)組長度是行不通的需要額外傳一個長度參數(shù)。這也是C面試題里“如何獲取函數(shù)內(nèi)數(shù)組長度”的標準答案坑。避免這個坑的實用方法是如果你確實需要在多個函數(shù)之間共享數(shù)組和它的長度要么用C的std::array或std::vector要么在傳參時把數(shù)組長度一起傳過去。不要試圖在函數(shù)內(nèi)部對退化后的指針做任何sizeof操作那得到的一定是指針大小不是數(shù)組長度。2.2 指針數(shù)組與數(shù)組指針兩個名字順序反了的概念指針數(shù)組和數(shù)組指針這兩個詞中文讀起來特別拗口但它們的區(qū)別是C語言必須跨過去的一道坎。我給一個自己常用的記憶方式先看變量名左邊先跟誰結(jié)合。int *p[10]; // p先和[10]結(jié)合說明p是數(shù)組數(shù)組里有10個int*元素 // 所以這是“指針數(shù)組” int (*p)[10]; // p先和*結(jié)合說明p是指針它指向一個包含10個int的數(shù)組 // 所以這是“數(shù)組指針”判斷的關(guān)鍵在括號。加了括號后*優(yōu)先和變量名結(jié)合說明變量本身是指針不加括號[]優(yōu)先和變量名結(jié)合說明變量本身是數(shù)組。這個規(guī)則我在實際代碼review里見過太多次被寫反的案例一寫反整個類型體系就全亂了。數(shù)組指針最常見的應(yīng)用場景是二維數(shù)組傳參。你寫void func(int arr[][10])時編譯器其實把它調(diào)整為int (*arr)[10]也就是一個指向“包含10個int的數(shù)組”的指針。所以二維數(shù)組傳參時第二維的大小必須在參數(shù)類型里明確寫出來否則指針運算無法進行下一步尋址。2.3 指針加減法的步長陷阱指針加減法的步長和指向類型的sizeof直接掛鉤。int *p加1地址值增加4如果p指向一個結(jié)構(gòu)體數(shù)組p 1增加的是整個結(jié)構(gòu)體的大小。這個規(guī)則本身不復(fù)雜但一旦和多維數(shù)組混在一起就很容易算錯。int arr[3][4]; int (*p)[4] arr; // p指向第一行p 1指向第二行步長是4個int16字節(jié)如果你錯誤地把二維數(shù)組名賦值給int *類型的指針比如int *q arr;編譯器通常會給出警告但有些編譯器只是警告不報錯。后續(xù)你用q做下標運算比如q[1]訪問的其實是arr[0][1]而不是arr[1][0]數(shù)據(jù)完全對不上。要處理二維數(shù)組的線性遍歷正確做法是int *q arr[0][0]顯式取首元素地址這樣整塊內(nèi)存的線性布局才可預(yù)測。2.4 字符串?dāng)?shù)組和字符指針的經(jīng)典混淆C語言里字符串常量是char[]類型還是char *類型這個問題的答案在不同標準下有細微差別但實際操作中最大的坑是“能不能修改”?？催@兩行char str1[] hello; char *str2 hello; str1[0] H; // 合法str1是本地數(shù)組可修改 str2[0] H; // 未定義行為字符串常量通常存儲在只讀區(qū)可能崩潰str1是一個字符數(shù)組它在棧上分配了6個字節(jié)含末尾的\0內(nèi)容可以修改。str2是一個指向字符串常量的指針字符串常量通常放在只讀數(shù)據(jù)區(qū)你嘗試修改它的時候行為未定義。在多數(shù)Linux系統(tǒng)上會直接觸發(fā)段錯誤Windows上可能表現(xiàn)為異常退出。這個坑的隱蔽之處在于編譯階段很少報警賦值和讀取看起來都一樣直到運行期才炸。為了避免這類問題我現(xiàn)在的習(xí)慣是用const char *聲明指向字符串字面量的指針這樣任何試圖修改內(nèi)容的代碼在編譯期就會被攔下來。另外對比兩個字符串時用比較的是指針地址而不是內(nèi)容這又是一類高頻錯誤必須用strcmp或std::string的operator來比較內(nèi)容。3. 數(shù)組初始化的默認值陷阱聲明與賦值之間藏著巨大的差異數(shù)組初始化是另一個高頻翻車點。不同語言對“聲明后未顯式賦值的元素”處理方式完全不同有的給0有的給垃圾值有的給undefined還有的給對象引用。一字之差線上行為天差地別。我按語言逐個拆每個都配一個實際場景。3.1 C語言局部數(shù)組是垃圾值static和部分初始化卻另有規(guī)則C語言里局部數(shù)組如果沒有初始化里面存的是棧上的隨機垃圾值。這個大家都知道但真正容易記混的是部分初始化規(guī)則只要初始化列表里出現(xiàn)了一個值其余沒寫到的元素會被自動置為0。所以int arr[10] {0};是C語言里標準的“全零初始化”寫法這個習(xí)慣很多老手一直在用因為它簡潔安全。static修飾的數(shù)組會自動零初始化也就是說static int arr[10];即使不寫初始化列表10個元素也全是0。這背后的原因是靜態(tài)存儲期的變量會被放在BSS段程序加載時系統(tǒng)會把這部分內(nèi)存清零。知道這個原理后你會明白依賴static的零初始化是穩(wěn)定可靠的不是編譯器心情好才給0。游戲開發(fā)里常見一個坑在熱更新模塊或嵌入式設(shè)備上程序員認為malloc之后數(shù)組一定清零但malloc完全不保證這一點它只分配內(nèi)存不初始化里面可能是上一個進程留下的數(shù)據(jù)。正確做法是分配后立即memset或calloc。我見過排查很久的“數(shù)據(jù)莫名其妙有殘留”問題最后根因就是malloc后忘了清零老數(shù)據(jù)干擾了新邏輯這種坑一旦踩到極難復(fù)現(xiàn)。3.2 Cvector和new[]的初始化行為不一致C里std::vector v(10);會把10個元素全部初始化為0因為vector走的是值初始化路徑。但如果你寫int *p new int[10];這10個int是不確定的垃圾值除非你寫new int 10 帶一對空括號才會全部置0。這個括號之差在代碼Review里幾乎注意不到運行期卻可能帶來完全不同的結(jié)果。我在實現(xiàn)一個緩存池時踩過這個坑new出來的數(shù)組沒初始化然后我往里面寫入部分數(shù)據(jù)讀取時沒來得及更新位置的元素全是一堆歷史殘留導(dǎo)致緩存命中判斷錯誤。后面改成new int 10 之后問題立刻消失。現(xiàn)在我的原則是凡是new數(shù)組要么立即用括號初始化要么用vector不要裸著用內(nèi)存分配和初始化的狀態(tài)不明確后面十有八九出問題。3.3 Python的 [[0] * n] * m一個列表的引用復(fù)制災(zāi)難Python里有一個知名的二維列表初始化寫法坑matrix [[0] * 3] * 3 matrix[0][0] 1 print(matrix) # [[1, 0, 0], [1, 0, 0], [1, 0, 0]]預(yù)期是只改第一行第一列結(jié)果三行的第一列全變成了1。原因是[0] * 3創(chuàng)建了一個包含3個0的列表然后外層* 3復(fù)制的是這個列表的引用不是復(fù)制這個列表的內(nèi)容。也就是說matrix里三個元素指向的是同一個列表對象修改任何一個“行”其他“行”同步變化。正確寫法是列表推導(dǎo)式[[0] * 3 for _ in range(3)]每次迭代都生成一個全新的子列表?；蛘哂胣umpynumpy的二維數(shù)組是真正的內(nèi)存塊布局不存在這種引用復(fù)制問題。這個坑之所以隱蔽是因為你只讀取matrix的時候看不出任何問題一旦寫入數(shù)據(jù)全行列同時變化的現(xiàn)象就出現(xiàn)了。處理圖像矩陣、二維狀態(tài)表時尤其要當(dāng)心。3.4 JavaScript的Array(n)與fill()的空槽位問題JavaScript里new Array(3)創(chuàng)建的是一個長度為3的稀疏數(shù)組這個數(shù)組只有l(wèi)ength屬性沒有任何實際元素索引讀取會得到undefined。這里要注意undefined是“索引存在但值為undefined”而稀疏數(shù)組是“索引根本不存在”兩者在遍歷時的表現(xiàn)不一樣forEach、map等方法會跳過稀疏數(shù)組的空槽位但不會跳過值為undefined的元素。fill方法可以把稀疏數(shù)組填充成密集數(shù)組Array(3).fill(0)能得到[0, 0, 0]。但這里有個類似Python的坑看下面這段const matrix new Array(3).fill([]); matrix[0].push(1); console.log(matrix); // [[1], [1], [1]]fill([])的時候[]作為一個引用值被填進了三個位置這三個位置指向同一個空數(shù)組。修改matrix[0]其它“行”跟著變。這和Python那個坑如出一轍。正確的二維數(shù)組創(chuàng)建方式應(yīng)該是Array.from({length: 3}, () [])每次調(diào)用函數(shù)生成新數(shù)組。記住了這個前端處理表格、矩陣數(shù)據(jù)時就不會被莫名其妙的聯(lián)動修改坑到。3.5 Java、VBA和PHP的默認值差異Java數(shù)組有確定的默認值int數(shù)組默認0、boolean數(shù)組默認false、引用類型數(shù)組默認null。這種設(shè)計很省心但等一個坑聲明一個Integer數(shù)組然后直接用如果沒逐個初始化元素會是null而不是0拆箱成int時直接拋NullPointerException。這個在從int數(shù)組改成Integer數(shù)組做緩存時極易踩到。VBA里有個Option Base的坑。Dim arr(5)如果沒有顯式聲明下標起始默認是0到5還是1到5取決于模塊頂部的Option Base設(shè)置。這個設(shè)置一個模塊改了整個工程的數(shù)組下標行為全變。最好的做法是寫死下標范圍比如Dim arr(0 To 5)或Dim arr(1 To 5)明確上下界別依賴默認配置。VBA另一個高頻問題是數(shù)組與Excel單元格Range之間的往返轉(zhuǎn)換如果你直接對Excel區(qū)域賦值給數(shù)組得到的是二維數(shù)組即使只有一列它的維度也是(n, 1)UBound的第二個參數(shù)必須寫清楚。PHP數(shù)組本身就是“有序映射”本質(zhì)上是哈希表加順序列表的混合體所以它不存在“未初始化元素為垃圾值”的問題。但PHP在數(shù)組合并時有一個容易忽略的鍵名重排規(guī)則array_merge遇到數(shù)字鍵會重新編號遇到字符串鍵會保留并覆蓋同名鍵。如果混用數(shù)字鍵和字符串鍵合并后數(shù)字鍵的可能變了位置下標對不上容易造成數(shù)據(jù)錯亂。4. JavaScript與Python數(shù)組的隱性陷阱引用、排序與類型混用動態(tài)語言數(shù)組看起來比C簡單因為它們不要求你手動管理內(nèi)存但動態(tài)語言把數(shù)組問題轉(zhuǎn)移到了另一種維度引用語義和隱式類型轉(zhuǎn)換。這兩個維度造成的Bug隱蔽程度比越界訪問還要高因為不報錯、不亂碼就是結(jié)果看起來“不太對”。4.1 JavaScript sort默認按字符串排序JavaScript數(shù)組的sort方法如果不傳比較函數(shù)默認行為是把元素先轉(zhuǎn)成字符串再按字符串的UTF-16碼元順序排序。這個行為對很多初學(xué)者是反直覺的因為10、9、25這三個數(shù)字按字符串排序的結(jié)果是10、25、9。const nums [10, 9, 25]; nums.sort(); console.log(nums); // [10, 25, 9]為什么默認這么設(shè)計因為sort在設(shè)計之初要兼容字符串排序而且JS的類型系統(tǒng)足夠動態(tài)數(shù)組里可以混裝string、number、object所以默認排序只能先統(tǒng)一轉(zhuǎn)字符串。處理數(shù)字數(shù)組排序時必須顯式傳比較函數(shù)nums.sort((a, b) a - b)。這個比較函數(shù)的返回值是負數(shù)、0還是正數(shù)決定了元素是往前排、維持還是往后排理解這一點就能應(yīng)付各種自定義排序。另外一個JS數(shù)組排序的坑是sort會修改原數(shù)組而map、filter、slice不會。如果你需要保留原始順序去做后續(xù)操作必須先淺拷貝一份再排序。我遇到過同事直接對props傳入的數(shù)組做sort結(jié)果父組件的數(shù)據(jù)被改掉頁面重渲染后順序全亂排查半天才發(fā)現(xiàn)是sort原地修改了原數(shù)組引用。4.2 Python切片的復(fù)制與嵌套列表的引用層級Python切片arr[:]會生成一個新的列表但這是一個淺拷貝新列表的元素是原列表元素的引用。如果原列表里存的是基本類型數(shù)字、字符串淺拷貝足夠安全如果存的是可變對象列表、字典修改新列表里的某個元素對象原列表的對應(yīng)元素也會變。以二維列表為例a [[1, 2], [3, 4]] b a[:] b[0].append(99) print(a) # [[1, 2, 99], [3, 4]]a也跟著變了。要完全復(fù)制嵌套結(jié)構(gòu)必須用copy模塊的deepcopy。這個坑在做矩陣變換、狀態(tài)快照、數(shù)據(jù)備份時特別常踩。我的習(xí)慣是先問“我復(fù)制這份數(shù)組是為了改數(shù)據(jù)還是只讀”只讀的話淺拷貝夠用要改數(shù)據(jù)或做回滾就得deepcopy否則操作的是同一份底層對象。4.3 對象數(shù)組去重為什么Set對對象無效數(shù)組去重是前端面試題?？鸵彩菢I(yè)務(wù)里高頻場景。Set去重對基本類型很有效但對對象數(shù)組完全無效因為兩個對象只要引用不同Set就認為它們不同哪怕字段完全一樣。const arr [{id: 1}, {id: 1}]; const unique [...new Set(arr)]; console.log(unique.length); // 2因為兩個對象引用不同正確做法是根據(jù)某個唯一鍵去重傳統(tǒng)寫法是一層循環(huán)加一個Map緩存key用對象里唯一的字段比如id一旦Map里已經(jīng)有這個key就跳過否則存入結(jié)果并記錄key。ES6之后也可以用Map直接實現(xiàn)Map.get(id)判斷。前端處理接口返回的列表去重時用這個思路比Set穩(wěn)妥。對象數(shù)組去重本質(zhì)上是“按業(yè)務(wù)主鍵去重”主鍵的選擇直接決定去重是否正確比如用id還是用name業(yè)務(wù)語義完全不同。Python里要處理類似需求可以用字典推導(dǎo)式按key合并{item[id]: item for item in arr}.values()同樣也是按業(yè)務(wù)主鍵去重。注意Python中范圍返回的是dict_values視圖如果要列表就list()包一下。這個寫法簡潔但要先確認你理解的“去重”是哪一層語義完全相等對象內(nèi)容一致還是業(yè)務(wù)主鍵一致。前者在多語言中都可以用序列化后的字符串作為key后者必須顯式指定字段。4.4 數(shù)組轉(zhuǎn)字符串與字符串轉(zhuǎn)數(shù)組的隱式轉(zhuǎn)換JavaScript數(shù)組的toString和join方法會把每個元素toString之后再拼接元素里如果包含null或undefined會被轉(zhuǎn)成空字符串。這個行為在日志輸出時看著正常但如果你拿這個字符串去做解析還原很容易損失信息。比如[1, null, 2].toString()得到1,,2再split(,)回來得到[1, , 2]null變成了空串類型和值全變了。更經(jīng)典的是用運算符把數(shù)組轉(zhuǎn)成字符串[1, 2] [3]得到1,23這是數(shù)組先toString再拼接的結(jié)果完全不是數(shù)學(xué)上的數(shù)組加法JS數(shù)組本來也沒有加法。這種隱式轉(zhuǎn)換在表單提交、URL參數(shù)拼接時會引發(fā)難以察覺的Bug比如orderIds數(shù)組拼接后多了一個逗號后端解析時多出一個空ID。我現(xiàn)在處理這類場景的約定是序列化數(shù)組一律用JSON.stringify和JSON.parse格式明確類型完整不依賴隱式轉(zhuǎn)換規(guī)則。Python的數(shù)組轉(zhuǎn)字符串則有一條常見捷徑..join(arr)但join要求所有元素都是字符串元素包含數(shù)字時會拋TypeError。很多人在這里直接寫str.join(arr)然后報錯原因是沒做類型轉(zhuǎn)換正確寫法是..join(map(str, arr))。這個和JS的隱式轉(zhuǎn)換是兩個方向的坑JS隱式轉(zhuǎn)換太自由Python顯式要求太嚴格各自都要適應(yīng)。5. 常用數(shù)組操作的性能誤區(qū)去重、切片與動態(tài)增刪的隱性成本數(shù)組易錯點還有一個維度被經(jīng)常忽視性能。有些寫法在功能上完全正確但復(fù)雜度差出一個數(shù)量級數(shù)據(jù)量一上來就卡頓或者超時。這一節(jié)我會把幾個真正寫過業(yè)務(wù)代碼才會察覺的性能陷阱攤開講。樹狀數(shù)組這類競賽模板本身也有很多易錯細節(jié)下標從1開始這一點我在競賽代碼里被自己坑過不止一次這里也一并說清楚。5.1 二分查找里那個著名的整數(shù)溢出這個問題我在第1章提到過一種形式這里單獨再強調(diào)一次因為它差點重復(fù)引爆好幾個經(jīng)典代碼庫。Java的Arrays.binarySearch里有一段內(nèi)部實現(xiàn)曾經(jīng)就存在因為mid (low high) 1的寫法規(guī)避了溢出但如果你自己手寫二分很容易寫成(low high) / 2。low和high都是int加出來的結(jié)果在極端情況下超過Integer.MAX_VALUE變成負數(shù)mid就成負數(shù)了數(shù)組下標直接越界或者死循環(huán)。Java里用(low high) 1可以規(guī)避溢出問題因為無符號右移對負值也能得到正確的一半。C/C和Python里就沒必要用這個技巧了C直接寫low (high - low) / 2Python的整數(shù)無上限直接(low high) // 2也安全。關(guān)鍵在于寫二分時不要想當(dāng)然要把“加法可能溢出”作為一個默認假設(shè)去寫代碼尤其在語言固定整數(shù)寬度的情況下。5.2 Python insert(0)與JavaScript unshift的O(n)代價Python的list.insert(0, item)和JavaScript的unshift(item)在功能上都是往頭部插入元素但它們的實現(xiàn)都是把整塊數(shù)組的元素向后搬移復(fù)雜度O(n)。如果你在一個循環(huán)里反復(fù)執(zhí)行頭部插入總復(fù)雜度會變成O(n^2)數(shù)據(jù)量超過10萬級別就能明顯感覺到卡頓。我自己處理過一個日志收集的場景需要不斷把新日志放到列表最前面用insert(0, item)硬寫了跑到兩萬條日志時延遲明顯上升。優(yōu)化方案很簡單先把日志append到尾部最后統(tǒng)一reverse一次或者用collections.deque它的appendleft是O(1)。JavaScript那邊也有對應(yīng)的問題如果頻繁頭部增刪用鏈表結(jié)構(gòu)或改用尾部追加再reverse或者用雙端隊列庫。保持對“頭部操作”的敏感是寫出高性能數(shù)組代碼的第一步。另一個類似的誤區(qū)是JavaScript的splice方法arr.splice(0, 0, item)和unshift一樣也是O(n)arr.splice(index, 1)刪除中部元素同樣需要搬移后續(xù)元素。如果要頻繁刪除中間元素且數(shù)組很大建議換個數(shù)據(jù)結(jié)構(gòu)比如鏈表或哈希表別裸用數(shù)組硬扛。5.3 數(shù)組去重算法的性能分水嶺數(shù)組去重看著簡單但不同寫法的復(fù)雜度相差很大。最粗暴的雙重循環(huán)外層遍歷每個元素內(nèi)層遍歷已結(jié)果判斷是否重復(fù)O(n^2)。幾千條數(shù)據(jù)還能接受幾萬條就開始緩慢幾十萬條基本沒法用。用Set或哈希表是O(n)一個Set記錄已出現(xiàn)的值另一個數(shù)組保存唯一值。關(guān)鍵是判斷是否重復(fù)的步驟從線性查找變成了哈希查找整體復(fù)雜度降了一個數(shù)量級。JavaScript里最簡寫法是return [...new Set(arr)]Python里是list(dict.fromkeys(arr))保留順序或list(set(arr))不保留順序。對象數(shù)組去重則必須用Map按業(yè)務(wù)主鍵緩存前面章節(jié)已經(jīng)說過這里不再展開。實際生產(chǎn)經(jīng)驗是去重前先確認數(shù)據(jù)規(guī)模。純前端做下拉列表選項去重幾千條隨便服務(wù)端處理幾十萬條的數(shù)據(jù)就必須選擇O(n)寫法。而且JavaScript的Set內(nèi)部基于哈希表實現(xiàn)不會因為你使用了Set就自動解決所有問題如果你拿Set去存對象那是按引用哈希等于沒有去重。5.4 樹狀數(shù)組的“下標從1開始”和其他隱藏約束樹狀數(shù)組和普通數(shù)組有個顯著的區(qū)別它為了在二進制上做lowbit運算通常下標從1開始0號位置是哨兵節(jié)點。這個特性讓很多從0下標走過來的人踩坑初始化時樹狀數(shù)組的更新循環(huán)條件是for (int i index; i n; i lowbit(i))如果你習(xí)慣性地寫成i n最后一輪更新就漏了如果查詢前綴和的時候直接從0開始循環(huán)則會死循環(huán)或漏算。我提一個實際經(jīng)驗寫樹狀數(shù)組模板時第一行先注釋“下標從1開始”然后所有調(diào)用方都約定傳1-based下標。這樣雖然和C數(shù)組的0-based慣例有沖突但至少在模塊內(nèi)部自洽。樹狀數(shù)組另一個高頻錯誤是lowbit寫錯int lowbit(int x) { return x (-x); }這個寫法依賴補碼表示里負數(shù)為原碼取反加一的特性運算結(jié)果正好是x二進制中最低位的1所代表的整數(shù)值。這里如果寫成x (x - 1)那就變成了清除最低位1的操作語義完全不同千萬別混。5.5 二維數(shù)組連續(xù)內(nèi)存遍歷的性能差異C/C的二維數(shù)組在內(nèi)存中的存儲是行優(yōu)先的也就是先排列第一行的所有元素再排列第二行。遍歷時按行訪問比按列訪問要快一個數(shù)量級因為按列訪問會跳著訪問內(nèi)存破壞CPU緩存局部性。int arr[1024][1024]; // 按行遍歷緩存友好 for (int i 0; i n; i) for (int j 0; j n; j) sum arr[i][j]; // 按列遍歷緩存不友好 for (int j 0; j n; j) for (int i 0; i n; i) sum arr[i][j];兩者結(jié)果完全一樣但性能可能差10倍甚至更多。在圖像處理里這種問題尤其突出因為像素矩陣動輒幾千乘幾千。理解這個原理就不難明白為什么很多高性能代碼會刻意調(diào)整循環(huán)順序來配合內(nèi)存布局。Python的numpy也有類似考量它默認C order存儲如果你把它轉(zhuǎn)成Fortran order列優(yōu)先而不注意訪問模式性能同樣會有波動。6. 排查數(shù)組Bug的實用套路從現(xiàn)象倒推根因的檢查清單整理完這些具體的坑之后我想分享一個通用排查思路。數(shù)組相關(guān)Bug最棘手的不是難修而是找不到根因現(xiàn)象可能在業(yè)務(wù)層根因卻在數(shù)組操作的底層細節(jié)里。我自己摸索出一套倒推法每次排查數(shù)組問題都按這個順序來節(jié)省了大量時間。6.1 一次線上數(shù)據(jù)錯亂的完整排查過程最近一次實戰(zhàn)案例可以說明整個套路。線上一個跑批任務(wù)輸出價格錯亂部分訂單的價格被覆蓋成了歷史殘留值單看業(yè)務(wù)邏輯完全不對。我第一步先看代碼里有沒有數(shù)組越界寫入的可能把所有循環(huán)條件里的逐個過了一遍沒有發(fā)現(xiàn)。第二步看數(shù)組是否初始化找到一處malloc后直接通過索引寫入的緩沖區(qū)寫入范圍依賴一個外部傳入的批次號批次號異常大時這個寫入就越界了恰好覆蓋到相鄰的一個價格數(shù)組的內(nèi)存區(qū)域。第三步確認后修復(fù)方案是給批次號加范圍校驗同時把malloc改成calloc讓緩沖區(qū)初始化為全零這樣即使后續(xù)邏輯有異常殘留值也不會被誤讀成有效價格。這個案例里現(xiàn)象是“價格被覆蓋”直接原因是“越界寫”但被忽略的根因其實是“緩沖區(qū)未初始化 外部參數(shù)未校驗”。如果按業(yè)務(wù)邏輯去排查永遠查不到問題。所以我的第一步永遠是問這個數(shù)據(jù)是不是被某個數(shù)組操作寫壞過而不是問業(yè)務(wù)邏輯哪里不對。6.2 數(shù)組Bug自檢清單我把高頻問題整理成一張清單每排查一個數(shù)組相關(guān)Bug就按這個表逐項對照檢查項具體追問對應(yīng)章節(jié)索引邊界循環(huán)條件是否多一次或少一次切片右邊界是否開區(qū)間第1章下標計算lowhigh是否溢出mid是否會死循環(huán)第1、5章數(shù)組與指針數(shù)組名是否退化sizeof是否取到指針大小第2章指針步長多維數(shù)組指針加減時步長是否按行第2章初始化局部數(shù)組是否垃圾值部分初始化規(guī)則是否被遺忘第3章引用復(fù)制外層乘法是否復(fù)制了內(nèi)層列表引用第3、4章排序比較JS sort是否傳了比較函數(shù)第4章去重語義按引用去重還是按業(yè)務(wù)主鍵去重第4章復(fù)雜度是否頻繁頭部增刪是否雙重循環(huán)去重第5章內(nèi)存布局二維數(shù)組按行還是按列遍歷第5章這張表看起來簡單但它覆蓋了我在多年開發(fā)里遇到過的絕大多數(shù)數(shù)組問題。每排查一個Bug我都建議對著它打一遍勾而不是憑直覺去猜。很多次我以為問題在算法邏輯最后查到的是初始化或邊界對照清單能幫你繞過思維定式。6.3 如何在設(shè)計階段避開數(shù)組坑能靠排查解決的問題都不如從設(shè)計上提前規(guī)避。我在寫新代碼時有一套習(xí)慣第一所有數(shù)組的下標訪問盡量封裝成帶邊界檢查的函數(shù)特別是在C/C這種越界不報錯的語言里寫一個small_access函數(shù)做斷言Debug版本跑測試時就能暴露越界問題。第二數(shù)組初始化和后續(xù)賦值分開寫不要在一行里靠語言默認規(guī)則去猜初始值任何情況下顯式初始化都比依賴默認值安全。第三處理引用語義語言Python、JavaScript里的嵌套數(shù)組時一律用推導(dǎo)式或Array.from創(chuàng)建新對象永遠不用乘法復(fù)制引用。第四數(shù)組長度尺寸大且需要動態(tài)增刪時先問自己“這個場景真的適合用數(shù)組嗎”答案如果是否定的果斷換鏈表、字典或雙端隊列。這樣一通操作下來你能踩到的數(shù)組坑至少少一半。剩下的那一半就是上面這張排查清單要解決的問題。數(shù)組的坑永遠踩不完但把最常見的幾類記在腦子里至少能讓定位問題的速度快很多。我現(xiàn)在的習(xí)慣是每次提交代碼前把涉及數(shù)組的段落單獨過一遍自查清單重點關(guān)注邊界、初始化和引用復(fù)制這三類——因為這三類Bug在測試環(huán)境往往不顯眼只有數(shù)據(jù)量和場景變化后才炸。希望這篇梳理能幫你少走一些我走過的彎路也希望你下次再看到j(luò)s的sort不帶比較函數(shù)、Python里[[0]*m]*n、C里malloc忘了清零這些寫法時能條件反射地意識到風(fēng)險在那里。