數(shù)組：是一種線性表數(shù)據(jù)結(jié)構(gòu)培己，它用一組連續(xù)的內(nèi)存空間，來存儲一組相同類型的數(shù)據(jù)。
從以下幾點去掌握數(shù)組：
① 線性表：數(shù)據(jù)排成一條線一樣的數(shù)據(jù)結(jié)構(gòu)温算。每個線性表最多有前后兩個方向她肯。除了數(shù)組佳头，鏈表、隊列晴氨、棧都是線性表結(jié)構(gòu)康嘉。
與之相反的概念是非線性表。比如二叉樹籽前、堆亭珍、圖。之所以叫非線性表聚假，是因為非線性表中块蚌，數(shù)據(jù)之間并不是簡單的前后關(guān)系。
② 連續(xù)的內(nèi)存空間 和 相同的數(shù)據(jù)類型膘格。這兩點峭范，才使得數(shù)據(jù)具有“隨機訪問”的特性（根據(jù)數(shù)據(jù)下標(biāo)進(jìn)行隨機訪問）。有利有弊瘪贱，這兩個限制讓數(shù)據(jù)的很多操作變的很低效纱控。比如辆毡，在數(shù)據(jù)中進(jìn)行插入、刪除一個數(shù)據(jù)甜害，就需要對大量數(shù)據(jù)進(jìn)行遷移工作舶掖。
Q：數(shù)組是如何根據(jù)下標(biāo)進(jìn)行隨機訪問的？
A：我們拿一個長度為 10 的 int 類型的數(shù)組 int[] a = new int[10] 來舉例尔店。在我畫的這個圖中眨攘，計算機給數(shù)組 a[10]，分配了一塊連續(xù)內(nèi)存空間 1000～1039嚣州，其中鲫售，內(nèi)存塊的首地址為 base_address = 1000。
我們知道，計算機會給每個內(nèi)存單元分配一個地址匀哄，計算通過地址來訪問內(nèi)存中的數(shù)據(jù)秦效。當(dāng)計算機需要隨機訪問數(shù)組中某個數(shù)據(jù)時，會通過下邊的尋址公式涎嚼，計算出該元素的內(nèi)存地址阱州。
????a[i]_address = base_address + i * data_type_size
特別糾正一個“錯誤”。我在面試的時候铸抑，常常會問數(shù)組和鏈表的區(qū)別贡耽，很多人都回答說，“鏈表適合插入鹊汛、刪除蒲赂，時間復(fù)雜度 O(1)；數(shù)組適合查找刁憋，查找時間復(fù)雜度為 O(1)”滥嘴。
實際上，這種表述是不準(zhǔn)確的至耻。數(shù)組是適合查找操作若皱，但是查找的時間復(fù)雜度并不為 O(1)。即便是排好序的數(shù)組尘颓，你用二分查找走触，時間復(fù)雜度也是 O(logn)。所以疤苹，正確的表述應(yīng)該是互广，數(shù)組支持隨機訪問，根據(jù)下標(biāo)隨機訪問的時間復(fù)雜度為 O(1)。
數(shù)組缺點：
抵消的? 插入? 和? 刪除? ?操作惫皱。
我們先來看插入操作像樊。
假設(shè)數(shù)組的長度為 n，現(xiàn)在旅敷，如果我們需要將一個數(shù)據(jù)插入到數(shù)組中的第 k 個位置生棍。為了把第 k 個位置騰出來，給新來的數(shù)據(jù)媳谁，我們需要將第 k～n 這部分的元素都順序地往后挪一位涂滴。那插入操作的時間復(fù)雜度是多少呢？你可以自己先試著分析一下韩脑。
如果在數(shù)組的末尾插入元素氢妈，那就不需要移動數(shù)據(jù)了，這時的時間復(fù)雜度為 O(1)段多。但如果在數(shù)組的開頭插入元素，那所有的數(shù)據(jù)都需要依次往后移動一位壮吩，所以最壞時間復(fù)雜度是 O(n)进苍。 因為我們在每個位置插入元素的概率是一樣的，所以平均情況時間復(fù)雜度為 (1+2+…n)/n=O(n)鸭叙。
如果數(shù)組中的數(shù)據(jù)是有序的觉啊，我們在某個位置插入一個新的元素時，就必須按照剛才的方法搬移 k 之后的數(shù)據(jù)沈贝。但是杠人，如果數(shù)組中存儲的數(shù)據(jù)并沒有任何規(guī)律，數(shù)組只是被當(dāng)作一個存儲數(shù)據(jù)的集合宋下。在這種情況下嗡善，如果要將某個數(shù)組插入到第 k 個位置，為了避免大規(guī)模的數(shù)據(jù)搬移学歧，我們還有一個簡單的辦法就是罩引，直接將第 k 位的數(shù)據(jù)搬移到數(shù)組元素的最后，把新的元素直接放入第 k 個位置枝笨。
為了更好地理解袁铐，我們舉一個例子。假設(shè)數(shù)組 a[10] 中存儲了如下 5 個元素：a横浑，b剔桨，c，d徙融，e洒缀。
利用這種處理技巧，在特定場景下张咳，在第 k 個位置插入一個元素的時間復(fù)雜度就會降為 O(1)帝洪。這個處理思想在快排中也會用到似舵，我會在排序那一節(jié)具體來講，這里就說到這兒葱峡。
我們再來看刪除操作砚哗。
跟插入數(shù)據(jù)類似，如果我們要刪除第 k 個位置的數(shù)據(jù)砰奕，為了內(nèi)存的連續(xù)性蛛芥，也需要搬移數(shù)據(jù)，不然中間就會出現(xiàn)空洞军援，內(nèi)存就不連續(xù)了仅淑。
和插入類似，如果刪除數(shù)組末尾的數(shù)據(jù)胸哥，則最好情況時間復(fù)雜度為 O(1)涯竟；如果刪除開頭的數(shù)據(jù)，則最壞情況時間復(fù)雜度為 O(n)空厌；平均情況時間復(fù)雜度也為 O(n)庐船。
實際上，在某些特殊場景下嘲更，我們并不一定非得追求數(shù)組中數(shù)據(jù)的連續(xù)性筐钟。如果我們將多次刪除操作集中在一起執(zhí)行，刪除的效率是不是會提高很多呢赋朦？
我們繼續(xù)來看例子篓冲。數(shù)組 a[10] 中存儲了 8 個元素：a，b宠哄，c壹将，d，e琳拨，f瞭恰，g，h∮樱現(xiàn)在惊畏，我們要依次刪除 a，b密任，c 三個元素颜启。
為了避免 d，e浪讳，f缰盏，g，h 這幾個數(shù)據(jù)會被搬移三次，我們可以先記錄下已經(jīng)刪除的數(shù)據(jù)口猜。每次的刪除操作并不是真正地搬移數(shù)據(jù)负溪，只是記錄數(shù)據(jù)已經(jīng)被刪除。當(dāng)數(shù)組沒有更多空間存儲數(shù)據(jù)時济炎，我們再觸發(fā)執(zhí)行一次真正的刪除操作川抡，這樣就大大減少了刪除操作導(dǎo)致的數(shù)據(jù)搬移。
如果你了解 JVM须尚，你會發(fā)現(xiàn)崖堤，這不就是 JVM 標(biāo)記清除垃圾回收算法的核心思想嗎？沒錯耐床，數(shù)據(jù)結(jié)構(gòu)和算法的魅力就在于此密幔，很多時候我們并不是要去死記硬背某個數(shù)據(jù)結(jié)構(gòu)或者算法，而是要學(xué)習(xí)它背后的思想和處理技巧撩轰，這些東西才是最有價值的胯甩。如果你細(xì)心留意，不管是在軟件開發(fā)還是架構(gòu)設(shè)計中钧敞，總能找到某些算法和數(shù)據(jù)結(jié)構(gòu)的影子蜡豹。
警惕數(shù)組的訪問越界問題
了解了數(shù)組的幾個基本操作后，我們來聊聊數(shù)組訪問越界的問題溉苛。
首先，我請你來分析一下這段 C 語言代碼的運行結(jié)果：
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;
}
你發(fā)現(xiàn)問題了嗎弄诲？這段代碼的運行結(jié)果并非是打印三行“hello word”愚战，而是會無限打印“hello world”，這是為什么呢齐遵？
因為寂玲，數(shù)組大小為 3，a[0]梗摇，a[1]拓哟，a[2]，而我們的代碼因為書寫錯誤伶授，導(dǎo)致 for 循環(huán)的結(jié)束條件錯寫為了 i<=3 而非 i<3断序，所以當(dāng) i=3 時，數(shù)組 a[3] 訪問越界糜烹。
我們知道违诗，在 C 語言中，只要不是訪問受限的內(nèi)存疮蹦，所有的內(nèi)存空間都是可以自由訪問的诸迟。根據(jù)我們前面講的數(shù)組尋址公式，a[3] 也會被定位到某塊不屬于數(shù)組的內(nèi)存地址上，而這個地址正好是存儲變量 i 的內(nèi)存地址阵苇，那么 a[3]=0 就相當(dāng)于 i=0壁公，所以就會導(dǎo)致代碼無限循環(huán)。
數(shù)組越界在 C 語言中是一種未決行為绅项，并沒有規(guī)定數(shù)組訪問越界時編譯器應(yīng)該如何處理紊册。因為，訪問數(shù)組的本質(zhì)就是訪問一段連續(xù)內(nèi)存趁怔，只要數(shù)組通過偏移計算得到的內(nèi)存地址是可用的湿硝，那么程序就可能不會報任何錯誤。
容器能否完全替代數(shù)組润努？
針對數(shù)組類型关斜，很多語言都提供了容器類，比如 Java 中的 ArrayList铺浇、C++ STL 中的 vector痢畜。在項目開發(fā)中，什么時候適合用數(shù)組鳍侣，什么時候適合用容器呢丁稀？
這里我拿 Java 語言來舉例。如果你是 Java 工程師倚聚，幾乎天天都在用 ArrayList线衫，對它應(yīng)該非常熟悉。那它與數(shù)組相比惑折，到底有哪些優(yōu)勢呢授账？
我個人覺得，ArrayList 最大的優(yōu)勢就是可以將很多數(shù)組操作的細(xì)節(jié)封裝起來惨驶。比如前面提到的數(shù)組插入白热、刪除數(shù)據(jù)時需要搬移其他數(shù)據(jù)等。另外粗卜，它還有一個優(yōu)勢屋确，就是支持動態(tài)擴容。
數(shù)組本身在定義的時候需要預(yù)先指定大小续扔，因為需要分配連續(xù)的內(nèi)存空間攻臀。如果我們申請了大小為 10 的數(shù)組，當(dāng)?shù)?11 個數(shù)據(jù)需要存儲到數(shù)組中時测砂，我們就需要重新分配一塊更大的空間茵烈，將原來的數(shù)據(jù)復(fù)制過去，然后再將新的數(shù)據(jù)插入砌些。
如果使用 ArrayList呜投，我們就完全不需要關(guān)心底層的擴容邏輯加匈，ArrayList 已經(jīng)幫我們實現(xiàn)好了。每次存儲空間不夠的時候仑荐，它都會將空間自動擴容為 1.5 倍大小雕拼。
不過，這里需要注意一點粘招，因為擴容操作涉及內(nèi)存申請和數(shù)據(jù)搬移啥寇，是比較耗時的。所以洒扎，如果事先能確定需要存儲的數(shù)據(jù)大小辑甜，最好在創(chuàng)建 ArrayList 的時候事先指定數(shù)據(jù)大小。
比如我們要從數(shù)據(jù)庫中取出 10000 條數(shù)據(jù)放入 ArrayList袍冷。我們看下面這幾行代碼磷醋，你會發(fā)現(xiàn)，相比之下胡诗，事先指定數(shù)據(jù)大小可以省掉很多次內(nèi)存申請和數(shù)據(jù)搬移操作邓线。
ArrayList<User> users = new ArrayList(10000);
for (int i = 0; i < 10000; ++i) {
? users.add(xxx);
}
作為高級語言編程者，是不是數(shù)組就無用武之地了呢煌恢？當(dāng)然不是骇陈，有些時候，用數(shù)組會更合適些瑰抵，我總結(jié)了幾點自己的經(jīng)驗你雌。
1.Java ArrayList 無法存儲基本類型，比如 int二汛、long匪蝙，需要封裝為 Integer、Long 類习贫，而 Autoboxing、Unboxing 則有一定的性能消耗千元，所以如果特別關(guān)注性能苫昌，或者希望使用基本類型，就可以選用數(shù)組幸海。
2. 如果數(shù)據(jù)大小事先已知祟身，并且對數(shù)據(jù)的操作非常簡單，用不到 ArrayList 提供的大部分方法物独，也可以直接使用數(shù)組袜硫。
3. 還有一個是我個人的喜好，當(dāng)要表示多維數(shù)組時挡篓，用數(shù)組往往會更加直觀婉陷。比如 Object[][] array帚称；而用容器的話則需要這樣定義：ArrayList<ArrayList > array。
我總結(jié)一下秽澳，對于業(yè)務(wù)開發(fā)闯睹，直接使用容器就足夠了，省時省力担神。畢竟損耗一丟丟性能楼吃，完全不會影響到系統(tǒng)整體的性能。但如果你是做一些非常底層的開發(fā)妄讯，比如開發(fā)網(wǎng)絡(luò)框架孩锡，性能的優(yōu)化需要做到極致，這個時候數(shù)組就會優(yōu)于容器亥贸，成為首選躬窜。
解答開篇
現(xiàn)在我們來思考開篇的問題：為什么大多數(shù)編程語言中，數(shù)組要從 0 開始編號砌函，而不是從 1 開始呢斩披？
從數(shù)組存儲的內(nèi)存模型上來看，“下標(biāo)”最確切的定義應(yīng)該是“偏移（offset）”讹俊。前面也講到垦沉，如果用 a 來表示數(shù)組的首地址，a[0] 就是偏移為 0 的位置仍劈，也就是首地址厕倍，a[k] 就表示偏移 k 個 type_size 的位置，所以計算 a[k] 的內(nèi)存地址只需要用這個公式：
a[k]_address = base_address + k * type_size
但是贩疙，如果數(shù)組從 1 開始計數(shù)讹弯，那我們計算數(shù)組元素 a[k] 的內(nèi)存地址就會變?yōu)椋?/p>
a[k]_address = base_address + (k-1)*type_size
對比兩個公式，我們不難發(fā)現(xiàn)这溅，從 1 開始編號组民，每次隨機訪問數(shù)組元素都多了一次減法運算，對于 CPU 來說悲靴，就是多了一次減法指令臭胜。
數(shù)組作為非常基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)癞尚，通過下標(biāo)隨機訪問數(shù)組元素又是其非乘嗜基礎(chǔ)的編程操作，效率的優(yōu)化就要盡可能做到極致浇揩。所以為了減少一次減法操作仪壮，數(shù)組選擇了從 0 開始編號，而不是從 1 開始胳徽。
還有一個歷史原因积锅。C 語言設(shè)計者用 0 開始計數(shù)數(shù)組下標(biāo)爽彤，之后的 Java、JavaScript 等高級語言都效仿了 C 語言乏沸，或者說淫茵，為了在一定程度上減少 C 語言程序員學(xué)習(xí) Java 的學(xué)習(xí)成本，因此繼續(xù)沿用了從 0 開始計數(shù)的習(xí)慣蹬跃。
內(nèi)容小結(jié)? //學(xué)習(xí) 一是總結(jié)
我們今天學(xué)習(xí)了數(shù)組匙瘪。它可以說是最基礎(chǔ)、最簡單的數(shù)據(jù)結(jié)構(gòu)了蝶缀。數(shù)組用一塊連續(xù)的內(nèi)存空間丹喻，來存儲相同類型的一組數(shù)據(jù)，最大的特點就是支持隨機訪問翁都，但插入碍论、刪除操作也因此變得比較低效，平均情況時間復(fù)雜度為 O(n)柄慰。在平時的業(yè)務(wù)開發(fā)中鳍悠，我們可以直接使用編程語言提供的容器類，但是坐搔，如果是特別底層的開發(fā)藏研，直接使用數(shù)組可能會更合適。
課后思考? ?//二是? 舉一反三
前面我基于數(shù)組的原理引出 JVM 的標(biāo)記清除垃圾回收算法的核心理念概行。我不知道你是否使用 Java 語言蠢挡，理解 JVM，如果你熟悉凳忙，可以在評論區(qū)回顧下你理解的標(biāo)記清除垃圾回收算法业踏。
-------轉(zhuǎn)自 王爭
https://time.geekbang.org/column/article/40961
