程序猿修仙之路--數據結構之你是否真的懂數組？

但凡IT江湖俠士，算法與數據結構為必修之課。早有前輩已經明確指出：程序=算法+數據結構 。要想在之后的江湖歷練中通關，數據結構必不可少。數據結構與算法相輔相成，亦是陰陽互補之法。

開篇

說道數組，幾乎每個IT江湖人士都不陌生，甚至過半人還會很自信覺的它很簡單。
的確，在菜菜所知道的編程語言中幾乎都會有數組的影子。不過它不僅僅是一種基礎的數據類型，更是一種基礎的數據結構。如果你覺的對數組足夠了解，那能不能回答一下：

• 數組的本質定義？
• 數組的內存結構？
• 數組有什么優勢？
• 數組有什么劣勢？
• 數組的應用場景？
• 數組為什么大部分都從0開始編號？
• 數組能否用其他容器來代替，例如c#中的List<T>？

定義

百科

所謂數組，是相同的元素序列。數組是在程序設計中，為了處理方便，把具有相同類型的若干元素按無序的形式組織起來的一種形式。

正如以上所述，數組在應用上屬于數據的容器。不過我還是要補充兩點：

1. 數組在數據結構范疇屬于一種線性結構，也就是只有前置節點和后續節點的數據結構，除數組之外，像我們平時所用的隊列，棧，鏈表等也都屬于線性結構。
   

有線性結構當然就有非線性結構，比如之后我們要介紹的二叉樹，圖 等等，這里不再展開~~~

2. 數組元素在內存分配上是連續的。這一點對于數組這種數據結構來說非常重要，甚至可以說是它最大的“殺手锏”。下邊會有更詳細的介紹。

優勢和劣勢

優勢

我相信所有人在使用數組的時候都知道數組可以按照下標來訪問，例如 array[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開始計算，這里不再展開，有興趣的可以去搜索一下。

• 由于數組的連續性，所以在遍歷數組的時候非常快，不僅得益于數組的連續性，另外也得益于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 有可能會訪問到數組元素以外的數據，因為要訪問的內存地址確實存在。

其他

1. 很多編程語言中你會發現“純數組”并沒有提供直接刪除元素的方法（例如：c#，golang），而是需要將數組轉化為另一種數據結構來實現數組元素的刪除。比如在golang種可以轉化為slice。這也驗證了數組的不變性。

應用場景

我們學習的每個數據結構其實都有對應的適合場景，只不過是場景多少的問題，具體什么時候用，需要我們對該數據結構的特性做深入分析。
關于數組的特性，通過以上介紹可以知道最大的一個亮點就是按照下標訪問，那有沒有具體業務映射這種特性呢？

1. 相信很多IT人士都遇到過會員機制，每個會員到達一定的經驗值就會升級，怎么判斷當前的經驗是否到達升級條件呢？我們是不是可以這樣做：比如當前會員等級為3，判斷是否到達等級4的經驗值，只需要array[4]的值判斷即可，大多數人把配置放到DB，資源耗費太嚴重。也有的人放到其他容器緩存。但是大部分場景下查詢的時間復雜度要比數組大很多。
2. 在分布式底層應用中，我們會有利用一致性哈希方案來解決每個請求交給哪個服務器去處理的場景。有興趣的同學可以自己去研究一下。其中有一個環節：根據哈希值查找對應的服務器，這是典型的讀多寫少的應用，而且比較偏底層。如果用其他數據結構來解決大量的查找問題，可能會觸碰到性能的瓶頸。而數據按下標訪問時間復雜度為O(1)的特性，使得數組在類似這些應用中非常廣泛。

添加關注，查看更精美版本，收獲更多精彩