探究JS V8引擎下的“數組”底層實作

JavaScript 中的數組有很多特性：存放不同類型元素、數組長度可變等等，這與資料結構中定義的數組結構或者C++、Java等語言中的數組不太一樣，那麼JS數組的這些特性底層是如何實作的呢，我們打開V8引擎的源碼，從中尋找到了答案。V8中對數組做了一層封裝，使其有兩種實作方式：快數組和慢數組，快數組底層是連續記憶體，通過索引直接定位，慢數組底層是哈希表，通過計算哈希值來定位。兩種實作方式各有特點，有各自的使用情況，也會互相轉換。

一、背景

使用 JS 的數組時，發現 JS 的數組可以存放不同類型的元素、并且數組長度是可變的。資料結構中定義的數組是定長的、資料類型一緻的存儲結構。JS 中的數組竟然如此特殊，這也是為什麼标題中數組二字加上了“”的原因。帶着一臉的懵逼，打開V8源碼，一探究竟。

二、什麼是數組

首先來看下什麼是數組，下面的圖是維基百科上對于數組的定義：

圖中有兩個關鍵的點，相同類型、連續記憶體。

這兩個關鍵點先不必深究，繼續往下看，下面來解釋。

看完資料結構中的定義，再來看下具體語言中對數組的實作：

C、C++、Java、Scala 等語言中數組的實作，是通過在記憶體中劃分一串連續的、固定長度的空間，來實作存放一組有限個相同資料類型的資料結構。這裡面也涉及到了幾個重要的概念：連續、固定長度、相同資料類型，與資料結構中的定義是類似的。

下面來分别解釋下這幾個概念：

1.連續

連續空間存儲是數組的特點，下圖是數組在記憶體中的存儲示意圖。

可以明顯的看出各元素在記憶體中是相鄰的，是一種線性的存儲結構。

2.固定長度

因為數組的空間是連續的，這就意味着在記憶體中會有一整塊空間來存放數組，如果不是固定長度，那麼記憶體中位于數組之後的區域會沒辦法配置設定，記憶體不知道數組還要不要繼續存放，要使用多長的空間。長度固定，就界定了數組使用記憶體的界限，數組之外的空間可以配置設定給别人使用。

3.相同資料類型

因為數組的長度是固定的，如果不是相同資料類型，一會存 int ，一會存String ，兩種不同長度的資料類型，不能保證各自存放幾個，這樣有悖固定長度的規定，是以也要是相同的資料類型。

看到這，想必大部分人應該感覺：嗯，這跟我認識的數組幾乎吻合吧。

那我們再來點刺激的，進入正菜，JavaScript 中的數組。

三、JavaScript 中的數組

先來看段代碼：

let arr = [100, 12.3, "red", "blue", "green"];
arr[arr.length] = "black";
console.log(arr.length);    // 6
console.log(arr[arr.length-1]);  //black           

這短短幾行代碼可以看出 JS 數組非同尋常的地方。

• 第一行代碼，數組中竟然存放了三種資料類型？
• 第二行代碼，竟然向數組中添加了一個值？
• 第三行和第四行代碼驗證了，數組的長度改變了，添加的值也生效了。

除了這些，JS的數組還有很多特殊的地方：

1. JS 數組中不止可以存放上面的三種資料類型，它可以存放數組、對象、函數、Number、Undefined、Null、String、Boolean 等等。
2. JS 數組可以動态的改變容量，根據元素的數量來擴容、收縮。
3. JS 數組可以表現的像棧一樣，為數組提供了push()和pop()方法。也可以表現的像隊列一樣，使用shift()和 push()方法，可以像使用隊列一樣使用數組。
4. JS 數組可以使用for-each周遊，可以排序，可以倒置。
5. JS 提供了很多操作數組的方法，比如Array.concat()、Array.join()、Array.slice()。

看到這裡，應該可以看出一點端倪，大膽猜想，JS的數組不是基礎的資料結構實作的，應該是在基礎上面做了一些封裝。

下面發車，一步一步地驗證我們的猜想。

四、刨根問底：從V8源碼上看數組的實作

Talk is cheap，show me the code.

下面一圖是 V8 中數組的源碼：

首先，我們看到JSArray 是繼承自JSObject，也就是說，數組是一個特殊的對象。

那這就好解釋為什麼JS的數組可以存放不同的資料類型，它是個對象嘛，内部也是key-value的存儲形式。

我們使用這段代碼來驗證一下：

let a = [1, "hello", true, function () {
  return 1;
}];           

