數(shù)組是我們前端日常開發(fā)中最熟悉的一種數(shù)據(jù)類型，但你真的了解數(shù)組嗎？

什么是數(shù)組？

數(shù)組的定義：

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

首先它是一個線性表

• 線性表：就是數(shù)據(jù)排列成一條先一樣的結(jié)構(gòu)鳍置，每個線性表上的數(shù)據(jù)最多只有前和后兩個方向辽剧。除了數(shù)組，鏈表税产，隊列怕轿，棧等也是線性表結(jié)構(gòu)。

• 非線性表：二叉樹砖第，堆撤卢，圖等。之所以是非線性梧兼，是因為數(shù)據(jù)之間并不是簡單的前后關(guān)系放吩。

• 然后它是連續(xù)的內(nèi)存空間和相同的數(shù)據(jù)類型

有了這兩個限制，才能讓數(shù)組可以隨機(jī)訪問羽杰。當(dāng)然有利就有弊渡紫，這兩個限制也讓數(shù)組的很多操作變得低效，比如刪除和插入操作考赛，為了保證連續(xù)性需要做大量的數(shù)據(jù)搬移工作惕澎。

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

比如一個長度為10的int類型的數(shù)組int[] a = new int[10],

image.png

從圖中可以看到颜骤，計算機(jī)給數(shù)組a分配了一塊連續(xù)的內(nèi)存1000-1039.其中內(nèi)存塊的首地址為base_address=1000唧喉。

我們知道計算機(jī)會給每一個內(nèi)存單元分配一個地址，計算機(jī)通過地址來訪問內(nèi)存中的數(shù)據(jù)忍抽。當(dāng)計算機(jī)要訪問數(shù)組中的某個元素的時候就會通過下面公式尋找地址

a[i]_address = base_address + i*data_type_size
這里的data_type_size表示數(shù)組中每個元素的大小八孝，因為例子中是int所以大小為4.

注意，這里有兩個關(guān)鍵詞：相同類型鸠项、連續(xù)內(nèi)存干跛，這也是它的特征！好祟绊，重點(diǎn)來了：

那我怎么及得JS中的數(shù)組元素可以是各種類型楼入？哥捕？？比如下面這樣：

let arr = [100, 'foo', 1.1, {a: 1}];

這就有意思了嘉熊，按理維基百科對于數(shù)組的描述應(yīng)該是具有一定權(quán)威的遥赚，難道JS的數(shù)組不是真的“數(shù)組”？

image

這么來看阐肤，我們姑且推斷出一個結(jié)論鸽捻，因為：不同數(shù)據(jù)類型存儲所需空間大小不同。
所以：用來存放數(shù)組的內(nèi)存地址一定是連續(xù)的（除非類型相同）泽腮。
因此我們大膽猜測，JS中的數(shù)組實(shí)現(xiàn)一定不是基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的衣赶。所以诊赊，如標(biāo)題所說的，JS中原本沒有“真正”的數(shù)組府瞄！這就引起了我的好奇心了碧磅，那么JS中是如何“實(shí)現(xiàn)”數(shù)組這個概念的呢？ 我們來一探究竟遵馆！

數(shù)組中概念一：連續(xù)內(nèi)存

在講連續(xù)內(nèi)存前鲸郊，先來了解下什么是內(nèi)存，知道的本節(jié)直接繞過货邓。

1. 什么是內(nèi)存秆撮？
   通俗理解，在計算機(jī)中换况，CPU用于數(shù)據(jù)的運(yùn)算职辨，而數(shù)據(jù)來源于硬盤，但考慮到CPU直接從硬盤讀寫數(shù)據(jù)效率低戈二，所以內(nèi)存在其中扮演了“搬運(yùn)工”的角色舒裤。

內(nèi)存是由DRAM（動態(tài)隨機(jī)存儲器）芯片組成的。DRAM的內(nèi)部結(jié)構(gòu)可以說是PC芯片中最簡單的觉吭，是由許多重復(fù)的“單元”——cell組成腾供，每一個cell由一個電容和一個晶體管（一般是N溝道MOSFET）構(gòu)成，電容可儲存1bit數(shù)據(jù)量鲜滩，充放電后電荷的多少（電勢高低）分別對應(yīng)二進(jìn)制數(shù)據(jù)0和1伴鳖。

