发布于 由admin

JavaScript 数组去重最全实现：从 Set 到 Map 再到 Reduce 的性能优劣

各位技术同仁，大家好！欢迎来到今天的技术讲座。今天我们将深入探讨JavaScript数组去重这一看似简单实则充满细节与选择的议题。数组去重是前端开发中一个极其常见的需求，从处理用户输入、清洗API数据到优化UI渲染，其身影无处不在。然而，面对不同数据类型、性能要求以及代码可读性，我们该如何选择最合适的去重策略呢？

今天的讲座，我们将一同穿越JavaScript历史与现代，从基础的循环遍历到ES6的Set、Map，再到强大的Reduce，层层深入，剖析各种实现方式的原理、优劣及其在不同场景下的适用性。我们不仅会看到简洁高效的现代解决方案，也会审视那些在特定条件下依然有其价值的传统方法。同时，性能将是我们贯穿始终的核心考量，我们将探讨如何理解和衡量不同方案的性能表现。

1. 数组去重：为何以及何处需要？

在软件开发中，数据往往不是以我们期望的完美形态呈现。数组去重，顾名思义，就是从一个包含重复元素的数组中移除所有重复项，只保留唯一的元素。这项任务在以下场景中尤为关键：

  • 数据清洗与预处理：从数据库查询、API接口返回或用户输入中获取的数据可能包含重复项，需要去重以保证数据的一致性和准确性。
  • 优化用户体验：例如，在搜索历史记录、标签云或推荐列表中，展示重复项会显得冗余且影响用户体验。
  • 性能优化：在某些计算或渲染场景中，处理唯一数据可以显著减少计算量和内存消耗。
  • 集合操作：在执行集合的并集、交集等操作前，确保集合内部元素的唯一性是基础。

理解去重的重要性，是选择正确去重策略的第一步。接下来，让我们从最基础、最直观的方法开始，逐步深入。

2. 基础去重方法：循环与查找

在ES6之前，或者当我们面对非常基础的场景时，我们通常会借助循环和数组的查找方法来实现去重。这些方法虽然在现代JavaScript中可能不是最优解，但理解它们有助于我们掌握去重的基本逻辑，并为后续更高级的方法打下基础。

2.1. 利用 indexOf 或 includes 方法

这是最直观的去重方法之一。我们创建一个新数组，遍历原数组的每个元素。在将元素添加到新数组之前，我们先检查新数组中是否已经存在该元素。

核心思想：遍历原数组，如果新数组中不包含当前元素，则将其添加到新数组。

/**
 * 使用 Array.prototype.indexOf 进行数组去重 (基本版本)
 * 适用于原始类型 (数字, 字符串, 布尔值)
 *
 * @param {Array<any>} arr - 待去重的数组
 * @returns {Array<any>} - 去重后的新数组
 */
function deduplicateWithIndexOf(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    const uniqueArr = [];
    for (let i = 0; i < arr.length; i++) {
        const currentElement = arr[i];
        if (uniqueArr.indexOf(currentElement) === -1) {
            uniqueArr.push(currentElement);
        }
    }
    return uniqueArr;
}

// 示例
const numbers = [1, 2, 2, 3, 4, 4, 5];
const strings = ['a', 'b', 'a', 'c', 'd', 'b'];
const mixedPrimitives = [1, 'a', 2, 'b', 1, 'a', null, undefined, null, NaN, NaN];

console.log("deduplicateWithIndexOf(numbers):", deduplicateWithIndexOf(numbers));
// 输出: [1, 2, 3, 4, 5]
console.log("deduplicateWithIndexOf(strings):", deduplicateWithIndexOf(strings));
// 输出: ['a', 'b', 'c', 'd']
console.log("deduplicateWithIndexOf(mixedPrimitives):", deduplicateWithIndexOf(mixedPrimitives));
// 输出: [1, 'a', 2, 'b', null, undefined, NaN]
// 注意：NaN === NaN 为 false，但 indexOf 内部对 NaN 有特殊处理，会找到第一个 NaN。

// 针对对象/数组的限制
const objects = [{id: 1}, {id: 2}, {id: 1}];
console.log("deduplicateWithIndexOf(objects):", deduplicateWithIndexOf(objects));
// 输出: [{id: 1}, {id: 2}, {id: 1}] - 对象是按引用比较的，所以它们都被认为是唯一的。

// 另一种变体：使用 Array.prototype.filter 和 indexOf
/**
 * 使用 Array.prototype.filter 和 indexOf 进行数组去重
 *
 * @param {Array<any>} arr - 待去重的数组
 * @returns {Array<any>} - 去重后的新数组
 */
function deduplicateWithFilterAndIndexOf(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    return arr.filter((item, index, self) => {
        // 如果当前元素的第一个出现位置就是当前位置，则保留
        return self.indexOf(item) === index;
    });
}

console.log("ndeduplicateWithFilterAndIndexOf(numbers):", deduplicateWithFilterAndIndexOf(numbers));
// 输出: [1, 2, 3, 4, 5]
console.log("deduplicateWithFilterAndIndexOf(strings):", deduplicateWithFilterAndIndexOf(strings));
// 输出: ['a', 'b', 'c', 'd']
console.log("deduplicateWithFilterAndIndexOf(mixedPrimitives):", deduplicateWithFilterAndIndexOf(mixedPrimitives));
// 输出: [1, 'a', 2, 'b', null, undefined, NaN]
console.log("deduplicateWithFilterAndIndexOf(objects):", deduplicateWithFilterAndIndexOf(objects));
// 输出: [{id: 1}, {id: 2}, {id: 1}] - 同样，对象按引用比较。

原理分析：
indexOf(element) 方法会返回数组中第一次出现指定元素的索引，如果不存在则返回 -1。includes(element) 方法则直接返回布尔值。它们的内部实现都需要遍历数组。

性能分析：
这种方法的时间复杂度是 O(n^2)。外层循环遍历 n 个元素，内层 indexOf 或 includes 操作在最坏情况下也需要遍历 n 个元素。因此，对于大型数组，这种方法的性能会急剧下降。

