如何實(shí)現(xiàn)隨機(jī)訪問(wèn)？

數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，來(lái)存儲(chǔ)一組具有相同類(lèi)型的數(shù)據(jù)。

1. 第一是線性表（Linear List）。
   顧名思義，線性表就是數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)。每個(gè)線性表上的數(shù)據(jù)最多只有前和后兩個(gè)方向。其實(shí)除了數(shù)組，鏈表、隊(duì)列、棧等也是線性表結(jié)構(gòu)。
   
   image

而與它相對(duì)立的概念是非線性表，比如二叉樹(shù)、堆、圖等。之所以叫非線性，是因?yàn)?，在非線性表中，數(shù)據(jù)之間并不是簡(jiǎn)單的前后關(guān)系。

image

2. 第二個(gè)是連續(xù)的內(nèi)存空間和相同類(lèi)型的數(shù)據(jù)。
   正是因?yàn)檫@兩個(gè)限制，它才有了一個(gè)堪稱“殺手锏”的特性：“隨機(jī)訪問(wèn)”。但有利就有弊，這兩個(gè)限制也讓數(shù)組的很多操作變得非常低效，比如要想在數(shù)組中刪除、插入一個(gè)數(shù)據(jù)，為了保證連續(xù)性，就需要做大量的數(shù)據(jù)搬移工作。

數(shù)組是如何實(shí)現(xiàn)根據(jù)下標(biāo)隨機(jī)訪問(wèn)數(shù)組元素的?

我們拿一個(gè)長(zhǎng)度為 10 的 int 類(lèi)型的數(shù)組 int[] a = new int[10] 來(lái)舉例。在我畫(huà)的這個(gè)圖中，計(jì)算機(jī)給數(shù)組 a[10]，分配了一塊連續(xù)內(nèi)存空間 1000～1039，其中，內(nèi)存塊的首地址為 base_address = 1000。

image

我們知道，計(jì)算機(jī)會(huì)給每個(gè)內(nèi)存單元分配一個(gè)地址，計(jì)算機(jī)通過(guò)地址來(lái)訪問(wèn)內(nèi)存中的數(shù)據(jù)。當(dāng)計(jì)算機(jī)需要隨機(jī)訪問(wèn)數(shù)組中的某個(gè)元素時(shí)，它會(huì)首先通過(guò)下面的尋址公式，計(jì)算出該元素存儲(chǔ)的內(nèi)存地址：

a[i]_address = base_address + i * data_type_size

其中 data_type_size 表示數(shù)組中每個(gè)元素的大小。我們舉的這個(gè)例子里，數(shù)組中存儲(chǔ)的是 int 類(lèi)型數(shù)據(jù)，所以 data_type_size 就為 4 個(gè)字節(jié)。

• 這里我要特別糾正一個(gè)“錯(cuò)誤”。我在面試的時(shí)候，常常會(huì)問(wèn)數(shù)組和鏈表的區(qū)別，很多人都回答說(shuō)，“鏈表適合插入、刪除，時(shí)間復(fù)雜度 O(1)；數(shù)組適合查找，查找時(shí)間復(fù)雜度為 O(1)”。
• 實(shí)際上，這種表述是不準(zhǔn)確的。數(shù)組是適合查找操作，但是查找的時(shí)間復(fù)雜度并不為 O(1)。即便是排好序的數(shù)組，你用二分查找，時(shí)間復(fù)雜度也是 O(logn)。所以，正確的表述應(yīng)該是，數(shù)組支持隨機(jī)訪問(wèn)，根據(jù)下標(biāo)隨機(jī)訪問(wèn)的時(shí)間復(fù)雜度為 O(1)。

低效的“插入”和“刪除”

插入操作

假設(shè)數(shù)組的長(zhǎng)度為 n，現(xiàn)在，如果我們需要將一個(gè)數(shù)據(jù)插入到數(shù)組中的第 k 個(gè)位置。為了把第 k 個(gè)位置騰出來(lái)，給新來(lái)的數(shù)據(jù)，我們需要將第 k～n 這部分的元素都順序地往后挪一位。那插入操作的時(shí)間復(fù)雜度是多少呢？你可以自己先試著分析一下。

