本文首發(fā)于 vivo互聯(lián)網(wǎng)技術(shù) 微信公眾號?
鏈接：https://mp.weixin.qq.com/s/np9Yoo02pEv9n_LCusZn3Q
作者：李超創(chuàng)新互聯(lián)建站是一家專業(yè)提供連山企業(yè)網(wǎng)站建設(shè),專注與網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站設(shè)計(jì)、H5開發(fā)、小程序制作等業(yè)務(wù)。10年已為連山眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站制作公司優(yōu)惠進(jìn)行中。
JavaScript 中的數(shù)組有很多特性：存放不同類型元素、數(shù)組長度可變等等，這與數(shù)據(jù)結(jié)構(gòu)中定義的數(shù)組結(jié)構(gòu)或者C++、Java等語言中的數(shù)組不太一樣，那么JS數(shù)組的這些特性底層是如何實(shí)現(xiàn)的呢，我們打開V8引擎的源碼，從中尋找到了答案。V8中對數(shù)組做了一層封裝，使其有兩種實(shí)現(xiàn)方式：快數(shù)組和慢數(shù)組，快數(shù)組底層是連續(xù)內(nèi)存，通過索引直接定位，慢數(shù)組底層是哈希表，通過計(jì)算哈希值來定位。兩種實(shí)現(xiàn)方式各有特點(diǎn)，有各自的使用情況，也會(huì)相互轉(zhuǎn)換。
使用 JS 的數(shù)組時(shí)，發(fā)現(xiàn) JS 的數(shù)組可以存放不同類型的元素、并且數(shù)組長度是可變的。數(shù)據(jù)結(jié)構(gòu)中定義的數(shù)組是定長的、數(shù)據(jù)類型一致的存儲結(jié)構(gòu)。JS 中的數(shù)組竟然如此特殊，這也是為什么標(biāo)題中數(shù)組二字加上了“”的原因。帶著一臉的懵逼，打開V8源碼，一探究竟。
首先來看下什么是數(shù)組，下面的圖是維基百科上對于數(shù)組的定義：
圖中有兩個(gè)關(guān)鍵的點(diǎn)，相同類型、連續(xù)內(nèi)存。
這兩個(gè)關(guān)鍵點(diǎn)先不必深究，繼續(xù)往下看，下面來解釋。
看完數(shù)據(jù)結(jié)構(gòu)中的定義，再來看下具體語言中對數(shù)組的實(shí)現(xiàn)：
C、C++、Java、Scala 等語言中數(shù)組的實(shí)現(xiàn)，是通過在內(nèi)存中劃分一串連續(xù)的、固定長度的空間，來實(shí)現(xiàn)存放一組有限個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)。這里面也涉及到了幾個(gè)重要的概念：連續(xù)、固定長度、相同數(shù)據(jù)類型，與數(shù)據(jù)結(jié)構(gòu)中的定義是類似的。
下面來分別解釋下這幾個(gè)概念：
連續(xù)空間存儲是數(shù)組的特點(diǎn)，下圖是數(shù)組在內(nèi)存中的存儲示意圖。
可以明顯的看出各元素在內(nèi)存中是相鄰的，是一種線性的存儲結(jié)構(gòu)。
因?yàn)閿?shù)組的空間是連續(xù)的，這就意味著在內(nèi)存中會(huì)有一整塊空間來存放數(shù)組，如果不是固定長度，那么內(nèi)存中位于數(shù)組之后的區(qū)域會(huì)沒辦法分配，內(nèi)存不知道數(shù)組還要不要繼續(xù)存放，要使用多長的空間。長度固定，就界定了數(shù)組使用內(nèi)存的界限，數(shù)組之外的空間可以分配給別人使用。
因?yàn)閿?shù)組的長度是固定的，如果不是相同數(shù)據(jù)類型，一會(huì)存 int ，一會(huì)存String ，兩種不同長度的數(shù)據(jù)類型，不能保證各自存放幾個(gè)，這樣有悖固定長度的規(guī)定，所以也要是相同的數(shù)據(jù)類型。
看到這，想必大部分人應(yīng)該感覺：嗯，這跟我認(rèn)識的數(shù)組幾乎吻合吧。
那我們再來點(diǎn)刺激的，進(jìn)入正菜，JavaScript 中的數(shù)組。
先來看段代碼：
重慶分公司
重慶分公司
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 數(shù)組非同尋常的地方。
第一行代碼，數(shù)組中竟然存放了三種數(shù)據(jù)類型？
第二行代碼，竟然向數(shù)組中添加了一個(gè)值？
除了這些，JS的數(shù)組還有很多特殊的地方：
JS 數(shù)組中不止可以存放上面的三種數(shù)據(jù)類型，它可以存放數(shù)組、對象、函數(shù)、Number、Undefined、Null、String、Boolean 等等。
JS 數(shù)組可以動(dòng)態(tài)的改變?nèi)萘?，根?jù)元素的數(shù)量來擴(kuò)容、收縮。
JS 數(shù)組可以表現(xiàn)的像棧一樣，為數(shù)組提供了push()和pop()方法。也可以表現(xiàn)的像隊(duì)列一樣，使用shift()和 push()方法，可以像使用隊(duì)列一樣使用數(shù)組。
JS 數(shù)組可以使用for-each遍歷，可以排序，可以倒置。
看到這里，應(yīng)該可以看出一點(diǎn)端倪，大膽猜想，JS的數(shù)組不是基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，應(yīng)該是在基礎(chǔ)上面做了一些封裝。
下面發(fā)車，一步一步地驗(yàn)證我們的猜想。
Talk is cheap，show me the code.
下面一圖是 V8 中數(shù)組的源碼：
首先，我們看到JSArray 是繼承自JSObject，也就是說，數(shù)組是一個(gè)特殊的對象。
那這就好解釋為什么JS的數(shù)組可以存放不同的數(shù)據(jù)類型，它是個(gè)對象嘛，內(nèi)部也是key-value的存儲形式。
我們使用這段代碼來驗(yàn)證一下：
let a = [1, "hello", true, function () {
return 1;
}];通過 jsvu 來看一下底層是如何實(shí)現(xiàn)的：
可以看到，底層就是個(gè) Map ，key 為0，1，2，3這種索引，value 就是數(shù)組的元素。
其中，數(shù)組的index其實(shí)是字符串。
驗(yàn)證完這個(gè)問題，我們再繼續(xù)看上面的V8源碼，摩拳擦掌，準(zhǔn)備見大招了！
從注釋上可以看出，JS 數(shù)組有兩種表現(xiàn)形式，fast 和 slow ，啥？英文看不懂？那我讓谷歌幫我們翻譯好了！
fast ：
快速的后備存儲結(jié)構(gòu)是 FixedArray ，并且數(shù)組長度 <= elements.length();
slow ：
緩慢的后備存儲結(jié)構(gòu)是一個(gè)以數(shù)字為鍵的 HashTable 。
HashTable，維基百科中解釋的很好：
散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來訪問記錄，這加快了查找速度。這個(gè)映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。
源碼注釋中的fast和slow，只是簡單的解釋了一下，其對應(yīng)的是快數(shù)組和慢數(shù)組，下面來具體的看一下兩種形式是如何實(shí)現(xiàn)的。
快數(shù)組是一種線性的存儲方式。新創(chuàng)建的空數(shù)組，默認(rèn)的存儲方式是快數(shù)組，快數(shù)組長度是可變的，可以根據(jù)元素的增加和刪除來動(dòng)態(tài)調(diào)整存儲空間大小，內(nèi)部是通過擴(kuò)容和收縮機(jī)制實(shí)現(xiàn)，那來看下源碼中是怎么擴(kuò)容和收縮的。
源碼中擴(kuò)容的實(shí)現(xiàn)方法（C++）：
新容量的的計(jì)算方式：
即new_capacity = old_capacity /2 + old_capacity + 16
也就是，擴(kuò)容后的新容量 = 舊容量的1.5倍 + 16
擴(kuò)容后會(huì)將數(shù)組拷貝到新的內(nèi)存空間中，源碼：
看完了擴(kuò)容，再來看看當(dāng)空間多余時(shí)如何收縮數(shù)組空間。
源碼中收縮的實(shí)現(xiàn)方法（C++）:
可以看出收縮數(shù)組的判斷是：
如果容量 >= length的2倍 + 16，則進(jìn)行收縮容量調(diào)整，否則用holes對象（什么是holes對象？下面來解釋）填充未被初始化的位置。
如果收縮，那收縮到多大呢？
看上面圖中的這段代碼：
這個(gè)elements_to_trim就是需要收縮的大小，需要根據(jù) length + 1 和 old_length 進(jìn)行判斷，是將空出的空間全部收縮掉還是只收縮二分之一。
解釋完了擴(kuò)容和減容，來看下剛剛提到的holes對象。
holes （空洞）對象指的是數(shù)組中分配了空間，但是沒有存放元素的位置。對于holes，快數(shù)組中有個(gè)專門的模式，在 Fast Elements 模式中有一個(gè)擴(kuò)展，是Fast Holey Elements模式。
Fast Holey Elements 模式適合于數(shù)組中的 holes （空洞）情況，即只有某些索引存有數(shù)據(jù)，而其他的索引都沒有賦值的情況。
那什么時(shí)候會(huì)是Fast Holey Elements 模式呢？
當(dāng)數(shù)組中有空洞，沒有賦值的數(shù)組索引將會(huì)存儲一個(gè)特殊的值，這樣在訪問這些位置時(shí)就可以得到 undefined。這種情況下就會(huì)是 Fast Holey Elements 模式。
Fast Holey Elements 模式與Fast Elements 模式一樣，會(huì)動(dòng)態(tài)分配連續(xù)的存儲空間，分配空間的大小由最大的索引值決定。
新建數(shù)組時(shí)，如果沒有設(shè)置容量，V8會(huì)默認(rèn)使用 Fast Elements 模式實(shí)現(xiàn)。
如果要對數(shù)組設(shè)置容量，但并沒有進(jìn)行內(nèi)部元素的初始化，例如let a = new Array(10);，這樣的話數(shù)組內(nèi)部就存在了空洞，就會(huì)以Fast Holey Elements 模式實(shí)現(xiàn)。
使用jsvu調(diào)用v8-debug版本的底層實(shí)現(xiàn)來驗(yàn)證一下：
一目了然，HOLEY_SMI_ELEMENTS?就是Fast Holey Elements 模式 。
如果對數(shù)組進(jìn)行了初始化，比如let a = new Array(1,2,3);，這種就不存在空洞，就是以Fast Elements 模式實(shí)現(xiàn)。
驗(yàn)證：
這個(gè)PACKED_SMI_ELEMENTS就是Fast Elements 模式。
快數(shù)組先到這，再來看下慢數(shù)組：
慢數(shù)組是一種字典的內(nèi)存形式。不用開辟大塊連續(xù)的存儲空間，節(jié)省了內(nèi)存，但是由于需要維護(hù)這樣一個(gè) HashTable，其效率會(huì)比快數(shù)組低。
源碼中 Dictionary 的結(jié)構(gòu)
可以看到，內(nèi)部是一個(gè)HashTable，然后定義了一些操作方法，和 Java 的 HashMap類似，沒有什么特別之處。
了解了數(shù)組的兩種實(shí)現(xiàn)方式，我們來總結(jié)下兩者的區(qū)別。
存儲方式方面：快數(shù)組內(nèi)存中是連續(xù)的，慢數(shù)組在內(nèi)存中是零散分配的。
內(nèi)存使用方面：由于快數(shù)組內(nèi)存是連續(xù)的，可能需要開辟一大塊供其使用，其中還可能有很多空洞，是比較費(fèi)內(nèi)存的。慢數(shù)組不會(huì)有空洞的情況，且都是零散的內(nèi)存，比較節(jié)省內(nèi)存空間。
既然有快數(shù)組和慢數(shù)組，兩者的也有各自的特點(diǎn)，每個(gè)數(shù)組的存儲結(jié)構(gòu)不會(huì)是一成不變的，會(huì)有具體情況下的快慢數(shù)組轉(zhuǎn)換，下面來看一下什么情況下會(huì)發(fā)生轉(zhuǎn)換。
首先來看 V8 中判斷快數(shù)組是否應(yīng)該轉(zhuǎn)為慢數(shù)組的源碼：
關(guān)鍵代碼：
新容量 >= 3 擴(kuò)容后的容量 2 ，會(huì)轉(zhuǎn)變?yōu)槁龜?shù)組。
我們主要來看下第二種關(guān)鍵代碼的情況。
kMaxGap 是源碼中的一個(gè)常量，值為1024。
也就是說，當(dāng)對數(shù)組賦值時(shí)使用遠(yuǎn)超當(dāng)前數(shù)組的容量+ 1024時(shí)（這樣出現(xiàn)了大于等于 1024 個(gè)空洞，這時(shí)候要對數(shù)組分配大量空間則將可能造成存儲空間的浪費(fèi)，為了空間的優(yōu)化，會(huì)轉(zhuǎn)化為慢數(shù)組。
代碼實(shí)錘：
let a = [1, 2]
a[1030] = 1;數(shù)組中只有三個(gè)元素，但是卻在 1030 的位置存放了一個(gè)值，那么中間會(huì)有多于1024個(gè)空洞，這時(shí)就會(huì)變?yōu)槁龜?shù)組。
來驗(yàn)證一下：
可以看到，此時(shí)的數(shù)組確實(shí)是字典類型了，成功！
好了，看完了快數(shù)組轉(zhuǎn)慢數(shù)組，再反過來看下慢數(shù)組轉(zhuǎn)換為快數(shù)組。
處于哈希表實(shí)現(xiàn)的數(shù)組，在每次空間增長時(shí)， V8 的啟發(fā)式算法會(huì)檢查其空間占用量， 若其空洞元素減少到一定程度，則會(huì)將其轉(zhuǎn)化為快數(shù)組模式。
V8中是否應(yīng)該轉(zhuǎn)為快數(shù)組的判斷源碼：
關(guān)鍵代碼：
當(dāng)慢數(shù)組的元素可存放在快數(shù)組中且長度在 smi 之間且僅節(jié)省了50%的空間,則會(huì)轉(zhuǎn)變?yōu)榭鞌?shù)組
來寫代碼驗(yàn)證一下：
let a = [1,2];
a[1030] = 1;
for (let i = 200; i < 1030; i++) {
a[i] = i;
}上面我們說過的，在 1030 的位置上面添加一個(gè)值，會(huì)造成多于 1024 個(gè)空洞，數(shù)組會(huì)使用為 Dictionary 模式來實(shí)現(xiàn)。
那么我們現(xiàn)在往這個(gè)數(shù)組中再添加幾個(gè)值來填補(bǔ)空洞，往 200-1029 這些位置上賦值，使慢數(shù)組不再比快數(shù)組節(jié)省 50% 的空間，會(huì)發(fā)生什么神奇的事情呢？
可以看到，數(shù)組變成了快數(shù)組的 Fast Holey Elements 模式，驗(yàn)證成功。
那是不是快數(shù)組存儲空間連續(xù)，效率高，就一定更好呢？其實(shí)不然。
快數(shù)組就是以空間換時(shí)間的方式，申請了大塊連續(xù)內(nèi)存，提高效率。
慢數(shù)組以時(shí)間換空間，不必申請連續(xù)的空間，節(jié)省了內(nèi)存，但需要付出效率變差的代價(jià)。
JS在ES6也推出了可以按照需要分配連續(xù)內(nèi)存的數(shù)組，這就是ArrayBuffer。
ArrayBuffer會(huì)從內(nèi)存中申請?jiān)O(shè)定的二進(jìn)制大小的空間，但是并不能直接操作它，需要通過ArrayBuffer構(gòu)建一個(gè)視圖，通過視圖來操作這個(gè)內(nèi)存。
let buffer = new ArrayBuffer(1024);這行代碼就申請了 1kb 的內(nèi)存區(qū)域。但是并不能對 arrayBuffer 直接操作，需要將它賦給一個(gè)視圖來操作內(nèi)存。
let intArray = new Int32Array(bf);這行代碼創(chuàng)建了有符號的32位的整數(shù)數(shù)組，每個(gè)數(shù)占 4 字節(jié)，長度也就是 1024 / 4 = 256 個(gè)。
代碼驗(yàn)證：
看到這，腦瓜子是不是嗡嗡的？喘口氣，我們來回顧一下，這篇文章我們主要討論了這幾件事：
傳統(tǒng)意義上的數(shù)組是怎么樣的
JavaScript 中的數(shù)組有哪些特別之處
從V8源碼下研究 JS 數(shù)組的底層實(shí)現(xiàn)
JS 數(shù)組的兩種模式是如何轉(zhuǎn)換的
總的來說，JS 的數(shù)組看似與傳統(tǒng)數(shù)組不一樣，其實(shí)只是 V8 在底層實(shí)現(xiàn)上做了一層封裝，使用兩種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)數(shù)組，通過時(shí)間和空間緯度的取舍，優(yōu)化數(shù)組的性能。
了解數(shù)組的底層實(shí)現(xiàn)，可以幫助我們寫出執(zhí)行效率更高的代碼。
