提到數(shù)組牢硅，我想你肯定不陌生，甚至還會自信地說芝雪，它很簡單啊减余。

是的，在每一種編程語言中惩系，基本都會有數(shù)組這種數(shù)據(jù)類型位岔。不過如筛，它不僅僅是一種編程語言中的數(shù)據(jù)類型，還是一種最基礎的數(shù)據(jù)結構抒抬。盡管數(shù)組看起來非常

基礎妙黍、簡單，但是我估計很多人都并沒有理解這個基礎數(shù)據(jù)結構的精髓瞧剖。

在大部分編程語言中拭嫁，數(shù)組都是從0開始編號的，但你是否下意識地想過抓于，為什么數(shù)組要從0開始編號做粤，而不是從1開始呢？ 從1開始不是更符合人類的思維習慣

嗎捉撮？

你可以帶著這個問題來學習接下來的內(nèi)容怕品。

如何實現(xiàn)隨機訪問？

什么是數(shù)組巾遭？我估計你心中已經(jīng)有了答案肉康。不過，我還是想用專業(yè)的話來給你做下解釋灼舍。數(shù)組（Array）是一種線性表數(shù)據(jù)結構吼和。它用一組連續(xù)的內(nèi)存空間，來存

儲一組具有相同類型的數(shù)據(jù)骑素。

這個定義里有幾個關鍵詞炫乓，理解了這幾個關鍵詞，我想你就能徹底掌握數(shù)組的概念了献丑。下面就從我的角度分別給你 “ 點撥 ” 一下末捣。

第一是線性表（Linear List）。顧名思義创橄，線性表就是數(shù)據(jù)排成像一條線一樣的結構箩做。每個線性表上的數(shù)據(jù)最多只有前和后兩個方向。其實除了數(shù)組妥畏，鏈表邦邦、隊

列、棧等也是線性表結構咖熟。

而與它相對立的概念是非線性表圃酵，比如二叉樹、堆馍管、圖等郭赐。之所以叫非線性，是因為，在非線性表中捌锭，數(shù)據(jù)之間并不是簡單的前后關系俘陷。

第二個是連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)。正是因為這兩個限制观谦，它才有了一個堪稱“殺手锏”的特性：“隨機訪問”拉盾。但有利就有弊，這兩個限制也讓數(shù)組的很多

操作變得非常低效豁状，比如要想在數(shù)組中刪除捉偏、插入一個數(shù)據(jù)，為了保證連續(xù)性泻红，就需要做大量的數(shù)據(jù)搬移工作夭禽。

說到數(shù)據(jù)的訪問，那你知道數(shù)組是如何實現(xiàn)根據(jù)下標隨機訪問數(shù)組元素的嗎谊路？

我們拿一個長度為 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ù)喉恋。當計算機需要隨機訪問數(shù)組中的某個元素時沃饶，它會首先通過下面的尋

址公式母廷，計算出該元素存儲的內(nèi)存地址：

a[i]_address = base_address + i * data_type_size

其中 data_type_size 表示數(shù)組中每個元素的大小轻黑。我們舉的這個例子里，數(shù)組中存儲的是 int 類型數(shù)據(jù)琴昆，所以 data_type_size 就為 4 個字節(jié)氓鄙。這個公式非常簡單，我就不

多做解釋了业舍。

這里我要特別糾正一個 “ 錯誤 ” 抖拦。我在面試的時候，常常會問數(shù)組和鏈表的區(qū)別舷暮，很多人都回答說态罪， “ 鏈表適合插入、刪除下面，時間復雜度 O(1) 复颈；數(shù)組適合查找，查找

時間復雜度為 O(1)” 沥割。

實際上耗啦，這種表述是不準確的凿菩。數(shù)組是適合查找操作，但是查找的時間復雜度并不為 O(1) 帜讲。即便是排好序的數(shù)組衅谷，你用二分查找，時間復雜度也是 O(logn) 似将。所

以获黔，正確的表述應該是，數(shù)組支持隨機訪問在验，根據(jù)下標隨機訪問的時間復雜度為 O(1) 肢执。

低效的 “ 插入 ” 和 “ 刪除 ”

前面概念部分我們提到，數(shù)組為了保持內(nèi)存數(shù)據(jù)的連續(xù)性译红，會導致插入预茄、刪除這兩個操作比較低效。現(xiàn)在我們就來詳細說一下侦厚，究竟為什么會導致低效耻陕？又有哪

些改進方法呢？

我們先來看插入操作刨沦。

假設數(shù)組的長度為 n 诗宣，現(xiàn)在，如果我們需要將一個數(shù)據(jù)插入到數(shù)組中的第 k 個位置想诅。為了把第 k 個位置騰出來召庞，給新來的數(shù)據(jù)，我們需要將第 k ～ n 這部分的元素都順

序地往后挪一位来破。那插入操作的時間復雜度是多少呢篮灼？你可以自己先試著分析一下。

如果在數(shù)組的末尾插入元素徘禁，那就不需要移動數(shù)據(jù)了诅诱，這時的時間復雜度為 O(1) 。但如果在數(shù)組的開頭插入元素送朱，那所有的數(shù)據(jù)都需要依次往后移動一位娘荡，所以