如果在數(shù)組的末尾插入元素，那就不需要移動(dòng)數(shù)據(jù)了，這時(shí)的時(shí)間復(fù)雜度為 O(1)。但如果在數(shù)組的開(kāi)頭插入元素，那所有的數(shù)據(jù)都需要依次往后移動(dòng)一位，所以最壞時(shí)間復(fù)雜度是 O(n)。 因?yàn)槲覀冊(cè)诿總€(gè)位置插入元素的概率是一樣的，所以平均情況時(shí)間復(fù)雜度為 (1+2+…n)/n=O(n)。

如果數(shù)組中的數(shù)據(jù)是有序的，我們?cè)谀硞€(gè)位置插入一個(gè)新的元素時(shí)，就必須按照剛才的方法搬移 k 之后的數(shù)據(jù)。但是，如果數(shù)組中存儲(chǔ)的數(shù)據(jù)并沒(méi)有任何規(guī)律，數(shù)組只是被當(dāng)作一個(gè)存儲(chǔ)數(shù)據(jù)的集合。在這種情況下，如果要將某個(gè)數(shù)組插入到第 k 個(gè)位置，為了避免大規(guī)模的數(shù)據(jù)搬移，我們還有一個(gè)簡(jiǎn)單的辦法就是，直接將第 k 位的數(shù)據(jù)搬移到數(shù)組元素的最后，把新的元素直接放入第 k 個(gè)位置。

為了更好地理解，我們舉一個(gè)例子。假設(shè)數(shù)組 a[10] 中存儲(chǔ)了如下 5 個(gè)元素：a，b，c，d，e。

我們現(xiàn)在需要將元素 x 插入到第 3 個(gè)位置。我們只需要將 c 放入到 a[5]，將 a[2] 賦值為 x 即可。最后，數(shù)組中的元素如下： a，b，x，d，e，c。

image

利用這種處理技巧，在特定場(chǎng)景下，在第 k 個(gè)位置插入一個(gè)元素的時(shí)間復(fù)雜度就會(huì)降為 O(1)。這個(gè)處理思想在快排中也會(huì)用到，我會(huì)在排序那一節(jié)具體來(lái)講，這里就說(shuō)到這兒。

刪除操作

跟插入數(shù)據(jù)類(lèi)似，如果我們要?jiǎng)h除第 k 個(gè)位置的數(shù)據(jù)，為了內(nèi)存的連續(xù)性，也需要搬移數(shù)據(jù)，不然中間就會(huì)出現(xiàn)空洞，內(nèi)存就不連續(xù)了。

和插入類(lèi)似，如果刪除數(shù)組末尾的數(shù)據(jù)，則最好情況時(shí)間復(fù)雜度為 O(1)；如果刪除開(kāi)頭的數(shù)據(jù)，則最壞情況時(shí)間復(fù)雜度為 O(n)；平均情況時(shí)間復(fù)雜度也為 O(n)。

實(shí)際上，在某些特殊場(chǎng)景下，我們并不一定非得追求數(shù)組中數(shù)據(jù)的連續(xù)性。如果我們將多次刪除操作集中在一起執(zhí)行，刪除的效率是不是會(huì)提高很多呢？

我們繼續(xù)來(lái)看例子。數(shù)組 a[10] 中存儲(chǔ)了 8 個(gè)元素：a，b，c，d，e，f，g，h?，F(xiàn)在，我們要依次刪除 a，b，c 三個(gè)元素。

image

為了避免 d，e，f，g，h 這幾個(gè)數(shù)據(jù)會(huì)被搬移三次，我們可以先記錄下已經(jīng)刪除的數(shù)據(jù)。每次的刪除操作并不是真正地搬移數(shù)據(jù)，只是記錄數(shù)據(jù)已經(jīng)被刪除。當(dāng)數(shù)組沒(méi)有更多空間存儲(chǔ)數(shù)據(jù)時(shí)，我們?cè)儆|發(fā)執(zhí)行一次真正的刪除操作，這樣就大大減少了刪除操作導(dǎo)致的數(shù)據(jù)搬移。

