Array

数组是 JavaScript 中最常用的数据结构之一。在高级前端面试中，不仅会考察 API 的熟练度，还会深挖诸如 sort 的排序算法、flat 的手写实现以及 V8 引擎下数组的内存存储机制。

高阶函数 (map / filter / reduce)

这三个 API 是函数式编程的核心。面试不仅会考察基础使用，还经常要求手写实现，以及询问对于稀疏数组（empty slots）的处理细节。

1. map (映射)

map 用于对数组中的每个元素执行提供的回调函数，并返回一个新数组，不改变原数组。

基础与进阶用法：

const nums = [1, 2, 3];
const doubled = nums.map((n) => n * 2); // [2, 4, 6]

// 经典面试题：
["1", "2", "3"].map(parseInt);
// 结果是 [1, NaN, NaN]。因为 map 会传三个参数：(currentValue, index, array)。
// parseInt('1', 0) -> 1
// parseInt('2', 1) -> NaN (因为在 1 进制中 '2' 不合法，且进制范围是 2-36)
// parseInt('3', 2) -> NaN (二进制里没有 3)

手写 map：

Array.prototype.myMap = function (callback, thisArg) {
  if (this == null) throw new TypeError("this is null or not defined");
  if (typeof callback !== "function")
    throw new TypeError(callback + " is not a function");

  const O = Object(this);
  const len = O.length >>> 0;
  const A = new Array(len); // 创建同长度新数组

  for (let i = 0; i < len; i++) {
    if (i in O) {
      // 处理稀疏数组：跳过 empty slots
      A[i] = callback.call(thisArg, O[i], i, O);
    }
  }
  return A;
};

2. filter (过滤)

filter 根据回调函数的返回值（Truthy/Falsy）来决定是否保留当前元素，返回一个包含所有保留元素的新数组。

基础使用：

const arr = [1, 2, 3, 4, 5, null, undefined, 0];
// 过滤偶数
const evens = arr.filter((n) => n % 2 === 0);
// 快速过滤所有假值 (Falsy: 0, "", null, undefined, NaN, false)
const truthyOnly = arr.filter(Boolean); // [1, 2, 3, 4, 5]

手写 filter：

Array.prototype.myFilter = function (callback, thisArg) {
  if (this == null) throw new TypeError("this is null or not defined");
  if (typeof callback !== "function")
    throw new TypeError(callback + " is not a function");

  const O = Object(this);
  const len = O.length >>> 0;
  const res = [];

  for (let i = 0; i < len; i++) {
    if (i in O) {
      // 跳过空位
      if (callback.call(thisArg, O[i], i, O)) {
        res.push(O[i]);
      }
    }
  }
  return res;
};

3. reduce (归并)

reduce 是最强大的数组方法，它可以将数组所有元素计算为一个单一的值，也可以用来实现 map、filter 的功能。

高阶用法场景：

const fruits = ["apple", "banana", "apple", "orange", "banana", "apple"];

// 场景1：统计元素出现次数
const count = fruits.reduce((acc, cur) => {
  acc[cur] = (acc[cur] || 0) + 1;
  return acc;
}, {}); // { apple: 3, banana: 2, orange: 1 }

// 场景2：按属性分组 (groupBy 的简易实现)
const people = [
  { age: 20, name: "A" },
  { age: 20, name: "B" },
  { age: 25, name: "C" },
];
const grouped = people.reduce((acc, cur) => {
  (acc[cur.age] = acc[cur.age] || []).push(cur);
  return acc;
}, {});
// { '20': [{age:20, name:'A'}, {age:20, name:'B'}], '25': [{age:25, name:'C'}] }

手写 reduce： 重点考察对 initialValue 缺省情况的处理，以及对回调签名的理解 (acc, cur, index, array)。

Array.prototype.myReduce = function (callback, initialValue) {
  if (this == null) throw new TypeError("this is null or not defined");
  if (typeof callback !== "function")
    throw new TypeError(callback + " is not a function");

  const O = Object(this);
  const len = O.length >>> 0;
  let acc = initialValue;
  let startIndex = 0;

  // 如果没有提供 initialValue，寻找数组第一个非空位元素作为初始值
  // 注意：不能用 initialValue === undefined 判断，因为可能主动传入了 undefined
  if (arguments.length < 2) {
    let k = 0;
    while (k < len && !(k in O)) {
      k++;
    }
    if (k >= len) {
      throw new TypeError("Reduce of empty array with no initial value");
    }
    acc = O[k++];
    startIndex = k;
  }

  for (let i = startIndex; i < len; i++) {
    if (i in O) {
      // 忽略稀疏数组的空位
      acc = callback(acc, O[i], i, O);
    }
  }
  return acc;
};