DRAM由于結(jié)構(gòu)簡單，可以做到面積很小绒北，存儲容量很大黎侈。用芯片短暫存儲數(shù)據(jù)，讀寫的效率要遠(yuǎn)高于磁盤闷游。所以內(nèi)存的運(yùn)行也決定了計算機(jī)的穩(wěn)定運(yùn)行峻汉。

2. 內(nèi)存和數(shù)組的故事
   了解完什么是內(nèi)存后贴汪，回過頭再來看一下數(shù)組的概念：

數(shù)組是由相同類型的元素（element）的集合所組成的數(shù)據(jù)結(jié)構(gòu)，分配一塊連續(xù)內(nèi)存來存儲休吠。

那么數(shù)組中的連續(xù)內(nèi)存說的是扳埂，通過在內(nèi)存中劃出一串連續(xù)且長度固定的空間，用來于存放一組有限且數(shù)據(jù)類型相同的數(shù)據(jù)結(jié)構(gòu)瘤礁。在C/C++阳懂、Java等編譯型語言中數(shù)組的實(shí)現(xiàn)都是這個。C++數(shù)組聲明示例代碼如下：

// 數(shù)據(jù)類型 數(shù)組名[元素數(shù)量]
double balance[10];

上述代碼中柜思，需要指定元素類型和數(shù)量岩调，這非常重要。細(xì)細(xì)品味其中的蘊(yùn)含的內(nèi)容赡盘，將其聯(lián)系到內(nèi)存以及計算機(jī)運(yùn)行原理信息量很大号枕！

數(shù)組中概念二：固定長度

從上面說的就很容易理解，計算機(jī)語言設(shè)計者為什么要讓C/C++陨享、Java這類編譯型語言在數(shù)組的設(shè)計上要固定長度葱淳。因為數(shù)組空間數(shù)連續(xù)的，所以這就意味著內(nèi)存中需要有一整塊的空間用來存放數(shù)組抛姑。如果長度不固定赞厕，那么內(nèi)存中位于數(shù)組之后的區(qū)域沒法繼續(xù)往下分配了！內(nèi)存不知道當(dāng)前數(shù)組還要不要繼續(xù)存放定硝，要多少空間了皿桑。畢竟數(shù)組后面的空間得要留出來給別人去用，不可能讓你（數(shù)組）一直霸占著對吧蔬啡。

數(shù)組中概念三：相同數(shù)據(jù)類型

為什么數(shù)組的定義需要每個元素數(shù)據(jù)類型相同呢唁毒。其實(shí)比較容易理解了，如果數(shù)組允許各種類型的數(shù)據(jù)星爪，那么每存入一個元素都要進(jìn)行裝箱操作浆西，每讀取一個元素又要進(jìn)行拆箱操作。統(tǒng)一數(shù)據(jù)類型就可以省略裝箱和拆箱的步驟了顽腾，這樣能提高存儲和讀取的效率近零。

數(shù)組優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

1. 按照索引查詢元素速度快
2. 能存儲大量數(shù)據(jù)
3. 按照索引遍歷數(shù)組方便

缺點(diǎn)：

1. 根據(jù)內(nèi)容查找元素速度慢
2. 數(shù)組的大小一經(jīng)確定不能改變。
3. 數(shù)組只能存儲一種類型的數(shù)據(jù)
4. 增加抄肖、刪除元素效率慢
5. 未封裝任何方法久信，所有操作都需要用戶自己定義。

為什么數(shù)組的插入和刪除是低效的漓摩？

插入操作：

假如數(shù)組的長度為n裙士，如果我們需要將一個數(shù)據(jù)插入到數(shù)組中的第k個位置，為了把第k個位置騰出來管毙，需要把第k~n這部分的元素都順序的往后挪一位腿椎，操作復(fù)雜桌硫。

如果在數(shù)組的末尾插入元素，那就不需要移動數(shù)據(jù)了啃炸，插入比較簡單铆隘，單是如果在數(shù)組的頭部插入元素就復(fù)雜了，需要把所有的數(shù)據(jù)都往后移動一位南用。

