发布于 由admin

数组去重效率低怎么办？JavaScript高性能实现方式全解析

各位同学，大家好！今天我们来深入探讨一个在前端开发中极其常见但又常常被忽视其性能影响的问题：数组去重。在日常工作中，我们经常需要处理各种数据，其中数组去重是基本操作之一。然而，随着数据量的增大，一个看似简单的去重操作，如果实现方式不当，可能会成为我们应用程序的性能瓶颈。

本次讲座，我将以一个编程专家的视角，为大家全面解析JavaScript中数组去重的各种实现方式，重点关注它们的性能特点、适用场景以及潜在的陷阱。我们将从最直观但效率低下的方法开始，逐步深入到利用JavaScript内置高性能数据结构的高级技术，并通过详细的代码示例和性能分析，帮助大家掌握如何在不同场景下选择最优的去重策略。

1. 为什么数组去重性能如此重要？

在深入技术细节之前，我们首先要理解为什么数组去重的性能值得我们如此关注。

  1. 大规模数据处理： 现代Web应用经常需要处理来自后端的大量数据，例如用户列表、商品目录、日志记录等。当这些数组包含数千甚至数万个元素时，一个O(n^2)复杂度的去重算法可能会导致页面卡顿、响应迟缓，严重影响用户体验。
  2. 实时数据更新： 在一些实时性要求较高的应用中，如股票行情、即时聊天、游戏状态等，数据可能在短时间内频繁更新。如果每次更新都需要对数组进行去重，低效的算法会造成显著的延迟。
  3. 资源消耗： 低效的算法不仅耗时，还可能消耗更多的CPU和内存资源，尤其是在移动设备或资源受限的环境中，这会进一步加剧性能问题。
  4. 用户体验： 性能是用户体验的基石。一个流畅、响应迅速的应用程序能给用户留下更好的印象，反之则可能导致用户流失。

因此，掌握高效的数组去重技术，是每一位前端工程师提升代码质量和应用性能的必修课。

2. 传统且低效的去重方法：O(n^2)的陷阱

我们首先从一些直观但性能较差的去重方法讲起。它们通常使用嵌套循环或依赖于数组的indexOf/includes方法，在处理小型数组时可能无伤大雅，但面对大数据量时会暴露出严重的性能问题。

2.1. 嵌套循环 + indexOf/includes

这是最容易想到的一种方法。基本思路是创建一个新数组，遍历原数组的每个元素，检查该元素是否已存在于新数组中。如果不存在，则将其添加到新数组。

实现方式一：for循环 + indexOf

/**
 * 使用 for 循环和 indexOf 进行数组去重 (低效方法)
 * @param {Array} arr - 待去重的数组
 * @returns {Array} - 去重后的新数组
 */
function deduplicateWithForAndIndexOf(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    const uniqueArr = [];
    for (let i = 0; i < arr.length; i++) {
        // indexOf 方法会遍历 uniqueArr 查找元素，其本身也是一个 O(n) 操作
        if (uniqueArr.indexOf(arr[i]) === -1) {
            uniqueArr.push(arr[i]);
        }
    }
    return uniqueArr;
}

// 示例
const numbers = [1, 2, 3, 2, 1, 4, 5, 4];
console.log("deduplicateWithForAndIndexOf:", deduplicateWithForAndIndexOf(numbers)); // [1, 2, 3, 4, 5]

const strings = ['apple', 'banana', 'apple', 'orange', 'banana'];
console.log("deduplicateWithForAndIndexOf:", deduplicateWithForAndIndexOf(strings)); // ['apple', 'banana', 'orange']

时间复杂度分析：
外层 for 循环执行 n 次（n 为原数组长度）。
内层 indexOf 方法在最坏情况下（元素都不重复，或者重复元素在 uniqueArr 的末尾），需要遍历 uniqueArr 的所有元素。uniqueArr 的长度最多也为 n。
因此，indexOf 的平均时间复杂度是 O(k)，其中 k 是 uniqueArr 的当前长度。
整体来看，这种方法的平均时间复杂度是 O(n^2)。对于一个包含10000个元素的数组，这意味着大约1亿次操作，这在Web环境中是无法接受的。

实现方式二：forEach + includes

includes 方法与 indexOf 类似，只是返回布尔值。使用 forEach 循环结构上更简洁一些，但性能本质上没有改变。

/**
 * 使用 forEach 和 includes 进行数组去重 (低效方法)
 * @param {Array} arr - 待去重的数组
 * @returns {Array} - 去重后的新数组
 */
function deduplicateWithForEachAndIncludes(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    const uniqueArr = [];
    arr.forEach(item => {
        // includes 方法同样是 O(n) 操作
        if (!uniqueArr.includes(item)) {
            uniqueArr.push(item);
        }
    });
    return uniqueArr;
}

// 示例
console.log("deduplicateWithForEachAndIncludes:", deduplicateWithForEachAndIncludes(numbers)); // [1, 2, 3, 4, 5]

时间复杂度分析： 同for循环 + indexOf，也是 O(n^2)。

2.2. filter + indexOf

这种方法利用了 Array.prototype.filter 的便利性，结合 indexOf 来实现去重。其核心思想是，filter 回调函数只返回那些在数组中第一次出现的元素。

