天天看點

js 中稀疏數組的一些知識

什麼是稀疏數組?

在說稀疏數組之前,你需要知道很多語言将數組的分為稀疏數組與密集數組(差別是數組的各個子元素是否有孔,我們稱為"hole")。也就是說稀疏數組中的元素之間可以有空隙,在那些僅有少部分項被使用的數組中,hole 可以大大減少記憶體空間的浪費。

V8中數組的實作

快數組(FAST ELEMENTS)

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

Fast Holey Elements模式

前面說了新建立的數組,預設是Fast Elements方式。在Fast Elements 模式中有一個擴充,是 Fast Holey Elements 模式。Fast Holey Elements 模式适合于數組中的空洞情況,即隻有某些索引存有資料,而其他的索引都沒有指派的情況。在 Fast Holey Elements 模式下,當容量小于1024時,沒有指派的數組索引将會存儲一個特殊的值,這樣在通路這些位置時就可以得到 undefined。但是 Fast Holey Elements 同樣會動态配置設定連續的存儲空間,配置設定空間的大小由最大的索引值決定。

// 如下産生Fast Holey Elements的兩種方式
let a = new Array(10);
console.log(a);
// (10) [empty × 10]

let b = [1, , , , 4];
console.log(b)
// (5) [1, empty × 3, 4]複制代碼      

慢數組(Dictionary Elements)

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

在 Fast Elements 模式下,capacity 用于訓示目前記憶體占用量大小,通常根據數組目前最大索引的值确定。在數組索引過大,超過 capacity 到一定程度( 由V8中 kMaxGap 常量決定,其值為 1024) ,數組将直接轉化為 Dictionary Elements 模式。更多關于V8的知識請移步 justjavac 的專欄

常見數組方法如何來處理稀疏數組?

map 方法

var array = [1,,,2]
var mapArray = array.map((item, index) => {
	console.log(index)
	return item + 1;
})
// 方法執行是列印 0,3 似乎跳過了數組中 hole 元素
console.log(mapArray)
// (4) [2, empty × 2, 3]複制代碼      

find 方法

var array = [1,,,2]
var findArray = array.find((item, index) => {
	console.log(index)
	return item >= 2;
})
// 方法執行是列印 0,1,2,3 沒有跳過 hole 元素
console.log(findArray)
// 2複制代碼      

findIndex 方法

var array = [1,,,2]
var findIndexArray = array.findIndex((item, index) => {
	console.log(index)
	return item >= 2;
})
// 方法執行是列印 0,1,2,3 沒有跳過 hole 元素
console.log(findIndexArray)
// 3複制代碼      

filter 方法

var array = [1,,,2]
var filterArray = array.filter((item, index) => {
	console.log(index)
	return item >= 2;
})
// 方法執行是列印 0,3 似乎跳過了數組中 hole 元素
console.log(filterArray)
// [2]複制代碼      

forEach 方法

var array = [1,,,2]
array.forEach((item, index) => {
	console.log(index)
})
// 方法執行是列印 0,3 似乎跳過了數組中 hole 元素複制代碼      

reduce 方法

var array = [1,,,2]
var count = array.reduce((acc, item, index) => {
	console.log(index)
	return acc + item;
}, 0)
// 方法執行是列印 0,3 似乎跳過了數組中 hole 元素
console.log(count)
// 3複制代碼      

總結