7. 集合

集合：是一种不允许值重复的顺序数据结构

7.1 构建数据集合

集合是由一组无序且唯一（即不能重复）的项组成的。该数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。

在深入学习集合的计算机科学实现之前，我们先看看它的数学概念。在数学中，集合是一组不同对象的集。

比如说，一个由大于或等于 0 的整数组成的自然数集合：N = {0, 1, 2, 3, 4, 5, 6, …}。集合中的对象列表用花括号（{}）包围。

还有一个概念叫空集。空集就是不包含任何元素的集合。比如 24 和 29 之间的素数集合，由于 24 和 29 之间没有素数（除了 1 和自身，没有其他正因数的、大于 1 的自然数），这个集合就是空集。空集用{ }表示。

你也可以把集合想象成一个既没有重复元素，也没有顺序概念的数组。

在数学中，集合也有并集、交集、差集等基本运算。本章也会介绍这些运算。

7.2 创建集合类

用下面的 Set 类以及它的构造函数声明作为开始。

class Set {
  constructor() {
    this.items = {};
  }
}

有一个非常重要的细节是，我们使用对象而不是数组来表示集合（items）。不过，也可以用数组实现。此处用对象来实现，和我们在第 4 章与第 5 章中学习到的对象实现方式很相似。同样地，JavaScript 的对象不允许一个键指向两个不同的属性，也保证了集合里的元素都是唯一的。

接下来，需要声明一些集合可用的方法（我们会尝试模拟与 ECMAScript 2015 实现相同的 Set 类）。

• add(element)：向集合添加一个新元素。
• delete(element)：从集合移除一个元素。
• has(element)：如果元素在集合中，返回 true，否则返回 false。
• clear()：移除集合中的所有元素。
• size()：返回集合所包含元素的数量。它与数组的 length 属性类似。
• values()：返回一个包含集合中所有值（元素）的数组。

7.2.1 has(element)方法

首先要实现的是 has(element)方法，因为它会被 add、delete 等其他方法调用。它用来检验某个元素是否存在于集合中，下面看看它的实现。

    has(element){
      return element in items;
    };

既然我们使用对象来存储集合的元素，就可以用 JavaScript 的 in 运算符来验证给定元素是否是 items 对象的属性。

然而这个方法还有更好的实现方式，如下所示。

    has(element) {
      return Object.prototype.hasOwnProperty.call(this.items, element);
    }

Object 原型有 hasOwnProperty 方法。该方法返回一个表明对象是否具有特定属性的布尔值。in 运算符则返回表示对象在原型链上是否有特定属性的布尔值。

我们也可以在代码中使用 this.items.hasOwnProperty(element)。但是，如果这样的话，代码检查工具如 ESLint 会抛出一个错误。错误的原因为不是所有的对象都继承了 Object.prototype，甚至继承了 Object.prototype 的对象上的 hasOwnProperty 方法也有可能被覆盖，导致代码不能正常工作。要避免出现任何问题，使用 Object.prototype.hasOwnProperty.call 是更安全的做法。

7.2.2 add 方法

接下来要实现 add 方法。

    add(element) {
      if (!this.has(element)) {
        this.items[element] = element; // {1}
        return true;
      }
      return false;
    }

对于给定的 element，可以检查它是否存在于集合中。如果不存在，就把 element 添加到集合中（行{1}），返回 true，表示添加了该元素。如果集合中已经有了这个元素，就返回 false，表示没有添加它。

添加一个 element 的时候，把它同时作为键和值保存，因为这样有利于查找该元素。

7.2.3 delete 和 clear 方法

下面要实现 delete 方法。

    delete(element) {
      if (this.has(element)) {
        delete this.items[element]; // {1}
        return true;
      }
      return false;
    }

在 delete 方法中，我们会验证给定的 element 是否存在于集合中。如果存在，就从集合中移除 element（行{1}），返回 true，表示元素被移除；否则返回 false。