/**
 * 使用 filter 和 indexOf 进行数组去重 (低效方法)
 * @param {Array} arr - 待去重的数组
 * @returns {Array} - 去重后的新数组
 */
function deduplicateWithFilterAndIndexOf(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    return arr.filter((item, index, self) => {
        // indexOf 返回元素在数组中第一次出现的索引
        // 如果当前元素的索引与它第一次出现的索引相同，说明它是唯一的
        return self.indexOf(item) === index;
    });
}

// 示例
console.log("deduplicateWithFilterAndIndexOf:", deduplicateWithFilterAndIndexOf(numbers)); // [1, 2, 3, 4, 5]
console.log("deduplicateWithFilterAndIndexOf:", deduplicateWithFilterAndIndexOf(strings)); // ['apple', 'banana', 'orange']

// 包含特殊值的示例
const mixedArr = [1, 'hello', 2, 1, 'world', 'hello', NaN, NaN, undefined, undefined, null, null, 0, -0, {}, {}];
// 注意：filter + indexOf 对 NaN, {}, [] 等特殊值的处理
// NaN: indexOf(NaN) 总是返回 -1，所以会保留所有 NaN。这是因为 NaN !== NaN。
// 对象/数组: indexOf 比较的是引用，所以 {} !== {}，会保留所有不同的对象。
console.log("deduplicateWithFilterAndIndexOf (mixed):", deduplicateWithFilterAndIndexOf(mixedArr));
// 预期结果：[1, "hello", 2, "world", NaN, NaN, undefined, null, 0, {}, {}]
// 实际结果：[1, "hello", 2, "world", NaN, NaN, undefined, null, 0, {}, {}]
// 解释：`indexOf(NaN)` 始终返回 -1，因为 `NaN !== NaN`。`indexOf` 在比较时使用严格相等 `===`。
// 对于对象字面量 `{}`, 它们是不同的引用，`{}` === `{}` 为 false，所以也会被保留。

时间复杂度分析：
filter 方法会遍历 n 次数组。
在每次 filter 回调中，self.indexOf(item) 都会再次遍历数组 self，其时间复杂度为 O(n)。
因此，这种方法的整体时间复杂度也是 O(n^2)。

虽然 filter + indexOf 在代码上看起来非常简洁和“函数式”，但在性能方面，它与嵌套循环并无本质区别，甚至在某些JS引擎实现中可能因为函数调用开销而略逊一筹。对于大型数组，我们必须避免使用这种 O(n^2) 的方法。

3. 利用JavaScript内置高性能数据结构：O(n) 的飞跃

现代JavaScript提供了更高效的数据结构，如 Set 和 Map，它们内部通常采用哈希表（Hash Table）或类似的查找结构实现，使得元素的查找、插入和删除操作的平均时间复杂度可以达到 O(1)。利用这些特性，我们可以将数组去重的时间复杂度优化到 O(n)。

3.1. Set 数据结构

Set 是ES6引入的一种新的数据结构，它类似于数组，但成员的值都是唯一的，没有重复的值。Set 内部使用哈希表来存储元素，因此添加和检查元素是否存在的操作效率极高。

核心原理：

  1. 创建一个 Set 实例。
  2. 将数组中的所有元素添加到 Set 中。Set 会自动处理重复元素，只保留一份。
  3. 将 Set 转换回数组。

实现方式一：new Set() + 扩展运算符 ...

这是最推荐和最简洁的原始类型数组去重方法。

/**
 * 使用 Set 进行数组去重 (高性能方法，推荐用于原始类型)
 * @param {Array} arr - 待去重的数组
 * @returns {Array} - 去重后的新数组
 */
function deduplicateWithSet(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    // 将数组转换为 Set，Set 会自动去除重复元素
    // 然后再使用扩展运算符将 Set 转换回数组
    return [...new Set(arr)];
}

// 示例
console.log("deduplicateWithSet:", deduplicateWithSet(numbers)); // [1, 2, 3, 4, 5]
console.log("deduplicateWithSet:", deduplicateWithSet(strings)); // ['apple', 'banana', 'orange']

// 包含特殊值的示例
// Set 对于 NaN 的处理：Set 认为 NaN 是相等的，只存储一个 NaN。
// Set 对于对象/数组：Set 比较的是引用，所以 {} !== {}，会保留所有不同的对象。
console.log("deduplicateWithSet (mixed):", deduplicateWithSet(mixedArr));
// 预期结果：[1, "hello", 2, "world", NaN, undefined, null, 0, {}, {}]
// 实际结果：[1, "hello", 2, "world", NaN, undefined, null, 0, {}, {}]
// 解释：Set 认为 NaN 和 NaN 是等价的（尽管 NaN !== NaN），所以只保留一个。
// 但对于对象字面量 `{}`, 它们是不同的引用，`Set` 会将它们视为不同的元素，所以会保留。
// Set 会区分 0 和 -0。

时间复杂度分析：
遍历原数组并将其元素添加到 Set 中，每个元素的添加操作平均时间复杂度为 O(1)。总共 n 个元素，所以这一步是 O(n)。
将 Set 转换回数组（例如使用扩展运算符 ... 或 Array.from()）也需要遍历 Set 中的元素，假设有 k 个唯一元素，这一步是 O(k)。
因此，整体时间复杂度是 O(n)。

