JavaScript数据结构与算法（五）集合

集合是由一组无序且唯一(不能重复)的项组成的，与我们高中数学学的集合同样具有有限性,
这种数据结构大多数用来存储唯一元素。

集合

创建集合类

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

检验某个元素是否存在集合中。

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

添加元素

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;
  };
clear() {
    this.items = {};
  };

返回集合中有多少个元素

size() {
    return Object.keys(this.items).length;
  };
//另外一种方式
/*
sizeLegacy(){
    let count = 0;
    for(let key in this.items){
      if(this.items.hasOwnProperty(key)){//判断是否是对象的属性，避免重复计数
        count++;
      }
      return count;
    };
  }
*/

返回对象所有属性值的数组

valuesLegacy(){
    let values = [];
    for(let key in this.items){
      if(this.items.hasOwnProperty(key)){
        values.push(key);
      };
    };
    return values;
  }
//另一种写法，只适用于现代浏览器
values() {
    return Object.values(this.items);
  }

以上就是集合数据结构的创建和成员函数的添加。而集合最主要的是它的运算，在计算机领域中应用最多的是数据库，发送一条SQL查询命令时，使用的是集合运算，返回的也是数据集合。接下来介绍相对常见的集合运算（以下代码引用ES6语法）

集合运算

并集

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;
    let smallerSet = otherValues;
    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;
  }

以上是我们实现的集合运算，但是ES2015原声的Set并没有这些功能，如果有需要的话，我们也可以模拟。

模拟运算

模拟并集运算

const union = (set1, set2) => {
  const unionAb = new Set();
  set1.forEach(value => unionAb.add(value));
  set2.forEach(value => unionAb.add(value));
  return unionAb;
};
//第二种：使用拓展运算符
new Set([...setA, ...setB]);

模拟交集运算

const intersection = (set1, set2) => {
  const intersectionSet = new Set();
  set1.forEach(value => {
    if (set2.has(value)) {
      intersectionSet.add(value);
    }
  });
  return intersectionSet;
};
//第二种：使用拓展运算符
new Set([...setA].filter(x => setB.has(x)))

模拟差集运算

const difference = (set1, set2) => {
  const differenceSet = new Set();
  set1.forEach(value => {
    if (!set2.has(value)) {
      differenceSet.add(value);
    }
  });
  return differenceSet;
};
//第二种：使用拓展运算符
new Set([...setA].filter(x => !setB.has(x)))