JS Set 集合运算：手动实现并集、交集、差集和子集方法

前言

在上一篇文章《JavaScript 数据结构之集合创建(1)》中，我们探讨了集合的基本概念，并手动构建了一个集合类。简而言之，集合是一种元素唯一且无序的数据集，其核心特征在于元素的唯一性。

ES6 引入了原生的数据类型，即 Set。回顾前文，我们实际上已经实现了 Set 的大部分基础功能。若对集合概念尚不熟悉，建议回顾之前的内容。

然而，前文提到的 Set 基础功能并未涵盖数学运算，如交集、并集和差集。尽管这些运算在数学中属于集合的一部分，但在基础 Set 中并不直接提供。本文将重点介绍如何扩展实现这些集合运算。

一、集合运算

集合在计算机科学中的主要应用之一是数据库领域。在关系型数据库中，常见的查询操作本质上是对一个或多个数据集合进行筛选、合并或过滤等运算。

例如，编写 SQL 语句时，你可能需要获取表中的所有数据，根据特定条件筛选部分数据，或者通过关联查询一次性获取多个表的数据。

根据具体需求决定集合的处理方式，在 SQL 中这被称为联接（Join）。SQL 联接的基础正是集合运算。

我们将实现以下四种集合运算：

并集：接收两个集合，返回包含两者所有元素的新集合
交集：接收两个集合，返回包含两者共有元素的新集合
差集：接收两个集合，返回仅存在于第一个集合而不存在于第二个集合的元素新集合
子集：验证一个集合是否为另一个集合的子集（即部分包含关系）

接下来我们将逐一展示这些运算的具体实现方式。

1.并集

并集是指包含两个集合中所有元素但不重复的集合。

实现起来相对直观，我们在现有的 Set 类基础上添加一个 union 方法。

union(otherSet) {
  let unionSet = new Set()
  this.values().forEach(value=> unionSet.add(value))
  otherSet.values().forEach(value=> unionSet.add(value))
  return unionSet;
}

上述实现逻辑首先实例化一个新的集合，然后分别将两个集合的所有元素添加到新集合中。由于 Set 在添加元素时会自动进行重复性校验，因此最终的新集合将包含所有元素且无重复。

2.交集

交集是由两个集合共有的元素组成的新集合，该集合必然是原两个集合的子集。

我们来实现 intersection 方法：

intersection(otherSet) {
  let inters = new Set()
  let values = this.values()
  for(let i = 0; i < values.length; i++) {
    if(otherSet.has(values[i])) {
      inters.add(values[i])
    }
  }
  return inters;
}

该实现方式与并集类似，首先定义一个新集合。区别在于，在遍历一个集合的元素时，判断该元素是否存在于另一个集合中。如果存在，则将其添加到新集合，从而形成交集。

改进交集

功能实现后，我们考虑另一种情况。假设两个集合如下：

集合 A：[1, 2, 3, 4, 5, 6, 7]
集合 B：[4, 7]

若按上述方式，我们需要循环七次才能得出交集。是否存在一种方法，通过遍历长度更小的集合来实现相同功能呢？

答案是肯定的。假设我们遍历集合 B，只需循环两次。具体改进方案如下：

intersection(otherSet) {
  let inters = new Set();
  let bigvals = this.values()
  let lessvals = otherSet.values();
  if(bigvals.length < lessvals.length) {
    bigvals = otherSet.values();
    lessvals =  this.values()
  }
  for(let i = 0; i < lessvals.length; i++) {
    if(bigvals.includes(lessvals[i])) {
      inters.add(lessvals[i])
    }
  }
  return inters;
}

这种优化方式首先判断哪个集合的长度更短，然后遍历较短的集合，并检查其元素是否存在于另一个集合中。这样可以避免不必要的循环，提高执行效率。

3.差集

差集是指元素存在于集合 A 中，但不存在于集合 B 中的集合，即计算 A - B 的部分。

我们来实现 Set 类的 different 方法：

different(otherSet) {
  let diffSet = new Set();
  this.values().forEach(value=> {
    if(!otherSet.has(value)) {
      diffSet.add(value)
    }
  })
  return diffSet;
}

从代码可以看出，差集的实现逻辑与交集正好相反。

4.子集

在数学概念中，如果集合 A 包含于集合 B，即集合 A 中的所有元素在集合 B 中都存在，则称集合 A 为集合 B 的子集。

从程序角度来看，如果集合 A 是从集合 B 中过滤出来的一部分，那么集合 A 就是一个子集。

我们来实现子集的 isSubsetOf 方法：

isSubsetOf(otherSet) {
  let isSubset = true
  let values = otherSet.values()
  for(let i = 0; i < values.length; i++) {
    if(!this.has(values[i])) {
      isSubset = false; break;
    }
  }
  return isSubset;
}

该方法用于检测参数集合中的每个元素是否都存在于实例集合中。如果存在任何一个元素不存在，则说明参数集合不是子集，此时终止循环并返回结果。

其实还有更简洁的实现方法：

isSubsetOf(otherSet) {
  return otherSet.values().every(value=> this.has(value))
}

利用 every 方法可以判断每个元素是否符合条件。如果所有元素都符合条件，则返回 true，否则返回 false。

二、使用集合运算

完成了集合基本运算的实现后，现在我们来实际测试一下：

let setA = new Set()
setA.add('北京')
setA.add('上海')
setA.add('广州')

let setB = new Set()
setB.add('北京')
setB.add('南京')
setB.add('武汉')

首先创建两个集合，然后利用它们测试基本的运算功能：

let sets = setA.union(setB);
console.log(sets.values()); // ['北京', '上海', '广州', '南京', '武汉']

let inters = setA.intersection(setB);
console.log(inters.values()); // ['北京']

let diffs = setA.different(setB);
console.log(diffs.values()); // ['上海', '广州']

最后再测试子集判断功能：

let issub = setA.isSubsetOf(setB);
console.log(issub); // false

let setC = new Set();
setC.add("上海");
issub = setA.isSubsetOf(setC);
console.log(issub); // true

测试通过，完美实现！

三、总结

通过这两篇文章，我们介绍了集合的相关知识。虽然 ES6 提供了原生的 Set 支持，但对于学习者而言，手动实现一次有助于深入理解其内部原理。

到此这篇关于 JavaScript 数据结构之集合创建(2)的文章就介绍到这了，更多相关 JavaScript 集合内容请搜索本站以前的文章或继续浏览下面的相关文章，希望大家以后多多支持本站！

JavaScript 集合运算详解：并集、交集、差集与子集实现

前言