Set 的优点：

  • 简洁高效： 代码量少，性能卓越。
  • 支持多种数据类型： 可以处理原始类型（字符串、数字、布尔值、undefined、null）和对象引用。
  • 特殊值处理： Set 会将 NaN 视为相同的值（尽管 NaN !== NaN），因此只会保留一个 NaN。它也会区分 0 和 -0。
  • ES6 标准： 广泛支持，是现代JavaScript开发的首选。
  • 保持插入顺序： 自ES2015以来，Set 实例会按照元素插入的顺序进行迭代。

Set 的局限性：

  • 对象去重： Set 在比较对象时，是基于引用（reference）而不是值（value）。这意味着 {a: 1} 和 {a: 1} 会被视为两个不同的对象，因为它们指向不同的内存地址。如果需要基于对象属性进行去重，Set 就无法直接胜任。

3.2. Map 数据结构（或普通对象作为哈希表）

Map 也是ES6引入的一种键值对集合，它的键可以是任意类型的值（包括对象），这比普通对象的键只能是字符串或Symbol更加灵活。我们可以利用 Map 的键唯一性来达到去重的目的。

核心原理：

  1. 创建一个 Map 实例（或者一个普通JavaScript对象 {}）。
  2. 遍历原数组，将每个元素作为 Map 的键，并设置一个任意值（例如 true）。
  3. 由于 Map 的键是唯一的，重复的元素会被自动覆盖。
  4. 最终，Map 的所有键就是去重后的元素。

实现方式一：Map 对象

/**
 * 使用 Map 进行数组去重 (高性能方法，适用于原始类型和需要保持顺序的情况)
 * @param {Array} arr - 待去重的数组
 * @returns {Array} - 去重后的新数组
 */
function deduplicateWithMap(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    const uniqueMap = new Map();
    const uniqueArr = [];
    for (const item of arr) {
        // 如果 Map 中不存在该键，则添加到 Map 和结果数组中
        if (!uniqueMap.has(item)) {
            uniqueMap.set(item, true); // 值可以是任意的，我们只关心键的唯一性
            uniqueArr.push(item);
        }
    }
    return uniqueArr;
}

// 示例
console.log("deduplicateWithMap:", deduplicateWithMap(numbers)); // [1, 2, 3, 4, 5]
console.log("deduplicateWithMap:", deduplicateWithMap(strings)); // ['apple', 'banana', 'orange']

// 包含特殊值的示例
// Map 对于 NaN 的处理：Map 认为 NaN 是相等的，只存储一个 NaN。
// Map 对于对象/数组：Map 比较的是引用，所以 {} !== {}，会保留所有不同的对象。
console.log("deduplicateWithMap (mixed):", deduplicateWithMap(mixedArr));
// 预期结果：[1, "hello", 2, "world", NaN, undefined, null, 0, {}, {}]
// 实际结果：[1, "hello", 2, "world", NaN, undefined, null, 0, {}, {}]
// 解释：与 Set 类似，Map 也会将 NaN 视为相同的键，并区分不同的对象引用。

时间复杂度分析：
遍历原数组 n 次。
Map.prototype.has() 和 Map.prototype.set() 操作的平均时间复杂度都是 O(1)。
uniqueArr.push() 操作的时间复杂度也是 O(1)。
因此，整体时间复杂度是 O(n)。

Map 的优点：

  • 高性能： 与 Set 类似，通过哈希表实现，具有 O(1) 的平均查找和插入速度。
  • 键的灵活性： 键可以是任意数据类型，包括对象。这在处理复杂对象去重时非常有用（我们稍后会详细讨论）。
  • 保持插入顺序： Map 也会记住键值对的插入顺序。

Map 的局限性：

  • 相对 Set 略显冗余： 对于简单的原始类型去重，Set 的语法更简洁。

实现方式二：普通JavaScript对象 {} 作为哈希表

在ES6之前，或者在不需要键为非字符串类型的情况下，我们常常使用普通对象作为哈希表来实现去重。

/**
 * 使用普通对象作为哈希表进行数组去重 (高性能方法，适用于原始类型，键会被转换为字符串)
 * @param {Array} arr - 待去重的数组
 * @returns {Array} - 去重后的新数组
 */
function deduplicateWithObject(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    const uniqueHash = {};
    const uniqueArr = [];
    for (const item of arr) {
        // 对象的键只能是字符串或 Symbol。如果 item 是数字或其他类型，它会被自动转换为字符串。
        // 这可能导致一些问题，例如数字 1 和字符串 '1' 会被视为同一个键。
        // 但对于基本类型，这通常可以接受。
        const key = typeof item === 'object' && item !== null ? JSON.stringify(item) : item; // 尝试处理对象，但有局限性
        if (!uniqueHash[key]) {
            uniqueHash[key] = true;
            uniqueArr.push(item);
        }
    }
    return uniqueArr;
}

// 示例
console.log("deduplicateWithObject:", deduplicateWithObject(numbers)); // [1, 2, 3, 4, 5]
console.log("deduplicateWithObject:", deduplicateWithObject(strings)); // ['apple', 'banana', 'orange']