既然我们用对象来存储集合的 items 对象，就可以简单地使用 delete 运算符从 items 对象中移除属性（行{1}）。

使用 Set 类的示例代码如下。

const set = new Set();
set.add(1);
set.add(2);

出于好奇，如果在执行以上代码之后，在控制台（console.log）输出 this.items 变量，谷歌 Chrome 就会输出如下内容。

Object {1: 1, 2: 2}

可以看到，这是一个有两个属性的对象。属性名就是添加到集合的值，同时它也是属性值。

如果想移除集合中的所有值，可以用 clear 方法。

    clear() {
      this.items = {}; // {2}
    }

要重置 items 对象，需要做的只是把一个空对象重新赋值给它（行{2}）。我们也可以迭代集合，用 delete 方法依次移除所有的值，不过既然有更简单的方法，这样做就太麻烦了。

7.2.4 size 方法

下一个要实现的是 size 方法（返回集合中有多少元素）。该方法有三种实现方式。

第一种方式是使用一个 length 变量，每当使用 add 或 delete 方法时就控制它，就像在之前的章节中使用 LinkedList、Stack 和 Queue 类一样。

第二种方式是使用 JavaScript 中 Object 类的一个内置方法（ECMAScript 2015 以上版本）。

    size() {
      return Object.keys(this.items).length; // {1}
    };

JavaScript 的 Object 类有一个 keys 方法，它返回一个包含给定对象所有属性的数组。在这种情况下，可以使用这个数组的 length 属性（行{1}）来返回 items 对象的属性个数。以上代码只能在现代浏览器（比如 IE9 以上版本、Firefox 4 以上版本、Chrome 5 以上版本、Opera 12 以上版本、Safari 5 以上版本等）中运行。

