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

目录

• 前言
• 一、集合运算
• 1.并集
• 2.交集
• 3.差集
• 4.子集
• 二、使用集合运算
• 三、总结

前言

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

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