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

數(shù)組（Array）是一種線性表數(shù)據(jù)結構。它用一組連續(xù)的內存空間，來存儲一組具有相同類型的數(shù)據(jù)。

1. 第一是線性表（Linear List）。
   顧名思義，線性表就是數(shù)據(jù)排成像一條線一樣的結構。每個線性表上的數(shù)據(jù)最多只有前和后兩個方向。其實除了數(shù)組，鏈表、隊列、棧等也是線性表結構。
   
   image

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

image

2. 第二個是連續(xù)的內存空間和相同類型的數(shù)據(jù)。
   正是因為這兩個限制，它才有了一個堪稱“殺手锏”的特性：“隨機訪問”。但有利就有弊，這兩個限制也讓數(shù)組的很多操作變得非常低效，比如要想在數(shù)組中刪除、插入一個數(shù)據(jù)，為了保證連續(xù)性，就需要做大量的數(shù)據(jù)搬移工作。

數(shù)組是如何實現(xiàn)根據(jù)下標隨機訪問數(shù)組元素的?

我們拿一個長度為 10 的 int 類型的數(shù)組 int[] a = new int[10] 來舉例。在我畫的這個圖中，計算機給數(shù)組 a[10]，分配了一塊連續(xù)內存空間 1000～1039，其中，內存塊的首地址為 base_address = 1000。

image

我們知道，計算機會給每個內存單元分配一個地址，計算機通過地址來訪問內存中的數(shù)據(jù)。當計算機需要隨機訪問數(shù)組中的某個元素時，它會首先通過下面的尋址公式，計算出該元素存儲的內存地址：

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，現(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。

image

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

刪除操作

跟插入數(shù)據(jù)類似，如果我們要刪除第 k 個位置的數(shù)據(jù)，為了內存的連續(xù)性，也需要搬移數(shù)據(jù)，不然中間就會出現(xiàn)空洞，內存就不連續(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?，F(xiàn)在，我們要依次刪除 a，b，c 三個元素。

image

為了避免 d，e，f，g，h 這幾個數(shù)據(jù)會被搬移三次，我們可以先記錄下已經刪除的數(shù)據(jù)。每次的刪除操作并不是真正地搬移數(shù)據(jù)，只是記錄數(shù)據(jù)已經被刪除。當數(shù)組沒有更多空間存儲數(shù)據(jù)時，我們再觸發(fā)執(zhí)行一次真正的刪除操作，這樣就大大減少了刪除操作導致的數(shù)據(jù)搬移。

如果你了解 JVM，你會發(fā)現(xiàn)，這不就是 JVM 標記清除垃圾回收算法的核心思想嗎？沒錯，數(shù)據(jù)結構和算法的魅力就在于此，很多時候我們并不是要去死記硬背某個數(shù)據(jù)結構或者算法，而是要學習它背后的思想和處理技巧，這些東西才是最有價值的。如果你細心留意，不管是在軟件開發(fā)還是架構設計中，總能找到某些算法和數(shù)據(jù)結構的影子。

JVM標記清除算法：
大多數(shù)主流虛擬機采用可達性分析算法來判斷對象是否存活，在標記階段，會遍歷所有 GC ROOTS，將所有 GC ROOTS 可達的對象標記為存活。只有當標記工作完成后，清理工作才會開始。
不足：1.效率問題。標記和清理效率都不高，但是當知道只有少量垃圾產生時會很高效。2.空間問題。會產生不連續(xù)的內存空間碎片。

警惕數(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;
}

• 問題：無限打印“hello world”
• 原因：數(shù)組大小為 3，a[0]，a[1]，a[2]，而我們的代碼因為書寫錯誤，導致 for 循環(huán)的結束條件錯寫為了 i<=3 而非 i<3，所以當 i=3 時，數(shù)組 a[3] 訪問越界。

我們知道，在 C 語言中，只要不是訪問受限的內存，所有的內存空間都是可以自由訪問的。根據(jù)我們前面講的數(shù)組尋址公式，a[3] 也會被定位到某塊不屬于數(shù)組的內存地址上，而這個地址正好是存儲變量 i 的內存地址，那么 a[3]=0 就相當于 i=0，所以就會導致代碼無限循環(huán)。

數(shù)組越界在 C 語言中是一種未決行為，并沒有規(guī)定數(shù)組訪問越界時編譯器應該如何處理。因為，訪問數(shù)組的本質就是訪問一段連續(xù)內存，只要數(shù)組通過偏移計算得到的內存地址是可用的，那么程序就可能不會報任何錯誤。

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

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

數(shù)組本身在定義的時候需要預先指定大小，因為需要分配連續(xù)的內存空間。如果我們申請了大小為 10 的數(shù)組，當?shù)?11 個數(shù)據(jù)需要存儲到數(shù)組中時，我們就需要重新分配一塊更大的空間，將原來的數(shù)據(jù)復制過去，然后再將新的數(shù)據(jù)插入。

如果使用 ArrayList，我們就完全不需要關心底層的擴容邏輯，ArrayList 已經幫我們實現(xiàn)好了。每次存儲空間不夠的時候，它都會將空間自動擴容為 1.5 倍大小。

不過，這里需要注意一點，因為擴容操作涉及內存申請和數(shù)據(jù)搬移，是比較耗時的。所以，如果事先能確定需要存儲的數(shù)據(jù)大小，最好在創(chuàng)建 ArrayList 的時候事先指定數(shù)據(jù)大小。

比如我們要從數(shù)據(jù)庫中取出 10000 條數(shù)據(jù)放入 ArrayList。我們看下面這幾行代碼，你會發(fā)現(xiàn)，相比之下，事先指定數(shù)據(jù)大小可以省掉很多次內存申請和數(shù)據(jù)搬移操作。

ArrayList<User> users = new ArrayList(10000);
for (int i = 0; i < 10000; ++i) {
  users.add(xxx);
}

作為高級語言編程者，是不是數(shù)組就無用武之地了呢？當然不是，有些時候，用數(shù)組會更合適些，我總結了幾點自己的經驗。

• 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)于容器，成為首選。

