在計算機里，所有的數據結構本質上其實都可以歸為兩類：數組和鏈表。對于鏈表，我將會在第03 與第 04 講中著重講解。今天我將要和你一起探索數據結構中最基本的知識點——數組（Array）。 #### 數組的內存模型 * [ ] 1.一維數組 還記得在學某種編程語言時，寫的第一個程序是“Hello World”嗎？在學數據結構時，數組也是第一個要接觸的知識點，那什么是數組呢？在計算機科學中，數組可以被定義為是一組被保存在連續存儲空間中，并且具有相同類型的數據元素集合。而數組中的每一個元素都可以通過自身的索引（Index）來進行訪問。 那么下面就以 Java 語言中的一個例子來說明一下數組的內存模型，當定義了一個擁有 5 個元素的 int 數組后，來看看內存長什么樣子。 ``` int[] data = new int[5]; ``` 通過上面這段聲明，計算機會在內存中分配一段連續的內存空間給這個 data 數組。現在假設在一個 32 位的機器上運行這段程序，Java 的 int 類型數據占據了 4 個字節的空間，同時也假設計算機分配的地址是從 0x80000000 開始的，整個 data 數組在計算機內存中分配的模型如下圖所示。  這種分配連續空間的內存模型同時也揭示了數組在數據結構中的另外一個特性，即隨機訪問（Random Access）。隨機訪問這個概念在計算機科學中被定義為：可以用同等的時間訪問到一組數據中的任意一個元素。這個特性除了和連續的內存空間模型有關以外，其實也和數組如何通過索引訪問到特定的元素有關。 剛接觸計算機時的你，不知是否會有這樣的一個疑惑：為什么在訪問數組中的第一個元素時，程序一般都是表達成以下這樣的： ``` data[0] ``` 也就是說，數組的第一個元素是通過索引“0”來進行訪問的，第二個元素是通過索引“1”來進行訪問的，……，這種從 0 開始進行索引的編碼方式被稱為是“Zero-based Indexing”。當然了，在計算機世界中也存在著其他的索引編碼方式，像 Visual Basic 中的某些函數索引是采用 1-based Indexing 的，也就是說第一個元素是通過“1”來獲取的，但這并不在我們這一講的討論范圍內，大家可自行查詢資料了解詳情。 我們回到數組中第一個元素通過索引“0”來進行訪問的問題上來，之所以采取這樣的索引方式，原因在于，獲取數組元素的方式是按照以下的公式進行獲取的： ``` base_address + index（索引）× data_size（數據類型大小） ``` 索引在這里可以看作是一個偏移量（Offset），還是以上面的例子來進行說明。  data 這個數組被分配到的起始地址是 0x80000000，是因為 int 類型數據占據了 4 個字節的空間，如果我們要訪問第 5 個元素 data[4] 的時候，按照上面的公式，只需要取得 0x80000000 + 4 × 4 = 0x80000010 這個地址的內容就可以了。隨機訪問的背后原理其實也就是利用了這個公式達到了同等的時間訪問到一組數據中的任意元素。 * [ ] 2.二維數組 上面所提到的數組是屬于一維數組的范疇，我們平時可能還會聽到一維數組的其他叫法，例如，向量（Vector）或者表（Table）。因為在數學上，二維數組可以很好地用來表達矩陣（Matrix）這個概念，所以很多時候我們又會將矩陣或者二維數組這種稱呼交替使用。 如果我們按照下面的方式來聲明一個二維數組： ``` int[][] data = new int[2][3]; ``` 在面試中，如果我們知道了數組的起始地址，在基于上面的二維數組聲明的前提下，data[0][1] 這個元素的內存地址是多少呢？標準的答案其實應該是“無法確定”。什么？標準答案是無法確定，別著急，因為這個問題的答案其實和二維數組在內存中的尋址方式有關。而這其實涉及到計算機內存到底是以行優先（Row-Major Order）還是以列優先（Column-Major Order）存儲的。 假設現在有一個二維數組，如下圖所示：  下面我們來一起看看行優先或列優先的內存模型會造成什么樣的區別。 * （1）行優先 行優先的內存模型保證了每一行的每個相鄰元素都保存在了相鄰的連續內存空間中，對于上面的例子，這個二維數組的內存模型如下圖所示，假設起始地址是 0x80000000：  可以看到，在二維數組的每一行中，每個相鄰元素都保存在了相鄰的連續內存里。 在以行優先存儲的內存模型中，假設我們要訪問 data[i][j] 里的元素，獲取數組元素的方式是按照以下的公式進行獲取的： ``` base_address + data_size × (i × number_of_column + j) ``` 回到一開始的問題里，當我們訪問 data[0][1] 這個值時，可以套用上面的公式，其得到的值，就是我們要找的 0x80000004 地址的值，也是就 2。 ``` 0x80000000 + 4 × (0 × 3 + 1) = 0x80000004 ```  * （2）列優先 列優先的內存模型保證了每一列的每個相鄰元素都保存在了相鄰的連續內存中，對于上面的例子，這個二維數組的內存模型如下圖所示，我們同樣假設起始地址是 0x80000000：  可以看到，在二維數組的每一列中，每個相鄰元素都保存在了相鄰的連續內存里。 在以列優先存儲的內存模型中，假設我們要訪問 data[i][j] 里的元素，獲取數組元素的方式是按照以下的公式進行獲取的： ``` base_address + data_size × (i + number_of_row × j) ``` 當我們訪問 `data[0][1] `這個值時，可以套用上面的公式，其得到的值，就是我們要找的 0x80000008 地址的值，同樣也是 2。 ``` 0x80000000 + 4 × (0 + 2×1) = 0x80000008 ```  所以回到一開始的那個面試問題里，行優先還是列優先存儲方式會造成 data[0][1] 元素的內存地址不一樣。 * [ ] 3.多維數組 多維數組其實本質上和前面介紹的一維數組和二維數組是一樣的。如果我們按照下面的方式來聲明一個三維數組： ``` int[][][] data = new int[2][3][4]; ``` 則可以把這個聲明想象成聲明了兩個 int[3][4] 這樣的二維數組，對于多維數組則可以以此類推。下面我將把行優先和列優先的內存尋址計算方式列出來，若感興趣的話可以將上面所舉的二維數組例子套入公式，自行驗證一下。 假設我們聲明了一個 data[S1][S2][S3].....[Sn] 的多維數組，如果我要訪問 data[D1][D2][D3].....[Dn] 的元素，內存尋址計算方式將按照如下方式尋址： * 行優先 ``` base_address + data_size × (Dn + Sn × (Dn-1 + Sn-1 × (Dn-2 + Sn-2 × (... + S2 × D1)...))) ``` * 列優先 ``` base_address + data_size × (D1 + (S1 × (D2 + S2 × (D3 + S3 × (... + Sn-1 × Dn)...))) ``` 雖然行優先或是列優先這種內存模型對于我們工程師來說是透明的，但是如果我們掌握好了哪種高級語言是采用哪種內存模型的話，這就對于我們來說是很有用的。 我們都知道，CPU 在讀取內存數據的時候，通常會有一個 CPU 緩存策略。也就是說，在 CPU 讀取程序指定地址的數值時，CPU 會把和它地址相鄰的一些數據也一并讀取并放到更高一級的緩存中，比如 L1 或者 L2 緩存。當數據存放在這種緩存上的時候，讀取的速度有可能會比直接從內存上讀取的速度快 10 倍以上。 如果知道了數據存放的內存模型是行優先的話，在設計數據結構的時候，會更傾向于讀取每一行上的數據，因為每一行的數據在內存中都是保存在相鄰位置的，它們更有可能被一起讀取到 CPU 緩存中；反之，我們更傾向于讀取每一列上的數據。 那高級語言中有哪些是行優先又有哪些是列優先呢？我們常用的 C/C++ 和 Objective-C 都是行優先的內存模型，而 Fortran 或者 Matlab 則是列優先的內存模型。 “高效”的訪問與“低效”的插入刪除 從前面的數組內存模型的學習中，我們知道了訪問一個數組中的元素采用的是隨機訪問的方式，只需要按照上面講到的尋址方式來獲取相應位置的數值便可，所以訪問數組元素的時間復雜度是 O(1)。 對于保存基本類型（Primitive Type）的數組來說，它們的內存大小在一開始就已經確定好了，我們稱它為靜態數組（Static Array）。靜態數組的大小是無法改變的，所以我們無法對這種數組進行插入或者刪除操作。但是在使用高級語言的時候，比如 Java，我們知道 Java 中的 ArrayList 這種 Collection 是提供了像 add 和 remove 這樣的 API 來進行插入和刪除操作，這樣的數組可以稱之為動態數組（Dynamic Array）。 我們來一起看看 add 和 remove 函數在 Java Openjdk-jdk11 中的源碼，一起分析它們的時間復雜度。 在 Java Collection 中，底層的數據結構其實還是使用了數組，一般在初始化的時候會分配一個比我們在初始化時設定好的大小更大的空間，以方便以后進行增加元素的操作。 假設所有的元素都保存在 elementData[] 這個數組中，add 函數的主要時間復雜度來自于以下源碼片段。 * [ ] 1.add(int index, E element) 函數源碼 首先來看看 add(int index, E element) 這個函數的源碼。 ([點擊這里查看源代碼](https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/ArrayList.java#L511)) ``` public void add(int index, E element) { ... System.arraycopy(elementData, index, elementData, index + 1, s - index); elementData[index] = element; ... } ``` 可以看到，add 函數調用了一個 System.arraycopy 的函數進行內存操作，s 在這里代表了 ArrayList 的 size。當我們調用 add 函數的時候，函數在實現的過程中到底發生了什么呢？我們來看一個例子。 假設 elementData 里面存放著以下元素：  如果我們調用了 add(1, 4) 函數，也就是在 index 為 1 的地方插入 4 這個元素，在 add 的函數中則會執行 System.arraycopy(elementData, 1, elementData, 2, 6 - 1) 語句，它的意思是將從 elementData 數組 index 為 1 的地址開始，復制往后的 5 個元素到 elementData 數組 index 為 2 的地址位置，如下圖所示：  紅色的部分代表著執行完 System.arraycopy 函數的結果，最后執行 elementData[1] = 4; 這條語句：  因為這里涉及到了每個元素的復制，平均下來的時間復雜度相當于 O(n)。 * [ ] 2.remove(int index) 函數源碼 同理，我們來看看 remove(int index) 這個函數的源碼。（點擊[這里查看源代碼](https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/ArrayList.java#L534)） ``` public void remove(int index) { ... fastRemove(es, index); ... } private void fastRemove(Object[] es, int i) { ... System.arraycopy(es, i + 1, es, i, newSize - i); ... } ``` 這里的 newSize 是指原來 elementData 的 size - 1，當我們調用 remove(1) 會發生什么呢？我們還是以下面的例子來解釋。  如果我們調用了 remove(1) 函數，也就是刪除在 index 為 1 這個地方的元素，在 remove 的函數中則會執行 System.arraycopy(elementData, 1 + 1, elementData, 1, 2) 語句，它的意思是將從 elementData 數組 index 為 2 的地址開始，復制后面的 2 個元素到 elementData 數組 index 為 1 的地址位置，如下圖所示：  因為這里同樣涉及到了每個元素的復制，平均下來時間復雜度相當于 O(n)。 #### 小結 今天我們一起探討了數組這個數據結構的內存模型，知道了讀取數組的時間復雜度為 O(1)，也一起通過分析 Java Openjdk-jdk11，知道了插入和刪除數組元素的時間復雜度為 O(n)。 #### 課后問答 * 1、對于Java的二維數組，本質上還是一維的，每一位中存儲的是另外一個一維數組的地址。上述對于Java多維數組描述錯誤！ 講師回復： “對于Java的二維數組，本質上還是一維的”這個描述是對的。“每一位中存儲的是另外一個一維數組的地址”這個不太恰當，本質上不會存數組的地址 * 2、java是列優先還是行優先？ 講師回復： ava的情況比較特殊，它既不是行優先也不是列優先，一般在Java聲明了一個二維數組，實際上內存并不是連續分配的，而是保存了多個不同的一維數組的首地址 * 3、對于java的多維數組，是不是在數組對象的對象頭中保存了多個一維數組的首地址 講師回復： 理解得十分正確，以二維數組為例，數組對象從起始地址開始都保存著每個元素里一維數組的起始地址。如果是三位數組的話，數組對象從起始地址開始都保存著每個元素里二維數組的起始地址，這樣遞歸回去。