【深度揭秘】為什么很多語言的數(shù)組下標(biāo)是從0開始的？

作者丨手藝人

來源丨IT爛筆頭

數(shù)組的隨機訪問

盡管大家都知道了什么是數(shù)組，但是還是用官方的術(shù)語描述一下：數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，來存儲一組具有相同類型的數(shù)據(jù)。

我們可以抓住里面的幾個重點詞匯，來充分理解數(shù)組這種結(jié)構(gòu)。 

1、線性表，就是數(shù)據(jù)的排列從前到后順序排列，就像一條線，像隊列、棧列表、數(shù)組等都是線性表結(jié)構(gòu)。 

當(dāng)然有線性表結(jié)構(gòu)就有非線性表結(jié)構(gòu)：

2、連續(xù)內(nèi)存空間和相同的數(shù)據(jù)類型。為啥數(shù)據(jù)訪問一個數(shù)據(jù)效率非常高？那是因為數(shù)組的定義將數(shù)組這種結(jié)構(gòu)定好了規(guī)矩，線性連續(xù)給了我們快速隨機訪問的機會。但是同時也帶來了不好的地方，如果我們向其中插入或者刪除一條數(shù)據(jù)是比較費勁的。 

來看看數(shù)組是怎么實現(xiàn)隨機訪問的？ 

假設(shè)有這么一個數(shù)組：
java int[] a = new int[10]; 
操作系統(tǒng)給分配了一塊連續(xù)的內(nèi)存空間，假設(shè)為1000~1039，那么內(nèi)存的首地址就是base_add = 1000

如果你去走訪親戚，你需要知道的是什么？親戚家的地址吧（具體到門牌號），內(nèi)存也一樣，我們想讀取內(nèi)存里面的數(shù)據(jù)，操作系統(tǒng)也是通過內(nèi)存的地址來訪問的，那么問題來了，內(nèi)存的地址是怎么知道呢？ 

這就涉及到操作系統(tǒng)的尋址，比如我想獲取a[2]的值，那么操作系統(tǒng)先會根據(jù)下面的公式計算對應(yīng)內(nèi)存的地址：

 a[2]的地址 = base_add + 2 * data_unit_size 

dataunitsize表示該數(shù)據(jù)類型每個元素的大小，當(dāng)前是int類型為4個字節(jié)，所以算出來a[2]的地址就是1008 

那是不是可以說數(shù)組的查找的時間復(fù)雜度就是O(1)？當(dāng)然不是了，正常情況下我們查找數(shù)可不是通過下標(biāo)來查找的，我們是通過值來查找的，即便是二分查找時間復(fù)雜度也是O(logn)。 

刪除和插入怎么就低效了

1、插入操作
假設(shè)我們要在長度為n的數(shù)組的第k個位置插入一個數(shù)據(jù)，我們就要講第k~n的數(shù)往后挪，同理如果在最后插入就不需要挪位置，如果在第一個位置插入就要挪n個數(shù)，所以平均時間復(fù)雜度就是：（1+2+3+...+n)/n=O(n)

當(dāng)然，如果不要求插入后順序還保持原來一樣，有個討巧的插入方法就是講第K個元素放到最后，將待插入的數(shù)放到第K個位置。 

舉個例子，假設(shè)數(shù)組 a[10]中存儲了如下 5 個元素：a，b，c，d，e。 

我們現(xiàn)在需要將元素 x 插入到第 3 個位置。我們只需要將 c 放入到 a[5]，將 a[2]賦值為 x 即可。最后，數(shù)組中的元素如下：a，b，x，d，e，c。

2、刪除操作. 

其實和插入操作是相似的，當(dāng)我們對長度為n的數(shù)組的第K個數(shù)組進(jìn)行刪除時，需要對后面的數(shù)據(jù)進(jìn)行向前搬移操作，同理，時間復(fù)雜度和插入一樣也是O(n)，這里就不詳細(xì)介紹了。

當(dāng)然，在不考慮維持連續(xù)性的特殊情況下，為了提高刪除的效率，沒必要每次刪除立即進(jìn)行搬移操作，不然如果連續(xù)刪除數(shù)據(jù)，就要連續(xù)進(jìn)行多次的搬移。比較討巧的辦法是將待刪除的元素進(jìn)行標(biāo)記，實際未做刪除，等等內(nèi)存不足的時候，將這些標(biāo)記的數(shù)據(jù)統(tǒng)一進(jìn)行刪除操作。這樣就會大大減少刪除操作帶來的大量數(shù)據(jù)搬移操作。 

災(zāi)難！數(shù)組越界啦