第三种方式是手动提取 items 对象的每一个属性，记录属性的个数并返回这个数。该方法可以在任何浏览器上运行，和之前的代码是等价的。

    sizeLegacy() {
      let count = 0;
      for(let key in this.items) { // {2}
        if(this.items.hasOwnProperty(key)) { // {3}
            count++;   // {4}
      }
      return count;
    };

迭代 items 对象的所有属性（行{2}），检查它们是否是对象自身的属性（避免重复计数——行{3}）。如果是，就递增 count 变量的值（行{4}），最后在方法结束时返回这个数。

我们不能简单地使用 for-in 语句迭代 items 对象的属性，并递增 count 变量的值，还需要使用 has 方法（以验证 items 对象具有该属性），因为对象的原型包含了额外的属性（属性既有继承自 JavaScript 的 Object 类的，也有属于对象自身、未用于数据结构的）。

7.2.5 values 方法

要实现 values 方法，我们同样可以使用 Object 类内置的 values 方法。

    values() {
      return Object.values(this.items);
    }

Object.values()方法返回了一个包含给定对象所有属性值的数组。它是在 ECMAScript 2017 中被添加进来的，目前只在现代浏览器中可用。

如果想让代码在任何浏览器中都能执行，可以用与之前代码等价的下面这段代码。

    valuesLegacy() {
      let values = [];
      for(let key in this.items) { // {1}
        if(this.items.hasOwnProperty(key)) {
          values.push(key); // {2}
        }
      }
      return values;
    };

首先迭代 items 对象的所有属性（行{1}），把它们添加到一个数组中（行{2}），并返回这个数组。该方法类似于我们开发的 sizeLegacy 方法，但这里不是计算属性个数，而是在一个数组里做加法。

7.2.6 使用 Set 类

现在数据结构已经完成了，看看如何使用它吧。试着执行一些命令，测试我们的 Set 类。

const set = new Set();
set.add(1);

console.log(set.values()); // 输出[1]
console.log(set.has(1)); // 输出true
console.log(set.size()); // 输出1

set.add(2);
console.log(set.values()); // 输出[1, 2]
console.log(set.has(2)); // 输出true
console.log(set.size()); // 输出2

set.delete(1);
console.log(set.values()); // 输出[2]

set.delete(2);
console.log(set.values()); // 输出[]

现在我们有了一个和 ECMAScript 2015 中非常类似的 Set 类实现。

7.3 集合运算

集合是数学中基础的概念，在计算机领域也非常重要。它在计算机科学中的主要应用之一是数据库，而数据库是大多数应用程序的根基。集合被用于查询的设计和处理。当我们创建一条从关系型数据库（Oracle、Microsoft SQL Server、MySQL 等）中获取一个数据集合的查询语句时，使用的就是集合运算，并且数据库也会返回一个数据集合。当我们创建一条 SQL 查询命令时，可以指定是从表中获取全部数据还是获取其中的子集；也可以获取两张表共有的数据、只存在于一张表中的数据（不存在于另一张表中），或是存在于两张表内的数据（通过其他运算）。这些 SQL 领域的运算叫作联接，而 SQL 联接的基础就是集合运算。

想学习更多有关 SQL 联接运算的知识，请阅读http://www.sql-join.com/sql-join-types。

我们可以对集合进行如下运算。

• 并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合。
• 交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合。
• 差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合。
• 子集：验证一个给定集合是否是另一集合的子集。

7.3.1 并集

本节介绍并集的数学概念。集合 A 和集合 B 的并集表示如下。

A∪B

该集合定义如下。

A∪B = {x | x ∈ A ∨ x ∈ B}

意思是 x（元素）存在于 A 中，或 x 存在于 B 中。下图展示了并集运算。

现在来实现 Set 类的 union 方法。

    union(otherSet) {
      const unionSet = new Set(); // {1}
      this.values().forEach(value => unionSet.add(value)); // {2}
      otherSet.values().forEach(value => unionSet.add(value)); // {3}
      return unionSet;
    }

首先需要创建一个新的集合，代表两个集合的并集（行{1}）。接下来，获取第一个集合（当前的 Set 类实例）所有的值（values），迭代并全部添加到代表并集的集合中（行{2}）。然后对第二个集合做同样的事（行{3}）。最后返回结果。

既然我们创建的 values 方法返回一个数组，可以使用 Array 类的 forEach 方法来迭代数组的所有元素。需要提醒的是 forEach 方法是 ECMAScript 2015 中引入的。forEach 方法接收一个表示数组每个元素值的参数（value），同时有一个执行可编辑逻辑的回调函数。在之前的代码中，我们也使用了箭头函数（=>）来代替显式声明 function(value) { unionSet.add(value) }。使用我们在第 2 章学到的 ES2015 的功能会使代码看起来更现代、更简明。

也可以把 union 方法写成下面这样，不使用 forEach 方法和箭头函数，但是只要可以，我们就应该试着使用 ES2015 以上版本的功能。

    union(otherSet) {
      const unionSet = new Set(); // {1}

      let values = this.values(); // {2}
      for (let i = 0; i < values.length; i++){
          unionSet.add(values[i]);
      }

      values = otherSet.values(); // {3}
        for (let i = 0; i < values.length; i++){
          unionSet.add(values[i]);
      }

      return unionSet;
    };
    // 测试一下上面的代码。
    const setA = new Set();
    setA.add(1);
    setA.add(2);
    setA.add(3);

    const setB = new Set();
    setB.add(3);
    setB.add(4);
    setB.add(5);
    setB.add(6);

    const unionAB = setA.union(setB);
    console.log(unionAB.values());

输出为[1, 2, 3, 4, 5, 6]。注意元素 3 同时存在于 setA 和 setB 中，它在结果集合中只出现一次。

重要的是要注意，本章实现的 union、intersection 和 difference 方法不会修改当前的 Set 类实例或是作为参数传入的 otherSet。没有副作用的方法和函数被称为纯函数。纯函数不会修改当前的实例或参数，只会生成一个新的结果。这在函数式编程中是非常重要的概念，本书后面的内容中会介绍。

7.3.2 交集

本节介绍交集的数学概念。集合 A 和集合 B 的交集表示如下。

A∩B

该集合定义如下。

A∩B = {x | x ∈ A ∧ x ∈ B}

意思是 x（元素）存在于 A 中，且 x 存在于 B 中。下图展示了交集运算。

现在来实现 Set 类的 intersection 方法。

    intersection(otherSet) {
      const intersectionSet = new Set(); // {1}

      const values = this.values();
      for (let i = 0; i < values.length; i++) { // {2}
        if (otherSet.has(values[i])) { // {3}
          intersectionSet.add(values[i]); // {4}
        }
      }
      return intersectionSet;
    }

intersection 方法需要找到当前 Set 实例中所有也存在于给定 Set 实例（otherSet）中的元素。首先创建一个新的 Set 实例（行{1}），这样就能用它返回共有的元素。接下来，迭代当前 Set 实例所有的值（行{2}），验证它们是否也存在于 otherSet 实例之中（行{3}）。可以用本章前面实现的 has 方法来验证元素是否存在于 Set 实例中。然后，如果这个值也存在于另一个 Set 实例中，就将其添加到创建的 intersectionSet 变量中（行{4}），最后返回它。

我们做些测试。

const setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

const setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);

