复合数据结构：数组

SyYhunfhds2026/7/11大约 11 分钟

数组、列表

底层定义

JavaScript 只有一种内建的"顺序集合"类型：Array。没有内建的链表（Linked List）或向量（Vector）类型——如果你需要这些，必须自己实现或引入第三方库。

V8 引擎的 ElementsKind

V8 引擎在内存层面对 Array 做了分类优化，每种数组都有一个 ElementsKind 标记，决定了底层存储结构和操作策略：

packed_smi_elements       →  packed_double_elements     →  packed_elements
（纯小整数，最紧凑）          （含浮点数）                    （含普通对象）

     ↓ 插入对象                 ↓ 数组变稀疏
dictionary_elements        ←  holey_xxx / sparse
（退化为哈希表存储）            （含空洞或大量空缺）

ElementsKind	说明	示例
`packed_smi_elements`	所有元素都是小整数（SMI），内存连续紧致，性能最高	`[1, 2, 3]`
`packed_double_elements`	含浮点数，使用 double 数组存储	`[1, 2.5]`
`packed_elements`	含普通对象或字符串，退化为通用元素数组	`[1, "a", {}]`
`holey_smi_elements`	数组含空洞（稀疏索引），但值仍为 SMI	`[1, , 3]`
`dictionary_elements`	极其稀疏（约 1024+ 个 hole），退化为哈希表，键为索引字符串	`arr[9999] = "x"`

迁移是不可逆的（monomorphic → polymorphic → megamorphic），一旦退化为 dictionary_elements，性能显著下降。

实用建议

保持数组元素类型一致（纯整数、纯对象等），避免 V8 退化
避免创建超大稀疏数组（如 new Array(10000) 后再逐个赋值）
delete arr[i] 会制造空洞，可能触发退化

动态扩容机制

与 Go 的 slice 一样，JS 的 Array 底层也有预分配容量的概念：

JS 引擎（V8）             Go (runtime)
─────────────────────────────────────
// 每次 push 时检查容量         // 每次 append 时检查容量
// 不足时扩容约 1.5 倍 + 1       // 不足时扩容约 2 倍（<1024）/ 1.25 倍
// length 属性始终可见           // len/cap 分离
// 无手动扩容 API                // 可用 make(T, 0, cap) 预分配

// JS —— 容量对开发者不可见
const arr: number[] = []
arr.push(1, 2, 3)       // 内部自动扩容

// 预分配（V8 会创建相应类型的 ElementsKind，但无法指定容量）
const big = new Array(1000)   // 创建 1000 个 hole 的数组——可能退化为字典模式

// Go —— cap 对开发者可见
arr := make([]int, 0, 1000)   // 预分配 1000 容量
arr = append(arr, 1, 2, 3)   // 不触发扩容，直到超过 cap

核心区别：Go 让你手动管理容量以获得可预测的性能；JS 把这一切交给引擎，你无法控制。

原型链（继承关系）

JS 对象的"继承"是通过原型链实现的，Array 也不例外。不存在传统 OOP 中的类继承树，只有一条原型链：

arr → Array.prototype → Object.prototype → null

const arr = [1, 2, 3]

arr.__proto__                // Array.prototype——所有数组方法的来源
arr.__proto__.__proto__      // Object.prototype——toString/hasOwnProperty 等
arr.__proto__.__proto__.__proto__  // null —— 原型链终点

arr instanceof Array         // true —— 通过原型链检查
Array.isArray(arr)           // true —— 更可靠，跨 iframe 也能工作

检测数组的可靠方式

// 虽然 instanceof 可以工作，但在多 realm 环境（iframe, Node VM）中不可靠
const iframe = document.createElement('iframe')
document.body.appendChild(iframe)
const iframeArray = new iframe.contentWindow.Array(1)

arr instanceof Array             // true
iframeArray instanceof Array    // false —— 来自不同 realm！

// 可靠的方式 —— isArray
Array.isArray(arr)              // true
Array.isArray(iframeArray)      // true —— 跨 realm 正确

Array 构造函数

// 三种创建方式
const a1 = []                           // 字面量 —— 推荐
const a2 = new Array(1, 2, 3)           // new Array(items) —— 等价于 [1, 2, 3]
const a3 = new Array(5)                 // new Array(size) —— 创建一个长为 5 的稀疏数组 ⚠️

// 坑：new Array(5) 创建的是稀疏数组
console.log(a3.length)                  // 5
console.log(a3[0])                      // undefined —— 但这是"空洞"而非真正赋值
a3.map(x => x + 1)                      // [empty × 5] —— map 跳过空洞！

