簡介
陣列本質上是一種線性表資料結構，它用一組連續的記憶體空間，來存盤一組具有相同型別的資料，
線性表
如上圖所示，線性表就是資料排成一條線一樣的結構，因此每個線性表中的資料只有前后兩個方向，像陣列、鏈表、堆疊、佇列都是線性表結構，
與線性表對應的就是非線性表結構，非線性表中的資料會存在多個方向，資料之間不是簡單的前后關系，像樹、堆都是非線性表結構，
連續的記憶體空間
陣列存盤使用的記憶體空間是連續的，在陣列存盤的這一片空間只會存盤陣列元素，不會再拆分出來存盤其他的資料，
相同型別的資料
在陣列的原始定義中，陣列只能存盤相同型別的資料，這樣可以保證陣列中每個元素占用的記憶體空間都能保持一致，
正是陣列存在“連續的記憶體空間”和“相同型別的資料”這兩個限制，才讓它擁有了隨機存取這個高效的特性，但同時也使得陣列在插入、洗掉資料的時候會比較低效，
陣列的特性
就陣列增刪改查的操作而言，陣列擁有高效隨機存取的特性，也存在低效插入、洗掉的劣勢，
隨機存取
這里的“隨機存取”指的的是通過下標訪問陣列元素，然后對這個元素做存取操作，
計算機會給每個記憶體單元分配一個地址，然后通過地址來訪問記憶體中的資料，當計算機需要隨機訪問陣列中的資料時，它可以通過下面的尋址公式來計算出對應下標的記憶體地址：
address[i] = base_address + data_type_size * i
其中 base_address 表示陣列的起始地址，data_type_size 表示每個元素占用的空間大小，
可想而知，同時具有“連續的記憶體空間”和“相同型別的資料”兩個限制的陣列結構，通過下標查找陣列中的元素能達到 \(O(1)\) 的時間復雜度，
插入、洗掉
同隨機存盤的高效不同，對一個陣列做插入、洗掉操作是非常低效的，這里的低效體現在插入和洗掉元素之后，需要對陣列中的其他元素做搬移操作，以保證陣列元素的連續性，
在一個長度為 n 的陣列中，假如要在第 k 個位置插入一個元素，這不是修改元素的操作，不能直接替換掉第 k 個元素，而是需要依次將第 k 個及之后的元素都往后挪一位，然后才能在第 k 個位置上存入這個元素，
陣列洗掉元素時和插入元素類似，為了避免洗掉元素之后導致陣列中間出現空洞，需要將洗掉位置之后的元素往前挪一位，
通過計算得知，插入、洗掉的最好時間復雜度為 \(O(1)\)、最壞時間復雜度為 \(O(n)\)，平均時間復雜度為 \(O(n)\)，
使用上的問題
陣列越界
陣列可以通過尋址公式做到高效隨機訪問，但這并沒有限制使用超出陣列長度的下標訪問陣列，通常把訪問的陣列下標超出陣列長度的情況稱為陣列越界，
在 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;
}
如上述代碼，在位元組對齊和分配記憶體的特性下，先后定義了 i 和 arr 共占據了 8 個位元組，表現為 {arr[0], arr[1], arr[2], i} 的形式，當回圈到下標為 3 時，實際 arr[3] 指向的就是 i 所在地址，也就出現 arr[3] = i = 3，出現死回圈，
相比較下，使用 Java 會更加安全，Java 不會把檢查陣列越界的作業丟給程式員來做，其本身就會做越界檢查，如果出現錯誤則會拋出 java.lang.ArrayIndexOutOfBoundsException 例外，而不是出現死回圈，
容器和陣列的選擇
這里說的容器指的是封裝了陣列的操作方法、并且支持動態擴容的容器類，比如 Java 中的 ArrayList 類，
與原生陣列相比，ArrayList 擁有非常大的優勢，但并不是所有地方都必須使用 ArrayList 而不使用陣列，在某些地方使用陣列更方便、效率更高，以下情況可以選擇原生陣列：
- 追求極致性能選擇原生陣列，Java 的
ArrayList不支持存盤基本型別，而是存盤基本型別封裝后的物件，自動裝箱、拆箱會有一定的性能消耗 - 操作簡單，僅使用原生功能選擇原生陣列，雖然
ArrayList提供了非常多額外的功能，但也額外增加了風險，使用原生陣列更簡單便捷
為什么陣列從 0 開始編號
這個問題可以通過陣列的尋址公式來回答，
首先需要重新定義陣列下標：下標不是只陣列的第幾個元素，而是指陣列元素的偏移，
在使用時，使用 0 作為起始下標，陣列使用下述的運算式作為尋址公式：
address[i] = base_address + data_type_size * i
如果使用 1 作為起始下標，將不能直接使用上面的尋址公式，而是需要修改如下：
address[i] = base_address + data_type_size * (i - 1)
在對比前后兩個尋址公式之后，可以發現，使用 1 作為起始下標的尋址公式會比使用 0 作為起始下標的尋址公式多一個簡單的減法指令，
對于非常底層的程式來說，即使只是多出一個簡單的減法指令，也是一種性能的損耗，為了做到極致優化，選擇 0 作為起始下標會更好，
當然還有一個歷史原因，C 語言使用了 0 作為陣列的起始下標，后續 Java、JavaScript 都紛紛仿效，這也算是為了統一，降低程式員的學習成本，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/423589.html
標籤：其他
上一篇：ClickHouse 在 UBA 系統中的字典編碼優化實踐
下一篇：AI 智能寫情詩、藏頭詩