const intersectionAB = setA.intersection(setB);
console.log(intersectionAB.values());

输出为[2, 3]，因为 2 和 3 同时存在于两个集合中。

改进交集方法

假设我们有下面两个集合：

• setA 的值为[1, 2, 3, 4, 5, 6, 7]
• setB 的值为[4, 6]

使用我们创建的 intersection 方法，需要迭代七次 setA 的值，也就是 setA 中元素的个数，然后还要将这七个值和 setB 中的两个值进行比较。如果我们只需要迭代两次 setB 就好了，更少的迭代次数意味着更少的过程消耗。那么就来优化代码，使得迭代元素的次数更少吧，如下所示。

    intersection(otherSet) {
      const intersectionSet = new Set(); // {1}
      const values = this.values(); // {2}
      const otherValues = otherSet.values(); // {3}
      let biggerSet = values; // {4}
      let smallerSet = otherValues; // {5}
      if (otherValues.length - values.length > 0) { // {6}
        biggerSet = otherValues;
        smallerSet = values;
      }
      smallerSet.forEach(value => { // {7}
        if (biggerSet.includes(value)) {
          intersectionSet.add(value);
        }
      });
      return intersectionSet;
    }

首先创建一个新的集合来存放 intersection 方法的返回结果（行{1}）。同样要获取当前集合实例中的值（行{2}）并将其作为参数传入 intersection 方法（行{3}）。然后，假设当前的集合元素较多（行{4}），另一个集合元素较少（行{5}）。比较两个集合的元素个数（行{6}），如果另一个集合元素个数多于当前集合的话，我们就交换 biggerSet 和 smallerSet 的值。最后，迭代较小集合（行{7}）来计算出两个集合的共有元素并返回。

7.3.3 差集

本节介绍差集的数学概念。集合 A 和集合 B 的差集表示为:

A - B

定义如下。

A-B= {x|x∈A∧x∉B}

意思是 x（元素）存在于 A 中，且 x 不存在于 B 中。下图展示了集合 A 和集合 B 的差集运算。

现在来实现 Set 类的 difference 方法。

    difference(otherSet) {
      const differenceSet = new Set(); // {1}
      this.values().forEach(value => { // {2}
        if (! otherSet.has(value)) { // {3}
          differenceSet.add(value); // {4}
        }
      });
      return differenceSet;
    }

intersection 方法会得到所有同时存在于两个集合中的元素。而 difference 方法会得到所有存在于集合 A 但不存在于集合 B 的元素。首先要创建结果集合（行{1}），因为我们不想修改原来的集合。然后，要迭代集合中的所有值（行{2}）。我们会检查当前值（元素）是否存在于给定集合中（行{3}），如果不存在于 otherSet 中，则将此值加入结果集合中。