new Array(size) 的陷阱

new Array(5) 创建的数组5 个位置都是空洞（hole），不是 5 个 undefined。大多数迭代方法（map/filter/forEach）会跳过空洞：

const holes = new Array(3)
holes.map(() => 'x')        // [empty × 3] —— 什么都没执行！

const filled = [undefined, undefined, undefined]
filled.map(() => 'x')       // ['x', 'x', 'x']

// 安全的替代方案
Array.from({ length: 3 }, () => 'x')   // ['x', 'x', 'x']
Array(3).fill('x')                     // ['x', 'x', 'x']

所有 FP 操作（含完整回调签名）

以下是 TypeScript 中 Array 提供的所有函数式操作方法，每个都附有完整的回调参数签名。

遍历类

方法	回调签名	返回	原地改变
`forEach`	`(value: T, index: number, array: T[]) => void`	`void`	否
`map`	`(value: T, index: number, array: T[]) => U`	`U[]`	否

// TypeScript 中的类型定义
interface Array<T> {
  forEach(callbackfn: (value: T, index: number, array: T[]) => void, thisArg?: any): void
  map<U>(callbackfn: (value: T, index: number, array: T[]) => U, thisArg?: any): U[]
}

筛选类

方法	回调签名	返回	原地改变
`filter`	`(value: T, index: number, array: T[]) => unknown`	`T[]`	否
`find`	`(value: T, index: number, array: T[]) => boolean`	`T \| undefined`	否
`findIndex`	`(value: T, index: number, array: T[]) => boolean`	`number`	否
`findLast` (ES2023)	`(value: T, index: number, array: T[]) => boolean`	`T \| undefined`	否
`findLastIndex` (ES2023)	`(value: T, index: number, array: T[]) => boolean`	`number`	否
`includes`	无回调，直接传值 `(searchElement: T, fromIndex?: number)`	`boolean`	否
`indexOf`	无回调，直接传值 `(searchElement: T, fromIndex?: number)`	`number`	否

// TypeScript 类型定义
interface Array<T> {
  filter<S extends T>(predicate: (value: T, index: number, array: T[]) => value is S, thisArg?: any): S[]
  filter(predicate: (value: T, index: number, array: T[]) => unknown, thisArg?: any): T[]
  find(predicate: (value: T, index: number, array: T[]) => boolean, thisArg?: any): T | undefined
  findIndex(predicate: (value: T, index: number, array: T[]) => boolean, thisArg?: any): number
  findLast(predicate: (value: T, index: number, array: T[]) => boolean, thisArg?: any): T | undefined
  findLastIndex(predicate: (value: T, index: number, array: T[]) => boolean, thisArg?: any): number
}

filter 的类型守卫签名

filter 有一个特殊的类型守卫重载，可以在过滤的同时收窄类型：

const items: (number | undefined)[] = [1, undefined, 3]
const defined: number[] = items.filter((x): x is number => x !== undefined)
// 类型由 (number | undefined)[] 收窄为 number[]

判定类

方法	回调签名	返回	原地改变
`every`	`(value: T, index: number, array: T[]) => boolean`	`boolean`	否
`some`	`(value: T, index: number, array: T[]) => boolean`	`boolean`	否

interface Array<T> {
  every(predicate: (value: T, index: number, array: T[]) => boolean, thisArg?: any): boolean
  some(predicate: (value: T, index: number, array: T[]) => boolean, thisArg?: any): boolean
}

every：所有元素满足条件 → true（空数组返回 true ⟂）
some：任一元素满足条件 → true（空数组返回 false）
两者都是短路求值：every 在第一个 false 停止，some 在第一个 true 停止

归并类

方法	回调签名	返回	原地改变
`reduce`	`(accumulator: U, currentValue: T, index: number, array: T[]) => U`	`U`	否
`reduceRight`	同上，从右向左遍历	`U`	否

interface Array<T> {
  reduce(callbackfn: (previousValue: T, currentValue: T, currentIndex: number, array: T[]) => T): T
  reduce(callbackfn: (previousValue: T, currentValue: T, currentIndex: number, array: T[]) => T, initialValue: T): T
  reduce<U>(callbackfn: (previousValue: U, currentValue: T, currentIndex: number, array: T[]) => U, initialValue: U): U
}

reduce 有两种调用方式——有初始值和无初始值。无初始值时，数组的第一个元素作为累加器初始值（从索引 1 开始迭代）；空数组无初始值会抛 TypeError。

