數(shù)組內(nèi)存模型
一維數(shù)組
當(dāng)定義一個數(shù)組后
int[] data = new int[5];
1
內(nèi)存模型如圖所示
這種連續(xù)空間的內(nèi)存模型揭示了一個重要特性：隨機(jī)訪問（random access）random access：可以用同等的時間訪問到一組數(shù)據(jù)中的任意一個元素。
我們可以用如下代碼獲取數(shù)組中的值：
data[0]
1
這種從 0 開始進(jìn)行索引的編碼方式被稱為是“Zero-based Indexing”我們可以通過以下公式獲取數(shù)組特定元素：
base_address + index * date_size = target_address
1
此公式保證了，不同的數(shù)組元素達(dá)到的時間是相同的。
二維數(shù)組
一般稱為一維數(shù)組為 向量(Vector) 或 表(Table)，數(shù)學(xué)上稱二維數(shù)組為 矩陣(Matrix)
按照以下代碼聲明一個矩陣：
int[][] data = new int[2][3]
1
基于這個二維數(shù)組，我們是無法確定 data[0][1]的內(nèi)存地址，因為這個問題涉及到二維數(shù)組在內(nèi)存中的尋址方式。其本質(zhì)是 行優(yōu)先（Row-Major Order） 還是 列優(yōu)先（Column-Major Order）
在行優(yōu)先內(nèi)存模型中，每一行的相鄰元素保存在相鄰的連續(xù)內(nèi)存空間中，這個二維數(shù)組內(nèi)存模型如下所示：
我們可以按照以下公式獲取data[i][j]里的元素：
base_address + data_size * (i * number_of_column + j)
1
在列優(yōu)先內(nèi)存模型中，每一列的相鄰元素保存在相鄰的連續(xù)內(nèi)存空間中，這個二維數(shù)組內(nèi)存模型如下所示：
我們可以按照以下公式獲取data[i][j]里的元素：
base_address + data_size * (i * number_of_row + j)
1
CPU 在讀取內(nèi)存數(shù)據(jù)的時候，通常會有一個 CPU 緩存策略。也就是說，在 CPU 讀取程序指定地址的數(shù)值時，CPU 會把和它地址相鄰的一些數(shù)據(jù)也一并讀取并放到更高一級的緩存中，比如 L1 或者 L2 緩存。當(dāng)數(shù)據(jù)存放在這種緩存上的時候，讀取的速度有可能會比直接從內(nèi)存上讀取的速度快 10 倍以上。
數(shù)組特點
高效的訪問和低效的插入刪除
數(shù)組的訪問時間復(fù)雜度是 O(1)
對于保存基本類型（Primitive Type）的數(shù)組來說，它們的內(nèi)存大小在一開始就已經(jīng)確定好了，我們稱它為靜態(tài)數(shù)組（Static Array）。靜態(tài)數(shù)組的大小是無法改變的，所以我們無法對這種數(shù)組進(jìn)行插入或者刪除操作。但是在使用高級語言的時候，比如 JAVA，我們知道 Java 中的 ArrayList 這種 Collection 是提供了像 add 和 remove 這樣的 API 來進(jìn)行插入和刪除操作，這樣的數(shù)組可以稱之為動態(tài)數(shù)組（Dynamic Array）。
為了維持?jǐn)?shù)組內(nèi)存中的連續(xù)性，當(dāng)插入一個數(shù)據(jù)時，需要把待插入節(jié)點及之后所有的數(shù)據(jù)都拷貝，然后給數(shù)組擴(kuò)容，把拷貝的數(shù)據(jù)放入待插入節(jié)點之后，最后再在待插入節(jié)點插入目標(biāo)值。刪除元素同理，所以插入刪除時間復(fù)雜度是 O(n)
