JS 数据结构：集合

集合

集合是由一组无序且唯一（即不能重复）的项组成的。该数据结构使用了与有限集合相同的数学概念。ES6 JS 原生实现了集合 Set 数据结构（具体看这篇文章JS Set 与 weakSet），但是没有取两集合交集、并集、差集的 API ，所以本篇博客就自己实现一个集合并实现原生集合未实现的操作。

集合 API

定义集合

这里底层我们使用对象（使用数组也可以），使用对象的原因是为了更好的模拟 Set 的行为。

class MySet {
  constructor() {
    this.items = {};
  }
}
1
2
3
4
5

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

因为是对象，所以我们可以使用 in 运算符，in 运算符会返回某个属性是否在对象及其原型链上，存在返回 true，否则返回 false。

// 检验某个元素是否存在于集合中
  has(item) {
    return item in this.items;
  }
1
2
3
4

添加、删除、清空

添加：因为集合内元素唯一，所以新增元素前需要先判断集合中是否由该元素。
删除：依然需要先判断集合中是否由该元素，有才能删除。
清空：因底层使用对象，所以清空直赋值空对象就好了。

// 添加元素
  add(item) {
    if (!this.has(item)) {
      this.items[item] = item;
      return true;
    }
    return false;
  }
  // 删除元素
  delete(item) {
    if (!this.has(item)) {
      delete this.items[item];
      return true;
    }
    return false;
  }
  // 清空集合
  clear() {
    this.items = {};
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

获取集合元素的数量

我们使用for in便利对象的属性，但是由于for in会遍历所有的可迭代对象（包括原型链上的），所以需要使用hasOwnProperty方法判断一下当前属性是否是对象本身的属性。size 方法中是 count 才加一，最后返回 count 就是元素的数量了。values 方法中是才将当前属性值添加到结果数组中。

// 获取集合元素的数量
  size() {
    let count = 0;
    for (let key in this.items) { // {2} 
      if (this.items.hasOwnProperty(key)) { // {3} 
        count++; // {4} 
      }
      return count;
    };
  }
  // 以数组的形式返回所有元素
  values() {
    let values = [];
    for (let key in this.items) { // {1} 
      if (this.items.hasOwnProperty(key)) {
        values.push(key); // {2} 
      }
    }
    return values;
  };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

并集

两集合并集

给定的两个集合，返回一个包含两个集合中所有元素的新集合。

// 并集
  union(set) {
    const resSet = new Set();
    this.values().forEach(value => resSet.add(value));
    set.values().forEach(value => resSet.add(value));
    return resSet;
  }
1
2
3
4
5
6
7

多集合并集

给定的多个集合，返回一个包含所有集合中所有元素的新集合。

//多集合并集
  unionMany(...sets) {
    const resSet = new Set();
    this.values().forEach(value => resSet.add(value));
    sets.forEach(set => {
      set.values().forEach(value => resSet.add(value));
    })
    return resSet;
  }
1
2
3
4
5
6
7
8
9

交集

两集合交集

给定的两个集合，返回一个包含两个集合中共有元素的新集合。

 // 交集
  intersection(set) {
    const resSet = new Set();
    const values = this.values();
    for (let i = 0; i < values.length; i++) {
      if (set.has(values[i])) {
        resSet.add(values[i]);
      }
    }
    return resSet;
  }
1
2
3
4
5
6
7
8
9
10
11

多集合交集

给定的多个集合，返回一个包含所有集合中共有元素的新集合。

// 多集合交集
  intersection(...sets) {
    const resSet = new Set();
    const values = this.values();
    for (let i = 0; i < values.length; i++) {
      resSet.add(values[i]);
    }
    for (let i = 0; i < values.length; i++) {
      for (let set of sets) {
        if (!set.has(values[i])) {
          resSet.delete(values[i]);
        }
      }
    }
    return resSet;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

差集

给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合。

// 差集
  difference(set) {
    const resSet = new Set();
    this.values().forEach(value => {
      if (!set.has(value)) {
        resSet.add(value);
      }
    });
    return resSet;
  }
1
2
3
4
5
6
7
8
9
10

判断是否子集

验证一个给定集合是否是另一集合的子集。给定集合的所有元素都能在另一个集合中找到。

  // 子集
    // 子集
  isSubsetOf(set) {
    if (this.size() > set.size()) {
      return false;
    }
    let isSubset = true;
    this.values().every(value => {
      if (!set.has(value)) {
        isSubset = false;
        return false;
      }
      return true;
    });
    return isSubset;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

集合的操作就这么多了，我是孤城浪人，一名正在前端路上摸爬滚打的菜鸟，欢迎你的关注。