展平类

方法	回调签名	返回	原地改变
`flat`	无回调 `(depth?: number)`	`T[]`（展平后的新数组）	否
`flatMap`	`(value: T, index: number, array: T[]) => U[]`	`U[]`（map + flat(1)）	否

interface Array<T> {
  flat<A, D extends number = 1>(this: A, depth?: D): FlatArray<A, D>[]
  flatMap<U>(callbackfn: (value: T, index: number, array: T[]) => U[] | U, thisArg?: any): U[]
}

排序类

方法	回调签名	返回	原地改变
`sort`	`(a: T, b: T) => number`	`T[]`	是（修改原数组，同时返回引用）
`toSorted` (ES2023)	`(a: T, b: T) => number`	`T[]`	否（返回排序后的新副本）

interface Array<T> {
  sort(compareFn?: (a: T, b: T) => number): this     // 注意返回的是 this（原数组引用）
  toSorted(compareFn?: (a: T, b: T) => number): T[]  // 返回新数组
}

比较器返回值：

< 0：a 排在 b 前面
= 0：顺序不变（不稳定排序！V8 使用的 TimSort 是稳定的，但规范不保证）
> 0：b 排在 a 前面

其他常用的非回调方法

方法	签名	返回	原地改变
`concat`	`(...items: ConcatArray<T>[]) => T[]`	新合并数组	否
`slice`	`(start?: number, end?: number) => T[]`	浅拷贝片段	否
`join`	`(separator?: string) => string`	字符串	否
`push`	`(...items: T[]) => number`	新长度	是
`pop`	`() => T \| undefined`	移除的元素	是
`unshift`	`(...items: T[]) => number`	新长度	是
`shift`	`() => T \| undefined`	移除的元素	是
`splice`	`(start: number, deleteCount?: number, ...items: T[]) => T[]`	移除的元素	是
`toReversed` (ES2023)	`() => T[]`	反转后的新副本	否
`toSpliced` (ES2023)	`(start: number, deleteCount?: number, ...items: T[]) => T[]`	替换后的新副本	否
`with` (ES2023)	`(index: number, value: T) => T[]`	替换索引后的新副本	否
`fill`	`(value: T, start?: number, end?: number) => this`	原数组（同引用）	是

性能隐患与副作用

变异（Mutating）vs 非变异（Non-mutating）

所有数组方法分为两类：

类别	方法
变异（修改原数组）	`push`, `pop`, `unshift`, `shift`, `splice`, `sort`, `reverse`, `fill`, `copyWithin`
非变异（返回新数组）	`map`, `filter`, `slice`, `concat`, `reduce`, `flat`, `flatMap`, `join`, `toSorted`, `toReversed`, `toSpliced`, `with`, `forEach`

区分的关键原则

看返回值类型——如果返回的是 this 或 number（新长度），大概率是变异的
ES2023 新增的 toXxx 方法族都是非变异的，是对应变异方法的不可变版本
sort 是特例——它修改原数组并且返回原数组引用，极易造成混淆：

const arr = [3, 1, 2]
const sorted = arr.sort()
console.log(arr === sorted)   // true —— 同一个对象！

ES2023 复制方法族

ES2023（ES14）引入了四个不可变的数组复制方法，专门解决"想对数组做变换但不改原数组"的需求：

不可变方法	对应的变异方法	作用
`arr.toSorted(fn)`	`arr.sort(fn)`	返回排序后的副本
`arr.toReversed()`	`arr.reverse()`	返回反转后的副本
`arr.toSpliced(i, n, ...items)`	`arr.splice(i, n, ...items)`	返回"替换/删除"后的副本
`arr.with(i, val)`	`arr[i] = val`	返回"修改某一索引"后的副本

const arr = [3, 1, 2]

// 旧方式——需要手动复制
const sorted1 = [...arr].sort((a, b) => a - b)   // 先展开再排序

// ES2023 方式——语义更清晰
const sorted2 = arr.toSorted((a, b) => a - b)    // 直接返回新副本

兼容性

toSorted/toReversed/toSpliced/with 是 ES2023 特性，target 设为 es2023 以上或在 lib 中包含 "ES2023.Array" 才能获取类型定义。

常见性能陷阱

1. `unshift` / `shift` 的 O(n) 复杂度

在数组开头插入/删除元素，需要移动所有后续元素：

const arr: number[] = []
for (let i = 0; i < 10000; i++) arr.unshift(i)  // ❌ 每次 O(n)，总体 O(n²)！

