JS 引擎视角：数组与对象的底层

本节目标

理解 JS 数组 / 对象在 V8 里的表示
知道哪些操作"看起来 O(1) 其实 O(n)"
会用性能测量验证直觉

JS 数组不是"连续内存的定长数组"：V8 会根据使用方式在两种表示间切换。

快数组（PACKED）：连续内存 + 元素类型一致 → 按下标访问 O(1)
慢数组（字典模式）：退化成哈希表 → 按下标访问变慢

退化触发条件（性能陷阱）：delete arr[5]（制造空洞）、混入不同类型、稀疏赋值 arr[100000]=1。

// 运行环境：Node.js 14+
// 保存为 dsa-l3.js，执行：node dsa-l3.js

// 几个关键操作的"真相"
const truths = {
  'arr[i]': 'O(1) 快数组下标',
  'arr.push/pop': 'O(1) 均摊',
  'arr.shift/unshift': 'O(n)！头部操作要搬移所有元素',
  'arr.slice/splice': 'O(n) 拷贝/搬移',
  'arr.includes/indexOf': 'O(n) 线性查找',
  'arr.sort': '平均 O(n log n)，注意默认按字符串排序'
}
console.log(truths)

// 性能测量：对比 shift 1e5 次 vs 头指针队列 1e5 次
function bench(fn, label) {
  const t0 = performance.now()
  fn()
  console.log(label, '耗时', (performance.now() - t0).toFixed(1) + 'ms')
}
function shiftVersion() {
  const a = []; for (let i = 0; i < 1e5; i++) a.push(i)
  while (a.length) a.shift()
}
function headPtrVersion() {
  const a = []; let h = 0; for (let i = 0; i < 1e5; i++) a.push(i)
  while (h < a.length) h++
}
bench(shiftVersion, 'shift 版')
bench(headPtrVersion, '头指针版')

// 排序一定要给比较器，否则 '10' < '2'
console.log([10, 2, 30, 4].sort())          // [10, 2, 30, 4] 错误！
console.log([10, 2, 30, 4].sort((a, b) => a - b)) // [2, 4, 10, 30]

优化建议：频繁头部增删用双端队列（手写或库），别用 shift；大量查找用 Set/Map（哈希 O(1)）；删除元素 splice 会搬移，"把尾部换过来再 pop"是 O(1) 技巧（乱序可接受时）。

名词解释

隐藏类（Hidden Class）：V8 给"结构相同"的对象分配同一个隐藏类，属性访问通过偏移量直接定位（O(1)）。随意增删属性会让对象"分裂"成不同隐藏类，访问变慢。类比：图书馆给同类书同一排书架号，乱塞书就找不到。
快数组 / 慢数组（Fast / Dictionary Mode）：V8 数组的两种内部表示；连续同构时是快数组（快），出现空洞或类型混杂会退化成哈希表式的慢数组（慢）。
均摊 O(1)：见上节。push 因翻倍扩容，平均每次追加是常数时间。

课后练习

实测 shift 与自定义头指针队列各 10 万次耗时，差距大约几个数量级？
- 答案：shift 每次 O(n)，10 万次约 O(n²)≈1e10 量级操作，会慢到几百毫秒甚至更久；头指针版是纯 O(n)，通常快 100 倍以上。上面 bench 可直接看到差距。
为什么 arr.sort() 对数字必须给 (a,b)=>a-b？
- 答案：默认把元素转成字符串再按字典序比较，'10'<'2'，导致数字排序错乱。比较器返回负数/0/正数告诉它真正的先后。

总结

知道"数组在 JS 里本质是对象"只是第一步，真正拉开差距的是理解 V8 的两种数组模式：连续同构时是 O(1) 的快数组，一旦出现空洞或类型混杂就退化成哈希表式的慢数组。这条知识直接决定你写的代码会不会"看起来很简单、跑起来却很慢"。最常被忽视的陷阱是 shift/unshift——很多人以为数组头部操作和尾部一样快，其实它是 O(n)，在循环里反复 shift 会让算法悄悄退化。养成用 performance.now() 实测的习惯比任何"我以为"都可靠：直觉会被打脸，数字不会。把"引擎视角"装进脑子，你写出的前端代码才会既正确又快。