优缺点：

  • 优点：代码直观易懂，兼容性好（ES5及之前即可使用）。
  • 缺点：性能差，对于包含对象或数组的复杂数据类型，由于是按引用比较，无法实现基于值内容的去重。

2.2. 利用对象属性（Hash Map）作为“见过”的标记

为了优化 indexOf 的 O(n^2) 性能瓶颈，我们可以引入一个辅助对象（或者说一个哈希表）来记录已经“见过”的元素。这样，每次检查元素是否重复时，我们只需要 O(1) 的时间复杂度（平均情况）去查询对象属性，而不是 O(n) 去遍历数组。

核心思想：遍历原数组，将每个元素作为辅助对象的键（或值），如果该键不存在，则说明是第一次遇到，将其添加到结果数组并标记为已见过。

/**
 * 使用对象属性作为哈希表进行数组去重
 * 适用于原始类型 (数字, 字符串, 布尔值)，但会将数字键转换为字符串
 *
 * @param {Array<any>} arr - 待去重的数组
 * @returns {Array<any>} - 去重后的新数组
 */
function deduplicateWithObjectHash(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    const uniqueArr = [];
    const seen = {}; // 辅助对象，用于记录已见过的元素

    for (let i = 0; i < arr.length; i++) {
        const currentElement = arr[i];
        // 将元素转换为字符串作为对象的键
        // 注意：这里是最大的限制，对象的键只能是字符串或Symbol
        // 如果原始类型值可能冲突（例如数字1和字符串'1'），需要更复杂的键生成策略
        const key = typeof currentElement === 'object' && currentElement !== null
                    ? JSON.stringify(currentElement) // 尝试将对象序列化为键，但有局限性
                    : String(currentElement); // 其他原始类型转换为字符串

        if (!seen[key]) {
            uniqueArr.push(currentElement);
            seen[key] = true; // 标记为已见过
        }
    }
    return uniqueArr;
}

// 示例
const numbers = [1, 2, 2, 3, 4, 4, 5, 1];
const strings = ['a', 'b', 'a', 'c', 'd', 'b'];
const mixedPrimitives = [1, 'a', 2, 'b', 1, 'a', null, undefined, null, NaN, NaN, '1'];

console.log("ndeduplicateWithObjectHash(numbers):", deduplicateWithObjectHash(numbers));
// 输出: [1, 2, 3, 4, 5]
console.log("deduplicateWithObjectHash(strings):", deduplicateWithObjectHash(strings));
// 输出: ['a', 'b', 'c', 'd']
console.log("deduplicateWithObjectHash(mixedPrimitives):", deduplicateWithObjectHash(mixedPrimitives));
// 输出: [1, 'a', 2, 'b', null, undefined, NaN]
// 注意：NaN作为键时，String(NaN) => 'NaN'，所以只会保留一个NaN。
// 数字1和字符串'1'会被视为不同的键，因为String(1) => '1'，String('1') => '1'，这里会冲突，
// 在这个实现中，'1'会覆盖1，或者1被'1'覆盖，取决于谁先出现。
// 修正：如果1和'1'出现，String(1)和String('1')都生成'1'，所以只会保留第一个遇到的。
// 这是一个问题，因为1和'1'是不同的值。

// 针对对象/数组的局限性：JSON.stringify
// 注意：JSON.stringify 的结果取决于对象属性的顺序，以及无法处理循环引用。
const objects1 = [{id: 1, name: 'Alice'}, {name: 'Bob', id: 2}, {id: 1, name: 'Alice'}];
console.log("deduplicateWithObjectHash(objects1):", deduplicateWithObjectHash(objects1));
// 输出: [{id:1, name:'Alice'}, {name:'Bob', id:2}] (如果JSON.stringify顺序一致)

const objects2 = [{a:1, b:2}, {b:2, a:1}]; // 属性顺序不同
console.log("deduplicateWithObjectHash(objects2):", deduplicateWithObjectHash(objects2));
// 输出: [{a:1, b:2}, {b:2, a:1}] - JSON.stringify结果不同，认为它们是不同的。

原理分析：
JavaScript对象的键会自动转换为字符串。这意味着，如果你的数组中包含数字 1 和字符串 '1'，它们在作为键时都会被转换为 '1'，从而导致冲突，只有一个能被保留下来。对于 null 和 undefined，它们也会被转换为 'null' 和 'undefined'。NaN 也会被转换为 'NaN'。对于对象，如果直接作为键，会变成 "[object Object]"，这显然无法区分不同的对象。因此，我们尝试使用 JSON.stringify 将对象序列化为字符串作为键，但这也有其自身的局限性。

性能分析：
在平均情况下，对象属性的访问和设置是 O(1) 时间复杂度。因此，这种方法的时间复杂度在平均情况下是 O(n)。这比 indexOf 方法有了显著提升。

优缺点：

  • 优点：性能显著优于 indexOf 方法，时间复杂度达到 O(n)。
  • 缺点：
    • 键的类型限制：对象的键必须是字符串或 Symbol。这意味着数字 1 和字符串 '1' 会被视为同一个键，导致错误去重。
    • 无法直接处理对象或数组：如果数组元素是对象或数组，它们作为键时会失效（如 "[object Object]"），JSON.stringify 存在属性顺序、循环引用和性能开销等问题。
    • null 和 undefined 会被转化为字符串 'null' 和 'undefined'。

小结：传统方法的局限性

传统方法虽然易于理解，但在处理复杂数据类型（如对象、数组）和追求高性能时显得力不从心。尤其是对象作为数组元素时，由于JavaScript的引用比较机制，简单的 indexOf 或对象哈希都无法实现基于“内容”的去重。接下来，我们将迎来ES6带来的强大新特性，它们为数组去重带来了革命性的变化。

3. 现代JavaScript的利器：Set

ES6引入的 Set 是一种全新的数据结构，它最大的特点就是其成员的值都是唯一的，没有重复的值。这使得 Set 天生就是为数组去重而生。

3.1. Set 的基本用法与去重