（用跟 intersection 部分相同的集合）做些测试。

const setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

const setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);
const differenceAB = setA.difference(setB);
console.log(differenceAB.values());

输出为[1]，因为 1 是唯一一个仅存在于 setA 的元素。如果我们执行 setB.difference (setA)，会得到[4]作为输出结果，因为 4 是只存在于 setB 中的元素。

我们不能像优化 intersection 方法一样优化 difference 方法，因为 setA 与 setB 之间的差集可能和 setB 与 setA 之间的差集不同。

7.3.4 子集

要介绍的最后一个集合运算是子集。其数学概念的一个例子是集合 A 是集合 B 的子集（或集合 B 包含集合 A），表示如下。

A ⊆ B

该集合定义如下。

{x | ∀x ∈ A ⇒ x ∈ B}

意思是集合 A 中的每一个 x（元素），也需要存在于集合 B 中。下图展示了集合 A 是集合 B 的子集。

现在来实现 Set 类的 isSubsetOf 方法。

    isSubsetOf(otherSet) {
      if (this.size() > otherSet.size()) { // {1}
        return false;
      }
      let isSubset = true; // {2}
      this.values().every(value => { // {3}
        if (! otherSet.has(value)) { // {4}
          isSubset = false; // {5}
          return false;
        }
        return true; // {6}
      });
      return isSubset; // {7}
    }

首先需要验证的是当前 Set 实例的大小。如果当前实例中的元素比 otherSet 实例更多，它就不是一个子集（行{1}）。子集的元素个数需要小于或等于要比较的集合。

接下来，假定当前实例是给定集合的子集（行{2}）。我们要迭代当前集合的所有元素（行{3}），验证这些元素也存在于 otherSet 中（行{4}）。如果有任何元素不存在于 otherSet 中，就意味着它不是一个子集，返回 false（行{5}）。如果所有元素都存在于 otherSet 中，行{5}就不会被执行，那么就返回 true（行{6}）, isSubset 标识不会改变（行{7}）。

在 isSubsetOf 方法中，我们不会像在并集、交集和差集中一样使用 forEach 方法。我们会用 every 方法代替，它也是 ES2015 中的数组方法。第 3 章我们学习了 forEach 方法会在数组中的每个值上调用。在子集逻辑中，当我们发现一个值不存在于 otherSet 中时，可以停止迭代值，表示这不是一个子集。只要回调函数返回 true, every 方法就会被调用（行{6}）。如果回调函数返回 false，循环会停止，这就是为什么我们要在行{5}改变 isSubset 标识的值。

检验一下上面的代码效果如何。

const setA = new Set();
setA.add(1);
setA.add(2);

const setB = new Set();
setB.add(1);
setB.add(2);
setB.add(3);

const setC = new Set();
setC.add(2);
setC.add(3);
setC.add(4);

console.log(setA.isSubsetOf(setB));
console.log(setA.isSubsetOf(setC));

我们有三个集合：setA 是 setB 的子集（因此输出为 true），然而 setA 不是 setC 的子集（setC 只包含了 setA 中的 2，而不包含 1），因此输出为 false。

7.4 ECMAScript 2015——Set 类

ECMAScript 2015 新增了 Set 类作为 JavaScript API 的一部分。我们可以基于 ES2015 的 Set 开发我们的 Set 类。

https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Set。

我们先看看原生的 Set 类怎么用。还是用我们原来测试 Set 类的例子：

const set = new Set();
set.add(1);
console.log(set.values()); // 输出@Iterator
console.log(set.has(1)); // 输出true
console.log(set.size); // 输出1

和原来的 Set 不同，ES2015 的 Set 的 values 方法返回 Iterator（第 3 章提到过），而不是值构成的数组。另一个区别是，我们实现的 size 方法返回 set 中存储的值的个数，而 ES2015 的 Set 则有一个 size 属性。

我们可以用 delete 方法删除 set 中的元素。

set.delete(1);

