集合

1. 构建数据集合

• 集合是由一组无序且唯一的（不能重复）的项组成。
• 可以把集合想象成一个既没有重复元素，也没有顺序概念的数组。

2. 创建集合类

Set 类：

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

此处用对象来存储数据，对象不允许一个键指向两个不同的属性，保证了集合元素的唯一性。

集合方法：

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

2.1 has 方法

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

说明

• 这里使用 hasOwnProperty() 比使用 in 操作符更好，因为 in 还会检查原型链上的属性。
• 使用 Object.prototype.hasOwnProperty.call() 的方式比 this.items.hasOwnProperty() 更安全，因为不是所有对象都继承了 Object.prototype，或者 hasOwnProperty() 方法可能被覆盖。

2.2 add 方法

先检查是否存在，不存在就添加并返回 true，否则返回 false。

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

2.3 delete 和 clear 方法

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

  clear() {
    this.items = {}
  }
}

2.4 size 方法

class Set {
  size() {
    // ES2015以上才有
    return Object.keys(this.items).length;
  }

  // 兼容性更强的代码
  sizeLegacy() {
    let count = 0;
    for(let key in this.items){
      if(this.has(key)) {
        count++;
      }
    }
    return count;
  }
}

2.5 values 方法

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

  // 兼容性更强
  valuesLegacy() {
    let values = []
    for(let key in this.items){
      if(this.has(key)) {
        values.push(this.items[key])
      }
    }
    return values;
  }
}

3. 集合运算

可以对集合进行如下运算：

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

3.1 并集

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

提示

没有副作用的方法和函数被称为纯函数。

3.2 交集

首先判断两个集合的大小，遍历更小的集合的元素，将另一集合中也存在的元素添加到结果集并返回：

class Set {
  intersection(otherSet) {
    const intersectionSet = new Set();

    let smallSet, bigSet;
    if(this.size() > otherSet.size()) {
      smallSet = otherSet;
      bigSet = this;
    } else {
      smallSet = this;
      bigSet = otherSet;
    }

    const values = smallSet.values();
    for(let i = 0; i < values.length; i++) {
      if(bigSet.has(values[i])) {
        intersectionSet.add(values[i])
      }
    }
    return intersectionSet;
  }
}

3.3 差集

class Set {
  difference(otherSet) {
    const differenceSet = new Set();
    this.values().forEach(value => {
      if(!otherSet.has(value)) {
        differenceSet.add(value);
      }
    })
    return differenceSet;
  }
}

3.4 子集

首先判断大小，如果当前集合比目标集合元素更多，肯定不是其子集。然后再遍历每个元素，判断目标集合中是否存在，不存在则不是子集。这里使用了数组的 every() 方法，当不存在时可以提前退出遍历，而使用 forEach() 不能提前退出。

class Set {
  isSubsetOf(otherSet) {
    if(this.size() > otherSet.size()) {
      return false;
    }
    let isSubset = true;
    this.values().every(value => {
      if(!otherSet.has(value)) {
        isSubset = false;
        return false;
      }
      return true;
    })
    return isSubset;
  }
}

4. JavaScript 中的 Set 类

ES2015 之后新增了 Set 类：

const set = new Set();
set.add(1);
console.log(set.has(1)) // true
console.log(set.values()) // 迭代器
console.log(set.size) // 1

• 和自定义的不同，ES2015 中的 Set 的 values() 方法返回一个迭代器，而不是值构成的数组。
• size 属性返回集合中元素个数，而不是 size() 方法。
• 通过 delete() 方法可以删除元素，clear() 方法清空集合，与自定义的集合方法功能一样。

4.1 模拟集合运算

原生 Set 并没有集合运算方法，有需要可以进行模拟。

4.1.1 并集

function union(setA, setB) {
  const unionSet = new Set();
  setA.forEach(value => unionSet.add(value));
  setB.forEach(value => unionSet.add(value));
  return unionSet;
}

4.1.2 交集

function intersection(setA, setB) {
  const intersectionSet = new Set();

  let smallSet, bigSet;
  if(setA.size > setB.size) {
    smallSet = setB;
    bigSet = setA;
  } else {
    smallSet = setA;
    bigSet = setB;
  }

  for(let value of smallSet) {
    if(bigSet.has(value)) {
      intersectionSet.add(value)
    }
  }
  return intersectionSet;
}

4.1.3 差集

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

4.2 使用拓展运算符

有一种计算并集、交集和差集的简便方法，就是使用拓展运算符。

• 通过拓展运算符 ... 可以很快的将集合转为数组。
• 原生 Set 构造函数可以传入一个数组进行初始化，对自动将数组元素去重并添加到集合。

使用拓展运算符模拟并集：

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

使用拓展运算符模拟交集：

new Set([...setA].filter(value => setB.has(value)));

使用拓展运算符模拟差集：

new Set([...setA].filter(value => !setB.has(value)));