JavaScript稀疏数组示例教程_Javascript

前言

最近有空在看一本关于 js 数据结构和算法的书，里面有提到数组，却对数组的基本概念轻轻带过，虽然用了 js 很久但是一直忙于需求业务的实现从未停下好好回视一下这个既熟悉又陌生的朋友，于是查阅了一些资料，尤其是密集数组和稀疏数组的区别，意犹未尽之下，写了这篇文章，以便更好地帮助理解书中的要点，稍显浅显，也有不足望各位提点。

什么是稀疏数组？

通常编程语言中（c、java等）数组都是预先设定好长度的，他们的内存占用是固定的，内存地址是连续不间断、紧密相连的，我们称之为密集数组，好比 js 中类型化数组（typedarray）的 arraybuffer，但我们这里着重要说的是通过 array 创建的数组，它其实是个对象，当我们通过 new array() 创建一个数组时，它只是一个带有 length 属性的数组对象，我们可以像对象一样去操作它的属性：

let array = new array(10)
// 下标可以是任何的字符串，就像操作 object 一样
array.name = 'this is an array.'
array['name'] = 'this is an array.' // 等效 array.name

虽然可以像操作 object 那样为数组对象添加属性，但是真正计入数组元素的只能是以整数类型的字符作为下标去映射值的元素，同时会影响其长度属性 length，我们接上段代码继续：

// 虽然之前赋上了一个新的属性 name，但是其长度仍然输出10，而非11
console.log(array.length) // 10
// 用整数类型下标定义一个数组元素才会计入数组长度
array['0'] = 'first' // 下标其实都是字符串
array[11] = 'eleventh' // 看起来这个下标是一个数字，但是 js 会自动把它转为字符
console.log(array.length) // 12

长度属性是可以手动变更的：

array.length = 100
console.log(array.length) // 100

数组对象本身可能不占用太多内存，它只是包含了映射关系和长度，真正占用内存的是元素所映射的目标，也就是“键值”中的“值”。在v8引擎里，js 的数组得到进一步的优化，其中有个概念叫 holey（有孔洞的），也就是那些没有被指明映射关系的空间，他们不占用内存。如上看到，作为一门动态语言，我们随时可以向这个数组对象里添加、修改元素映射，也能随时改变其长度 length。自然地，其元素所占的内存地址也就无所谓固定连续了，我们称这种数组为稀疏数组（sparse array）。

创建带有孔洞的稀疏数组

使用 array 构造函数：

let sparse = new array(100)

通过字面量：

let sparse = []
// 用一个超过原始长度的下标为元素赋值，也就为该元素创建了一个映射关系，同时改变了该数组的长度
sparse[99] = 'last'
console.log(sparse.length) // 100
// 用对象字面量书写数组时，允许元素留空
sparse = [, , ,] // 这就创建了长度为3的空洞的数组
console.log(sparse.length) // 3

手动修改一个大于原数组长度的 length 值：

let sparse = ['red', 'green', 'blue'] // 三个元素的数组
sparse.length = 100 // 此时长度已是100，但有效元素仍然只有3个

删除元素的映射

从数组中删除某个元素可以使用 pop、shift、splice 方法，那如何解除元素与某个对象的映射关系呢？我们可以像操作对象一样用 delete，它不会删除映射目标，仅仅是将元素和目标对象的关联断开，从而形成一个孔洞，所以也不会改变这个数组的 length。

let one = '壹'
let array = []
array[0] = one // 将数组的第一个元素指到对象 one，长度变为 1
console.log(array, array.length) // ['壹'], 1
delete array[0] // 删除数组第一个元素的映射关系
console.log(array) // [空]
console.log(array.length) // 因为只是删除了元素的映射，长度并没有改变，仍然输出 1
console.log(one) // one 的值并不会删除，仍然保留，输出 '壹'

现象

我们说到，js 的数组本质上是对象——由整数字符作为下标与目标值构成映射关系的自带长度属性的对象，长度可以大于有效（已创建映射关系的）元素的个数。从映射状态来看，完全映射的数组有着和传统密集数组类似的表现，而不完全映射的数组在生产中会有些特别，但又在情理之中。

访问没有映射关系的数组元素时，相当于一个申明了却没有定义值的变量，所以会输出 undefined：

let sparse = new array(10)
console.log(sparse[0]) // undefined

不完全映射的数组，在用 map()、foreach() 等方法做遍历时，它们只会遍历已有映射关系的元素：

// 此时数组元素的映射关系一个都没有创建，所以 foreach 不会有任何输出
sparse.foreach((value, i) =&gt; {
  console.log(i, value)
}) // nothing
// 根据下标为最后一个元素赋值
sparse[sparse.length - 1] = 'tenth'
// 只会输出已建立映射的元素 sparse[sparse.length-1] 的值 'tenth'
sparse.foreach((value, i) =&gt; {
  console.log(i, value)
}) // 9, tenth

使用 for 语句也只是用数组的 length 值作为循环依据，它不会主动判断当前位置是否有映射值，所以当循环体试图通过下标访问没有映射关系的位置时，会输出 undefined：

for( let i = 0; i &lt; sparse.length; i += 1){
  console.log(i, sparse[i])
}

映射完全的数组，可以被所有常用数组方法遍历：

let array = ['1', 'day', 'white', 'jake', undefined, null, 0] // 一个完全映射的数组
// 输出每个元素，包括null、undefined、0
array.foreach((value, i) =&gt; {
  console.log(i, value)
})

在做 some()、every() 等操作时，不完全映射的数组的表现是特殊的，但也在情理之中，这取决于这些方法的设计，例如 some()，即便长度大于0，但因为其中没有任何建立映射的元素，所以，相当于给一个空数组（[]）做操作：

let sparse = new array(10)
// 由于还没有建立映射关系，所以 some 的回调也没有触发，于是得到的结果依然是 false
console.log(sparse.some(item =&gt; !item)) // false
// 在所有元素都被赋值后，用同样的回调，some 的结果发生了变化
sparse.fill(false) // 赋值
console.log(sparse.some(item =&gt; !item)) // true

当把长度设成小于实际元素个数的值时，会把超出长度的元素从当前数组中剔除：

let array = ['one', 'two', 'three']
array.length = 1
console.log(array) // ['one']

稀疏数组的快速映射（强制创建映射关系）

只是让数组中的映射元素个数与长度属性相同，并不能改变其稀疏的特性：

let sparse = new array(5)
// array.apply
let array1 = array.apply(null, sparse)
// array.from方法
let array2 = array.from(sparse)
// 解构
let array3 = new array(...sparse)
let array4 = [...sparse]
// 把所有元素映射为 undefined 了
array1.foreach((item, i) =&gt; {
  console.log(i, item) // 输出 undefined × 5
})
……