最壞時間復雜度是 O(n) 。 因為我們在每個位置插入元素的概率是一樣的驶沼，所以平均情況時間復雜度為 (1+2+…n)/n=O(n) 炮沐。

如果數(shù)組中的數(shù)據(jù)是有序的，我們在某個位置插入一個新的元素時回怜，就必須按照剛才的方法搬移 k 之后的數(shù)據(jù)大年。但是，如果數(shù)組中存儲的數(shù)據(jù)并沒有任何規(guī)律，數(shù)

組只是被當作一個存儲數(shù)據(jù)的集合鲜戒。在這種情況下专控，如果要將某個數(shù)組插入到第 k 個位置，為了避免大規(guī)模的數(shù)據(jù)搬移遏餐，我們還有一個簡單的辦法就是伦腐，直接將

第 k 位的數(shù)據(jù)搬移到數(shù)組元素的最后，把新的元素直接放入第 k 個位置失都。

為了更好地理解柏蘑，我們舉一個例子。假設數(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 。

利用這種處理技巧播掷，在特定場景下审编，在第 k 個位置插入一個元素的時間復雜度就會降為 O(1) 。這個處理思想在快排中也會用到叮趴，我會在排序那一節(jié)具體來講割笙，這里

就說到這兒。

我們再來看刪除操作眯亦。

跟插入數(shù)據(jù)類似，如果我們要刪除第 k 個位置的數(shù)據(jù)般码，為了內(nèi)存的連續(xù)性妻率，也需要搬移數(shù)據(jù)，不然中間就會出現(xiàn)空洞板祝，內(nèi)存就不連續(xù)了宫静。

和插入類似，如果刪除數(shù)組末尾的數(shù)據(jù)，則最好情況時間復雜度為 O(1) 孤里；如果刪除開頭的數(shù)據(jù)伏伯，則最壞情況時間復雜度為 O(n) ；平均情況時間復雜度也為 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)被刪除。當數(shù)

組沒有更多空間存儲數(shù)據(jù)時愈涩，我們再觸發(fā)執(zhí)行一次真正的刪除操作望抽，這樣就大大減少了刪除操作導致的數(shù)據(jù)搬移。

如果你了解JVM履婉，你會發(fā)現(xiàn)煤篙，這不就是JVM標記清除垃圾回收算法的核心思想嗎？沒錯毁腿，數(shù)據(jù)結構和算法的魅力就在于此辑奈，很多時候我們并不是要去死記硬背某

個數(shù)據(jù)結構或者算法苛茂，而是要學習它背后的思想和處理技巧，這些東西才是最有價值的鸠窗。如果你細心留意妓羊，不管是在軟件開發(fā)還是架構設計中，總能找到某些算

法和數(shù)據(jù)結構的影子稍计。

警惕數(shù)組的訪問越界問題

了解了數(shù)組的幾個基本操作后躁绸，我們來聊聊數(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;

}

你發(fā)現(xiàn)問題了嗎涨颜？這段代碼的運行結果并非是打印三行 “hello word” ，而是會無限打印 “hello world” 茧球，這是為什么呢庭瑰？

因為，數(shù)組大小為 3 抢埋， a[0] 弹灭， a[1] ， a[2] 揪垄，而我們的代碼因為書寫錯誤穷吮，導致 for 循環(huán)的結束條件錯寫為了 i<=3 而非 i<3 ，所以當 i=3 時饥努，數(shù)組 a[3] 訪問越界捡鱼。

我們知道，在 C 語言中酷愧，只要不是訪問受限的內(nèi)存驾诈，所有的內(nèi)存空間都是可以自由訪問的。根據(jù)我們前面講的數(shù)組尋址公式溶浴， a[3] 也會被定位到某塊不屬于數(shù)組的

內(nèi)存地址上乍迄，而這個地址正好是存儲變量 i 的內(nèi)存地址，那么 a[3]=0 就相當于 i=0 士败，所以就會導致代碼無限循環(huán)闯两。

05|數(shù)組：為什么很多編程語言中數(shù)組都從0開始編號？

file:///F/temp/geektime/數(shù)據(jù)結構與算法之美/05數(shù)組：為什么很多編程語言中數(shù)組都從0開始編號谅将？.html[2019/1/15 15:35:15]

數(shù)組越界在 C 語言中是一種未決行為漾狼，并沒有規(guī)定數(shù)組訪問越界時編譯器應該如何處理。因為戏自，訪問數(shù)組的本質(zhì)就是訪問一段連續(xù)內(nèi)存邦投，只要數(shù)組通過偏移計算得

到的內(nèi)存地址是可用的，那么程序就可能不會報任何錯誤擅笔。

這種情況下志衣，一般都會出現(xiàn)莫名其妙的邏輯錯誤，就像我們剛剛舉的那個例子猛们， debug 的難度非常的大念脯。而且，很多計算機病毒也正是利用到了代碼中的數(shù)組越界