如果一個數(shù)組中的數(shù)據(jù)是有序的膀钠，那我們在某一個位置插入一個新的元素的時候就必須得按照上面的方法移動k之后的數(shù)據(jù)，但是數(shù)組中存儲的數(shù)據(jù)如果沒有任何規(guī)律裹虫，這時候肿嘲，如果想要把某個元素插入到k位置，為了避免大規(guī)模的數(shù)據(jù)搬移筑公，有個簡單的辦法就是：直接把k位置的數(shù)據(jù)搬到數(shù)組的最后面睦刃，把新元素放到第k個位置。

刪除操作：

跟插入數(shù)據(jù)類似十酣，如果我們要刪除第k個位置的數(shù)據(jù)，為了內(nèi)存的連續(xù)性际长，也需要搬移數(shù)據(jù)耸采，不然中間就會出現(xiàn)空洞。

在某些情況下工育，如果我們不要求數(shù)據(jù)必須是連續(xù)的虾宇，那么刪除的時候可以不真刪除，只是把這個元素標(biāo)記為已刪除如绸，當(dāng)組空間不夠用的時候嘱朽，在觸發(fā)一次真正的刪除，這樣就大大減少了刪除操作導(dǎo)致的搬移操作怔接。

V8引擎下數(shù)組的實(shí)現(xiàn)

寫在前面
首先搪泳，我們要了解JS代碼是如何在計算機(jī)上被執(zhí)行的。和Python一樣扼脐，它作為一門解釋型語言岸军，需要宿主環(huán)境去對它進(jìn)行“轉(zhuǎn)換”，然后再由機(jī)器運(yùn)行機(jī)器碼瓦侮，也就是二進(jìn)制艰赞。我們平時對JS的討論很多都是（默認(rèn)）基于瀏覽器來講的，當(dāng)前大多主流瀏覽器底層都是基于C++開發(fā)的肚吏，并且Node底層也是基于Chrome V8引擎的JS運(yùn)行環(huán)境方妖，而V8底層也是基于C++來開發(fā)的。所以會有開發(fā)者以為JavaScript是用C++寫的罚攀，要知道這是不對的党觅。

作為一門解釋型語言雌澄，JS并非只有C++才能去解析JS，其實(shí)還有：

• D：DMDScript
• Java：Rhino仔役、Nashorn掷伙、DynJS、Truffle/JS 等
• C#：Managed JScript又兵、SPUR 等等

還有最近熱度不減的Rust：deno（也是基于V8）任柜。所以，我們要來研究JS中數(shù)組的實(shí)現(xiàn)就要依賴“解釋”他JS引擎來講了沛厨。本文我們用V8引擎來進(jìn)行講解宙地。

V8源碼中的JS數(shù)組
為了追蹤JS到底是如何實(shí)現(xiàn)數(shù)組的，我們追蹤到V8中看看它是如何去“解析”JS數(shù)組的逆皮。下面截圖來自V8源碼：

image.png

1. JSArray數(shù)組繼承于JSObject對象
2. 數(shù)組有快慢兩種模式

下面我們來具體講講宅粥。

JS數(shù)組就是“對象”
如果說JS中的數(shù)組底層是一個對象，那么我們就可以解釋為什么JS中數(shù)組可以放各種類型了电谣。假設(shè)我們猜測是對的秽梅，那么如何來驗證這一點(diǎn)呢？為此最近花了點(diǎn)時間探索了一番剿牺，在網(wǎng)上看了很多資料企垦，也找了很多方法，最終鎖定使用通過觀察JS最終執(zhí)行生產(chǎn)的字節(jié)碼來看最終代碼的轉(zhuǎn)換晒来。最后選用了GoogleChromeLabs的jsvu钞诡，他可以幫我們安裝各種JS引擎，也可以將JS轉(zhuǎn)為字節(jié)碼湃崩。

測試代碼：

const arr = [1, true, 'foo'];

然后使用V8-debug引擎去debug打印他轉(zhuǎn)譯的字節(jié)碼荧降，如下圖所示：

image

那么這就可以得出結(jié)論，其實(shí)arr就是一個map攒读，它有key朵诫，有value，而key就是數(shù)組的索引薄扁，value就是數(shù)組中的元素拗窃。