如果你了解 JVM，你會(huì)發(fā)現(xiàn)，這不就是 JVM 標(biāo)記清除垃圾回收算法的核心思想嗎？沒(méi)錯(cuò)，數(shù)據(jù)結(jié)構(gòu)和算法的魅力就在于此，很多時(shí)候我們并不是要去死記硬背某個(gè)數(shù)據(jù)結(jié)構(gòu)或者算法，而是要學(xué)習(xí)它背后的思想和處理技巧，這些東西才是最有價(jià)值的。如果你細(xì)心留意，不管是在軟件開(kāi)發(fā)還是架構(gòu)設(shè)計(jì)中，總能找到某些算法和數(shù)據(jù)結(jié)構(gòu)的影子。

JVM標(biāo)記清除算法：
大多數(shù)主流虛擬機(jī)采用可達(dá)性分析算法來(lái)判斷對(duì)象是否存活，在標(biāo)記階段，會(huì)遍歷所有 GC ROOTS，將所有 GC ROOTS 可達(dá)的對(duì)象標(biāo)記為存活。只有當(dāng)標(biāo)記工作完成后，清理工作才會(huì)開(kāi)始。
不足：1.效率問(wèn)題。標(biāo)記和清理效率都不高，但是當(dāng)知道只有少量垃圾產(chǎn)生時(shí)會(huì)很高效。2.空間問(wèn)題。會(huì)產(chǎn)生不連續(xù)的內(nèi)存空間碎片。

警惕數(shù)組的訪問(wèn)越界問(wèn)題

C語(yǔ)言代碼：

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;
}

• 問(wèn)題：無(wú)限打印“hello world”
• 原因：數(shù)組大小為 3，a[0]，a[1]，a[2]，而我們的代碼因?yàn)闀?shū)寫(xiě)錯(cuò)誤，導(dǎo)致 for 循環(huán)的結(jié)束條件錯(cuò)寫(xiě)為了 i<=3 而非 i<3，所以當(dāng) i=3 時(shí)，數(shù)組 a[3] 訪問(wèn)越界。

我們知道，在 C 語(yǔ)言中，只要不是訪問(wèn)受限的內(nèi)存，所有的內(nèi)存空間都是可以自由訪問(wèn)的。根據(jù)我們前面講的數(shù)組尋址公式，a[3] 也會(huì)被定位到某塊不屬于數(shù)組的內(nèi)存地址上，而這個(gè)地址正好是存儲(chǔ)變量 i 的內(nèi)存地址，那么 a[3]=0 就相當(dāng)于 i=0，所以就會(huì)導(dǎo)致代碼無(wú)限循環(huán)。

數(shù)組越界在 C 語(yǔ)言中是一種未決行為，并沒(méi)有規(guī)定數(shù)組訪問(wèn)越界時(shí)編譯器應(yīng)該如何處理。因?yàn)?，訪問(wèn)數(shù)組的本質(zhì)就是訪問(wèn)一段連續(xù)內(nèi)存，只要數(shù)組通過(guò)偏移計(jì)算得到的內(nèi)存地址是可用的，那么程序就可能不會(huì)報(bào)任何錯(cuò)誤。

容器能否完全替代數(shù)組？

我個(gè)人覺(jué)得，ArrayList 最大的優(yōu)勢(shì)就是可以將很多數(shù)組操作的細(xì)節(jié)封裝起來(lái)。比如前面提到的數(shù)組插入、刪除數(shù)據(jù)時(shí)需要搬移其他數(shù)據(jù)等。另外，它還有一個(gè)優(yōu)勢(shì)，就是支持動(dòng)態(tài)擴(kuò)容。

數(shù)組本身在定義的時(shí)候需要預(yù)先指定大小，因?yàn)樾枰峙溥B續(xù)的內(nèi)存空間。如果我們申請(qǐng)了大小為 10 的數(shù)組，當(dāng)?shù)?11 個(gè)數(shù)據(jù)需要存儲(chǔ)到數(shù)組中時(shí)，我們就需要重新分配一塊更大的空間，將原來(lái)的數(shù)據(jù)復(fù)制過(guò)去，然后再將新的數(shù)據(jù)插入。