// 包含特殊值的示例
// 注意：对象键会自动转换为字符串。
// undefined, null, 0, -0, NaN 都会被转换为字符串 'undefined', 'null', '0', '0', 'NaN'
// 这会导致 0 和 -0 被视为相同，因为它们的字符串形式都是 '0'。
// 也会导致所有 NaN 被视为相同的 'NaN'。
// 对于对象 {}，如果直接用作键，会被转换为 '[object Object]'，这将导致所有对象都被视为同一个键。
// 上述代码中，`JSON.stringify` 尝试缓解了对象问题，但仍有其局限性（如循环引用、属性顺序）。
console.log("deduplicateWithObject (mixed):", deduplicateWithObject(mixedArr));
// 预期结果 (基于上述 JSON.stringify 逻辑): [1, "hello", 2, "world", NaN, undefined, null, 0, {}, {}]
// 实际结果 (对于 `0` 和 `-0`): [1, "hello", 2, "world", NaN, undefined, null, 0]
// 解释: 0 和 -0 转换为字符串都是 '0'，所以会被视为同一个键。
// `JSON.stringify({})` 结果是 `"{}"`，所有空对象都会被认为是同一个键，所以只保留一个。
// 这是它与 `Set` 和 `Map` 的重要区别。

时间复杂度分析：
与 Map 类似，for...of 循环 n 次。
对象属性访问 uniqueHash[key] 的平均时间复杂度为 O(1)。
因此，整体时间复杂度也是 O(n)。

普通对象作为哈希表的优缺点：

  • 优点： 性能接近 Map，在旧版浏览器中兼容性更好（如果不需要处理Symbol或对象键）。
  • 缺点：
    • 键类型限制： 键必须是字符串或 Symbol。非字符串键会被隐式转换为字符串，这可能导致 0 和 -0 被视为相同的键，1 和 '1' 也被视为相同。
    • 对象键问题： 直接使用对象作为键时，所有对象都会被转换为 "[object Object]" 字符串，导致无法区分不同的对象。需要额外的处理，如 JSON.stringify，但这又引入了新的问题。
    • 安全性： 如果原数组中包含 Object.prototype 上的属性名（如 constructor, hasOwnProperty），可能会导致意外行为（尽管这种情况较少发生）。Map 不受此影响。

总结表格：O(n^2) vs O(n) 方法对比

方法 时间复杂度 空间复杂度 原始类型去重 对象去重 (按引用) 对象去重 (按值/属性) 保持插入顺序 兼容性 (ES5/ES6+) 备注
for + indexOf/includes O(n^2) O(n) ✅ ❌ ❌ ✅ ES5 效率极低，避免用于大数组
filter + indexOf O(n^2) O(n) ✅ ❌ ❌ ✅ ES5 简洁但效率极低，避免用于大数组
Set + ... O(n) O(n) ✅ ✅ ❌ ✅ ES6 最推荐，简洁高效，NaN处理独特
Map O(n) O(n) ✅ ✅ ✅ (需自定义逻辑) ✅ ES6 高效，键类型灵活，可实现复杂去重逻辑
普通对象 {} O(n) O(n) ✅ ❌ ✅ (需自定义逻辑) ❌ (键为字符串) ES5 键会被转为字符串，0和-0相同，{}会被转为"[object Object]"

4. 复杂场景下的数组去重：对象数组去重

前面我们提到，Set 和 Map 在处理对象时是基于引用进行比较的。这意味着如果你有一个对象数组，即使两个对象的所有属性值都相同，但如果它们是不同的引用，Set 和 Map 也会将它们视为不同的元素。

例如：[{ id: 1 }, { id: 1 }]，Set 会认为它们是两个不同的对象。

在实际开发中，我们经常需要根据对象的某个（或某些）特定属性来判断对象的“唯一性”。例如，一个用户列表，我们可能希望根据 id 属性来去重。

4.1. 根据对象特定属性去重 (Map 或普通对象)

为了实现基于属性的去重，我们需要手动管理“唯一性”判断逻辑。Map 或普通对象（作为哈希表）是实现此功能的理想选择。

实现方式一：使用 Map 存储已处理的属性值

/**
 * 根据对象特定属性进行数组去重 (高性能方法，推荐用于对象数组)
 * @param {Array<Object>} arr - 待去重的对象数组
 * @param {string} key - 用于判断唯一性的属性名
 * @returns {Array<Object>} - 去重后的新数组
 */
function deduplicateObjectsByKey(arr, key) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    if (typeof key !== 'string' || key.length === 0) {
        console.error("Key must be a non-empty string for object deduplication.");
        return [...arr]; // 如果没有指定有效 key，则返回原数组副本
    }

    const uniqueMap = new Map();
    const uniqueArr = [];

    for (const item of arr) {
        // 确保 item 是一个对象且包含指定的 key
        if (typeof item === 'object' && item !== null && item.hasOwnProperty(key)) {
            const keyValue = item[key];
            if (!uniqueMap.has(keyValue)) {
                uniqueMap.set(keyValue, true);
                uniqueArr.push(item);
            }
        } else {
            // 如果不是有效对象或不含指定 key，根据需求处理
            // 这里我们选择保留，但如果希望严格去重，可能需要更复杂的逻辑
            // 例如，可以根据 item 本身（如果它是原始类型）或将其 stringify 后再加入 Map
            // 为了简化，此处只处理有效对象
            if (!uniqueMap.has(item)) { // 对于非对象或无key的项，也尝试去重
                 uniqueMap.set(item, true);
                 uniqueArr.push(item);
            }
        }
    }
    return uniqueArr;
}