clear 方法会重置 set 数据结构，这跟我们实现的功能一样。

ES2015 Set 类的运算

我们的 Set 类实现了并集、交集、差集、子集等数学运算，然而 ES2015 原生的 Set 并没有这些功能。不过，有需要的话，我们也可以模拟。

我们的例子会用到下面两个集合。

const setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

const setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);

1．模拟并集运算

我们可以创建一个函数，来返回包含 setA 和 setB 中所有的元素的新集合。迭代这两个集合，把所有元素都添加到并集的集合中。代码如下。

const union = (setA, setB) => {
  const unionAb = new Set();
  setA.forEach((value) => unionAb.add(value));
  setB.forEach((value) => unionAb.add(value));
  return unionAb;
};
console.log(union(setA, setB)); // 输出[1, 2, 3, 4]

2．模拟交集运算

模拟交集运算需要创建一个辅助函数，来生成包含 setA 和 setB 共有元素的新集合。代码如下。

const intersection = (setA, setB) => {
  const intersectionSet = new Set();
  setA.forEach((value) => {
    if (setB.has(value)) {
      intersectionSet.add(value);
    }
  });
  return intersectionSet;
};
console.log(intersection(setA, setB)); // 输出[2, 3]

这和 intersection 函数的效果完全一样，但是上面的代码没有被优化（我们开发的是经过优化的版本）。

3．模拟差集运算

交集运算创建的集合包含 setA 和 setB 都有的元素，差集运算创建的集合则包含 setA 有而 setB 没有的元素。看下面的代码。

const difference = (setA, setB) => {
  const differenceSet = new Set();
  setA.forEach((value) => {
    if (!setB.has(value)) {
      // {1}
      differenceSet.add(value);
    }
  });
  return differenceSet;
};
console.log(difference(setA, setB));

intersection 函数和 difference 函数除函数名外只有行{1}不同，因为差集中只添加 setA 有而 setB 没有的元素。

4．使用扩展运算符

有一种计算并集、交集和差集的简便方法，就是使用扩展运算符，它包含在 ES2015 中，我们在第 2 章中学到过。

整个过程包含三个步骤：

(1) 将集合转化为数组；

(2) 执行需要的运算；

(3) 将结果转化回集合。

我们来看看怎样用扩展运算符进行并集的计算。

console.log(new Set([...setA, ...setB]));

ES2015 的 Set 类支持向构造函数传入一个数组来初始化集合的运算，那么我们对 setA 使用扩展运算符（...setA）会将它的值转化为一个数组（展开它的值），然后对 setB 也这样做。

由于 setA 的值为[1, 2, 3], setB 的值为[2, 3, 4]，上述代码和 new Set([1, 2, 3, 2, 3, 4])是一样的，但集合中每种值只会有一个。

现在，我们来看看怎样用扩展运算符进行交集的运算。

console.log(new Set([...setA].filter((x) => setB.has(x))));

上面的代码同样将 setA 转化为了一个数组，并使用了 filter 方法，它会返回一个新数组，包含能通过回调函数检测的值——在本示例中验证了元素是否也存在于 setB 中。返回的数组会用来初始化结果集合。

最后，我们来看看怎样用扩展运算符完成差集的运算。

console.log(new Set([...setA].filter((x) => !setB.has(x))));

代码和求交集的运算很相似，不同之处在于我们需要的是不存在于 setB 中的元素。你可以使用你喜欢的方法来执行原生 ES2015 的 Set 类的集合运算！

7.5 多重集或袋

我们已经学习过，集合数据结构不允许存在重复的元素。但是，在数学中，有一个叫作多重集的概念，它允许我们向集合中插入之前已经添加过的元素。多重集（或袋）在计算集合中元素的出现次数时很有用。它也在数据库系统中得到了广泛运用。

我们不会在本书中解释袋数据结构。不过，你可以下载本书的代码包来查看源代码，或访问https://github.com/loiane/javascript-datastructures-algorithms。