Set 构造函数可以接受一个可迭代对象（如数组）作为参数，并将其所有成员添加到新的 Set 实例中。由于 Set 只存储唯一值，重复的元素会自动被过滤掉。

核心思想：利用 Set 的唯一性特性，将数组转换为 Set，再将 Set 转换回数组。

/**
 * 使用 Set 进行数组去重 (最简洁高效)
 * 适用于原始类型和对象引用去重
 *
 * @param {Array<any>} arr - 待去重的数组
 * @returns {Array<any>} - 去重后的新数组
 */
function deduplicateWithSet(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    // 方法一: 使用扩展运算符 (...) 将 Set 转换为数组
    return [...new Set(arr)];
    // 方法二: 使用 Array.from() 将 Set 转换为数组
    // return Array.from(new Set(arr));
}

// 示例
const numbers = [1, 2, 2, 3, 4, 4, 5, 1];
const strings = ['a', 'b', 'a', 'c', 'd', 'b'];
const mixedPrimitives = [1, 'a', 2, 'b', 1, 'a', null, undefined, null, NaN, NaN, '1'];

console.log("ndeduplicateWithSet(numbers):", deduplicateWithSet(numbers));
// 输出: [1, 2, 3, 4, 5]
console.log("deduplicateWithSet(strings):", deduplicateWithSet(strings));
// 输出: ['a', 'b', 'c', 'd']
console.log("deduplicateWithSet(mixedPrimitives):", deduplicateWithSet(mixedPrimitives));
// 输出: [1, 'a', 2, 'b', null, undefined, NaN, '1']
// Set 正确处理了 NaN (只保留一个) 和 1/'1' (视为不同值)。

// 处理对象/数组：按引用比较
const obj1 = {id: 1, name: 'Alice'};
const obj2 = {id: 2, name: 'Bob'};
const obj3 = {id: 1, name: 'Alice'}; // 与 obj1 内容相同，但引用不同
const objects = [obj1, obj2, obj3, obj1]; // obj1 出现两次，引用相同

console.log("deduplicateWithSet(objects):", deduplicateWithSet(objects));
// 输出: [{id: 1, name: 'Alice'}, {id: 2, name: 'Bob'}, {id: 1, name: 'Alice'}]
// 解释: Set 认为 obj1 和 obj3 是不同的对象，因为它们在内存中的引用地址不同。
// 只有 obj1 第一次出现和第二次出现时，由于引用相同，Set 才会去重。

const arr1 = [1, 2];
const arr2 = [3, 4];
const arr3 = [1, 2]; // 与 arr1 内容相同，但引用不同
const nestedArrays = [arr1, arr2, arr3, arr1];

console.log("deduplicateWithSet(nestedArrays):", deduplicateWithSet(nestedArrays));
// 输出: [[1, 2], [3, 4], [1, 2]]
// 解释: 同理，arr1 和 arr3 被视为不同的数组。

原理分析：
Set 内部使用了一种高效的哈希结构来存储其成员。

  • 原始类型：对于数字、字符串、布尔值、null、undefined，Set 会根据其值进行精确比较，确保唯一性。NaN 是一个特殊情况，NaN === NaN 为 false，但在 Set 中 NaN 被认为是与自身相等的，因此 Set 中只会出现一个 NaN。
  • 对象类型：对于对象（包括普通对象、数组、函数等），Set 是通过引用来判断唯一性的。这意味着，即使两个对象拥有完全相同的属性和值，只要它们是不同的内存引用，Set 就会将它们视为两个不同的元素。

性能分析：
Set 的添加和查找操作平均时间复杂度为 O(1)。因此，将数组转换为 Set，再将 Set 转换回数组，整个过程的时间复杂度是 O(n)，这是目前最快且最简洁的原始类型去重方法。

优缺点：

  • 优点：
    • 简洁高效：代码量少，易读性强。
    • 性能优异：对于原始类型，时间复杂度为 O(n)。
    • 正确处理特殊值：能正确处理 NaN、null、undefined。
    • 保持原始类型的值相等性：1 和 '1' 被视为不同的值。
  • 缺点：
    • 对象去重按引用：无法实现基于对象内容（值）的去重。这是 Set 在处理复杂数据结构时最大的局限性。
    • 不保证原始插入顺序：虽然现代JavaScript引擎在实现 Set 时通常会保留插入顺序，但ECMAScript规范并未强制要求 Set 的迭代顺序与插入顺序一致。因此，如果需要严格保持原始顺序，可能需要结合其他方法。

3.2. Set 结合 Map 实现更复杂的对象去重

当 Set 无法满足对象内容去重的需求时，我们通常需要自定义一个用于判断唯一性的“键”。这时，Map 就能派上用场，或者我们可以将 Set 与一些预处理逻辑结合。

核心思想：为了实现对象按内容去重，我们需要为每个对象生成一个唯一的“指纹”或“键”。这个键可以是对象的一个特定属性值，也可以是对象所有属性的序列化字符串。

/**
 * 使用 Map (或 Set) 结合自定义键实现对象数组去重
 * 场景1: 根据对象某个唯一属性 (如 id) 去重
 *
 * @param {Array<Object>} arr - 待去重的对象数组
 * @param {string} keyProp - 用于判断唯一性的属性名
 * @returns {Array<Object>} - 去重后的新数组
 */
function deduplicateObjectsByKeyProp(arr, keyProp) {
    if (!Array.isArray(arr) || !keyProp) {
        console.error("Input must be an array and a key property must be provided.");
        return [];
    }
    const uniqueArr = [];
    const seenKeys = new Set(); // 使用 Set 存储已见过的 key 值

    for (let i = 0; i < arr.length; i++) {
        const currentObject = arr[i];
        if (typeof currentObject !== 'object' || currentObject === null) {
            // 如果数组中混入了非对象元素，可以根据需求选择处理方式
            // 这里简单地将其视为唯一值，或者可以过滤掉
            if (!seenKeys.has(currentObject)) {
                uniqueArr.push(currentObject);
                seenKeys.add(currentObject);
            }
            continue;
        }

        const keyValue = currentObject[keyProp];
        if (keyValue === undefined) {
            // 如果对象没有指定的 keyProp，可以根据需求处理
            // 这里选择将其视为唯一，并添加到结果中
            console.warn(`Object at index ${i} does not have property '${keyProp}'.`);
            // 为了避免与实际的 undefined 值冲突，可以生成一个特殊的键
            const specialKey = `__NO_KEY_PROP__${JSON.stringify(currentObject)}`;
            if (!seenKeys.has(specialKey)) {
                uniqueArr.push(currentObject);
                seenKeys.add(specialKey);
            }
        } else if (!seenKeys.has(keyValue)) {
            uniqueArr.push(currentObject);
            seenKeys.add(keyValue);
        }
    }
    return uniqueArr;
}