為什么大多數(shù)編程語言中，數(shù)組要從 0 開始編號，而不是從 1 開始呢？

從數(shù)組存儲的內存模型上來看，“下標”最確切的定義應該是“偏移（offset）”。前面也講到，如果用 a 來表示數(shù)組的首地址，a[0] 就是偏移為 0 的位置，也就是首地址，a[k] 就表示偏移 k 個 type_size 的位置，所以計算 a[k] 的內存地址只需要用這個公式：

a[k]_address = base_address + k * type_size

但是，如果數(shù)組從 1 開始計數(shù)，那我們計算數(shù)組元素 a[k] 的內存地址就會變?yōu)椋?/p>

a[k]_address = base_address + (k-1)*type_size

對比兩個公式，我們不難發(fā)現(xiàn)，從 1 開始編號，每次隨機訪問數(shù)組元素都多了一次減法運算，對于 CPU 來說，就是多了一次減法指令。

數(shù)組作為非?；A的數(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。

內容小節(jié)

我們今天學習了數(shù)組。它可以說是最基礎、最簡單的數(shù)據(jù)結構了。數(shù)組用一塊連續(xù)的內存空間，來存儲相同類型的一組數(shù)據(jù)，最大的特點就是支持隨機訪問，但插入、刪除操作也因此變得比較低效，平均情況時間復雜度為 O(n)。在平時的業(yè)務開發(fā)中，我們可以直接使用編程語言提供的容器類，但是，如果是特別底層的開發(fā)，直接使用數(shù)組可能會更合適。

二維數(shù)組內存尋址：
對于 m * n 的數(shù)組，a [ i ][ j ] (i < m,j < n)的地址為：
address = base_address + ( i * n + j) * type_size
另外，對于數(shù)組訪問越界造成無限循環(huán)，我理解是編譯器的問題，對于不同的編譯器，在內存分配時，會按照內存地址遞增或遞減的方式進行分配。老師的程序，如果是內存地址遞減的方式，就會造成無限循環(huán)。

個人小結

數(shù)組用來儲存相同類型的數(shù)據(jù)，且內存是連續(xù)的，線性表數(shù)據(jù)結構。
方便訪問，但是對于刪除和插入效果不好。

隨機尋址：
a[i]_address = base_address + i * data_type_size

刪除和插入要進行移位操作，可以優(yōu)化的是，先處理完數(shù)據(jù)，最后再進行移位，和jvm垃圾回收機制類似。

一般情況可以用ArrayList來替代數(shù)組，它的好處是支持動態(tài)擴容和封裝了插入刪除等操作，沒有空間時它都會將空間自動擴容為 1.5 倍大小。

至于為什么從0開始，猜想
一是因為C語言和很多語言都是從0開始，為了學習成本數(shù)組也從0開始。
二是如果從1開始，內存地址就會成為a[k]_address = base_address + (k-1)*type_size，則會多一次減法運算，為了CPU性能，則從0開始計數(shù)。