JavaScript数据结构（四）集合

一种无序且唯一的数据结构

es6中有集合Set

集合的常见操作：去重、判断某元素是否在集合中、求交集

1. 定义

集合是由一组无序且唯一（即不能重复）的项组成的

2. 具体操作

创建

class Set {
	constructor() {
		this.items = {};  //使用对象来模拟
	}
}
复制代码

方法

• has(element)：如果元素在集合中，返回true，否则返回false

  has(element) {
      return element in items;
  }
  复制代码

  has(element) {
      return Object.prototype.hasOwnProperty.call(this.item, element);
  }
  复制代码

• add(element)：向集合添加一个新元素

  add(element) {
      if(!this.has(element)) {
          this.items[element] = element;
          return true;
      }
      return false;
  }
  复制代码

• delete(element)：从集合移除一个元素

  detele(element) {
      if(this.has(element)) {
          detele this.items[element];
          return true;
      }
      return false;
  }
  复制代码

• clear()：移除集合中的所有元素

  clear() {
      this.items = {};
  }
  复制代码

• size()：返回集合所包含元素的数量。它与数组的length 属性类似

  方法一：和其他数据结构一样，直接使用length

  方法二：

  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;
  }
  复制代码

• values()：返回一个包含集合中所有值（元素）的数组

  values() {
      return Object.values(this.items);
  }
  复制代码

  but Object.values()是ECMAScript 2017添加的，适用于现代浏览器中，等价于：

  valuesLegacy() {
      let values = [];
      for(let key in this.items) {
          if(this.items.hasOwnProperty(key)) {
              values.push(key);
          }
      }
      return values;
  }
  复制代码

3. 使用

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()); // []
复制代码

//去重
const arr = [1,1,2,2];
const arr2 = [...new Set(arr)];
复制代码

4. 集合的运算

并集

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();
    for(let i = 0; i < values.length; i++) {
        if(otherSet.has(values[i])) {
            intersectionSet.add(values[i]);
        }
    }
    return intersectionSet;
}
复制代码

优化一下，迭代AB集合中元素较少的那个

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;
}
复制代码

5. 前端与集合

let mySet = new Set();

let o = {a:1, b:2};
mySet.add(o)
mySet.add({a:1, b:2});
mySet.add('text');

const has = mySet.has(o);

mySet.delete(o)

for(let item of mySet.keys()) console.log(item);
for(let item of mySet.value()) console.log(item);
for(let [key, value] of mySet.keys()) console.log(key, value);

const myArr =[...mySet];
const myArr = Array.from(mySet);

const mySet2 = new Set([1,2,3,4]);
const intersection = new Set([..mySet].filter(x => mySet2.has(x)));
const difference = new Set([..mySet].filter(x => !mySet2.has(x)));
复制代码