通過 jsvu 來看一下底層是如何實作的：

可以看到，底層就是個 Map ，key 為0，1，2，3這種索引，value 就是數組的元素。

其中，數組的index其實是字元串。

驗證完這個問題，我們再繼續看上面的V8源碼，摩拳擦掌，準備見大招了！

從注釋上可以看出，JS 數組有兩種表現形式，fast 和 slow ，啥？英文看不懂？那我讓谷歌幫我們翻譯好了！

fast ：

快速的後備存儲結構是 FixedArray ，并且數組長度 <= elements.length();

slow ：

緩慢的後備存儲結構是一個以數字為鍵的 HashTable 。

HashTable，維基百科中解釋的很好：

散清單（Hash table，也叫哈希表），是根據鍵（Key）而直接通路在記憶體存儲位置的資料結構。也就是說，它通過計算一個關于鍵值的函數，将所需查詢的資料映射到表中一個位置來通路記錄，這加快了查找速度。這個映射函數稱做散列函數，存放記錄的數組稱做散清單。

源碼注釋中的fast和slow，隻是簡單的解釋了一下，其對應的是快數組和慢數組，下面來具體的看一下兩種形式是如何實作的。

1、快數組（FAST ELEMENTS）

快數組是一種線性的存儲方式。新建立的空數組，預設的存儲方式是快數組，快數組長度是可變的，可以根據元素的增加和删除來動态調整存儲空間大小，内部是通過擴容和收縮機制實作，那來看下源碼中是怎麼擴容和收縮的。

源碼中擴容的實作方法（C++）：

新容量的的計算方式：

即new_capacity = old_capacity /2 + old_capacity + 16

也就是，擴容後的新容量 = 舊容量的1.5倍 + 16

擴容後會将數組拷貝到新的記憶體空間中，源碼：

看完了擴容，再來看看當空間多餘時如何收縮數組空間。

源碼中收縮的實作方法（C++）:

可以看出收縮數組的判斷是：

如果容量 >= length的2倍 + 16，則進行收縮容量調整，否則用holes對象（什麼是holes對象？下面來解釋）填充未被初始化的位置。

如果收縮，那收縮到多大呢？

看上面圖中的這段代碼：

這個elements_to_trim就是需要收縮的大小，需要根據 length + 1 和 old_length 進行判斷，是将空出的空間全部收縮掉還是隻收縮二分之一。

解釋完了擴容和減容，來看下剛剛提到的holes對象。

holes （空洞）對象指的是數組中配置設定了空間，但是沒有存放元素的位置。對于holes，快數組中有個專門的模式，在 Fast Elements 模式中有一個擴充，是Fast Holey Elements模式。

Fast Holey Elements 模式适合于數組中的 holes （空洞）情況，即隻有某些索引存有資料，而其他的索引都沒有指派的情況。

那什麼時候會是Fast Holey Elements 模式呢？

當數組中有空洞，沒有指派的數組索引将會存儲一個特殊的值，這樣在通路這些位置時就可以得到 undefined。這種情況下就會是 Fast Holey Elements 模式。

Fast Holey Elements 模式與Fast Elements 模式一樣，會動态配置設定連續的存儲空間，配置設定空間的大小由最大的索引值決定。

建立數組時，如果沒有設定容量，V8會預設使用 Fast Elements 模式實作。

如果要對數組設定容量，但并沒有進行内部元素的初始化，例如let a = new Array(10);，這樣的話數組内部就存在了空洞，就會以Fast Holey Elements 模式實作。

使用jsvu調用v8-debug版本的底層實作來驗證一下：

一目了然，HOLEY_SMI_ELEMENTS 就是Fast Holey Elements 模式 。

如果對數組進行了初始化，比如let a = new Array(1,2,3);，這種就不存在空洞，就是以Fast Elements 模式實作。

驗證：

這個PACKED_SMI_ELEMENTS就是Fast Elements 模式。

快數組先到這，再來看下慢數組：

2、慢數組（DICTIONARY ELEMENTS）

慢數組是一種字典的記憶體形式。不用開辟大塊連續的存儲空間，節省了記憶體，但是由于需要維護這樣一個 HashTable，其效率會比快數組低。

源碼中 Dictionary 的結構

可以看到，内部是一個HashTable，然後定義了一些操作方法，和 Java 的 HashMap類似，沒有什麼特别之處。

了解了數組的兩種實作方式，我們來總結下兩者的差別。

3、快數組、慢數組的差別