可以訪問非法地址的漏洞弯淘，來攻擊系統(tǒng)绿店，所以寫代碼的時候一定要警惕數(shù)組越界。

但并非所有的語言都像 C 一樣庐橙，把數(shù)組越界檢查的工作丟給程序員來做假勿，像 Java 本身就會做越界檢查，比如下面這幾行 Java 代碼态鳖，就會拋

出 java.lang.ArrayIndexOutOfBoundsException 转培。

int[] a = new int[3];

a[3] = 10;

容器能否完全替代數(shù)組？

針對數(shù)組類型浆竭，很多語言都提供了容器類浸须，比如 Java 中的 ArrayList 、 C++ STL 中的 vector 邦泄。在項目開發(fā)中删窒，什么時候適合用數(shù)組，什么時候適合用容器呢顺囊？

這里我拿 Java 語言來舉例肌索。如果你是 Java 工程師，幾乎天天都在用 ArrayList 特碳，對它應該非常熟悉诚亚。那它與數(shù)組相比，到底有哪些優(yōu)勢呢测萎？

我個人覺得亡电，ArrayList最大的優(yōu)勢就是可以將很多數(shù)組操作的細節(jié)封裝起來。比如前面提到的數(shù)組插入硅瞧、刪除數(shù)據(jù)時需要搬移其他數(shù)據(jù)等份乒。另外，它還有一個優(yōu)

勢腕唧，就是支持動態(tài)擴容或辖。

數(shù)組本身在定義的時候需要預先指定大小，因為需要分配連續(xù)的內(nèi)存空間枣接。如果我們申請了大小為 10 的數(shù)組颂暇，當?shù)?11 個數(shù)據(jù)需要存儲到數(shù)組中時，我們就需要重

新分配一塊更大的空間但惶，將原來的數(shù)據(jù)復制過去耳鸯，然后再將新的數(shù)據(jù)插入湿蛔。

如果使用 ArrayList ，我們就完全不需要關心底層的擴容邏輯县爬， 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ù)組就無用武之地了呢？當然不是叠殷，有些時候改鲫，用數(shù)組會更合適些，我總結了幾點自己的經(jīng)驗林束。

1.Java ArrayList 無法存儲基本類型像棘，比如 int 、 long 壶冒，需要封裝為 Integer 缕题、 Long 類，而 Autoboxing 胖腾、 Unboxing 則有一定的性能消耗烟零，所以如果特別關注性能，或者希

望使用基本類型咸作，就可以選用數(shù)組锨阿。

2. 如果數(shù)據(jù)大小事先已知，并且對數(shù)據(jù)的操作非常簡單记罚，用不到 ArrayList 提供的大部分方法墅诡，也可以直接使用數(shù)組。

3.還有一個是我個人的喜好桐智，當要表示多維數(shù)組時末早，用數(shù)組往往會更加直觀烟馅。比如Object[][] array；而用容器的話則需要這樣定義：ArrayList<ArrayList > array荐吉。

我總結一下焙糟，對于業(yè)務開發(fā)口渔，直接使用容器就足夠了样屠，省時省力。畢竟損耗一丟丟性能缺脉，完全不會影響到系統(tǒng)整體的性能痪欲。但如果你是做一些非常底層的開發(fā)，

比如開發(fā)網(wǎng)絡框架攻礼，性能的優(yōu)化需要做到極致业踢，這個時候數(shù)組就會優(yōu)于容器，成為首選礁扮。

05|數(shù)組：為什么很多編程語言中數(shù)組都從0開始編號知举？

file:///F/temp/geektime/數(shù)據(jù)結構與算法之美/05數(shù)組：為什么很多編程語言中數(shù)組都從0開始編號？.html[2019/1/15 15:35:15]

解答開篇

現(xiàn)在我們來思考開篇的問題：為什么大多數(shù)編程語言中太伊，數(shù)組要從 0 開始編號雇锡，而不是從 1 開始呢？

從數(shù)組存儲的內(nèi)存模型上來看僚焦， “ 下標 ” 最確切的定義應該是 “ 偏移（ 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ù)組作為非匙兀基礎的數(shù)據(jù)結構淋纲，通過下標隨機訪問數(shù)組元素又是其非常基礎的編程操作院究，效率的優(yōu)化就要盡可能做到極致洽瞬。所以為了減少一次減法操作本涕，數(shù)組選

擇了從 0 開始編號，而不是從 1 開始伙窃。

不過我認為菩颖，上面解釋得再多其實都算不上壓倒性的證明，說數(shù)組起始編號非 0 開始不可为障。所以我覺得最主要的原因可能是歷史原因晦闰。

C 語言設計者用 0 開始計數(shù)數(shù)組下標，之后的 Java 鳍怨、 JavaScript 等高級語言都效仿了 C 語言呻右，或者說，為了在一定程度上減少 C 語言程序員學習 Java 的學習成本鞋喇，因此

繼續(xù)沿用了從 0 開始計數(shù)的習慣声滥。實際上，很多語言中數(shù)組也并不是從 0 開始計數(shù)的侦香，比如 Matlab 落塑。甚至還有一些語言支持負數(shù)下標，比如 Python