// ✅ 最佳实践：用 push 后反转
const arr2: number[] = []
for (let i = 0; i < 10000; i++) arr2.push(i)
arr2.reverse()

// ✅ 或直接使用队列数据结构（Deque）

// Go 中也没有原生 unshift——但可以用 copy 实现
// 同样 O(n)

2. `sort` 默认转字符串排序

[1, 2, 10].sort()          // ❌ [1, 10, 2] —— 默认按字符串字典序！
[1, 2, 10].sort((a, b) => a - b)  // ✅ [1, 2, 10]

// 对象排序必须传比较器
interface Person { name: string; age: number }
const people: Person[] = [{ name: 'Alice', age: 30 }, { name: 'Bob', age: 25 }]
people.sort((a, b) => a.age - b.age)  // ✅ 按年龄升序

3. 稀疏数组退化（Dictionary Mode）

const arr: string[] = []
arr[9999] = 'far away'   // 超过阈值 → 退化为哈希表
arr[0] = 'hello'          // 此时虽然只有两个元素，但底层是哈希表，访问 O(1) 变慢

4. `delete arr[i]` 留下空洞

const arr = ['a', 'b', 'c']
delete arr[1]                  // ['a', empty, 'c'] —— length 仍然是 3！
console.log(arr.length)        // 3

// ✅ 用 splice（变异的）
arr.splice(1, 1)               // ['a', 'c'] —— length 为 2

// ✅ 或用 filter（非变异的）
const cleaned = arr.filter(x => x !== undefined)

5. `forEach` 无法中断

const arr = [1, 2, 3, 4, 5]

// ❌ forEach 不支持 break——以下代码不会中断
arr.forEach((x) => {
  if (x > 3) return     // 这只是跳过当前迭代，不会退出循环！
  console.log(x)         // 会打印 1, 2, 3, 4, 5（没有"跳过"成功）
})

// ✅ 用 for...of + break（命令式方案）
for (const x of arr) {
  if (x > 3) break
  console.log(x)          // 1, 2, 3
}

// ✅ 或用 some 替代（函数式方案——提前返回 true 中断）
arr.some((x) => {
  if (x > 3) return true   // true 表示"找到"，迭代停止
  console.log(x)
  return false
})

6. 过长的链式操作产生大量临时数组

const data: number[] = /* ...大量数据... */

// ❌ 每次调用都创建中间数组
const result = data
  .filter(x => x > 0)       // 创建 temp1
  .map(x => x * 2)          // 创建 temp2
  .filter(x => x < 100)     // 创建 temp3
  .sort((a, b) => a - b)    // 修改 temp3（仍是原地），但 filter 已经创建了

// ✅ 数据量大时考虑用 for 循环合并操作
function processData(data: number[]): number[] {
  const result: number[] = []
  for (const x of data) {
    if (x > 0) {
      const doubled = x * 2
      if (doubled < 100) result.push(doubled)
    }
  }
  result.sort((a, b) => a - b)
  return result
}

对大多数场景（≤ 10⁴ 元素），链式操作的可读性收益远大于其性能损失。只在数据量大或性能敏感路径上才考虑优化。

与 Go 的对比

维度	JavaScript Array	Go slice
底层	V8 根据元素类型动态选择 ElementsKind	连续内存 + cap（容量），开发者可见
扩容	引擎自动管理，约 1.5x + 1	`append` 时自动，<1024 翻倍，之后 1.25x
头部插入	`unshift` O(n)	无内建操作，需手写 `copy` + 赋值 O(n)
FP 方法	原生支持 `map`/`filter`/`reduce` 等	无内建——需手写 for-range 循环
副作用	部分方法是变异的（陷阱）	`append`/`copy` 全是显式复制或原地操作
空值	有空洞（hole）、`undefined`、`null` 多种"空"	无空洞——slice 要么有值要么零值
gc 压力	链式操作创建大量临时对象	无 GC 压力（值类型）或显式管理

Go 开发者上手建议

不要依赖 mutations 的顺序——某些变异方法会同时返回原数组引用，极易踩坑
默认用非变异方法——map/filter/reduce 比 for 循环更安全（无副作用），优先使用
警惕 sort 的默认行为——永远传比较器，跟 Go 中永远用 sort.Slice 一样
用 ... 展开替代 concat——[...arr1, ...arr2] 更直观
大数组避免 unshift——和 Go 一样，考虑用队列（Deque）或先 push 后 reverse