数组

和其他强类型语言不同，在JavaScript中，数组可以容纳任何类型的值，可以是字符串、数字、对象，甚至是其他数组以组成多维数组。

let a = [1, '2', [3]]

a.length // 3
a[0] === 1 / true
a[2][0] === 3 // true

对数组声明后就可以向其中加入值，不需要预设长度。

let a = []
a.length // 0
a[0] = 1
a[1] = '2'
a[3] = [3]
a.length // 3

使用delete运算符可以将单元从数组中删除，但是通过这样的方式删除，数组的length属性并不会发生变化

如果我们想预设数组的长度也可以，但是可能会带来意想不到的问题，稀疏数组就是问题之一。

稀疏数组

若一个数组中包含至少一个“空单元”，这样的数组称为稀疏数组。

let a = []
a[0] = 1
a[2] = [3]

a[1] // undefined
a.length // 3

上面的代码执行完之后其实就已经预设了a的长度，就是3。它们可以正常运行，但其中的“空白单元”就会导致那些意想不到的结果。a[1]的值是undefined，但这与将其显示赋值为undefained还是有区别的（a[1] = undefined）。

const a = [undefined, undefined, undefined]
const b = []
b.length = 3
/* 
    a的创建相当于
    a = []
    a[0] = undefinde
    a[1] = undefined
    a[2] = undefined
*/

上面的代码中，显示的为a创建了稀疏数组，隐式的为b创建了稀疏数组。与此同时更上面提到的，他们的区别是什么呢？ 区别就在于，a在当前版本的Chrome中会显示为[undefined, undefine, undefined]，而b则会显示为[empty × 3]，更有意思的是，在更早的Chrome版本中，b会被显示为[undefined x 3]。 此外，不同的浏览器对于隐式创建的稀疏数组控制台输出的也有所不同，比如在FireFox早期版本中b会显示为[,,,]，现在会显示成Array [<3 empty slots>]。 输出行为的不一致会给我们的调试带来问题，更糟糕的是，a与b不仅在输出上不同，他们的的行为有时相同，有时候也会大相径庭：

a.join('-') // '--'
b.join('-') // '--'

a.map((_, i) => i) // [0, 1, 2]
b.map((_, i) => i) // [empty × 3]

b.map()之所以会失败，是因为b是隐式创建的稀疏数组，它当中并不存在任何单元，所以map会无从遍历，而a显示的为数组中置了三个undefined，map就能正常遍历了。 而join却不一样，它的具体实现如下：

function hkJoin (arr, connector) {
    let str = ''
    for (let i = 0; i < arr.length; i++) {
        if (i > 0) str += connector
        if (arr[i] !== undefined) str += arr[i]
    }
    return str
}

从上面的代码可以看出，join首先假定数组不为空，然后通过length属性遍历其中的单元，而在ECMA规范中，map并不会做这样的假定，它会跳过空值，不执行回调函数以保证数组的稀疏结构，因此结果也往往在预期之外，并可能导致失败。

关于map的具体实现，无论是在浏览器环境下还是node环境下，只要运行时环境为v8对，map所给出的期望都是一致的，这与EventLoop有所不同。

原型函数Array()

const a = new Array(1, 2, 3)
a // [1, 2, 3]

const b =[1, 2, 3]
b // [1, 2, 3]

构造函数Array()不要求必须带new 关键字，不带时引擎编译时会自动补上。因此Array(1, 2, 3)和new Array(1, 2, 3)的效果是一样的。 Array构造函数只带一个数字参数的时候，该参数会被作为数组的预设长度，而非充当数组中的一个元素，因此稀疏数组往往也能这样创造。 但这绝非明智之举，一是容易忘记，而是容易出错，更为关键的是，在js中并没有对数组预设长度这个概念。一个数组没有任何单元，但它的length属性却想告诉他人这里面有单元数量，这样奇特的数据结构就会导致上面所描述的怪异行为。而这一切都应该被归咎为已经被废弃的旧特性————类似arguments这样的类数组。

如果想通过Array构造函数创建包含undefined单元的稀疏数组，可以这样做Array.apply(null, { length: 3 })，这样做的结果比Array(3)更准确可靠，这样做的效果等同于 const a = [undefined, undefined, undefined]

类数组

上面提到的arguments就是类数组之一，有时候我们也会操作dom，通过某些API获取DOM时会得到类数组，注意观察原型，你会发现它是一种HTMLCollection。 类数组具有数组的特性，却无法调用数组定义的方法，比如forEach、map、filter... 由于具有数组特性，它还是可以使用for循环的：

for (let i = 0; i < arrLike.length; i++) {
    // ...
    // arrLike是一个类数组
}

