JavaScript 数据结构之集合创建(2)

前言

上一篇JavaScript 数据结构之集合创建(1)我们介绍了什么是集合，并且手动实现了一个集合的类。简单总结，集合就是一组元素唯一，并且没有顺序的数据集，关键是元素唯一。

ES6 提供了原生的集合支持，就是新增的 Set 数据类型。其实在上篇我们几乎已经实现了 Set 的所有功能，如果还不了解集合，请看上篇内容

但是我们也说到，Set 的基本功能中不包含数学运算如 交集，并集，差集，事实上这也是集合的一部分。本篇我们就要介绍这类集合的运算。

一、集合运算

集合在计算机世界中主要的应用之一就是数据库。比如在一个关系型数据库当中，我们常用的查询，基本都是对一个或多个数据集合进行筛选，合并，过滤等运算。

比如你写一条 SQL 语句，它可能是要获取表中的所有数据，也可能是根据条件获取一部分数据，还有可能是关联查询，要一次性获取多个表的数据。

根据不同的需求来决定集合如何处理，这在 SQL 中叫做联接。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;
}

如上的实现方式，首先实例化一个新集合，然后分别将两个集合的全部元素加入到新集合。因为集合在添加元素时会做重复校验，所以全部添加后新集合包含了所有元素，且不重复。

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 提供了原生支持，但是对于我们学习者来说，手动实现一次更有助于了解原理。

频道导航