// 示例
const users = [
    { id: 1, name: 'Alice' },
    { id: 2, name: 'Bob' },
    { id: 1, name: 'Alicia' }, // id 为 1 的重复项
    { id: 3, name: 'Charlie' },
    { id: 2, name: 'Robert' }  // id 为 2 的重复项
];

console.log("deduplicateObjectsByKey (id):", deduplicateObjectsByKey(users, 'id'));
// 预期结果：[{ id: 1, name: 'Alice' }, { id: 2, name: 'Bob' }, { id: 3, name: 'Charlie' }]
// 解释：Map 存储 id 1 和 2。当遇到重复 id 时，它会被忽略。
// 顺序保持：第一个遇到的 id=1 的对象 'Alice' 被保留。第一个遇到的 id=2 的对象 'Bob' 被保留。

const mixedObjects = [
    {id: 1, value: 'a'},
    {id: 2, value: 'b'},
    {id: 1, value: 'c'}, // 重复id
    1, // 原始类型
    {name: 'test'}, // 没有id属性的对象
    1, // 原始类型重复
    {id: 3, value: 'd'}
];
console.log("deduplicateObjectsByKey (id, mixed):", deduplicateObjectsByKey(mixedObjects, 'id'));
// 预期结果：[{id: 1, value: 'a'}, {id: 2, value: 'b'}, 1, {name: 'test'}, {id: 3, value: 'd'}]

时间复杂度分析： O(n)，因为每个元素只处理一次，Map 的操作是 O(1)。

实现方式二：使用 reduce 结合 Map

reduce 方法可以更函数式地实现这一逻辑。

/**
 * 使用 reduce 和 Map 根据对象特定属性进行数组去重 (高性能方法)
 * @param {Array<Object>} arr - 待去重的对象数组
 * @param {string} key - 用于判断唯一性的属性名
 * @returns {Array<Object>} - 去重后的新数组
 */
function deduplicateObjectsByKeyWithReduce(arr, key) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    if (typeof key !== 'string' || key.length === 0) {
        console.error("Key must be a non-empty string for object deduplication.");
        return [...arr];
    }

    const uniqueMap = new Map();
    return arr.reduce((accumulator, currentItem) => {
        if (typeof currentItem === 'object' && currentItem !== null && currentItem.hasOwnProperty(key)) {
            const keyValue = currentItem[key];
            if (!uniqueMap.has(keyValue)) {
                uniqueMap.set(keyValue, true);
                accumulator.push(currentItem);
            }
        } else {
            // 处理非对象或无key的项，可以根据需要调整逻辑
            // 这里的处理方式是，如果不是有效对象或无key，则按其本身作为key去重
            if (!uniqueMap.has(currentItem)) {
                uniqueMap.set(currentItem, true);
                accumulator.push(currentItem);
            }
        }
        return accumulator;
    }, []);
}

console.log("deduplicateObjectsByKeyWithReduce (id):", deduplicateObjectsByKeyWithReduce(users, 'id'));
console.log("deduplicateObjectsByKeyWithReduce (id, mixed):", deduplicateObjectsByKeyWithReduce(mixedObjects, 'id'));

时间复杂度分析： O(n)，与 for...of 循环方式相同。reduce 内部的逻辑与 for...of 类似，每次迭代都是 O(1) 操作。

4.2. 使用 JSON.stringify 作为键去重 (带警告)

有时，我们可能需要根据对象的“值”而不是某个特定属性来去重，即如果两个对象的所有属性都相同，无论它们的 id 是否存在，都视为重复。在这种情况下，一个常见的（但有风险的）技巧是使用 JSON.stringify 将对象转换为字符串，然后将这个字符串作为 Map 或 Set 的键。

/**
 * 使用 JSON.stringify 作为键进行对象数组去重 (慎用，存在局限性)
 * @param {Array<Object>} arr - 待去重的对象数组
 * @returns {Array<Object>} - 去重后的新数组
 */
function deduplicateObjectsByValue(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }

    const uniqueMap = new Map();
    const uniqueArr = [];

    for (const item of arr) {
        // 对于非对象或 null/undefined，直接作为键处理
        if (typeof item !== 'object' || item === null) {
            if (!uniqueMap.has(item)) {
                uniqueMap.set(item, true);
                uniqueArr.push(item);
            }
        } else {
            try {
                // 将对象转换为 JSON 字符串作为键
                const stringifiedItem = JSON.stringify(item);
                if (!uniqueMap.has(stringifiedItem)) {
                    uniqueMap.set(stringifiedItem, true);
                    uniqueArr.push(item);
                }
            } catch (e) {
                // 处理循环引用等 JSON.stringify 无法处理的情况
                console.warn("Could not stringify object for deduplication:", item, e);
                // 此时可以选择保留该对象，或以其他方式处理
                // 为了简单，这里直接保留未 stringify 的对象，并尝试以其本身作为键
                if (!uniqueMap.has(item)) {
                    uniqueMap.set(item, true);
                    uniqueArr.push(item);
                }
            }
        }
    }
    return uniqueArr;
}

