数据结构与算法-集合

《学习JavaScript数据结构与算法(第3版)》

集合是由一组无序且唯一（即不能重复）的项组成的。JavaScript的对象不允许一个键指向两个不同的属性，也保证了集合里的元素都是唯一的。所以使用对象来实现集合。

数据结构

class Set {
  constructor() {
    this.items = {};
  }
  // 向集合添加一个新元素
  add(element) {
    // 检查元素是否已存在
    if (!this.has(element)) {
      // 同时作为键和值保存，有利于查找该元素
      this.items[element] = element;
      return true;
    }
    return false;
  }
  // 从集合移除一个元素
  delete(element) {
    // 检查元素是否已存在
    if (this.has(element)) {
      delete this.items[element];
      return true;
    }
    return false;
  }
  // 如果元素在集合中，返回true，否则返回false
  has(element) {
    // 该方法返回一个表明对象是否具有特定属性的布尔值，使用in运算符则返回对象在原型链上是否有特定属性的布尔值
    return Object.prototype.hasOwnProperty.call(this.items, element);
  }
  // 返回一个包含集合中所有值（元素）的数组
  values() {
    return Object.values(this.items);
  }
  // 并集，对于给定的两个集合，返回一个包含两个集合中所有元素的新集合
  union(otherSet) {
    const unionSet = new Set();
    this.values().forEach(value => unionSet.add(value));
    otherSet.values().forEach(value => unionSet.add(value));
    return unionSet;
  }
  // 交集，对于给定的两个集合，返回一个包含两个集合中共有元素的新集合
  intersection(otherSet) {
    const intersectionSet = new Set();
    const values = this.values();
    const otherValues = otherSet.values();
    let biggerSet = values; // size较大的集合
    let smallerSet = otherValues; // size较小的集合
    if (otherValues.length - values.length > 0) {
      biggerSet = otherValues;
      smallerSet = values;
    }
    smallerSet.forEach(value => { // 循环元素较小的集合
      if (biggerSet.includes(value)) { // 元素较大的集合中判断是否有该元素
        intersectionSet.add(value);
      }
    });
    return intersectionSet;
  }
  // 差集，对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合
  difference(otherSet) {
    const differenceSet = new Set();
    this.values().forEach(value => {
      if (!otherSet.has(value)) {
        differenceSet.add(value);
      }
    });
    return differenceSet;
  }
  // 子集，验证一个给定集合是否是另一集合的子集
  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;
  }
  // 集合是否为空
  isEmpty() {
    return this.size() === 0;
  }
  // 返回集合所包含元素的数量。它与数组的length属性类似
  size() {
    // 也可以定义一个count变量进行维护
    return Object.keys(this.items).length;
  }
  // 移除集合中的所有元素
  clear() {
    this.items = {};
  }
  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const values = this.values();
    let objString = `${values[0]}`;
    for (let i = 1; i < values.length; i++) {
      objString = `${objString},${values[i].toString()}`;
    }
    return objString;
  }
}

使用Object.prototype.hasOwnProperty.call(obj, element)而不使用obj.hasOwnPeoperty(element)的原因是因为不是所有的对象都继承了Object.prototype，甚至继承了Object.prototype的对象上的hasOwnProperty方法也有可能被覆盖，导致代码不能正常工作，因此使用Object.prototype.hasOwnProperty.call(obj, element)更安全。