數(shù)組相關(guān)代碼請(qǐng)移步 Leooel 的博客
數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)澜搅。它用一組連續(xù)的內(nèi)存空間，來存儲(chǔ)一組具有相同類型的數(shù)據(jù)邪锌。
- 關(guān)鍵詞一：線性表
- 關(guān)鍵詞二：連續(xù)的內(nèi)存空間 和 相同類型的數(shù)據(jù)
正是因?yàn)檫@兩個(gè)限制勉躺，它才有了一個(gè)堪稱“殺手锏”的特性：“隨機(jī)訪問”。但有利就有弊秃流，這兩個(gè)限制也讓數(shù)組的很多操作變得非常低效赂蕴，比如要想在數(shù)組中刪除柳弄、插入一個(gè)數(shù)據(jù)舶胀，為了保證連續(xù)性，就需要做大量的數(shù)據(jù)搬移工作碧注。
數(shù)組是如何實(shí)現(xiàn)根據(jù)下標(biāo)隨機(jī)訪問數(shù)組元素的嚣伐？
計(jì)算機(jī)會(huì)給每個(gè)內(nèi)存單元分配一個(gè)地址，計(jì)算機(jī)通過下標(biāo)計(jì)算出地址萍丐，然后來訪問內(nèi)存中的數(shù)據(jù)轩端。
a[i]_address = base_address + i * data_type_size
data_type_size：數(shù)組中每個(gè)元素的大小
面試細(xì)節(jié) 01
問：數(shù)組和鏈表的區(qū)別
誤答：鏈表適合插入、刪除逝变，時(shí)間復(fù)雜度 O(1)基茵；數(shù)組適合查找，查找時(shí)間復(fù)雜度為 O(1)
正答：數(shù)組支持隨機(jī)訪問壳影，根據(jù)下標(biāo)隨機(jī)訪問的時(shí)間復(fù)雜度為 O(1)
低效的“插入”和“刪除”
數(shù)組為了保持內(nèi)存數(shù)據(jù)的連續(xù)性拱层，會(huì)導(dǎo)致插入、刪除這兩個(gè)操作比較低效宴咧，平均時(shí)間復(fù)雜度都為 O(n)根灯。
- 但是，如果數(shù)組中存儲(chǔ)的數(shù)據(jù)并沒有任何規(guī)律，數(shù)組只是被當(dāng)作一個(gè)存儲(chǔ)數(shù)據(jù)的集合烙肺。在這種情況下纳猪，如果要將某個(gè)數(shù)組插入到第 k 個(gè)位置，為了避免大規(guī)模的數(shù)據(jù)搬移桃笙，我們還有一個(gè)簡單的辦法就是直接將第 k 位的數(shù)據(jù)搬移到數(shù)組元素的最后氏堤，把新的元素直接放入第 k 個(gè)位置。這個(gè)處理思想在快排中也會(huì)用到怎栽。形象圖如下：
- 實(shí)際上丽猬，在某些特殊場(chǎng)景下，我們并不一定非得追求數(shù)組中數(shù)據(jù)的連續(xù)性熏瞄。如果我們將多次刪除操作集中在一起執(zhí)行脚祟，刪除的效率是不是更高？看下圖例子：
數(shù)組 a[10] 中存儲(chǔ)了 8 個(gè)元素：a强饮，b由桌，c，d邮丰，e行您，f，g剪廉，h⊥扪現(xiàn)在，我們要依次刪除 a斗蒋，b捌斧，c 三個(gè)元素。為了避免 d泉沾，e捞蚂，f，g跷究，h 這幾個(gè)數(shù)據(jù)會(huì)被搬移三次姓迅，我們可以先記錄下已經(jīng)刪除的數(shù)據(jù)。每次的刪除操作并不是真正地搬移數(shù)據(jù)俊马，只是記錄數(shù)據(jù)已經(jīng)被刪除丁存。當(dāng)數(shù)組沒有更多空間存儲(chǔ)數(shù)據(jù)時(shí)，我們?cè)儆|發(fā)執(zhí)行一次真正的刪除操作柴我，這樣就大大減少了刪除操作導(dǎo)致的數(shù)據(jù)搬移解寝。這也是JVM 標(biāo)記清除垃圾回收算法的核心思想。
警惕數(shù)組的訪問越界問題
先來分析一下這段 C 語言代碼的運(yùn)行結(jié)果：
#include<stdio.h>
int main(int argc, char* argv[])
{
int i = 0;
int arr[3] = {0};
for(; i<=3; i++)
{
arr[i] = 0;
printf("hello world\n");
}
return 0;
}
運(yùn)行結(jié)果并非是打印三行“hello word”屯换，而是會(huì)無限打印“hello world”编丘。
數(shù)組越界在 C 語言中是一種未決行為与学，并沒有規(guī)定數(shù)組訪問越界時(shí)編譯器應(yīng)該如何處理。因?yàn)樵L問數(shù)組的本質(zhì)就是訪問一段連續(xù)內(nèi)存嘉抓，只要數(shù)組通過偏移計(jì)算得到的內(nèi)存地址是可用的索守，那么程序就可能不會(huì)報(bào)任何錯(cuò)誤。
根據(jù)我們前面講的數(shù)組尋址公式抑片，a[3] 也會(huì)被定位到某塊不屬于數(shù)組的內(nèi)存地址上卵佛，而這個(gè)地址正好是存儲(chǔ)變量i 的內(nèi)存地址，那么 a[3]=0 就相當(dāng)于 i=0敞斋，所以會(huì)導(dǎo)致代碼無限循環(huán)截汪。
這種情況下，一般都會(huì)出現(xiàn)莫名其妙的邏輯錯(cuò)誤植捎，就像我們剛剛舉的那個(gè)例子衙解，debug 的難度非常的大。而且焰枢，很多計(jì)算機(jī)病毒也正是利用到了代碼中的數(shù)組越界可以訪問非法地址的漏洞蚓峦，來攻擊系統(tǒng)，所以寫代碼的時(shí)候一定要警惕數(shù)組越界济锄。
但并非所有的語言都像 C 一樣暑椰，把數(shù)組越界檢查的工作丟給程序員來做，像 Java 本身就會(huì)做越界檢查荐绝。
容器能否完全替代數(shù)組一汽？
針對(duì)數(shù)組類型，很多語言都提供了容器類低滩，比如 Java 中的 ArrayList召夹、C++ STL 中的 vector。在項(xiàng)目開發(fā)中什么時(shí)候適合用數(shù)組委造，什么時(shí)候適合用容器呢戳鹅？
拿 Java 語言來舉例均驶，ArrayList 與數(shù)組相比最大的優(yōu)勢(shì)就是可以將很多數(shù)組操作的細(xì)節(jié)封裝起來和支持動(dòng)態(tài)擴(kuò)容昏兆。
數(shù)組本身在定義的時(shí)候需要預(yù)先指定大小，因?yàn)樾枰峙溥B續(xù)的內(nèi)存空間妇穴。如果我們申請(qǐng)了大小為 10 的數(shù)組爬虱，當(dāng)?shù)?11 個(gè)數(shù)據(jù)需要存儲(chǔ)到數(shù)組中時(shí)，我們就需要重新分配一塊更大的空間腾它，將原來的數(shù)據(jù)復(fù)制過去跑筝，然后再將新的數(shù)據(jù)插入。
如果使用 ArrayList瞒滴，我們就完全不需要關(guān)心底層的擴(kuò)容邏輯曲梗，ArrayList 已經(jīng)幫我們實(shí)現(xiàn)好了赞警。每次存儲(chǔ)空間不夠的時(shí)候，它都會(huì)將空間自動(dòng)擴(kuò)容為 1.5 倍大小虏两。
不過愧旦，這里需要注意一點(diǎn)，因?yàn)閿U(kuò)容操作涉及內(nèi)存申請(qǐng)和數(shù)據(jù)搬移定罢，是比較耗時(shí)的笤虫。所以，如果事先能確定需要存儲(chǔ)的數(shù)據(jù)大小祖凫，最好在創(chuàng)建 ArrayList 的時(shí)候事先指定數(shù)據(jù)大小琼蚯。
哪些情況下用數(shù)組更合適呢？
Java ArrayList 無法存儲(chǔ)基本類型惠况，比如 int遭庶、long，需要封裝為 Integer稠屠、Long 類罚拟，而Autoboxing、Unboxing 則有一定的性能消耗完箩，所以如果特別關(guān)注性能赐俗，或者希望使用基本類型，就可以選用數(shù)組弊知。
如果數(shù)據(jù)大小事先已知阻逮，并且對(duì)數(shù)據(jù)的操作非常簡單，用不到 ArrayList 提供的大部分方法秩彤，也可以直接使用數(shù)組叔扼。
還有一個(gè)是我個(gè)人的喜好，當(dāng)要表示多維數(shù)組時(shí)漫雷，用數(shù)組往往會(huì)更加直觀瓜富。比如 Object[][] array；而用容器的話則需要這樣定義：ArrayList<ArrayList> array降盹。
小總結(jié)：對(duì)于業(yè)務(wù)開發(fā)与柑，直接使用容器就足夠了，省時(shí)省力蓄坏。畢竟損耗一丟丟性能价捧，完全不會(huì)影響到系統(tǒng)整體的性能。但如果你是做一些非常底層的開發(fā)涡戳，比如開發(fā)網(wǎng)絡(luò)框架结蟋，性能的優(yōu)化需要做到極致，這個(gè)時(shí)候數(shù)組就會(huì)優(yōu)于容器渔彰，成為首選嵌屎。
標(biāo)題解答
為什么大多數(shù)編程語言中推正，數(shù)組要從 0 開始編號(hào)，而不是從 1 開始呢宝惰？
下標(biāo)從 0 開始：
a[k]_address = base_address + k * type_size
下標(biāo)從 1 開始：a[k]_address = base_address + (k-1) * type_size
- 效率原因舔稀。數(shù)組從 1 開始編號(hào)，每次隨機(jī)訪問數(shù)組元素都多了一次減法運(yùn)算掌测，對(duì)于 CPU 來說内贮，就是多了一次減法指令。
數(shù)組作為非彻基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)夜郁，通過下標(biāo)隨機(jī)訪問數(shù)組元素又是其非常基礎(chǔ)的編程操作粘勒，效率的優(yōu)化就要盡可能做到極致竞端。所以為了減少一次減法操作，數(shù)組選擇了從 0 開始編號(hào)庙睡，而不是從 1 開始事富。
- 最主要的可能是歷史原因。C 語言設(shè)計(jì)者用 0 開始計(jì)數(shù)數(shù)組下標(biāo)乘陪，為了在一定程度上減少 C 語言程序員學(xué)習(xí)其他語言的學(xué)習(xí)成本统台，其他后來語言(Java、JavaScript...)也繼續(xù)沿用了從 0 開始計(jì)數(shù)的習(xí)慣實(shí)際上啡邑，很多語言中數(shù)組也并不是從 0 開始計(jì)數(shù)的贱勃，比如 Matlab。甚至還有一些語言支持負(fù)數(shù)下標(biāo)谤逼，比如 Python贵扰。
課后思考
- 你怎么理解JVM 的標(biāo)記清除垃圾回收算法？
大多數(shù)主流虛擬機(jī)采用可達(dá)性分析算法來判斷對(duì)象是否存活流部。在標(biāo)記階段戚绕，會(huì)遍歷所有 GC ROOTS，將所有 GC ROOTS 可達(dá)的對(duì)象標(biāo)記為存活枝冀。只有當(dāng)標(biāo)記工作完成后舞丛，清理工作才會(huì)開始，在清除階段會(huì)遍歷堆宾茂，回收那些沒有被標(biāo)記的對(duì)象瓷马。
缺點(diǎn)是會(huì)產(chǎn)生內(nèi)存碎片拴还，很有可能導(dǎo)致下一次分配一塊連續(xù)較大的內(nèi)存空間時(shí)跨晴，由于找不到合適的，又觸發(fā)一次垃圾回收操作片林，一般試用于老年代的回收端盆。
- 類比一維數(shù)組的內(nèi)存尋址公式怀骤，二維數(shù)組的內(nèi)存尋址公式是什么？
對(duì)于 m * n 的數(shù)組焕妙，a [ i ][ j ] (i < m蒋伦，j < n)的地址為：
address = base_address + ( i * n + j) * type_size