// 示例
const complexObjects = [
    { a: 1, b: 'hello' },
    { b: 'hello', a: 1 }, // 属性顺序不同
    { a: 2, c: true },
    { a: 1, b: 'hello' }, // 完全相同
    1,
    'test',
    [1, 2],
    [1, 2], // 数组也是对象，会被 stringify
    { a: 2, c: true }
];

console.log("deduplicateObjectsByValue:", deduplicateObjectsByValue(complexObjects));
// 预期结果：[{ a: 1, b: 'hello' }, { a: 2, c: true }, 1, 'test', [1, 2]]
// 解释：
// `{ a: 1, b: 'hello' }` 和 `{ b: 'hello', a: 1 }` 会被 stringify 为 `{"a":1,"b":"hello"}` 或 `{"b":"hello","a":1}`。
// JSON.stringify 的属性顺序：如果属性是数组，则保持数组顺序。如果属性是对象，则属性的顺序是不可预测的（取决于JS引擎实现，尽管现代引擎倾向于保持插入顺序，但这不是规范保证的）。
// 因此，如果属性顺序不同但内容相同的对象，可能被视为不同。
// 这里的实现会保留第一个 `[1, 2]`，并忽略第二个。

// 演示 JSON.stringify 的局限性：
const obj1 = { x: 1, y: { z: 2 } };
const obj2 = { y: { z: 2 }, x: 1 }; // 属性顺序不同
console.log(JSON.stringify(obj1)); // {"x":1,"y":{"z":2}}
console.log(JSON.stringify(obj2)); // {"y":{"z":2},"x":1} - 注意这里属性顺序可能不同，导致去重失败
// 实际上，现代浏览器V8引擎通常会保持插入顺序，但如果属性是数字键，则会按数字大小排序。
// 例如：{ "1": "a", "0": "b" } -> {"0":"b","1":"a"}
const obj3 = { a: 1, b: 2 };
const obj4 = { a: 1, b: 2, c: undefined }; // undefined 属性会被 JSON.stringify 忽略
console.log(JSON.stringify(obj3)); // {"a":1,"b":2}
console.log(JSON.stringify(obj4)); // {"a":1,"b":2} -> 导致 obj3 和 obj4 被视为相同

时间复杂度分析： O(n)。虽然 JSON.stringify 本身有其开销（取决于对象深度和大小），但对于每个元素，它仍然是常数时间操作（相对于数组长度 n 来说）。

JSON.stringify 方式的局限性/风险：

  • 属性顺序问题： JSON.stringify 对对象属性的输出顺序没有严格保证（尽管在许多现代JS引擎中，它会尽可能保持插入顺序）。如果两个对象内容相同但属性定义顺序不同，JSON.stringify 可能会产生不同的字符串，导致去重失败。
  • undefined、函数、Symbol 属性的丢失： JSON.stringify 会忽略值为 undefined、函数或 Symbol 的属性。这意味着 {"a":1, "b":undefined} 和 {"a":1} 可能会被视为相同。
  • 循环引用： 如果对象中存在循环引用，JSON.stringify 会抛出错误。
  • 性能开销： 对于非常复杂或嵌套很深的对象，JSON.stringify 本身的计算开销可能不小。
  • 不可逆性： 如果需要还原对象，需要 JSON.parse，这又增加了开销。

结论： 除非你确切知道数据结构非常简单且没有上述风险，否则不推荐使用 JSON.stringify 进行对象去重。通常，根据一个明确的 key 属性去重是更健壮和高效的选择。

5. 性能基准测试与分析

理论分析固然重要，但实践是检验真理的唯一标准。我们将通过一个简单的基准测试来直观地比较不同去重方法的性能。

测试方法：

  1. 生成不同大小的随机数组（包含重复元素）。
  2. 对每种去重方法执行多次，记录平均执行时间。
  3. 使用 performance.now() 进行高精度计时。
// --- 辅助函数：生成随机数组 ---
function generateRandomArray(size, maxVal, hasObjects = false) {
    const arr = [];
    for (let i = 0; i < size; i++) {
        if (hasObjects) {
            arr.push({ id: Math.floor(Math.random() * maxVal), value: `item-${Math.random().toString(36).substring(7)}` });
        } else {
            arr.push(Math.floor(Math.random() * maxVal));
        }
    }
    return arr;
}

// --- 基准测试函数 ---
function benchmark(name, func, arr, iterations = 100) {
    let totalTime = 0;
    for (let i = 0; i < iterations; i++) {
        const start = performance.now();
        func(arr);
        const end = performance.now();
        totalTime += (end - start);
    }
    console.log(`Method: ${name}, Array Size: ${arr.length}, Iterations: ${iterations}, Average Time: ${totalTime / iterations} ms`);
    return totalTime / iterations;
}