如果使用 ArrayList，我們就完全不需要關(guān)心底層的擴(kuò)容邏輯，ArrayList 已經(jīng)幫我們實(shí)現(xiàn)好了。每次存儲(chǔ)空間不夠的時(shí)候，它都會(huì)將空間自動(dòng)擴(kuò)容為 1.5 倍大小。

不過(guò)，這里需要注意一點(diǎn)，因?yàn)閿U(kuò)容操作涉及內(nèi)存申請(qǐng)和數(shù)據(jù)搬移，是比較耗時(shí)的。所以，如果事先能確定需要存儲(chǔ)的數(shù)據(jù)大小，最好在創(chuàng)建 ArrayList 的時(shí)候事先指定數(shù)據(jù)大小。

比如我們要從數(shù)據(jù)庫(kù)中取出 10000 條數(shù)據(jù)放入 ArrayList。我們看下面這幾行代碼，你會(huì)發(fā)現(xiàn)，相比之下，事先指定數(shù)據(jù)大小可以省掉很多次內(nèi)存申請(qǐng)和數(shù)據(jù)搬移操作。

ArrayList<User> users = new ArrayList(10000);
for (int i = 0; i < 10000; ++i) {
  users.add(xxx);
}

作為高級(jí)語(yǔ)言編程者，是不是數(shù)組就無(wú)用武之地了呢？當(dāng)然不是，有些時(shí)候，用數(shù)組會(huì)更合適些，我總結(jié)了幾點(diǎn)自己的經(jīng)驗(yàn)。

• 1. Java ArrayList 無(wú)法存儲(chǔ)基本類(lèi)型，比如 int、long，需要封裝為 Integer、Long 類(lèi)，而 Autoboxing、Unboxing 則有一定的性能消耗，所以如果特別關(guān)注性能，或者希望使用基本類(lèi)型，就可以選用數(shù)組。
• 2. 如果數(shù)據(jù)大小事先已知，并且對(duì)數(shù)據(jù)的操作非常簡(jiǎn)單，用不到 ArrayList 提供的大部分方法，也可以直接使用數(shù)組。
• 3. 還有一個(gè)是我個(gè)人的喜好，當(dāng)要表示多維數(shù)組時(shí)，用數(shù)組往往會(huì)更加直觀。比如 Object[][] array；而用容器的話則需要這樣定義：ArrayList<ArrayList > array。
     我總結(jié)一下，對(duì)于業(yè)務(wù)開(kāi)發(fā)，直接使用容器就足夠了，省時(shí)省力。畢竟損耗一丟丟性能，完全不會(huì)影響到系統(tǒng)整體的性能。但如果你是做一些非常底層的開(kāi)發(fā)，比如開(kāi)發(fā)網(wǎng)絡(luò)框架，性能的優(yōu)化需要做到極致，這個(gè)時(shí)候數(shù)組就會(huì)優(yōu)于容器，成為首選。

為什么大多數(shù)編程語(yǔ)言中，數(shù)組要從 0 開(kāi)始編號(hào)，而不是從 1 開(kāi)始呢？

從數(shù)組存儲(chǔ)的內(nèi)存模型上來(lái)看，“下標(biāo)”最確切的定義應(yīng)該是“偏移（offset）”。前面也講到，如果用 a 來(lái)表示數(shù)組的首地址，a[0] 就是偏移為 0 的位置，也就是首地址，a[k] 就表示偏移 k 個(gè) type_size 的位置，所以計(jì)算 a[k] 的內(nèi)存地址只需要用這個(gè)公式：

a[k]_address = base_address + k * type_size

但是，如果數(shù)組從 1 開(kāi)始計(jì)數(shù)，那我們計(jì)算數(shù)組元素 a[k] 的內(nèi)存地址就會(huì)變?yōu)椋?/p>

a[k]_address = base_address + (k-1)*type_size

對(duì)比兩個(gè)公式，我們不難發(fā)現(xiàn)，從 1 開(kāi)始編號(hào)，每次隨機(jī)訪問(wèn)數(shù)組元素都多了一次減法運(yùn)算，對(duì)于 CPU 來(lái)說(shuō)，就是多了一次減法指令。