對于Java來說發(fā)生數(shù)據(jù)越界的時候會拋出異常，但是對于有些語言比如C語言發(fā)生數(shù)組越界的時候并不會給你異常提示，比如下面這段代碼： 

int i = 0; int arr[3] = {0};for(;i<=3;i++) {  arr[i] = 0;  System.out.println("test");  }

顯然定義的是長度為3的數(shù)組，但是循環(huán)條件是<=，所以會訪問到數(shù)組外面的內(nèi)存，而a[3]的地址剛好是存儲i的內(nèi)存，所以當(dāng)循環(huán)到a[3]時又賦值為0，相當(dāng)于i=0;所以這個循環(huán)永遠(yuǎn)結(jié)束不了，“hello world”會一直打印。 

所以，對于C語言來說，如果沒控制好下標(biāo)，發(fā)生數(shù)組越界會出現(xiàn)莫名其妙的邏輯問題，還很難調(diào)試。這也是很多病毒利用數(shù)組越界來非法訪問內(nèi)存來攻擊系統(tǒng)。 

各種容器滿天飛，還需要數(shù)組？

對于Java開發(fā)者來說，ArrayList再熟悉不過了，它為我們封裝好了各種API來操作，比使用數(shù)組方便的多，而且是支持動態(tài)擴容的，因為數(shù)組是要提前訂好大小的，當(dāng)大小不滿足的時候，需要重新定義大的數(shù)組進(jìn)行復(fù)制操作，這顯然很不方便，而容器類是內(nèi)部有動態(tài)的分配的機制，當(dāng)大小不夠的時候自動的擴容，當(dāng)然這也是非常耗性能的。如果能確定數(shù)據(jù)的大小，提前指定容器的大小更好。 

那是不是意味著數(shù)組沒有存在的必要，那也不是的，比如在下面的情況： 

• ArrayList是不能存儲基本數(shù)據(jù)類型的，需要使用他們對應(yīng)的裝箱類，而拆箱和裝箱顯然都是非常耗性能的，如果特別關(guān)注性能，又需要使用基本數(shù)據(jù)類型，使用數(shù)組比使用ArrayList性能更好

• 定義多維數(shù)組時，使用數(shù)組更加的直觀
  

• 如果數(shù)據(jù)大小事先知道，而對數(shù)據(jù)的操作比較簡單。用不到ArrayList的大多API，這時候可以優(yōu)先使用數(shù)組

小結(jié)：對于上層業(yè)務(wù)開發(fā)者，由于業(yè)務(wù)變化大，操作數(shù)據(jù)變化頻繁，使用容器更加方便，犧牲一點性能對系統(tǒng)的整體功能影響不大。但是如果是做比較偏底層的開發(fā)就需要關(guān)注性能了，性能一丁點的提升，影響也是很廣泛的，所以選擇數(shù)組比較合適。

回到主題

為什么數(shù)組從0開始呢？
從數(shù)組存儲的內(nèi)存模型來看，下標(biāo)比較確切的定義是“偏移”，如果用a來表示數(shù)組的首地址，那么a[0]就表示偏移為0的位置。a[x]就表示偏移x個類型大小（int 4個字節(jié)）的的位置。java a[x]_address = base_address + x * data_type_size;

但是如果從1開始計數(shù)呢，那么尋址公式就變成：
java a[x]_address = base_address + (x-1) * data_type_size;  
顯然要多運算減一的操作，對于數(shù)組數(shù)據(jù)結(jié)構(gòu)的定義是偏基礎(chǔ)庫的，對于性能要求當(dāng)然是要追求極致的，多一步和少一步運算都是非常重要的參考點，所以為了更好的性能選擇從0開始而不是從1開始。 

當(dāng)然也有歷史因素，因為最早的C語言設(shè)計者使用從0開始的，所以后面的語言都延續(xù)了這一做法，這樣能減少程序員學(xué)習(xí)語言的成本。當(dāng)然也有一些不是從0開始的語言，這里就不舉例了，感興趣的同學(xué)可以自行去搜索一下。 

總結(jié)

數(shù)組這種數(shù)據(jù)結(jié)構(gòu)對于隨機訪問的效率特別高，但是對于插入和刪除的效率就比較低了，對于業(yè)務(wù)開發(fā)者來說使用容器類比較省時實力，而對于偏底層開發(fā)者來說選擇性能更好的數(shù)組就更合適了。 

-End-

最近有一些小伙伴，讓我?guī)兔φ乙恍?nbsp;面試題 資料，于是我翻遍了收藏的 5T 資料后，匯總整理出來，可以說是程序員面試必備！所有資料都整理到網(wǎng)盤了，歡迎下載！