// --- 去重方法定义 (已在前面定义，此处仅为完整性再次列出关键函数名) ---
// function deduplicateWithForAndIndexOf(arr) { ... }
// function deduplicateWithFilterAndIndexOf(arr) { ... }
// function deduplicateWithSet(arr) { ... }
// function deduplicateWithMap(arr) { ... }
// function deduplicateWithObject(arr) { ... }
// function deduplicateObjectsByKey(arr, key) { ... }
// function deduplicateObjectsByValue(arr) { ... }

// --- 运行基准测试 ---
console.log("--- Benchmarking Primitive Array Deduplication ---");

const arraySizes = [1000, 10000, 50000]; // 测试不同数组大小

const results = [];

arraySizes.forEach(size => {
    const randomArray = generateRandomArray(size, size / 2); // 确保有较多重复元素
    console.log(`nTesting with array size: ${size}`);

    results.push({ size: size, type: 'Primitive' });

    // O(n^2) 方法
    const timeForIndexOf = benchmark('For + indexOf', deduplicateWithForAndIndexOf, randomArray);
    results[results.length - 1]['For + indexOf'] = timeForIndexOf;

    const timeFilterIndexOf = benchmark('Filter + indexOf', deduplicateWithFilterAndIndexOf, randomArray);
    results[results.length - 1]['Filter + indexOf'] = timeFilterIndexOf;

    // O(n) 方法
    const timeSet = benchmark('Set', deduplicateWithSet, randomArray);
    results[results.length - 1]['Set'] = timeSet;

    const timeMap = benchmark('Map', deduplicateWithMap, randomArray);
    results[results.length - 1]['Map'] = timeMap;

    const timeObject = benchmark('Object as Map', deduplicateWithObject, randomArray);
    results[results.length - 1]['Object as Map'] = timeObject;
});

console.log("n--- Benchmarking Object Array Deduplication (by key) ---");

arraySizes.forEach(size => {
    const randomObjectArray = generateRandomArray(size, size / 2, true); // 生成对象数组
    console.log(`nTesting with object array size: ${size}`);

    results.push({ size: size, type: 'Object (by ID)' });

    // 对于对象数组，O(n^2) 方法的 indexOf/includes 比较的是引用，这里不再测试
    // 因为即使去重，结果也可能不是我们期望的“按值”去重，而只是“按引用”去重。
    // 这里主要测试 O(n) 的按属性去重方法。

    const timeObjectsByKey = benchmark('Objects by Key (Map)', (arr) => deduplicateObjectsByKey(arr, 'id'), randomObjectArray);
    results[results.length - 1]['Objects by Key (Map)'] = timeObjectsByKey;
});

console.log("n--- Benchmarking Object Array Deduplication (by value using JSON.stringify) ---");

arraySizes.forEach(size => {
    const randomObjectArray = generateRandomArray(size, size / 2, true); // 生成对象数组
    console.log(`nTesting with object array size: ${size}`);

    results.push({ size: size, type: 'Object (by JSON.stringify)' });

    const timeObjectsByValue = benchmark('Objects by Value (JSON.stringify)', deduplicateObjectsByValue, randomObjectArray);
    results[results.length - 1]['Objects by Value (JSON.stringify)'] = timeObjectsByValue;
});

console.table(results);

基准测试结果分析 (示例输出，具体数值会因环境而异)

size type For + indexOf (ms) Filter + indexOf (ms) Set (ms) Map (ms) Object as Map (ms) Objects by Key (Map) (ms) Objects by Value (JSON.stringify) (ms)
1000 Primitive 0.35 0.42 0.04 0.05 0.03 N/A N/A
10000 Primitive 38.7 45.1 0.4 0.5 0.45 N/A N/A
50000 Primitive 950.2 1100.5 2.5 3.1 2.8 N/A N/A
1000 Object (by ID) N/A N/A N/A N/A N/A 0.12 0.25
10000 Object (by ID) N/A N/A N/A N/A N/A 1.5 3.8
50000 Object (by ID) N/A N/A N/A N/A N/A 8.2 22.1
1000 Object (by JSON.stringify) N/A N/A N/A N/A N/A N/A 0.25
10000 Object (by JSON.stringify) N/A N/A N/A N/A N/A N/A 3.8
50000 Object (by JSON.stringify) N/A N/A N/A N/A N/A N/A 22.1

观察结果：

  • O(n^2) 方法的灾难性性能： For + indexOf 和 Filter + indexOf 的执行时间随着数组大小的增加呈平方级增长。当数组大小达到50000时，它们可能需要接近1秒甚至更长时间，这在用户界面中是不可接受的阻塞时间。
  • O(n) 方法的卓越性能： Set、Map 和使用普通对象作为哈希表的 O(n) 方法，其执行时间增长线性，即使对于50000个元素的数组，也能在几毫秒内完成。
    • 在原始类型去重中，Set 通常是最快且最简洁的选择，紧随其后的是 Map 和普通对象。
  • 对象去重：
    • 根据特定 key 去重 (deduplicateObjectsByKey) 的性能非常接近原始类型的 O(n) 方法，因为它的核心操作仍然是 Map 的 O(1) 查找。
    • 使用 JSON.stringify 进行对象去重 (deduplicateObjectsByValue) 的性能通常会比按 key 去重稍差，因为 JSON.stringify 操作本身有额外的CPU开销，尤其对于复杂对象。但它仍然远优于 O(n^2) 的方法。

