当处理包含数十万甚至更多项的大型javascript数组时，传统的`filter`结合`indexof`或`reduce`结合`includes`方法在提取唯一值时会导致严重的性能瓶颈，执行时间可达数分钟。本文将深入探讨这些方法的效率问题，并介绍如何利用javascript内置的`set`对象，以显著提高去重操作的效率，将时间复杂度从o(n^2)优化至接近o(n)，从而大幅提升用户体验。
传统去重方法的性能瓶颈
在JavaScript中，我们经常需要从数组中提取唯一的元素。对于小型数组，一些常见的去重方法表现良好，但在面对包含数十万甚至更多项的大型数组时，这些方法的性能会急剧下降，导致用户体验受损。
考虑以下两种常见的去重实现方式：
-
使用 filter 和 indexOf： 这种方法通过检查元素在数组中首次出现的索引是否与当前索引匹配来判断其唯一性。
const getUniqueValues = (array: string[]): string[] => { return array.filter((item, index, _array) => _array.indexOf(item) === index); }; // 示例用法：先映射数据，再进行去重和过滤假值 const uniqueValues = getUniqueValues( editedData.map((bodyItem: any) => bodyItem[index]) ).filter(Boolean);这种方法的性能问题在于 indexOf 操作。在最坏的情况下，indexOf 需要遍历数组的剩余部分来查找元素。对于一个长度为 n 的数组，filter 会迭代 n 次，每次迭代中的 indexOf 又可能需要 O(n) 的时间。因此，这种方法的整体时间复杂度为 O(n^2)。当数组包含50万项时，n^2 的操作次数将导致数分钟的执行时间。
-
使用 reduce 和 includes： 另一种常见方法是使用 reduce 迭代数组，并维护一个累加器（新数组），在每次添加元素前检查它是否已存在于累加器中。
const uniqueValues = editedData.reduce( (accumulator: string[], bodyItem: any) => { const item = bodyItem[index]; if (!accumulator.includes(item)) { accumulator.push(item); } return accumulator; }, [] );与 filter 和 indexOf 类似，reduce 方法中的 includes 操作也存在性能瓶颈。includes 在每次迭代中都需要遍历 accumulator 数组来检查元素是否存在。随着 accumulator 数组的增长，includes 的耗时也会增加。因此，这种方法的整体时间复杂度同样为 O(n^2)，对于大型数组，其性能表现同样不佳。
立即学习“Java免费学习笔记（深入）”；
JavaScript Set：高效去重利器
为了解决大型数组去重的性能问题，JavaScript ES6 引入的 Set 对象提供了一个极其高效的解决方案。Set 是一种数据结构，它允许你存储任何类型（包括原始值和对象引用）的唯一值。
Set 的工作原理与效率
Set 内部通常通过哈希表（Hash Table）实现。这意味着添加元素（add）、删除元素（delete）和检查元素是否存在（has）等操作的平均时间复杂度为 O(1)。这与数组的 indexOf 或 includes 的 O(n) 复杂度形成了鲜明对比。
使用 Set 进行去重
利用 Set 的特性，我们可以将数组转换为 Set，Set 会自动处理重复项，然后将 Set 转换回数组。
const getUniqueValues = (array: string[]): string[] => {
return [...new Set(array)];
};结合 map 操作的优化方案
将 Set 方法应用于原始问题场景，我们可以先进行 map 操作，然后将映射后的结果传递给 Set 进行去重。
// 假设 editedData 是原始数据数组 // index 是 bodyItem 中需要提取的属性键或索引 const mappedData: string[] = editedData.map((bodyItem: any) => bodyItem[index]); // 使用 Set 进行高效去重 const uniqueValues: string[] = [...new Set(mappedData)]; // 如果需要过滤假值（如 null, undefined, '', 0, false），可以继续链式调用 filter(Boolean) const uniqueAndTruthyValues: string[] = [...new Set(mappedData)].filter(Boolean);
性能对比与优势
-
时间复杂度：
- map 操作的时间复杂度为 O(n)。
- 将数组转换为 Set（new Set(array)）的时间复杂度平均为 O(n)，因为每个元素都需要被添加一次。
- 将 Set 转换回数组（[...set]）的时间复杂度为 O(m)，其中 m 是 Set 中唯一元素的数量。
- 因此，整个过程（map + Set去重）的整体时间复杂度约为 O(n)，这比 O(n^2) 有了质的飞跃。
实际效果：对于包含数十万项的数组，使用 Set 方法可以将执行时间从数分钟缩短到毫秒级别，极大地提升了应用程序的响应速度和用户体验。
代码简洁性：使用 Set 的代码更简洁、易读，且意图明确。
注意事项
- 元素类型：Set 可以存储任何类型的值。对于原始值（字符串、数字、布尔值、null、undefined、Symbol），Set 会根据值本身判断唯一性。对于对象（包括数组和函数），Set 会根据对象的引用（内存地址）判断唯一性。这意味着 {} 和 {} 会被视为两个不同的对象，即使它们内容相同。
- 顺序：虽然ES6规范没有强制要求 Set 保持元素的插入顺序，但现代JavaScript引擎（如V8、SpiderMonkey）通常会保留元素的插入顺序。因此，[...new Set(array)] 得到的新数组的元素顺序通常与原数组中首次出现的顺序一致。
- TypeScript 类型安全：在 TypeScript 环境中，确保 map 操作返回的数组类型与 Set 期望的类型一致，以保持类型安全。
总结
在处理大型JavaScript数组的去重需求时，我们应该优先考虑使用内置的 Set 对象。它提供了接近线性的时间复杂度（O(n)），远优于传统的 filter+indexOf 或 reduce+includes 方法的二次时间复杂度（O(n^2)）。通过将 map 操作与 Set 结合，我们可以高效、简洁地提取唯一值，从而显著提升应用程序的性能和用户体验。