const students = [
    {id: 1, name: 'Alice', age: 20},
    {id: 2, name: 'Bob', age: 22},
    {id: 1, name: 'Charlie', age: 21}, // id 重复，但 name, age 不同
    {id: 3, name: 'David', age: 23},
    {id: 2, name: 'Eve', age: 24}, // id 重复
    null, // 混入非对象
    undefined, // 混入非对象
    {id: 4, score: 90} // 没有 name 属性
];

console.log("ndeduplicateObjectsByKeyProp(students, 'id'):", deduplicateObjectsByKeyProp(students, 'id'));
// 输出: [
//   { id: 1, name: 'Alice', age: 20 },
//   { id: 2, name: 'Bob', age: 22 },
//   { id: 3, name: 'David', age: 23 },
//   null,
//   undefined,
//   { id: 4, score: 90 }
// ]

/**
 * 使用 Map 结合 JSON.stringify 实现对象数组去重 (按内容去重)
 * 优点: 简单粗暴，实现内容去重
 * 缺点: 性能开销大，无法处理循环引用，属性顺序不同会导致被认为是不同对象
 *
 * @param {Array<Object>} arr - 待去重的对象数组
 * @returns {Array<Object>} - 去重后的新数组
 */
function deduplicateObjectsByContent(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    const uniqueArr = [];
    const seenStrings = new Set(); // 使用 Set 存储对象的 JSON 字符串

    for (let i = 0; i < arr.length; i++) {
        const currentElement = arr[i];
        let serialized = String(currentElement); // 默认处理非对象和原始类型

        if (typeof currentElement === 'object' && currentElement !== null) {
            try {
                serialized = JSON.stringify(currentElement);
            } catch (e) {
                console.warn(`Could not stringify object at index ${i}:`, e.message);
                // 无法序列化的对象，可以根据需求选择如何处理
                // 这里选择将其视为唯一，并生成一个特殊的键
                serialized = `__NON_SERIALIZABLE__${i}`;
            }
        }

        if (!seenStrings.has(serialized)) {
            uniqueArr.push(currentElement);
            seenStrings.add(serialized);
        }
    }
    return uniqueArr;
}

const products1 = [
    {name: 'Laptop', price: 1200},
    {name: 'Mouse', price: 25},
    {name: 'Laptop', price: 1200}, // 完全相同
    {name: 'Keyboard', price: 75},
    {price: 25, name: 'Mouse'} // 属性顺序不同
];

console.log("ndeduplicateObjectsByContent(products1):", deduplicateObjectsByContent(products1));
// 输出: [
//   { name: 'Laptop', price: 1200 },
//   { name: 'Mouse', price: 25 },
//   { name: 'Keyboard', price: 75 },
//   { price: 25, name: 'Mouse' } // 属性顺序不同导致 JSON.stringify 结果不同，被认为是不同的
// ]

const products2 = [
    {name: 'Monitor', specs: {size: 27, resolution: '4K'}},
    {name: 'Webcam', specs: {resolution: '1080p'}},
    {name: 'Monitor', specs: {size: 27, resolution: '4K'}}, // 完全相同
    {specs: {size: 27, resolution: '4K'}, name: 'Monitor'} // 顶级属性顺序不同
];

console.log("ndeduplicateObjectsByContent(products2):", deduplicateObjectsByContent(products2));
// 输出: [
//   { name: 'Monitor', specs: { size: 27, resolution: '4K' } },
//   { name: 'Webcam', specs: { resolution: '1080p' } },
//   { specs: { size: 27, resolution: '4K' }, name: 'Monitor' } // 顶级属性顺序不同，被认为是不同的
// ]

原理分析：

  • 按特定属性去重：我们遍历数组，提取每个对象的指定 keyProp 值作为唯一标识。将这些 keyProp 值存储在一个 Set 中。如果 Set 中尚未包含该 keyProp 值，则将当前对象添加到结果数组，并将 keyProp 值添加到 Set。
  • 按内容（JSON.stringify）去重：将每个对象通过 JSON.stringify 转换为字符串。由于 Set 可以存储字符串，我们可以利用它来判断这些字符串是否重复。如果字符串重复，则认为对象内容重复。

性能分析：

  • 按特定属性去重：时间复杂度为 O(n)，因为 Set 的查找和添加是 O(1)。
  • 按内容 (JSON.stringify) 去重：时间复杂度为 *O(n L)**，其中 L 是 JSON.stringify 操作的平均时间复杂度，它取决于对象的复杂度和大小。JSON.stringify 可能会很慢，尤其对于大型或深层嵌套的对象。此外，它无法处理循环引用，并且不同属性顺序的对象会生成不同的字符串，导致无法正确去重。

优缺点：

  • 优点：
    • 能够实现更精细化的去重逻辑，例如根据对象的某个ID属性去重。
    • JSON.stringify 方法在属性顺序一致且无循环引用的情况下，能实现基于内容的基础去重。
  • 缺点：
    • JSON.stringify 存在显著的性能开销，特别是对于复杂对象。
    • JSON.stringify 无法处理循环引用，会抛出错误。
    • JSON.stringify 的结果取决于对象属性的顺序，如果两个内容相同的对象属性顺序不同，会被视为不同。
    • 对于深层嵌套且需要精确内容比较的场景，JSON.stringify 往往不够用，需要自定义深层比较函数。

4. Map 在去重中的应用