如果我们真的需要调用数组的某些方法，我们可以通过改变this指向去使用：

Array.prototype.slice.call(arrLike)
Array.prototype.filter.apply(arrLike, (item, index) => {})
Array.prototype.slice.bind(arrLike)()

如果你觉得上述方式过于丑陋，也有更优雅的解决方式，将类数组转为数组，在ES6之前，我们想要把类数组转为数组还需要调用slice方法，这仍然需要改变this指向。好在ES6之后内置工具函数Array.from()也能实现同样的功能：

const a = { '0': 1, '1': 2, '2': 3, length: 3 }

const arr1 = Array.prototype.slice.call(a)
const arr2 = Array.from(a)

// 上述两种方法效果一致

将Array.from与Set对象结合还能优雅的对简单数组去重：Array.from(new Set(myArray))

数组？类数组？

也许你已经注意到了上面那段代码中的a是一个对象，在控制台中arguments与HTMLCollection都以数组形式展示，为何对象也是类数组？ 要回答这个问题其实并不麻烦，我们可以从类数组的定义出发，《javascript权威指南》是这样定义类数组的————拥有length属性，且length属性可以隐式的转为number类型，并且不大于Math.pow(2, 32)

Math.pow(2, 32)的值为4294967296，如果你很关心为什么定义一个这样的界限，我大概会做出关于“js整数的安全范围Math.pow(2, 53)，它远远小于js定义的极大值Number.MAX_VALUE，而虽然最大能达到53位，但有些数字操作（比如位运算）却只适用于32位”这样的回答。

也许你已经对类数组有了一个较为清晰的概念，现在让我们基于此来更进一步的认识一下数组。 我们都知道数组通过数字进行索引，但有趣的是它们其实也是对象（做typeof [] === 'object'判断的你肯定知道），所以它们也可以包含字符串键值和属性（但这些都不会计算在数组长度内）：

let a = []

a[0] = 1
a['str'] = 2

a.length // 1
a['str'] // 2
a.str // 2

这里有个问题需要特别注意，如果字符串键值能够被强制类型转换为十进制数字的话，它就会被当成索引来处理:

let a = []

a['13'] = 13
a.length // 14  要命，又是一个稀疏数组

在数组中加入字符串键值/属性并不是一个好主意。建议使用对象来存放键值/属性值，用数组来存放数字索引/值。

遍历

在ES6之前，遍历数组多以forEach或for进行遍历，由于forEach无法break，ES6之后又引入了for...of。 但怎么遍历对象呢？无论是Object.key还是for...in获取的都是对象的键，很显然的是，我们遍历往往都期待获取到对象的值，就像遍历数组，索引坐标在更多时候是次要的。也许我们会通过键值索引去获取对象或者数组的值，这个过程消耗着一次又一次的右查询（RHS），而无论性能如何，我们的代码一定还有优化空间！ 当我们只需要值的时候，可以使用Object.values，它会将对象中的值输出到一个数组中。 当我们在一次遍历中既需要键又需要值的时候，我们无关乎是否使用Object.key还是for...in去做键值查询，这里还有一个更简单的方案Object.entries，它返回一个对象的键值对数组。

const a = {a: '1', b: '2', c: '3'}

for (const [key, value] of Object.entries(a)) {
    console.log(key, value)
}
// a, 1
// b, 2
// c, 3

私以为，如果需要遍历对象的原型，那么使用for...in是明智的，否则任何时候都应该使用Object.key或Object.entries来代替它。

有点很遗憾的是，上述所有对对象的方法都是随机遍历的。 遍历数组下标时采用的是数字顺序，但是遍历对象属性的顺序却是不确定的，因为在不同的JavaScript环境下可能会不太一样，因此，一定不要相信任何观察到的对象属性顺序，它们是不可靠的。

迭代器iterator

对象与数组的遍历有如此之多的相似之处，甚至数组本身也是对象，但为什么for...of无法遍历对象？这其实得益于数组内置了迭代器（iterator）。

const arr = [1, 2, 3]
const it = arr[Symbol.iterator]()

it.next() // { value: 1, done: false }
it.next() // { value: 2, done: false }
it.next() // { value: 3, done: false }
it.next() // { done: true }

我们使用ES6中的符号Symbol.iterator来获取迭代器，引用类似迭代器（iterator）的特殊属性时要用符号名，而不是符号包含的值。此外，虽然看起来很像一个对象，但是迭代器本身并不是一个迭代器对象，而是一个返回迭代器对象的函数。

