数组去重性能提升：Set和Object哈希表高效缘由探究

未分类 1天前程序员胖胖胖虎阿

7 0 0

数组去重性能优化：Set与Object哈希表高效之因探究

一、数组去重的基础认知

数组去重指的是从一个数组中剔除重复的元素，只保留唯一值的过程。例如，给定数组[1, 2, 2, 3, 4, 4]，去重后结果为[1, 2, 3, 4]。在日常开发里，数组去重是常见需求，不管是处理用户输入、分析数据集还是实现特定算法，它都能提升代码效率与可读性。然而，随着数据规模增大，不同去重方法在性能上的差别会愈发明显。本文将深入探究各类数组去重方法的性能表现，并着重分析如何利用Set和哈希表实现高效的去重操作。

二、常见的数组去重方法

本文聚焦数组去重的性能，对具体去重方法不做详细阐述，若有需求可参考相关合集，其中涵盖了数值类去重、引用类去重（去除完全重复的对象元素、去除部分重复的对象元素）、特殊情况（对象键值对顺序不同但内容相同）、混合数组去重等五大类场景的多种去重方法，适用于各类场景：

全网最全情景，深入浅出解析JavaScript数组去重：数值与引用类型的全面攻略-
CSDN博客文章浏览阅读3.3k次，点赞171次，收藏97次。在日常开发中，数组去重是一个不可避免的话题。不管是简单的数值数组去重，还是复杂的引用类型数组去重，掌握多种方法可以帮助开发者高效、优雅地解决实际问题。在这篇博客中，我们将从基础到进阶，结合大量代码案例，系统介绍数组去重的各种技巧。_f
(!txt.includes(num)) { txt.push(num) 什么意思https://opengms-
watermelo.blog.csdn.net/article/details/143950308

常见数组去重方法如下：

方法	适用场景	优点	缺点
Set	基础类型数组去重	简洁高效	无法处理引用类型
遍历 + includes	基础类型数组去重	易理解	性能较低
filter() + indexOf()	基础类型数组去重	通用	性能较低
reduce()	复杂逻辑处理或混合类型数组去重	灵活，可扩展逻辑	写法稍复杂
JSON.stringify+set	引用类型数组去重	简洁	无法处理嵌套或无序字段的对象
Map	引用类型数组去重	性能较优，适合复杂数据结构	写法稍繁琐

有人做过测试：处理含百万个数字且30%元素重复的数组时，常规方法去重执行时间超30秒，而使用Set和Object哈希表用时约100毫秒，性能差距显著。

下面分享生成大量元素且重复元素比例可控的方法，这是从其他资料获取的：

function generateTestArray(size) {
  const array = []; // 初始化空数组
  for (let i = 0; i < size; i++) {
    if (Math.random() > 0.7) { // 30%概率生成重复元素
      array.push(array[Math.floor(Math.random() * array.length)] || 0);
    } else { // 70%概率生成新随机数
      array.push(Math.floor(Math.random() * size * 10));
    }
  }
  return array;
}

拓展：该方法的系统误差

生成数范围是0 - 10size。比如传入5，生成0 - 50间整数，传入1000生成0 - 10000间整数，其中300个确定重复。但剩下700个整数也可能重复，经计算，重复期望约24.465个，实际重复率约33.5%。若要降低系统误差，可扩大size后的乘数。

拓展：排序后去重

这种去重方法时间复杂度为O(nlogn)，额外开销源于排序操作，仅适用于基础数据类型去重，且会改变原始数组顺序，在部分场景受限。

常规方法如遍历+includes、filter()+indexOf()、reduce()本质是双循环，复杂度为O(n²)，而Set和Object哈希表去重高效，接下来探究其高效原因。

三、Set与Object哈希表综合复杂度为O(n)的奥秘

1、数据结构区别

Set是ES6引入的集合数据结构，用于存储唯一值，底层基于哈希表，插入和查找时间复杂度接近O(1)。Object哈希表本质是利用Object键的映射创建哈希表，不过无法兼容引用类型（可通过JSON.stringify()处理）。V8引擎中，Set采用哈希表与红黑树结合实现，测试显示Set效率略优于Object哈希表。

2、Set去重的底层原理

Set的高效源于底层哈希表实现，关键步骤如下：
1. 计算哈希值：通过哈希函数将值映射为整数索引。
2. 定位存储位置：依据哈希值找到对应存储位置。
3. 处理冲突：若发生哈希冲突，采用链地址法或开放地址法解决。
4. 插入或跳过：若该位置已有相同值则跳过，否则插入。此机制使Set能快速判断值是否存在，实现高效去重。

3、Set去重的鲁棒性

看一个特殊例子：

function deduplicateWeirdValues(array) {
  return [...new Set(array)];
}

const weirdArray = [0, -0, NaN, NaN, undefined, null, false, 0, "0"];
console.log(deduplicateWeirdValues(weirdArray));
// 输出: [0, NaN, undefined, null, false, "0"]

在此去重案例中，NaN !== NaN，但Set只保留一个NaN，且区分了0和"0"，这是常规方法无法做到的。