Js中的稀疏数组与密集数组

一般而言，js中的数组是稀疏的，也就是说数组中的元素之间可以有空隙，因为一个数组其实就是一个键值映射。这篇本文解释了如何创建稀疏数组和不稀疏的数组，以及稀疏数组和密集数组之间的区别。

例如以下的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 语句中，同样适用。

const 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)的方式创建的数组属于稀疏数组，稀疏数组在一些数组方法中，特别是遍历数组的方法，往往与我们预期的不太一样，如果对其不了解，容易导致问题，而且稀疏数组在创建和访问元素方面性能表现并不好，所以在平时代码中应该尽量避免使用稀疏数组。

链接: https://fly63.com/article/detial/10769