數組（Array）是一種線性表數據結構。它用一組連續(xù)的內存空間，來存儲一組具有相同類型的數據。
- 關鍵詞一：線性表
- 關鍵詞二：連續(xù)的內存空間 和 相同類型的數據
正是因為這兩個限制，它才有了一個堪稱“殺手锏”的特性：“隨機訪問”。但有利就有弊，這兩個限制也讓數組的很多操作變得非常低效，比如要想在數組中刪除、插入一個數據，為了保證連續(xù)性，就需要做大量的數據搬移工作。
數組是如何實現根據下標隨機訪問數組元素的？
計算機會給每個內存單元分配一個地址，計算機通過下標計算出地址，然后來訪問內存中的數據。
a[i]_address = base_address + i * data_type_size
data_type_size：數組中每個元素的大小
面試細節(jié) 01
問：數組和鏈表的區(qū)別
誤答：鏈表適合插入、刪除，時間復雜度 O(1)；數組適合查找，查找時間復雜度為 O(1)
正答：數組支持隨機訪問，根據下標隨機訪問的時間復雜度為 O(1)
低效的“插入”和“刪除”
數組為了保持內存數據的連續(xù)性，會導致插入、刪除這兩個操作比較低效，平均時間復雜度都為 O(n)。
- 但是，如果數組中存儲的數據并沒有任何規(guī)律，數組只是被當作一個存儲數據的集合。在這種情況下，如果要將某個數組插入到第 k 個位置，為了避免大規(guī)模的數據搬移，我們還有一個簡單的辦法就是直接將第 k 位的數據搬移到數組元素的最后，把新的元素直接放入第 k 個位置。這個處理思想在快排中也會用到。形象圖如下：
- 實際上，在某些特殊場景下，我們并不一定非得追求數組中數據的連續(xù)性。如果我們將多次刪除操作集中在一起執(zhí)行，刪除的效率是不是更高？看下圖例子：
數組 a[10] 中存儲了 8 個元素：a，b，c，d，e，f，g，h?，F在，我們要依次刪除 a，b，c 三個元素。為了避免 d，e，f，g，h 這幾個數據會被搬移三次，我們可以先記錄下已經刪除的數據。每次的刪除操作并不是真正地搬移數據，只是記錄數據已經被刪除。當數組沒有更多空間存儲數據時，我們再觸發(fā)執(zhí)行一次真正的刪除操作，這樣就大大減少了刪除操作導致的數據搬移。這也是JVM 標記清除垃圾回收算法的核心思想。
警惕數組的訪問越界問題
先來分析一下這段 C 語言代碼的運行結果：
#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;
}
運行結果并非是打印三行“hello word”，而是會無限打印“hello world”。
數組越界在 C 語言中是一種未決行為，并沒有規(guī)定數組訪問越界時編譯器應該如何處理。因為訪問數組的本質就是訪問一段連續(xù)內存，只要數組通過偏移計算得到的內存地址是可用的，那么程序就可能不會報任何錯誤。
根據我們前面講的數組尋址公式，a[3] 也會被定位到某塊不屬于數組的內存地址上，而這個地址正好是存儲變量i 的內存地址，那么 a[3]=0 就相當于 i=0，所以會導致代碼無限循環(huán)。
這種情況下，一般都會出現莫名其妙的邏輯錯誤，就像我們剛剛舉的那個例子，debug 的難度非常的大。而且，很多計算機病毒也正是利用到了代碼中的數組越界可以訪問非法地址的漏洞，來攻擊系統，所以寫代碼的時候一定要警惕數組越界。
但并非所有的語言都像 C 一樣，把數組越界檢查的工作丟給程序員來做，像 Java 本身就會做越界檢查。
容器能否完全替代數組？
針對數組類型，很多語言都提供了容器類，比如 Java 中的 ArrayList、C++ STL 中的 vector。在項目開發(fā)中什么時候適合用數組，什么時候適合用容器呢？
拿 Java 語言來舉例，ArrayList 與數組相比最大的優(yōu)勢就是可以將很多數組操作的細節(jié)封裝起來和支持動態(tài)擴容。
數組本身在定義的時候需要預先指定大小，因為需要分配連續(xù)的內存空間。如果我們申請了大小為 10 的數組，當第 11 個數據需要存儲到數組中時，我們就需要重新分配一塊更大的空間，將原來的數據復制過去，然后再將新的數據插入。
如果使用 ArrayList，我們就完全不需要關心底層的擴容邏輯，ArrayList 已經幫我們實現好了。每次存儲空間不夠的時候，它都會將空間自動擴容為 1.5 倍大小。
不過，這里需要注意一點，因為擴容操作涉及內存申請和數據搬移，是比較耗時的。所以，如果事先能確定需要存儲的數據大小，最好在創(chuàng)建 ArrayList 的時候事先指定數據大小。
哪些情況下用數組更合適呢？
Java ArrayList 無法存儲基本類型，比如 int、long，需要封裝為 Integer、Long 類，而Autoboxing、Unboxing 則有一定的性能消耗，所以如果特別關注性能，或者希望使用基本類型，就可以選用數組。
如果數據大小事先已知，并且對數據的操作非常簡單，用不到 ArrayList 提供的大部分方法，也可以直接使用數組。
還有一個是我個人的喜好，當要表示多維數組時，用數組往往會更加直觀。比如 Object[][] array；而用容器的話則需要這樣定義：ArrayList<ArrayList> array。
小總結：對于業(yè)務開發(fā)，直接使用容器就足夠了，省時省力。畢竟損耗一丟丟性能，完全不會影響到系統整體的性能。但如果你是做一些非常底層的開發(fā)，比如開發(fā)網絡框架，性能的優(yōu)化需要做到極致，這個時候數組就會優(yōu)于容器，成為首選。
標題解答
為什么大多數編程語言中，數組要從 0 開始編號，而不是從 1 開始呢？
下標從 0 開始：
a[k]_address = base_address + k * type_size
下標從 1 開始：a[k]_address = base_address + (k-1) * type_size
- 效率原因。數組從 1 開始編號，每次隨機訪問數組元素都多了一次減法運算，對于 CPU 來說，就是多了一次減法指令。
數組作為非?；A的數據結構，通過下標隨機訪問數組元素又是其非?；A的編程操作，效率的優(yōu)化就要盡可能做到極致。所以為了減少一次減法操作，數組選擇了從 0 開始編號，而不是從 1 開始。
- 最主要的可能是歷史原因。C 語言設計者用 0 開始計數數組下標，為了在一定程度上減少 C 語言程序員學習其他語言的學習成本，其他后來語言(Java、JavaScript...)也繼續(xù)沿用了從 0 開始計數的習慣實際上，很多語言中數組也并不是從 0 開始計數的，比如 Matlab。甚至還有一些語言支持負數下標，比如 Python。
課后思考
- 你怎么理解JVM 的標記清除垃圾回收算法？
大多數主流虛擬機采用可達性分析算法來判斷對象是否存活。在標記階段，會遍歷所有 GC ROOTS，將所有 GC ROOTS 可達的對象標記為存活。只有當標記工作完成后，清理工作才會開始，在清除階段會遍歷堆，回收那些沒有被標記的對象。
缺點是會產生內存碎片，很有可能導致下一次分配一塊連續(xù)較大的內存空間時，由于找不到合適的，又觸發(fā)一次垃圾回收操作，一般試用于老年代的回收。
- 類比一維數組的內存尋址公式，二維數組的內存尋址公式是什么？
對于 m * n 的數組，a [ i ][ j ] (i < m，j < n)的地址為：
address = base_address + ( i * n + j) * type_size