如我们所见，调用迭代器的next()方法会返回形式为{ value: ..., done: ... }的值，value是当前的遍历值，done是一个布尔值，表示是否还有可遍历的值。 注意，和值 3 一起返回的是done: false，乍一看好像很奇怪，必须再调用一次next()才能得到done: true，从而确定完成遍历。这个机制其实和ES6中的生成器有关，但这已经不在本次讨论的范围内了。

我们知道的yield就是生成器函数的关键字，它和迭代器有着非常紧密的关系。

和数组不同，普通的对象没有内置的迭代器，所以无法完成for...of之类的遍历，无法按照我们观测到的顺序遍历键值，这其中有很多复杂的原因，不过简单来说，这样做是为了避免影响未来的对象类型。

当然，我们也可以给任何想遍历的对象定义迭代器，举例来说：

let obj = { a: 2, b: 3 }

Object.defineProperty(obj, Symbol.iterator, {
    enumerable: false,
    writable: false,
    configurable: true,
    value: function () { // 请不要把value写成箭头函数，this的运行时指向在这里很重要，我们并不需要箭头函数的定义时指向。
        const o = this
        let idx = 0
        const ks = Object.keys(o)
        return {
            next: () => {
                return { value: o[ks[idx++]], done: (idx > ks.length) }
            }
        }
    }
})

// 手动遍历obj
const it = obj[Symbol.iterator]()
it.next() // { value: 2, done: false }
it.next() // { value: 3, done: false }
it.next() // { value: undefined, done: true }

// 用for...of遍历obj
for (const v of obj) {
    console.log(v)
}
// 2
// 3

我们使用了Object.defineProperty定义了我们自己的迭代器（主要是为了配置属性参数，让他不可枚举与不可写），我们也可以直接再定义对象的时候进行声明，比如：

const obj = {
    a: 2,
    b: 3,
    [Symbol.iterator]: function () {/*...*/}
}

for...of循环每次调用obj迭代器对象next()方法时，内部的指针都会向前移动并返回对象属性列表的下一个值。

请留意顺序，它仍是不可预知的，因为我们仍然使用Object.key获取对象的属性。

代码中的遍历非常简单，只是传递了属性本身的值。不过只要我们原因，当然也可以在自定义的数据结构上实现各种复杂的遍历，只要我们使用迭代器（当然，请不要对数组原型的迭代器进行修改，擅自修改原生属性的原型和为原型添加属性是非常危险的）。对于用户定义的对象来说，结合for...of循环和自定义迭代器可以组成非常强大的对象操作工具。

比如说，一个Pixel对象（有x轴和y轴坐标值）列表可以按照距离原点的直线距离来决定遍历顺序，也可以过滤掉“太远”的点，等等。只要迭代器的next()调用会返回{ value: ..., done: true }，ES6中的for...of就可以遍历它。

这种说法更像是“如果一个东西长得像鸭子，叫的像鸭子，走的像鸭子，那么它就是鸭子”的暴力推断在JavaScript中并不少见，我们熟知的Promise的thenable便是如此，因此当有人说这是鸭子类型，请不要笑他~

现在，让我们尝试为一个对象定义一个“无限”迭代器，它永远不会“结束”，并且总会返回一个新值（比如随机数、递增值、唯一标识符等）。我们应该永远不会再for...of循环中使用这样的迭代器，因为它不会结束，所以我们的程序会被挂起：

const randoms = {
    [Symbol.iterator]: function () {
        return {
            next: () => {
                return { value: Math.random(), done: false }
            }
        }
    }
}

let randomList = []
for (const n of randoms) {
    randomList.push(n)
    if (randomList.length === 100) break
}

这个迭代器会生产无限个随机数，我们为了不让程序挂起，使其当数组长度达到100时停止遍历。

时间与空间

遍历往往伴随着性能的消耗，一般来说，代码的执行时间复杂度越小，程序响应的速度就会越快。

但是在我们的日常开发中，我们其实很难将时间复杂度降到最低，有时候，我们会开辟许多内存空间去降低时间复杂度，受限于程序运行的环境，过高的内存占用同样会导致程序卡死。

在我们遍历数组的时候，时间复杂度不外乎O(n)、O(n²)、O(nlogn)，当然，不排除多层嵌套带来的指数增长，但这已经非常少见了。

尽可能的减少嵌套循环，使用正确的方法进行遍历，开辟合适的内存空间缓存数据，倒序循环与提前退出等以降低时间复杂度。

减少在遍历中变量的生成，避免稀疏数组的产生（数组越界），减少中间状态、临时状态等以降低空间复杂度。

究竟是时间换空间，还是空间换时间，如何用尽可能小的代价提高程序性能，亦或是减少无意义的性能开销，如何取舍，这个问题其实已经交到了我们手上。