程式猿修仙之路--資料結構之你是否真的懂陣列？
說道陣列，幾乎每個IT江湖人士都不陌生，甚至過半人還會很自信覺的它很簡單。 的確，在菜菜所知道的程式語言中幾乎都會有陣列的影子。不過它不僅僅是一種基礎的資料型別，更是一種基礎的資料結構。如果你覺的對陣列足夠了解，那能不能回答一下：
陣列的本質定義？
陣列的記憶體結構？
陣列有什麼優勢？
陣列有什麼劣勢？
陣列的應用場景？
陣列為什麼大部分都從0開始編號？
陣列能否用其他容器來代替，例如c#中的List<T>？
Line"/> 正如以上所述，陣列在應用上屬於資料的容器。不過我還是要補充兩點：
1 . 陣列在資料結構範疇屬於一種線性結構，也就是隻有前置節點和後續節點的資料結構，除陣列之外，像我們平時所用的佇列，棧，連結串列等也都屬於線性結構。
有線性結構當然就有非線性結構，比如之後我們要介紹的二叉樹，圖 等等，這裡不再展開~~~
2. 陣列元素在記憶體分配上是連續的。這一點對於陣列這種資料結構來說非常重要，甚至可以說是它最大的“殺手鐗”。下邊會有更詳細的介紹。
優勢和劣勢
優勢
我相信所有人在使用陣列的時候都知道陣列可以按照下標來訪問，例如 array[1] 。作為一種最基礎的資料結構是什麼使陣列具有這樣的隨機訪問方式呢？天性聰慧的你可能已經想到了：記憶體連續+相同資料型別。
現在我們抽象一下資料在記憶體上分配的情景。
1 . 說到陣列按下標訪問，不得不說一下大多數人的一個“誤解”：陣列適合查詢元素。為什麼說是誤解呢,是因為這種說法不夠準確， 準確的說陣列適合按下標來查詢元素 ， 而且按照下標查詢元素的時間複雜度是O(1) 。為什麼呢？我們知道要訪問陣列的元素需要知道元素在記憶體中對應的記憶體地址，而陣列指向的記憶體的地址為首元素的地址，即：array[0]。由於陣列的每個元素都是相同的型別，每個型別佔用的位元組數系統是知道的，所以要想訪問一個數組的元素，按照下標查詢可以抽象為：
array[n]=array[0]+size*n
以上是元素地址的運算，其中size為每個元素的大小，如果為int型別資料，那size就為4個位元組。其實確切的說，n的本質是一個離首元素的偏移量，所以array[n]就是距離首元素n個偏移量的元素，因此計算array[n]的記憶體地址只需以上公式 。
論證一下，如果下標從1開始計算，那array[n]的記憶體地址計算公式就會變為：
array[n]=array[0]+size*(n-1)
對比很容易發現，從1開始編號比從0開始編號每次獲取記憶體地址都多了一次 減法運算，也就多了一次cpu指令的執行。這也是陣列從0下標開始訪問一個原因。
其實還有一種可能性，那就是所有現代程式語言的鼻祖：C語言，它是從0開始計數下標的，所以現在所有衍生出來的後代語言也就延續了這個傳統。雖然不符合人類的思想，但是符合計算機的原理。當然也有一些語言可以設定為不從下標0開始計算，這裡不再展開，有興趣的可以去搜索一下。
2. 由於陣列的連續性，所以在遍歷陣列的時候非常快，不僅得益於陣列的連續性，另外也得益於cpu的快取，因為cpu讀取快取只能讀取連續記憶體的內容，所以陣列的連續性正好符合cpu快取的指令原理，要知道cpu快取的速度要比記憶體的速度快上很多。
劣勢
1 . 由於陣列在記憶體排列上是連續的，而且要保持這種連續性，所以當增加一個元素或刪除一個元素的時候，為了保證連續性，需要做大量元素的移動工作。
舉個栗子：要在陣列頭部插入一個新元素，為了在頭部騰出位置，所有的元素都要後移一位，假設元素個數為n，這就導致了時間複雜度為O（n）的一次操作，當然如果是在陣列末尾插入新元素，其他所有元素都不必移動，操作的時間複雜度為O（1）。
當然這裡有一個技巧：如果你的業務要求並不是陣列連續有序的，當在位置k插入元素的時候，只需要把k元素轉移到陣列末尾，新元素插入到k位置即可。當然仔細沉思一下這種業務場景可能性太小了，陣列都可以無序，我直接插入末尾即可，沒有必要非得在k位置插入把。~~
當然還有一個特殊場景：如果是多次連續的k位置插入操作，我們完全可以合併為一次“批量插入”操作：把k之後的元素整體移動sum（插入次數）個位置，無需一個個位置移動，把三次操作的時間複雜度合併為一次。
與插入對應的就有刪除操作，同理，刪除運算元組為了保持連續性，也需要元素的移動。
綜上所述，陣列在新增和刪除元素的場景下劣勢比較明顯，所以在具體業務場景下應該避免頻繁新增和刪除的操作。
2. 陣列的連續性就要求建立陣列的時候，記憶體必須有相應大小的連續區塊，如果不存在，陣列就有可能出現建立失敗的現象。在某些高階語言中（比如c#，golang，java）就有可能引發一次GC（垃圾回收）操作，GC操作在系統執行中是非常昂貴的，有的語言甚至會掛起所有執行緒的操作，對外的表現就是“暫停服務”。
3. 陣列要求所有元素為同一個型別。在儲存資料維度，它可能算是一種劣勢，但是為了按照下標快速查詢元素，業務中這也是一種優勢。仁者見仁智者見智而已。
4. 陣列是長度固定的資料結構，所以在原始陣列的基礎上擴容是不可能的，有的語言可能實現陣列的“偽擴容”，為什麼說是“偽”呢，因為原理其實是建立了一個容量更大的陣列來存放原陣列元素，發生了資料複製的過程，只不過對於呼叫者而已透明而已。
5. 陣列有訪問越界的可能。我們按照下標訪問陣列的時候如果下標超出了陣列長度，在現代多數高階語言中，直接就會引發異常了，但是一些低階語言比如C 有可能會訪問到陣列元素以外的資料，因為要訪問的記憶體地址確實存在。
其他
很多程式語言中你會發現“純陣列”並沒有提供直接刪除元素的方法（例如：c#，golang），而是需要將陣列轉化為另一種資料結構來實現陣列元素的刪除。比如在golang種可以轉化為slice。這也驗證了陣列的不變性。
我們學習的每個資料結構其實都有對應的適合場景，只不過是場景多少的問題，具體什麼時候用，需要我們對該資料結構的特性做深入分析。
關於陣列的特性，通過以上介紹可以知道最大的一個亮點就是按照下標訪問，那有沒有具體業務對映這種特性呢？
1. 相信很多IT人士都遇到過會員機制，每個會員到達一定的經驗值就會升級，怎麼判斷當前的經驗是否到達升級條件呢？我們是不是可以這樣做：比如當前會員等級為3，判斷是否到達等級4的經驗值，只需要array[4]的值判斷即可，大多數人把配置放到DB，資源耗費太嚴重。也有的人放到其他容器快取。但是大部分場景下查詢的時間複雜度要比陣列大很多。
2. 在分散式底層應用中，我們會有利用一致性雜湊方案來解決每個請求交給哪個伺服器去處理的場景。有興趣的同學可以自己去研究一下。其中有一個環節：根據雜湊值查詢對應的伺服器，這是典型的讀多寫少的應用，而且比較偏底層。如果用其他資料結構來解決大量的查詢問題，可能會觸碰到效能的瓶頸。而資料按下標訪問時間複雜度為O(1)的特性，使得陣列在類似這些應用中非常廣泛。
菜鳥奮鬥史出品
見證菜鳥的成長之路