虽然 Set 是去重的主力，但 Map 凭借其强大的键值对存储能力（键可以是任意类型），在某些需要更复杂去重逻辑，特别是需要保留原始顺序或进行高级映射的场景中，也能发挥独特作用。

4.1. 利用 Map 存储已见过的元素并保持顺序

Map 与普通对象的主要区别在于 Map 的键可以是任意类型的值（包括对象、数组），而普通对象的键只能是字符串或 Symbol。此外，Map 会保留键值对的插入顺序。

核心思想：遍历数组，将每个元素（或其某个标识）作为 Map 的键，将元素本身作为 Map 的值。由于 Map 的键是唯一的，重复的键值对会被覆盖，最终 Map 中只保留唯一的键。遍历 Map 的值即可得到去重后的数组，且保持了第一次出现的顺序。

/**
 * 使用 Map 进行数组去重 (保留原始顺序，且键可以是任意类型)
 * 适用于原始类型和对象引用去重，或根据对象某个属性去重
 *
 * @param {Array<any>} arr - 待去重的数组
 * @param {Function} [keyGenerator] - 可选的键生成函数。
 *                                    如果提供，则根据此函数返回值判断唯一性；
 *                                    否则直接使用元素本身作为键 (按引用比较)。
 * @returns {Array<any>} - 去重后的新数组 (保留原始顺序)
 */
function deduplicateWithMap(arr, keyGenerator = (item) => item) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    const uniqueMap = new Map();

    for (let i = 0; i < arr.length; i++) {
        const currentElement = arr[i];
        const key = keyGenerator(currentElement); // 生成用于 Map 的键
        if (!uniqueMap.has(key)) {
            uniqueMap.set(key, currentElement); // 存储第一个遇到的元素
        }
    }
    // Map.prototype.values() 返回一个迭代器，Array.from 或扩展运算符可将其转换为数组
    return Array.from(uniqueMap.values());
}

// 示例1: 原始类型去重 (与 Set 行为类似，但保留了顺序)
const mixedPrimitives = [1, 'a', 2, 'b', 1, 'a', null, undefined, null, NaN, NaN, '1', 2];
console.log("ndeduplicateWithMap(mixedPrimitives):", deduplicateWithMap(mixedPrimitives));
// 输出: [1, 'a', 2, 'b', null, undefined, NaN, '1'] (顺序与Set不同，Set是基于哈希，Map保留插入顺序)

// 示例2: 对象按引用去重 (keyGenerator 默认为 item => item)
const objA = {id: 1};
const objB = {id: 2};
const objC = {id: 1}; // 内容与 objA 相同，但引用不同
const objectReferences = [objA, objB, objC, objA];
console.log("deduplicateWithMap(objectReferences):", deduplicateWithMap(objectReferences));
// 输出: [{id: 1}, {id: 2}, {id: 1}] (objA, objB, objC 引用不同，都被保留)

// 示例3: 对象按特定属性去重 (使用 keyGenerator)
const students = [
    {id: 1, name: 'Alice'},
    {id: 2, name: 'Bob'},
    {id: 1, name: 'Charlie'}, // id 重复
    {id: 3, name: 'David'},
    {id: 2, name: 'Eve'} // id 重复
];
console.log("deduplicateWithMap(students, (student) => student.id):", deduplicateWithMap(students, (student) => student.id));
// 输出: [{id: 1, name: 'Alice'}, {id: 2, name: 'Bob'}, {id: 3, name: 'David'}]
// 注意：对于 id=1 的学生，'Alice'被保留，'Charlie'被丢弃，因为'Alice'先出现。

// 示例4: 对象按内容去重 (使用 JSON.stringify 作为 keyGenerator)
// 同样存在 JSON.stringify 的局限性
const products = [
    {name: 'Laptop', price: 1200},
    {name: 'Mouse', price: 25},
    {name: 'Laptop', price: 1200},
    {price: 25, name: 'Mouse'} // 属性顺序不同
];
console.log("deduplicateWithMap(products, (product) => JSON.stringify(product)):", deduplicateWithMap(products, (product) => JSON.stringify(product)));
// 输出: [
//   { name: 'Laptop', price: 1200 },
//   { name: 'Mouse', price: 25 },
//   { price: 25, name: 'Mouse' } // 属性顺序不同导致被认为是不同的
// ]

原理分析：
Map 提供了一种将任意JavaScript值（包括对象和基本类型）作为键的能力。当 keyGenerator 函数没有提供时，默认直接使用元素本身作为键。对于原始类型，Map 会按值比较键；对于对象类型，Map 会按引用比较键。
如果提供了 keyGenerator，它会为每个元素生成一个自定义的键。这个键可以是对象的 id 属性、JSON.stringify 结果，甚至是自定义的哈希值。Map 内部会高效地查找这些键，确保只有第一个出现的键被存储。

性能分析：
Map 的 has() 和 set() 操作平均时间复杂度为 O(1)。因此，遍历数组并使用 Map 去重的时间复杂度是 O(n)。如果 keyGenerator 涉及到复杂计算（如 JSON.stringify 或深层比较），那么实际性能会受到 keyGenerator 自身复杂度的影响。

优缺点：

  • 优点：
    • 保持原始插入顺序：这是 Map 相对于 Set 的一个显著优势。
    • 键的灵活性：可以使用任意类型的值作为键，这使得它非常适合根据对象某个属性或自定义逻辑进行去重。
    • 性能优异：核心操作时间复杂度为 O(n)。
  • 缺点：
    • 代码量比 Set 略多。
    • 自定义 keyGenerator 函数的复杂性直接影响整体性能和正确性。

5. Reduce 的灵活运用

Array.prototype.reduce() 方法是一个极其强大的数组迭代器，它可以将一个数组“归约”成任何你想要的值，包括一个新的、去重后的数组。reduce 本身并不提供去重能力，但它可以与 Set 或 Map 结合，构建出高度灵活且性能优良的去重方案。

5.1. Reduce 结合 includes (不推荐，性能差)