数组扁平化 (flat / flatMap)

flat

Array.prototype.flat(depth) 用于将嵌套的数组“拉平”，默认拉平一层。传入 Infinity 可以无限拉平。

基础使用示例：

const arr = [1, 2, [3, 4, [5, 6]]];
console.log(arr.flat()); // [1, 2, 3, 4, [5, 6]] (默认 depth=1)
console.log(arr.flat(2)); // [1, 2, 3, 4, 5, 6]
console.log(arr.flat(Infinity)); // [1, 2, 3, 4, 5, 6] (无限深度拉平)

flatMap

Array.prototype.flatMap() 相当于先调用 map()，然后再对结果调用 flat(1)。注意它只能拉平一层。 它的效率比单独调用 map().flat() 稍微高一点，因为底层只遍历了一次。

基础使用场景：

1. 生成并拉平数据（如将一句话拆分为单词数组）：

const sentences = ["Hello world", "Hi JS"];
// 用 map 会得到二维数组: [["Hello", "world"], ["Hi", "JS"]]
// 用 flatMap 会直接拉平: ["Hello", "world", "Hi", "JS"]
const words = sentences.flatMap((s) => s.split(" "));

2. 在遍历时动态增加/删除元素（相当于 filter + map 的结合体）：

const numbers = [1, 2, 3, 4];
// 需求：剔除偶数，并把奇数翻倍
const result = numbers.flatMap((n) => {
  if (n % 2 === 0) return []; // 返回空数组，拉平后就相当于被剔除了
  return [n * 2]; // 包装成数组，拉平后就是 n * 2
});
console.log(result); // [2, 6]

数组排序 (sort)

Array.prototype.sort() 默认会将元素转换为字符串，然后按 UTF-16 编码顺序排列。因此 [10, 2, 1] 默认排序结果是 [1, 10, 2]。

面试高频考点：V8 引擎下 sort 是用什么排序算法实现的？

• 早期 V8 (v7.0 之前)：

  • 数组长度 $\le$ 10：使用插入排序（Insertion Sort）。
  • 数组长度 > 10：使用快速排序（Quick Sort）。
  • 缺点：快速排序是不稳定排序。在处理包含多个相同排序权重对象的数组时，可能会打乱原本的相对顺序。

• 现代 V8 (v7.0 之后 / ES2019 标准)：

  • ES2019 明确规定了 Array.prototype.sort 必须是稳定的。
  • V8 引擎将底层算法改为了 TimSort。
  • TimSort 原理：结合了归并排序（Merge Sort）和插入排序（Insertion Sort）的混合排序算法。它会在数据规模较小或部分有序时使用插入排序，在大规模无序数据时使用归并排序，性能极高且绝对保证了稳定性。

V8 引擎中数组的底层存储机制

面试考点：JS 中的数组真的是分配在连续内存里的吗？

JS 的数组并不是传统意义上内存连续的“纯数组”，V8 引擎根据数组的特征，将其分为两种存储模式：

1. 快数组 (Fast Elements)：

   • 当数组是连续的，且元素类型相对一致时，V8 会在底层使用 C++ 的线性连续内存（真正的数组）来存储。
   • 支持通过索引直接寻址，读写速度极快。
   • 快数组还细分为 PACKED_SMI_ELEMENTS (全是小整数)、PACKED_DOUBLE_ELEMENTS (包含浮点数) 等。

2. 慢数组 / 字典模式 (Dictionary Elements)：

   • 当数组变成稀疏数组（例如直接 arr[10000] = 1），或者向数组中添加了非数字属性（arr.foo = 'bar'）时。
   • 为了节省大量连续内存空间，V8 会将这块连续内存转换为哈希表（Hash Table）。
   • 此时数组退化为普通的 JS 对象，按 key-value 存储，访问速度变慢。

性能优化建议：

• 尽量避免创建稀疏数组（如用 new Array(100) 然后不赋值）。
• 尽量保证数组内元素类型一致，避免触发底层 Elements Kind 的降级（一旦降级为慢数组，很难再优化回去）。
• 优先预分配适当大小的数组，避免频繁动态扩容带来的内存重新分配开销。

类数组转真实数组

类数组（Array-like Object，如 arguments 或 DOM NodeList）具有 length 属性和索引，但不具备数组的 API。

面试常问的转换方式：

1. Array.from(arrayLike)：ES6 标准，推荐，同时支持转换可迭代对象。
2. [...arrayLike]：扩展运算符。注意：这要求对象必须实现了 Symbol.iterator 接口，普通的纯类数组对象 {0: 'a', length: 1} 不能用此方法展开。
3. Array.prototype.slice.call(arrayLike)：ES5 时代的经典 hack 做法，利用 slice 内部返回新数组的机制实现转换。