JavaScript中的稀疏數組與密集數組

​

一般而言，javaScript中的數組是稀疏的，也就是說數組中的元素之間可以有空隙，因為一個數組其實就是一個鍵值映射。這篇本文解釋了如何建立稀疏數組和不稀疏的數組，以及稀疏數組和密集數組之間的差別。

例如以下的js代碼建立的就是一個密集數組:​

var data = [3,1,6,9,2];      

什麼是稀疏數組呢？與密集數組相反。JavaScript并不強制要求數組元素是緊密相連的，即同意間隙的存在。例如以下的js代碼是合法的：

var sparse = new Array();
 sparse[0] = 0;
 sparse[3] = 3;
 alert(sparse[0]);//輸出0
 alert(sparse[1]);//輸出undefined      

建立稀疏數組

例如以下代碼建立了一個固定長度的稀疏數組

var a = new Array(3); 
a[2] = 1;
alert(a[0]);//undefined
alert(a[2]);//1      

說白了js中建立稀疏數組非常easy，僅僅要你有益讓數組元素之間存在間隙就可以。如：

var arr = []; 
arr[0] = 0;
arr[200] = 200;      

建立密集數組

什麼是密集數組呢？在java和C語言中，數組是一片連續的存儲空間，有着固定的長度。

增加數組事實上位置是address。長度為n。那麼占用的存儲空間是address[0],address[1],address[2].......address[n-1]。即數組元素之間是緊密相連的，不存在空隙。

能夠看到js中的數組一般都是稀疏的，一般來說稀疏數組的周遊比較麻煩。

var dense = Array.apply(null, Array(3));      

這行代碼等同于var  dense = Array(undefined, undefined, undefined) ;呵呵是不是認為非常奇怪，這樣的方式跟稀疏數組沒有什麼差別。

看代碼：

//稀疏數組
var array = new Array(3); 
array[2] = "name";
for(var a in array) {
    console.log("index=" + a + ",value=" + array[a]);
}
// 密集數組
var dense = Array.apply(null, Array(3)); 
dense[2] = "name";
for(var a in dense) {
  console.log("index=" + a + ",value=" + dense[a]);
}      

能夠看到确實是有差別的：稀疏數組僅僅周遊了一次(由于僅僅有一個元素)，密集數組周遊了3次。

稀疏數組與密集數組差別

稀疏數組：索引不連續，數組長度大于元素個數的數組, 可以簡單了解為有empty的數組；

密集數組：索引連續, 數組長度等于元素個數的數組；

稀疏數組在大多數周遊數組的方法中，遇到「empty」元素的時候，callback 函數是不會執行的，如：map, forEach, filter 等, 而且這種現象在 for...in 語句中，同樣适用。

nonst arr = [3,,4,,5] // 稀疏數組 
arr.forEach(item => { console.log(item)}) // 輸出：3，4，5  


console.log(arr.map(item => {
  console.log(item)
  return item+1
})) // 輸出：3，4，5，[4, empty, 5, empty, 6]
// 值得注意的是：稀疏數組中 「empty」元素在 map 後傳回的數組中仍然為 「empty」  


console.log(arr1.filter(item => item === undefined)) // 輸出：[]  
console.log(arr1.filter(item => item > 3 )) // 輸出：[4,5] 


for (var i in a) { console.log(a[i]) } // 輸出：3，4，5
for (var i of a) { console.log(i) } // 輸出：3，undefined，4，undefined，5      

稀疏數組在通路元素的速度上比密集數組慢

const arr = new Array(200000)
arr[19999] = 88
console.time('using[]')
arr[19999]
console.timeEnd('using[]')
// using[]: 0.031982421875ms


const ddd = [...new Array(200000)]
ddd[19999] = 88
console.time('using[]')
ddd[19999]
console.timeEnd('using[]')
// using[]: 0.010009765625ms      

具體原因是，對于稀疏數組 V8 引擎通路對象是使用 散清單模式的，該種模式在通路時需要計算一遍哈希值，是以會比較慢，但散清單對于空間利用來說，效率更高。

而密集數組，它是申請一段連續的記憶體空間，通路時可以直接通過「索引」來通路，是以速度比較快；

稀疏數組在一些數組方法中與密集數組存在差異。

var a = [1,,,,]
var b = new Array(5)
var c = []  


// Array.prototype.every() 和 Array.prototype.some() 


b.every(i => i === undefined); // true  
a.some(i => i === undefined); // false      

前面說到周遊數組的方法會跳過「empty」元素。是以在排除後「empty」元素後，數組内找不到 undefined 元素， some 會傳回 false。空數組使用 every 時，傳回 true。

// Array.prototype.find() 和 Array.prototype.findIndex()
a.findIndex(i => i === undefined) // 1
a.find(i => i === undefined) //undefined      

由于find和findIndex是使用 for 循環來實作的，與forEach有所不同,是以這兩種方法能周遊到「empty」元素。

// Array.prototype.includes() 
a.includes() // true
b.includes() // true
c.includes() // false
a.includes(undefined) // true
b.includes(undefined) // true      

includes() 方法表現較為特殊，大體可以總結為：當數組長度為 0 時，include 一定傳回 false；當數組為稀疏數組且長度不為 0 ，且入參為空或 undefined 時，include 一定傳回 true；

// Array.prototype.sort()
var sortArr = [5,,9,,1]
sortArr.sort()
console.log(sortArr) // 輸出：[1, 5, 9, empty × 2]      

sort 方法能夠正常排序，且sort 方法不會周遊「empty」元素，但 sort 後數組的長度并不會變化，這一點與map的表現一緻，map得到的數組長度也不變。​

// Array.prototype.join()  
[undefined,undefined,1].join() // 輸出：",,1"
[5,,9,,1].join() // 輸出："5,,9,,1"      

「empty」元素仍然會被保留。Array.prototype上的其他方法，稀疏數組和密集數組表現基本一緻。

總結

JavaScript中的數組并不像我們在C或java等語言中遇到的正常數組，在js中數組并非起始位址+長度構成的一片連續的位址空間。

javascript中數組事實上就是個對象,僅僅隻是會自己主動管理一些"數字"屬性和length屬性罷了。

說的更直接一點,JavaScript中的數組根本沒有索引,由于索引應該是數字,而JavaScript中數組的索引事實上是字元串。

arr[1]事實上就是arr["1"],給arr["1000"] = 1,arr.length也會自己主動變為1001。這些表現的根本原因就是：JavaScript中的對象就是字元串到随意值的鍵值對。

通過new Array(len)的方式建立的數組屬于稀疏數組，稀疏數組在一些數組方法中，特别是周遊數組的方法，往往與我們預期的不太一樣，如果對其不了解，容易導緻問題，而且稀疏數組在建立和通路元素方面性能表現并不好，是以在平時代碼中應該盡量避免使用稀疏數組。