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