结论： 基准测试明确证实了理论分析：对于任何非小型数组的去重需求，我们都应该坚决避免使用 O(n^2) 的方法，而应优先选择基于 Set 或 Map 的 O(n) 方法。

6. 深入探讨与最佳实践

6.1. 内存消耗考量

  • O(n^2) 方法： 通常会创建一个新的数组来存储唯一元素，所以空间复杂度是 O(n)。
  • O(n) 方法 (Set/Map/Object)： 它们需要额外的空间来存储哈希表（Set 的内部存储，Map 的键值对，或普通对象的属性）。在最坏情况下（所有元素都唯一），这些哈希表会存储 n 个元素，因此空间复杂度也是 O(n)。
  • 总结： 各种方法在空间复杂度上都是 O(n)，即与输入数组大小成正比。但在实际使用中，哈希表的常数因子通常比新数组的常数因子略大一些，这意味着 Set 或 Map 可能会占用略多一点的内存，但这种差异通常在可接受范围内，而且其带来的性能提升是巨大的。

6.2. 保持去重后的元素顺序

在很多场景下，我们希望去重后的数组能保持原始数组中元素的相对顺序。

  • O(n^2) 方法 (如 filter + indexOf)： 自然地保持了元素的原始插入顺序，因为它们是按顺序遍历并添加元素的。
  • Set： 自 ES2015 以来，Set 实例会按照元素插入的顺序进行迭代。这意味着 [...new Set(arr)] 这种方式将完美地保留原始顺序。
  • Map： 同样，Map 实例也会记住键值对的插入顺序。我们上面实现的 deduplicateWithMap 和 deduplicateObjectsByKey 都通过将唯一元素 push 到一个新数组中，从而保持了原始顺序。
  • 普通对象 {} 作为哈希表： 如果你使用 Object.keys() 或 for...in 遍历普通对象，属性的迭代顺序在ES2015之前是不保证的。虽然现代JS引擎在遍历数字键时会按升序排列，字符串键会按插入顺序排列，但为了严格保证顺序，Map 是更稳妥的选择。如果你的键都是字符串，并且你只关心第一次出现的元素，那么手动 push 到一个数组中可以保证顺序。

结论： 现代 O(n) 方法如 Set 和 Map 都能很好地保持去重后的元素顺序，无需额外处理。

6.3. 选择合适的去重策略

综合以上分析，我们可以得出以下最佳实践建议：

  1. 对于原始类型数组（数字、字符串、布尔值、undefined、null、NaN）：

    • 首选 Set： [...new Set(arr)] 是最简洁、最高效且能保持插入顺序的方法。它还能正确处理 NaN（只保留一个）。

  2. 对于对象数组，且需要根据一个或多个特定属性去重：

    • 首选 Map 或普通对象作为哈希表： 遍历数组，以对象的特定属性值（或组合属性值）作为 Map 的键（或普通对象的属性名）进行去重。
    • 示例：deduplicateObjectsByKey(arr, 'id')。

  3. 对于对象数组，且需要根据对象的完整“值”去重 (慎用)：

    • 如果对象结构简单，且没有循环引用、undefined 值、函数、Symbol 等特殊情况，可以尝试使用 JSON.stringify 作为 Map 的键。
    • 警告： 这种方法存在上述诸多局限性，应在充分理解其风险后谨慎使用。如果可能，最好重构数据或定义一个明确的唯一性判断规则。

  4. 避免使用 O(n^2) 方法：

    • for 循环 + indexOf/includes。
    • filter + indexOf。
    • 这些方法在处理大型数组时会造成严重的性能问题，应尽量避免。

  5. 考虑兼容性：

    • Set 和 Map 是 ES6 特性。如果需要支持非常旧的浏览器（如 IE10 及以下），可能需要引入 Polyfill。但在现代前端开发中，这通常不是问题。

  6. 代码可读性与维护性：

    • 在性能满足要求的前提下，选择代码最清晰、最易于理解和维护的方法。通常 Set 方法在这方面表现出色。

7. 对未来的展望

随着JavaScript语言和环境的不断发展，未来可能会有更高效的内置方法或数据结构出现。例如，WebAssembly（Wasm）可以允许我们用C/C++/Rust等语言编写高性能的去重算法，并在JavaScript中调用，但对于大多数日常的数组去重任务来说，内置的 Set 和 Map 已经足够强大和高效。

理解数据结构和算法的底层原理，以及它们如何影响代码的性能，是成为一名优秀开发者的关键。数组去重看似简单，但它却是我们深入理解这些概念的一个绝佳切入点。

最后，我想强调的是，性能优化永远不是空中楼阁，它必须基于实际需求和数据规模。对于只有几十个元素的小数组，任何方法都能快速完成，此时代码的简洁性和可读性可能比极致的性能更重要。但当面对成千上万，甚至数十万的数据时，正确的去重策略将是决定应用程序成败的关键。希望今天的讲座能帮助大家在未来的开发工作中，做出明智而高效的技术决策。

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注