为了完整性，我们先展示 reduce 结合 includes 的方法。这与之前 filter 结合 indexOf 的性能问题类似。

/**
 * 使用 Array.prototype.reduce 和 Array.prototype.includes 进行数组去重
 * 适用于原始类型，但性能较差
 *
 * @param {Array<any>} arr - 待去重的数组
 * @returns {Array<any>} - 去重后的新数组
 */
function deduplicateWithReduceAndIncludes(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    return arr.reduce((accumulator, current) => {
        if (!accumulator.includes(current)) {
            accumulator.push(current);
        }
        return accumulator;
    }, []);
}

const numbers = [1, 2, 2, 3, 4, 4, 5];
console.log("ndeduplicateWithReduceAndIncludes(numbers):", deduplicateWithReduceAndIncludes(numbers));
// 输出: [1, 2, 3, 4, 5]

性能分析：
与 filter + indexOf 类似，includes 在 reduce 内部每次调用时都需要遍历 accumulator 数组。因此，其时间复杂度为 O(n^2)。不推荐在大数组上使用。

5.2. Reduce 结合 Set 或 Map (推荐，灵活高效)

这是 reduce 在去重中最实用的场景。我们利用 reduce 迭代数组的灵活性，同时借助 Set 或 Map 提供的高效查找能力。

核心思想：
reduce 接收一个回调函数和一个初始值。回调函数会累积一个结果（例如，去重后的数组），同时使用一个 Set 或 Map 作为辅助数据结构来跟踪已经“见过”的元素。

/**
 * 使用 Array.prototype.reduce 和 Set 进行原始类型数组去重 (保留顺序)
 *
 * @param {Array<any>} arr - 待去重的数组
 * @returns {Array<any>} - 去重后的新数组
 */
function deduplicateWithReduceAndSet(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    const seen = new Set(); // 用于快速查找
    return arr.reduce((accumulator, current) => {
        if (!seen.has(current)) {
            seen.add(current);
            accumulator.push(current);
        }
        return accumulator;
    }, []);
}

const mixedPrimitives = [1, 'a', 2, 'b', 1, 'a', null, undefined, null, NaN, NaN, '1', 2];
console.log("ndeduplicateWithReduceAndSet(mixedPrimitives):", deduplicateWithReduceAndSet(mixedPrimitives));
// 输出: [1, 'a', 2, 'b', null, undefined, NaN, '1']
// 结果与 `deduplicateWithMap` 示例1 相同，因为都保留了原始顺序。

/**
 * 使用 Array.prototype.reduce 和 Map 进行对象数组去重 (按特定属性，保留顺序)
 *
 * @param {Array<Object>} arr - 待去重的对象数组
 * @param {string} keyProp - 用于判断唯一性的属性名
 * @returns {Array<Object>} - 去重后的新数组
 */
function deduplicateObjectsWithReduceAndMap(arr, keyProp) {
    if (!Array.isArray(arr) || !keyProp) {
        console.error("Input must be an array and a key property must be provided.");
        return [];
    }
    const seenMap = new Map(); // 用于存储已见过的 key 值及其对应的元素
    return arr.reduce((accumulator, current) => {
        if (typeof current !== 'object' || current === null) {
            // 处理非对象元素
            if (!seenMap.has(current)) {
                seenMap.set(current, true); // 记录已见
                accumulator.push(current);
            }
        } else {
            const keyValue = current[keyProp];
            if (!seenMap.has(keyValue)) {
                seenMap.set(keyValue, true); // 记录已见
                accumulator.push(current);
            }
        }
        return accumulator;
    }, []);
}

const students = [
    {id: 1, name: 'Alice'},
    {id: 2, name: 'Bob'},
    {id: 1, name: 'Charlie'},
    {id: 3, name: 'David'},
    {id: 2, name: 'Eve'},
    null
];
console.log("deduplicateObjectsWithReduceAndMap(students, 'id'):", deduplicateObjectsWithReduceAndMap(students, 'id'));
// 输出: [{id: 1, name: 'Alice'}, {id: 2, name: 'Bob'}, {id: 3, name: 'David'}, null]

/**
 * 使用 Array.prototype.reduce 和 Map 进行对象数组去重 (按内容，使用 JSON.stringify)
 *
 * @param {Array<Object>} arr - 待去重的对象数组
 * @returns {Array<Object>} - 去重后的新数组
 */
function deduplicateObjectsByContentWithReduceAndMap(arr) {
    if (!Array.isArray(arr)) {
        console.error("Input must be an array.");
        return [];
    }
    const seenMap = new Map();
    return arr.reduce((accumulator, current) => {
        let serializedKey;
        if (typeof current === 'object' && current !== null) {
            try {
                serializedKey = JSON.stringify(current);
            } catch (e) {
                console.warn(`Could not stringify object for deduplication: ${e.message}`);
                // 无法序列化的对象，生成一个特殊的唯一键
                serializedKey = `__NON_SERIALIZABLE__${accumulator.length}`;
            }
        } else {
            serializedKey = String(current); // 原始类型直接转换为字符串
        }

        if (!seenMap.has(serializedKey)) {
            seenMap.set(serializedKey, true);
            accumulator.push(current);
        }
        return accumulator;
    }, []);
}

const products = [
    {name: 'TV', price: 500},
    {name: 'Phone', price: 800},
    {name: 'TV', price: 500},
    {price: 800, name: 'Phone'} // 属性顺序不同
];
console.log("deduplicateObjectsByContentWithReduceAndMap(products):", deduplicateObjectsByContentWithReduceAndMap(products));
// 输出: [
//   { name: 'TV', price: 500 },
//   { name: 'Phone', price: 800 },
//   { price: 800, name: 'Phone' } // 属性顺序不同，被认为是不同的
// ]

原理分析：
reduce 遍历数组，accumulator 逐步构建去重后的结果数组。seen (Set 或 Map) 则作为快速查找表，存储已经处理过的元素的唯一标识。这种模式允许我们：

  • 保持原始顺序：reduce 按照原始数组的顺序遍历，并将第一次遇到的元素添加到 accumulator。
  • 高度定制化：通过调整 seen 的键（例如，使用 item 本身、item.id、JSON.stringify(item) 甚至一个自定义的哈希函数），可以实现各种复杂的去重逻辑。