數(shù)組作為非常基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，通過(guò)下標(biāo)隨機(jī)訪問(wèn)數(shù)組元素又是其非常基礎(chǔ)的編程操作，效率的優(yōu)化就要盡可能做到極致。所以為了減少一次減法操作，數(shù)組選擇了從 0 開(kāi)始編號(hào)，而不是從 1 開(kāi)始。

不過(guò)我認(rèn)為，上面解釋得再多其實(shí)都算不上壓倒性的證明，說(shuō)數(shù)組起始編號(hào)非 0 開(kāi)始不可。所以我覺(jué)得最主要的原因可能是歷史原因。

C 語(yǔ)言設(shè)計(jì)者用 0 開(kāi)始計(jì)數(shù)數(shù)組下標(biāo)，之后的 Java、JavaScript 等高級(jí)語(yǔ)言都效仿了 C 語(yǔ)言，或者說(shuō)，為了在一定程度上減少 C 語(yǔ)言程序員學(xué)習(xí) Java 的學(xué)習(xí)成本，因此繼續(xù)沿用了從 0 開(kāi)始計(jì)數(shù)的習(xí)慣。實(shí)際上，很多語(yǔ)言中數(shù)組也并不是從 0 開(kāi)始計(jì)數(shù)的，比如 Matlab。甚至還有一些語(yǔ)言支持負(fù)數(shù)下標(biāo)，比如 Python。

內(nèi)容小節(jié)

我們今天學(xué)習(xí)了數(shù)組。它可以說(shuō)是最基礎(chǔ)、最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)了。數(shù)組用一塊連續(xù)的內(nèi)存空間，來(lái)存儲(chǔ)相同類(lèi)型的一組數(shù)據(jù)，最大的特點(diǎn)就是支持隨機(jī)訪問(wèn)，但插入、刪除操作也因此變得比較低效，平均情況時(shí)間復(fù)雜度為 O(n)。在平時(shí)的業(yè)務(wù)開(kāi)發(fā)中，我們可以直接使用編程語(yǔ)言提供的容器類(lèi)，但是，如果是特別底層的開(kāi)發(fā)，直接使用數(shù)組可能會(huì)更合適。

二維數(shù)組內(nèi)存尋址：
對(duì)于 m * n 的數(shù)組，a [ i ][ j ] (i < m,j < n)的地址為：
address = base_address + ( i * n + j) * type_size
另外，對(duì)于數(shù)組訪問(wèn)越界造成無(wú)限循環(huán)，我理解是編譯器的問(wèn)題，對(duì)于不同的編譯器，在內(nèi)存分配時(shí)，會(huì)按照內(nèi)存地址遞增或遞減的方式進(jìn)行分配。老師的程序，如果是內(nèi)存地址遞減的方式，就會(huì)造成無(wú)限循環(huán)。

個(gè)人小結(jié)

數(shù)組用來(lái)儲(chǔ)存相同類(lèi)型的數(shù)據(jù)，且內(nèi)存是連續(xù)的，線性表數(shù)據(jù)結(jié)構(gòu)。
方便訪問(wèn)，但是對(duì)于刪除和插入效果不好。

隨機(jī)尋址：
a[i]_address = base_address + i * data_type_size

刪除和插入要進(jìn)行移位操作，可以優(yōu)化的是，先處理完數(shù)據(jù)，最后再進(jìn)行移位，和jvm垃圾回收機(jī)制類(lèi)似。

一般情況可以用ArrayList來(lái)替代數(shù)組，它的好處是支持動(dòng)態(tài)擴(kuò)容和封裝了插入刪除等操作，沒(méi)有空間時(shí)它都會(huì)將空間自動(dòng)擴(kuò)容為 1.5 倍大小。

至于為什么從0開(kāi)始，猜想
一是因?yàn)镃語(yǔ)言和很多語(yǔ)言都是從0開(kāi)始，為了學(xué)習(xí)成本數(shù)組也從0開(kāi)始。
二是如果從1開(kāi)始，內(nèi)存地址就會(huì)成為a[k]_address = base_address + (k-1)*type_size，則會(huì)多一次減法運(yùn)算，為了CPU性能，則從0開(kāi)始計(jì)數(shù)。