首先給出答案。
因為數(shù)組中的數(shù)據(jù)是存儲在連續(xù)的內(nèi)存中。
如果我們從0開始編號，那么第n個數(shù)據(jù)的編號就是n-1，此時我們就可以通過如下公式來獲取其位置。其中unitsize為單位數(shù)據(jù)所占用的內(nèi)存大小。
然而如果我們從1開始編號的話，第n個數(shù)據(jù)的編號就是n，計算公式為:
可以明顯看出下式比上式多進行了n-1這個計算，而數(shù)據(jù)的各種計算在計算機底層被大量應(yīng)用，一點點改進都能帶來巨大的性能提高，所以我們采用0作為第一個編號。
如何實現(xiàn)隨機訪問
首先給出數(shù)組的定義:
數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)，它用一組連續(xù)的內(nèi)存空間來存儲具有相同類型的數(shù)據(jù)。
要理解數(shù)組，上面加黑的重點詞是我們首先要攻克的難題。
- 線性表
線性表是數(shù)據(jù)排成一條線一樣的結(jié)構(gòu)。每個線性表上的數(shù)據(jù)最多只有前后兩個方向，除了數(shù)組，隊列、棧、鏈表等也是線性表結(jié)構(gòu)。
線性表.jpg
與線性表對應(yīng)的就是非線性表，如二叉樹、堆、圖等，其特點是數(shù)據(jù)并不是簡單地前后關(guān)系，以樹為例，A結(jié)點除了下面的C結(jié)點為相鄰結(jié)點，還有左邊的B結(jié)點以及右邊的D結(jié)點為相鄰結(jié)點。
非線性表.jpg - 連續(xù)的內(nèi)存空間存儲相同的數(shù)據(jù)類型的數(shù)據(jù)
正是因為這個特征，數(shù)組才有隨機訪問的特性。相同的數(shù)據(jù)類型保證了每個元素在內(nèi)存空間所占據(jù)的空間大小是一樣的。而連續(xù)的內(nèi)存空間則保證了我們可以通過數(shù)組中任一個元素的內(nèi)存位置推算到其他元素的位置。
如圖所示，計算機給這個數(shù)組分配了地址為1000~1039內(nèi)存空間，a[0]的地址為1000，而該數(shù)組中存儲的是int類型的數(shù)據(jù)，每個int占用4byte，所以我們可以通過公式：
來計算任一元素的存儲位置。在該數(shù)組情況下，unitsize的值為4。
還有一個很多人經(jīng)常犯錯的誤區(qū)。
鏈表適合插入、刪除，其時間復雜度為
，數(shù)組適合查找，時間復雜度為
低效的插入刪除
- 插入操作
如果我們給一個數(shù)量為n的數(shù)組插入數(shù)據(jù)，當在數(shù)組末尾插入數(shù)據(jù)的時候，有最好時間復雜度。平均時間復雜度為
- 刪除操作
與插入操作類似，在數(shù)組末尾刪除數(shù)據(jù)的時候為最好時間復雜度
但是在一些情況下我們并不要求數(shù)組中的數(shù)據(jù)具有連續(xù)性，如果我們把需要刪除的數(shù)據(jù)先進行標記，然后達到一定的數(shù)量之后再進行刪除，那么刪除的效率就能夠提高很多。刪除操作.jpg
如圖所示，在達到一定數(shù)量之前，我們進行的刪除操作只是進行標記，等達到數(shù)量之后再一次性刪除移動數(shù)據(jù)。Jvm的標記整理垃圾回收算法就是使用了這種思想。
警惕數(shù)組的訪問越界問題
首先看如下C語言代碼：
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;
}
該代碼的結(jié)果是無限打印hello world。原因是在C語言中，只要不是訪問受限的內(nèi)存，所有的內(nèi)存地址都是能夠訪問的。根據(jù)我們之前的公式，a[3]也是會被定位到某個內(nèi)存地址上，棧是從高位到低位的，所以i和數(shù)組的數(shù)據(jù)從高位到低位地址依次是：i，a[2]，a[1]，a[0]，那么a[3]定位的內(nèi)存地址就是i所在的內(nèi)存地址，所以導致代碼的無限循環(huán)。
數(shù)組越界在C語言中是一種未決問題，并沒有規(guī)定數(shù)組訪問越界時編譯器應(yīng)該如何處理。因為訪問數(shù)組的本質(zhì)就是訪問一段連續(xù)的內(nèi)存地址，只要通過尋址公式得到的內(nèi)存地址是可用的，數(shù)據(jù)就可能不會報任何錯誤。
容器能否完全替代數(shù)組
以Java為例，ArrayList將很多數(shù)組的細節(jié)封裝起來，比如插入刪除等。此外它還支持動態(tài)擴容，當存儲空間不夠的時候，就會擴容到原來的1.5倍。
但是擴容操作涉及到內(nèi)存申請和數(shù)據(jù)搬移，是比較耗時的，所以我們盡量在新建數(shù)組之前確定其大小。
即使容器類有這些優(yōu)點，在以下情況的時候仍然是使用數(shù)組更好：
- ArrayList不能夠存儲基本類型數(shù)據(jù)，需要進行裝箱拆箱等操作，會對性能造成一定的損耗。
- 如果數(shù)據(jù)大小事先直到，并且對數(shù)據(jù)的操作比較簡單，可以使用數(shù)組。
- 表現(xiàn)多維數(shù)組的時候，使用數(shù)組更為直觀。比如Object[][] array；使用容器類需要這樣定義：ArrayList<ArrayList> array。
總結(jié)：如果是做業(yè)務(wù)處理，那么使用容器類就可以，但是如果涉及到對性能特別在意的工作，比如網(wǎng)絡(luò)框架等，還是數(shù)組更優(yōu)于容器。
課后思考
二維數(shù)組的內(nèi)存尋址公式是怎樣的？
例如example[a][b]，其內(nèi)存尋址公式為：
其中n為第一維中數(shù)組的大小。
