深究 JavaScript 数组

强类型语言中的数组

如何实现随机访问？

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

  int[] arr = new int[10]

操作系统为数组分配了一块连续的内存空间，假设首地址为 base_address = 1000

得出内存地址的计算公式

arr[i].address = base_address + i * 4 (int)

所以，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)

低效的“插入”和“删除”

数组是线性的，假设在长度为 10 的数组中，将一个数据插入到第 5 项，我们需要把 5 - 10 项的元素向后移动一位，时间复杂度为 O(n)

删除同理

JavaScript 的数组

const arr = [1, 'str', false]

js 中的数组，存储的可能是不具有 相同类型的数据，没办法通过首地址 + 偏移 * 下标的方式得到对应的内存地址。

所以在 js 中，数组是哈希映射。下标: 内存地址的方式，也可以通过多种数据结构，比如链表等。

最近 JavaScript 也进化了很多， JavaScript 引擎已经在为同种数据类型的数组分配连续的存储空间了。

!类型化数组性能良好且非常高效

旧数组 VS 类化数组

旧数组-插入

const LIMIT = 10000000

const arr = new Array(LIMIT)
console.time('Array insertion time')
for (let i = 0; i < LIMIT; i++) {
  arr[i] = i
}
console.timeEnd('Array insertion time')

所需时间：55ms

类型化数组-插入

const LIMIT = 10000000

const buffer = new ArrayBuffer(LIMIT * 4)
const arr = new Int32Array(buffer)
console.time('ArrayBuffer insertion time')
for (let i = 0; i < LIMIT; i++) {
  arr[i] = i
}
console.timeEnd('ArrayBuffer insertion time')

所需时间：52ms

由于是类化数组没有太明显差异

旧数组-插入（类型不一致）

const LIMIT = 10000000
const arr = new Array(LIMIT)
// 插入类型不同的数据
arr.push({ a: 22 })
console.time('Array insertion time')
for (let i = 0; i < LIMIT; i++) {
  arr[i] = i
}
console.timeEnd('Array insertion time')

所需时间：1207ms

数组的类型不一致，其它所有的都跟前面一模一样。但是性能上有了巨大的变化：慢了整整 22 倍。

旧数组-读取

const arr = new Array(LIMIT);
arr.push({a: 22});
for (let i = 0; i &lt; LIMIT; i++) {
    arr[i] = i;
}
let p;
console.time("Array read time");
for (let i = 0; i &lt; LIMIT; i++) {
    //arr[i] = i;
    p = arr[i];
}
console.timeEnd("Array read time");

所需时间：196ms

类型化数组-读取

const LIMIT = 10000000;
const buffer = new ArrayBuffer(LIMIT * 4);
const arr = new Int32Array(buffer);
console.time("ArrayBuffer insertion time");
for (let i = 0; i &lt; LIMIT; i++) {
    arr[i] = i;
}
console.time("ArrayBuffer read time");
for (let i = 0; i &lt; LIMIT; i++) {
    const p = arr[i];
}
console.timeEnd("ArrayBuffer read time");

所需时间:27ms

结论

在 JavaScript 中引入类型化数组是一个巨大的进步，Int8Array, Uint8Array, Uint8ClampedArray, Int16Array, Uint16Array, Int32Array, Uint32Array, Float32Array, Float64Array 等都是类型化数组 view,按照原生的 byte 数排序。你也可以看看 DataView 创建自己的 view 窗口。希望在将来会有更多 DataView 库方便我们使用 ArrayBuffer。 JavaScript 对数组做的改进很棒。现在它们快速、高效并且在分配内存时足够聪明了。