數(shù)組三大特性
數(shù)組是一種線性表的數(shù)據(jù)結(jié)構(gòu)，它使用一組連續(xù)的內(nèi)存空間硫朦，來存儲一組具有相同類型的數(shù)據(jù)。
有三個關(guān)鍵詞可以輔助我們理解數(shù)組背镇，線性表咬展、連續(xù)內(nèi)存空間、相同數(shù)據(jù)類型瞒斩。
線性表
由零個或多個數(shù)據(jù)元素組成的有限序列破婆，線性表中的第一個元素?zé)o前驅(qū)，最后一個元素?zé)o后繼胸囱，其他元素有且只有一個前驅(qū)和后繼祷舀。常見的線性表除了數(shù)組，還有鏈表、隊列裳扯、棧也是線性表抛丽。
有線性表就有非線性表，如：樹饰豺、堆亿鲜、圖等就是非線性表。
連續(xù)內(nèi)存空間
連續(xù)的內(nèi)存空間哟忍，這個存儲特性非常重要狡门，它使得硬件對其友好。因為內(nèi)存空間是連續(xù)的锅很，而數(shù)組中的每個塊的大小又是相等的其馏。所以非常容易推導(dǎo)出公式：數(shù)組頭存儲的物理地址 + 偏移量=指定下標(biāo)的物理地址。因為直接能夠計算出物理地址爆安，因而計算機就無需再尋址可以直接訪問內(nèi)存叛复，因此這個特性也被稱為：數(shù)組的隨機訪問特性。
我們經(jīng)常會聽到如下結(jié)論：數(shù)據(jù)查詢的時間復(fù)雜度是O(1)扔仓，這個結(jié)論本身是不太準(zhǔn)確的褐奥。數(shù)組只有在隨機訪問的情況下，它的時間復(fù)雜度才是O(1)翘簇。如果是正常的搜索撬码，即使才有性能最優(yōu)的二分查找，所需的時間復(fù)雜度也要O(logn)版保。
前面講到了數(shù)組連續(xù)內(nèi)存空間帶來的益處：提供了隨機訪問特性呜笑。但是有利也有弊，因為要滿足數(shù)組占用空間的連續(xù)性的特性彻犁，就需要靠搬遷數(shù)據(jù)來保證內(nèi)存空間的連續(xù)性叫胁。
相同的數(shù)據(jù)類型
這是一個隱性的定義，日常的時候我們幾乎不會關(guān)注這個點汞幢。我們試想一下驼鹅，如果存儲在數(shù)組中的數(shù)組，包含 int(4)森篷、long(8)输钩、char(2)、byte(1)疾宏、double(8)张足、float(4) 元素的數(shù)組，那么計算物理內(nèi)存地址的時候是多么麻煩的一件事情坎藐。
正是因為要去類型一致，所以會存在空間上的浪費。在對內(nèi)存空間要求高的應(yīng)用場景下岩馍，如：Redis中自建了的ziplist的數(shù)據(jù)結(jié)構(gòu)碉咆，達到了節(jié)省空間的目的。
低效的插入刪除操作
import java.util.Arrays;
public class Test {
@org.junit.Test
public void test() {
Object[] objects = new Object[5];
for (int i = 0; i < 5; i++) {
objects[i] = i;
}
System.out.println(Arrays.asList(objects));
// case 1: 標(biāo)記清除
objects[1] = null;
System.out.println(Arrays.asList(objects));
// case 2: 執(zhí)行刪除
Object[] newObjects = new Object[4];
System.arraycopy(objects, 0, newObjects, 0, 1);
System.arraycopy(objects, 2, newObjects, 1, 3);
System.out.println(Arrays.asList(newObjects));
}
}
// [0, 1, 2, 3, 4]
// [0, null, 2, 3, 4]
// [0, 2, 3, 4]
初始化了樣本數(shù)據(jù)：[0, 1, 2, 3, 4]蛀恩，此時我們希望刪除數(shù)據(jù)1疫铜，我們可以怎么操作呢？
- 直接將對應(yīng)位置的數(shù)值置為
null双谆，刪除后的數(shù)據(jù)如：[0, null, 2, 3, 4]壳咕，對應(yīng)代碼 case 1。 - 執(zhí)行刪除操作顽馋，然后將后面的數(shù)據(jù)搬遷谓厘，最終數(shù)據(jù)如：
[0, 2, 3, 4]，對應(yīng)代碼 case 2寸谜。
標(biāo)記清除的本質(zhì)是使用空間換時間竟稳，我們可以通過觸發(fā)刪除執(zhí)行的頻率來調(diào)整性能。刪除操作熊痴，對應(yīng)了：新數(shù)組申請他爸、數(shù)據(jù)的拷貝、原數(shù)據(jù)的釋放果善，相比標(biāo)記清除算法是一個重量級的操作诊笤。
ArrayList 能否完全替代數(shù)組？
ArrayList 的優(yōu)勢是官方對 數(shù)組的封裝巾陕，它提供了許多實用的功能讨跟，比如：搬遷數(shù)據(jù)、自動擴容等惜论，種種這些都是手寫數(shù)組比較困擾的事情许赃。
通常我們的應(yīng)用場景，使用ArrayList是足夠的馆类，但這也不表明數(shù)組已無用武之地混聊。因為要使用 ArrayList，就必須要滿足 ArrayList 使用的條件乾巧。那么在破壞 ArrayList 使用的條件的一些例外情況句喜，則是需要使用數(shù)組的。
- ArrayList 使用泛型沟于，不支持基本類型咳胃。高性能場景下（包裝類型會自動裝箱、拆箱）旷太，推薦使用原始類型展懈。
- 高維數(shù)組場景下销睁，選擇
array[0][0][0][0][0][0][1]對比選擇list.get(0).get(0).get(0).get(0).get(0).get(0).get(1)，感覺數(shù)組更加直觀一點存崖。