快數(shù)組和慢數(shù)組

細(xì)心的同學(xué)可能發(fā)現(xiàn)了，前面截圖的V8源碼注釋中有這樣一段描述：

Such an array can be in one of two modes:

• fast, backing storage is a FixedArray and length <= elements.length();
• slow, backing storage is a HashTable with numbers as keys.

翻譯一下泌辫，一個數(shù)組含有兩種模式：

• 快（模式）：后備存儲是一個FixedArray随夸，長度 <= elements.length
• 慢（模式）：后備存儲是一個以數(shù)字為鍵的HashTable
  那么來思考下為什么要V8要將數(shù)組這樣“設(shè)計”，動機(jī)是什么震放？無非就是為了提升性能宾毒，一說到性能，就不得不提內(nèi)存殿遂，總之這一切無非就是：

犧牲性能節(jié)省內(nèi)存诈铛，犧牲內(nèi)存提高性能

這是時間換空間乙各，空間換時間的博弈，最后看到底哪個“劃算”（合理）幢竹。

快數(shù)組

先看快數(shù)組耳峦，快數(shù)組是一種線性存儲，其長度是可變的焕毫，可以動態(tài)調(diào)整存儲空間蹲坷。其內(nèi)部有擴(kuò)容和收縮機(jī)制，來看一下V8中擴(kuò)容的實(shí)現(xiàn)邑飒。
源碼（C++）：

./src/objects/js-objects.h

image

拓容時計算新容量是根據(jù)基于舊的容量來的:

新容量 = 舊容量 + 50% + 16

因為JS數(shù)組是動態(tài)可變的循签，所以這樣安排的固定空間勢必會造成內(nèi)存空間的損耗。
然后擴(kuò)容后會將數(shù)組拷貝到新的內(nèi)存空間：

image.png

收縮的實(shí)現(xiàn)源碼（C++）:

image.png

它的判斷依據(jù)是：當(dāng)前容量是否大于等于當(dāng)前數(shù)組長度的2倍+16疙咸，此外的都填入Holes（空洞）對象县匠。什么是Holes，簡單理解就是數(shù)組分配了空間但沒有存入元素撒轮，這里不展開乞旦。快數(shù)組就是空間換時間來提升JS數(shù)組在性能上的缺陷题山，也可以說這是參照編譯型語言的設(shè)計的一種“數(shù)組”兰粉。

一句話總結(jié)：V8用快數(shù)組來實(shí)現(xiàn)內(nèi)存空間的連續(xù)（增加內(nèi)存來提升性能），但由于JS是弱類型語言臀蛛，空間無法固定，所以使用數(shù)組的length來作為依據(jù)崖蜜，在底層進(jìn)行內(nèi)存的重新分配浊仆。

慢數(shù)組

慢數(shù)組底層實(shí)現(xiàn)使用的是 HashTable 哈希表，相比于快數(shù)組豫领，他不用開辟大塊的連續(xù)空間抡柿，從而節(jié)省內(nèi)存，但無疑執(zhí)行效率是比快數(shù)組要低的（時間換空間）等恐。相關(guān)代碼（C++）：

image

快慢數(shù)組之間的轉(zhuǎn)換

JS中長度不固定洲劣，類型不固定，所以我們在適合的適合會做相應(yīng)的轉(zhuǎn)換课蔬，以期望它能以最適合當(dāng)前數(shù)組的方式去提升性能囱稽。對應(yīng)源碼：

image

// 此處注釋翻譯：相比于快（模式）元素，如果字典元素能節(jié)省非常多的內(nèi)存空間扎即，那JSObjects更傾向于字典dictionary吞获。
static const uint32_t kPreferFastElementsSizeFactor = 3;

第二個紅框表示索引-當(dāng)前容量 >= 1024(kMaxGap的值)時况凉，也會從快數(shù)組轉(zhuǎn)為慢數(shù)組。其中 kMaxGap 是一個用于控制快慢數(shù)組轉(zhuǎn)換的試探性常量各拷，源碼中聲明如下：

// 此處注釋翻譯：kMaxGap 是“試探法”常量刁绒，用于控制快慢數(shù)組的轉(zhuǎn)換
static const uint32_t kMaxGap = 1024;