性能分析：
reduce 本身只是迭代器，其性能主要取决于回调函数内部的操作。

  • reduce + Set：时间复杂度为 O(n)，因为 Set.has() 和 Set.add() 是 O(1)。这是原始类型去重且保留顺序的非常高效且灵活的方法。
  • reduce + Map (自定义键)：时间复杂度为 O(n + C)，其中 C 是 keyGenerator 函数的平均计算成本。如果 keyGenerator 简单（如 item.id），则接近 O(n)。如果 keyGenerator 复杂（如 JSON.stringify 或深层比较），则性能会下降。

优缺点：

  • 优点：
    • 极致的灵活性：可以实现几乎任何去重逻辑，包括按内容去重、自定义比较等。
    • 保持原始顺序：可以轻松地在去重的同时保持元素的原始相对顺序。
    • 性能良好：结合 Set 或 Map 后，核心去重操作为 O(n)。
  • 缺点：
    • 代码相对复杂，可读性可能不如 [...new Set(arr)] 直观。
    • 需要对 reduce、Set/Map 有较好的理解。

6. 性能深度解析与考量

理解不同去重方法的性能特性至关重要，尤其是在处理大量数据时。我们不能仅仅依靠理论上的时间复杂度，还需要考虑实际操作中的常数因子和JavaScript引擎的优化。

6.1. 影响性能的因素

  • 数组大小 (n)：这是最主要的因素。O(n^2) 的方法在大数组上会指数级变慢。
  • 数据类型：原始类型（数字、字符串）通常比对象或数组的比较更快。
  • 数据分布：数组中重复元素的数量和位置也会影响某些方法的性能。
  • 键生成策略：对于对象去重，如何生成用于 Set 或 Map 的键（例如 item.id vs. JSON.stringify(item) vs. 自定义哈希）对性能影响巨大。
  • JavaScript引擎优化：V8、SpiderMonkey等引擎对内置数据结构（如 Set、Map）和方法（如 filter、reduce）进行了高度优化。

6.2. 性能概览表

下表总结了各种去重方法在典型场景下的性能、特点和适用性。

方法 最佳用例 时间复杂度 (平均) 空间复杂度 (平均) 顺序保留 对象按值去重 备注
filter + indexOf 简单原始类型，小数组 O(n^2) O(n) 是 否 性能最差，不推荐用于大数组。
循环 + Object 哈希 (seen 对象) 原始类型，键会被转换为字符串 O(n) O(n) 是 否 键类型限制，1 和 '1' 会冲突。
[...new Set(arr)] 原始类型，或对象按引用去重 O(n) O(n) 否* 否 最简洁高效。*现代引擎通常保留插入顺序，但非规范保证。
Map (默认键) + Array.from(map.values()) 原始类型，或对象按引用去重，需保留顺序 O(n) O(n) 是 否 键可以是任意类型，但默认仍是按引用比较对象。
Map (自定义 keyGenerator) 对象按特定属性去重，需保留顺序 O(n + KeyGen) O(n) 是 是 (通过键) KeyGen 函数的性能是关键。
Reduce + Set 原始类型，需保留顺序，或对象按引用去重 O(n) O(n) 是 否 结合了 reduce 的灵活性和 Set 的高效性。
Reduce + Map (自定义 keyGenerator) 对象按值去重，高度定制化，需保留顺序 O(n + KeyGen) O(n) 是 是 (通过键) 最灵活，但代码可能复杂。JSON.stringify 作键有局限性 (KeyGen 性能影响大，无法处理循环引用，属性顺序敏感)。
Reduce + Map (深比较函数) 复杂对象按值去重，深层比较 O(n * m) O(n) 是 是 (通过比较) m 是对象比较的复杂度，性能开销最大，通常需要第三方库 (lodash.isEqual)。仅在极少数严格要求场景下使用。

6.3. 性能测试示例 (概念性)

为了直观地感受性能差异，我们通常会进行基准测试。以下是一个概念性的测试框架，展示了如何比较不同方法的性能。

// 简单的基准测试函数
function benchmark(name, func, data, iterations = 1000) {
    console.time(name);
    for (let i = 0; i < iterations; i++) {
        func(data);
    }
    console.timeEnd(name);
}

// 生成测试数据
function generateRandomArray(size, type = 'number', uniqueRatio = 0.5) {
    const arr = [];
    for (let i = 0; i < size; i++) {
        let value;
        if (type === 'number') {
            value = Math.floor(Math.random() * (size * uniqueRatio)); // 制造重复
        } else if (type === 'string') {
            value = 'str' + Math.floor(Math.random() * (size * uniqueRatio));
        } else if (type === 'object') {
            const id = Math.floor(Math.random() * (size * uniqueRatio));
            value = {id: id, value: 'obj' + id};
        }
        arr.push(value);
    }
    return arr;
}

// 测试数据
const smallNumbers = generateRandomArray(100);
const largeNumbers = generateRandomArray(10000);
const smallObjects = generateRandomArray(100, 'object');
const largeObjects = generateRandomArray(10000, 'object');

console.log("n--- Benchmarking Primitive (Numbers) Deduplication ---");
benchmark("indexOf (small)", deduplicateWithIndexOf, smallNumbers);
benchmark("indexOf (large)", deduplicateWithIndexOf, largeNumbers); // 预计非常慢

benchmark("Object Hash (small)", deduplicateWithObjectHash, smallNumbers);
benchmark("Object Hash (large)", deduplicateWithObjectHash, largeNumbers);

benchmark("Set (small)", deduplicateWithSet, smallNumbers);
benchmark("Set (large)", deduplicateWithSet, largeNumbers);

benchmark("Map (small)", deduplicateWithMap, smallNumbers);
benchmark("Map (large)", deduplicateWithMap, largeNumbers);

benchmark("Reduce + Set (small)", deduplicateWithReduceAndSet, smallNumbers);
benchmark("Reduce + Set (large)", deduplicateWithReduceAndSet, largeNumbers);