1. 存儲方式方面：快數組記憶體中是連續的，慢數組在記憶體中是零散配置設定的。
2. 記憶體使用方面：由于快數組記憶體是連續的，可能需要開辟一大塊供其使用，其中還可能有很多空洞，是比較費記憶體的。慢數組不會有空洞的情況，且都是零散的記憶體，比較節省記憶體空間。
3. 周遊效率方面：快數組由于是空間連續的，周遊速度很快，而慢數組每次都要尋找 key 的位置，周遊效率會差一些。

既然有快數組和慢數組，兩者的也有各自的特點，每個數組的存儲結構不會是一成不變的，會有具體情況下的快慢數組轉換，下面來看一下什麼情況下會發生轉換。

五、快數組慢數組之間的轉換

1、快 -> 慢

首先來看 V8 中判斷快數組是否應該轉為慢數組的源碼：

關鍵代碼：

1. 新容量 >= 3 擴容後的容量 2 ，會轉變為慢數組。
2. 當加入的 index- 目前capacity >= kMaxGap（1024） 時（也就是至少有了 1024 個空洞），會轉變為慢數組。

我們主要來看下第二種關鍵代碼的情況。

kMaxGap 是源碼中的一個常量，值為1024。

也就是說，當對數組指派時使用遠超目前數組的容量+ 1024時（這樣出現了大于等于 1024 個空洞，這時候要對數組配置設定大量空間則将可能造成存儲空間的浪費，為了空間的優化，會轉化為慢數組。

代碼實錘：

let a = [1, 2]
a[1030] = 1;           

數組中隻有三個元素，但是卻在 1030 的位置存放了一個值，那麼中間會有多于1024個空洞，這時就會變為慢數組。

來驗證一下：

可以看到，此時的數組确實是字典類型了，成功！

好了，看完了快數組轉慢數組，再反過來看下慢數組轉換為快數組。

2、慢 -> 快

處于哈希表實作的數組，在每次空間增長時， V8 的啟發式算法會檢查其空間占用量， 若其空洞元素減少到一定程度，則會将其轉化為快數組模式。

V8中是否應該轉為快數組的判斷源碼：

當慢數組的元素可存放在快數組中且長度在 smi 之間且僅節省了50%的空間,則會轉變為快數組

來寫代碼驗證一下：

let a = [1,2];
a[1030] = 1;
for (let i = 200; i < 1030; i++) {
    a[i] = i;
}           

上面我們說過的，在 1030 的位置上面添加一個值，會造成多于 1024 個空洞，數組會使用為 Dictionary 模式來實作。

那麼我們現在往這個數組中再添加幾個值來填補空洞，往 200-1029 這些位置上指派，使慢數組不再比快數組節省 50% 的空間，會發生什麼神奇的事情呢？

可以看到，數組變成了快數組的 Fast Holey Elements 模式，驗證成功。

那是不是快數組存儲空間連續，效率高，就一定更好呢？其實不然。

3、各有優勢

快數組就是以空間換時間的方式，申請了大塊連續記憶體，提高效率。

慢數組以時間換空間，不必申請連續的空間，節省了記憶體，但需要付出效率變差的代價。

六、擴充：ArrayBuffer

JS在ES6也推出了可以按照需要配置設定連續記憶體的數組，這就是ArrayBuffer。

ArrayBuffer會從記憶體中申請設定的二進制大小的空間，但是并不能直接操作它，需要通過ArrayBuffer建構一個視圖，通過視圖來操作這個記憶體。

let buffer = new ArrayBuffer(1024);           

這行代碼就申請了 1kb 的記憶體區域。但是并不能對 arrayBuffer 直接操作，需要将它賦給一個視圖來操作記憶體。

let intArray = new Int32Array(bf);           

這行代碼建立了有符号的32位的整數數組，每個數占 4 位元組，長度也就是 1024 / 4 = 256 個。

代碼驗證：

七、總結

看到這，腦瓜子是不是嗡嗡的？喘口氣，我們來回顧一下，這篇文章我們主要讨論了這幾件事：

1. 傳統意義上的數組是怎麼樣的
2. JavaScript 中的數組有哪些特别之處
3. 從V8源碼下研究 JS 數組的底層實作
4. JS 數組的兩種模式是如何轉換的
5. ArrayBuffer

總的來說，JS 的數組看似與傳統數組不一樣，其實隻是 V8 在底層實作上做了一層封裝，使用兩種資料結構實作數組，通過時間和空間緯度的取舍，優化數組的性能。

了解數組的底層實作，可以幫助我們寫出執行效率更高的代碼。