也就是說當(dāng)前數(shù)組在重新賦值要遠(yuǎn)超其所需的容量+1024的時候，就會造成內(nèi)從的浪費(fèi)烤黍，于是改為慢數(shù)組知市。我們來驗證下：

示例代碼一：

let arr = [1];

%DebugPrint(arr) 后截圖如下：

image.png

然后將arr數(shù)組重新賦值:

arr[1024] = 2;

%DebugPrint(arr) 后截圖如下：

image.png

ok，驗證成功蚊荣。接下來我們來看如何從慢數(shù)組到快數(shù)組初狰。

image.png

我們繼續(xù)來驗證:

let arr = [1];
arr[1025] = 1;

上面代碼聲明的數(shù)組使用的是慢數(shù)組（Dictionary），截圖如下

image.png

接下來讓索引從500開始填充數(shù)字1媳叨，讓其滿足快數(shù)組節(jié)省空間小于50％：

for(let i=500;i<1024;i++){
    arr[i]=1;
}

得到結(jié)果如下：

image.png

最終我們得到結(jié)果腥光，讓arr數(shù)組從慢數(shù)組（Dictionary）轉(zhuǎn)為了快數(shù)組（HOLEY_SMI_ELEMENTS就是Fast Holey Elements）.

ArrayBuffer

講了真么多，無非就是在說JS中由于語言“特色”而在數(shù)組的實(shí)現(xiàn)上有一些性能問題糊秆，那么為了解決這個問題V8引擎中引入了連續(xù)數(shù)組的概念武福，這是在JS代碼轉(zhuǎn)譯層做的優(yōu)化，那么還有其他方式嗎痘番？

當(dāng)然有捉片，那就是ES6中ArrayBuffer。ArrayBuffer 對象用來表示通用的汞舱、固定長度的原始二進(jìn)制數(shù)據(jù)緩沖區(qū)伍纫，它是一個字節(jié)數(shù)組。使用ArrayBuffer能在操作系統(tǒng)內(nèi)存中得到一塊連續(xù)的二進(jìn)制區(qū)域昂芜。然后這塊區(qū)域供JS去使用莹规。

// create an ArrayBuffer with a size in bytes
const buffer = new ArrayBuffer(8); // 入?yún)?為length
 
console.log(buffer.byteLength);

但需要注意的是ArrayBuffer本身不具備操作字節(jié)能力，需要通過視圖去操作泌神。比如：

let buffer = new ArrayBuffer(3);
let view = new DataView(buffer);
view.setInt8(0, 8)

面試題：數(shù)組為什么查找元素效率比較高良漱？

如果你是這樣回答的：數(shù)組之所以查找效率高，是因為它有下標(biāo)欢际。對不起母市，我只能給你50分。

針對于這樣的問題损趋，我們應(yīng)該怎么回答呢窒篱，實(shí)際上這個需要從數(shù)組這種數(shù)據(jù)結(jié)構(gòu)存儲元素特點(diǎn)的方面進(jìn)行解說，以java為例：

1. Java的數(shù)組中存儲的每個元素類型一致，也就是說每個元素占用的空間大小相同墙杯。

2. Java的數(shù)組中存儲的每個元素在空間存儲上配并，內(nèi)存地址是連續(xù)狀態(tài)的。

3. 通常首元素的內(nèi)存地址作為整個數(shù)組對象的內(nèi)存地址高镐，可見我們是知道首元素內(nèi)存地址的溉旋。

4. 再加上數(shù)組中的元素是有下標(biāo)的，有下標(biāo)就可以計算出被查找的元素和首元素的偏移量嫉髓。

綜上所述观腊，實(shí)際上在數(shù)組中查找元素是可以通過數(shù)學(xué)表達(dá)式計算被查找元素的內(nèi)存地址的，通過內(nèi)存地址可以直接定位該元素算行。也就是說數(shù)組中有100個元素和有100萬個元素梧油，實(shí)際上在查找方面效率是一樣的。

更多細(xì)節(jié)本文不再展開州邢，請讀者自行探索儡陨。

參考：http://www.zyiz.net/tech/detail-142859.html