console.log("n--- Benchmarking Object Deduplication by ID ---");
benchmark("Map by ID (small)", (arr) => deduplicateWithMap(arr, item => item.id), smallObjects);
benchmark("Map by ID (large)", (arr) => deduplicateWithMap(arr, item => item.id), largeObjects);

benchmark("Reduce + Map by ID (small)", (arr) => deduplicateObjectsWithReduceAndMap(arr, 'id'), smallObjects);
benchmark("Reduce + Map by ID (large)", (arr) => deduplicateObjectsWithReduceAndMap(arr, 'id'), largeObjects);

console.log("n--- Benchmarking Object Deduplication by Content (JSON.stringify) ---");
// 注意 JSON.stringify 的性能开销
benchmark("Map by JSON.stringify (small)", (arr) => deduplicateWithMap(arr, item => JSON.stringify(item)), smallObjects);
benchmark("Map by JSON.stringify (large)", (arr) => deduplicateWithMap(arr, item => JSON.stringify(item)), largeObjects);

运行上述代码，你会清晰地看到 O(n^2) 方法（如 indexOf）在处理大型数组时与 O(n) 方法（如 Set 或 Map）之间的巨大性能鸿沟。同时，JSON.stringify 带来的额外开销也会在对象去重场景中显现出来。

7. 高级考量与最佳实践

在实际开发中，除了性能，我们还需要考虑代码的可读性、可维护性以及各种边缘情况。

7.1. 排序问题

  • Set 的迭代顺序：虽然规范没有强制要求，但现代JS引擎通常会保留 Set 元素的插入顺序。然而，如果你需要严格保证去重后的数组顺序与原始数组的第一次出现顺序一致，那么 Array.from(new Set(arr)) 或 [...new Set(arr)] 可能会有细微差别，而 reduce 结合 Set 或 Map 则能更好地控制顺序。
  • Map 的迭代顺序：Map 明确保证键值对的迭代顺序与其插入顺序一致。

7.2. 特殊值的处理

  • NaN：Set 和 Map 都将 NaN 视为唯一值，只保留一个。
  • null 和 undefined：它们也是唯一值，在 Set 和 Map 中会被正确处理。
  • 0 和 -0：Set 和 Map 将它们视为相同的值，只保留一个。

7.3. 循环引用对象

JSON.stringify() 无法处理包含循环引用的对象，会抛出 TypeError: Converting circular structure to JSON。如果你的数据可能存在循环引用，切勿使用 JSON.stringify 作为去重键。此时，你需要：

  • 避免去重：如果逻辑上不应去重循环引用对象。
  • 自定义序列化：实现一个能处理循环引用的序列化函数（非常复杂）。
  • 特定属性去重：如果循环引用对象有唯一ID，仍可按ID去重。

7.4. 性能与可读性的权衡

  • 小数组或原始类型：[...new Set(arr)] 是最推荐的方法，它简洁、高效且易于理解。
  • 对象数组按特定属性去重：reduce 结合 Map (deduplicateObjectsWithReduceAndMap) 是一个很好的平衡点，它明确地指定了去重依据，且保留了顺序。
  • 复杂对象按内容去重：
    • 如果对象结构简单、无循环引用且属性顺序不敏感，JSON.stringify 配合 Map 或 Set 可以作为快速解决方案。
    • 如果对象结构复杂、有循环引用、属性顺序敏感，或者需要深度比较，那么你需要一个自定义的深层比较函数。这通常会引入第三方库（如 Lodash 的 isEqual），但会带来显著的性能开销和代码复杂度。在大多数前端应用中，这种需求相对较少，通常可以通过设计更好的数据结构来规避。

7.5. 最终推荐

  1. 最通用且高效：对于原始类型的数组，或按对象引用去重，始终优先考虑：

    const uniqueArray = [...new Set(originalArray)];

    它简洁、性能卓越，且现代引擎通常保留了插入顺序。如果对顺序有严格要求，可以使用 reduce + Set。

  2. 对象按指定属性去重：当需要根据对象的某个唯一属性（如 id、code 等）去重时，推荐使用 reduce 结合 Map：

    function deduplicateById(arr, idProp) {
    const seen = new Map();
    return arr.reduce((acc, item) => {
        if (item && typeof item === 'object' && !seen.has(item[idProp])) {
            seen.set(item[idProp], true);
            acc.push(item);
        } else if (typeof item !== 'object' && !seen.has(item)) { // 处理非对象元素
            seen.set(item, true);
            acc.push(item);
        }
        return acc;
    }, []);
}

    这兼顾了性能、可读性，并保留了原始顺序。

  3. 复杂对象按内容去重：这通常是最困难的。

    • 如果 JSON.stringify 适用（无循环引用，属性顺序不敏感）： 
      function deduplicateByContent(arr) {
    const seen = new Map();
    return arr.reduce((acc, item) => {
        const key = (typeof item === 'object' && item !== null) ? JSON.stringify(item) : item;
        if (!seen.has(key)) {
            seen.set(key, true);
            acc.push(item);
        }
        return acc;
    }, []);
}
    • 如果 JSON.stringify 不适用，且必须深度比较：考虑引入像 Lodash isEqual 这样的工具，但要警惕其性能开销。自定义深比较函数通常会使代码变得复杂且容易出错。

8. 思考与展望

通过今天的探讨，我们看到了JavaScript数组去重方法的多样性，从简单到复杂，从传统到现代。每种方法都有其特定的适用场景、性能特点和优缺点。作为开发者，我们应该根据实际需求，综合考虑数据类型、数组大小、性能要求、代码可读性以及是否需要保留原始顺序等因素，明智地选择最合适的去重策略。

理解这些底层机制和权衡之道，将使我们能够编写出更健壮、更高效、更易维护的JavaScript代码。数组去重虽小，但其背后蕴含的编程思想和对数据结构的运用，正是我们不断提升技术能力的关键。

感谢大家的参与！希望今天的分享能为大家在未来的开发工作中提供有益的指导和启发。

发表回复

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