集合

集合是由一组无序并且不能存在重复的元素组成的。你可以把集合当成一个既没有重复元素，又没有顺序的数组。

创建集合

学过 ES6 的同学都知道，加入了一种新的数据结构Set。也是本章所说的集合。下面将基于 ES6 的Set数据结构来实现一个属于自己的Set类。

下面来声明一个Set类。

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

这里用一个对象items来表示集合，用对象的主要原因是，对象不允许用一个键指向两个不同的属性。这样也能确保集合中的元素是唯一的，不过也可以用数组来表示。

下面是集合的方法。

add(ele)：向集合中添加一个元素。

delete(ele)：从集合中删除一个元素。

has(ele)：查看集合中是否有该元素存在，如果存在返回true，否则返回false。

clear()：删除集合中的所有元素。

size()：返回集合中元素的数量。

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

has方法

首先来实现has方法，因为它会被add和delete方法调用。

has(ele){returnObject.prototype.hasOwnProperty.call(this.items, ele);}复制代码

这里使用了Object原型上的hasOwnProperty方法。该方法返回一个布尔值，查看对象上是否具有指定的属性。当然你也可以用in操作符。这两个方法的区别在于hasOwnProperty是检查实例中是否具有指定的属性。而in操作符是无论指定的属性是在原型中还是在实例中都会返回true。

add方法

下面是添加元素的方法。

add(ele){if(!this.has(ele)) {this.items[ele] = ele;returntrue;    }returnfalse;}复制代码

add方法相对于比较简单。首先，检查要添加的元素是否存在于集合中，没有就添加并返回true，有就直接返回false。

添加元素时，最好用它本身来当作键和值来保存，这样有利于查找该元素。

delete、clear方法

delete(ele){if(this.has(ele)) {deletethis.items[ele];returntrue;    }returnfalse;}复制代码

delete方法首先检查元素是否存在于集合中，存在就删除并返回true表示已删除，不存在直接返回false。

clear方法和其他数据结构的clear方法一样。

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

直接将items初始化就可以了。还有一种方法是通过迭代集合，使用delete操作符逐个将元素删除，不过这样显得麻烦。

size方法

实现size方法有三种：

像栈、队列那样，在使用add和delete方法是用一个count变量控制它。

使用Object.keys方法，该方法返回对象中可枚举属性组成的数组。然后用这个数组的长度length返回items对象中的属性个数。

用for-in遍历对象中的属性，用一个count变量记录属性的个数并返回count变量。

size(){returnObject.keys(this.items).length;}theOtherOneSize(){letcount =0;for(constkeyinthis.items) {if(this.has(key)) {        count++;      }    }returncount;}复制代码

迭代items对象的所有属性，并用has方法检查是否为自身的属性。如果是，就递增count变量。

用has方法这步的原因在于，假设在对象的原型上有额外的属性，也会导致count递增。

values方法

对于values方法，用Object.values和for-in迭代都可以。

values(){returnObject.values(this.items);}theOtherOneValues(){constarr = [];for(constkeyinthis.items) {if(this.has(key)) {        arr.push(key);      }    }returnarr;}复制代码

用for-in迭代就和上面的size方法一样，只不过这里不是计算属性的个数。

测试Set类

constset =newSet();console.log(set.size());// 0console.log(set.add(1));// trueconsole.log(set.add(2));// trueconsole.log(set.add(3));// trueconsole.log(set.size());// 3console.log(set.has(1));// trueconsole.log(set.values());// [1, 2, 3]console.log(set.delete(3));// true复制代码

整体代码

classSet{constructor(){this.items = {};  }has(ele){returnObject.prototype.hasOwnProperty.call(this.items, ele);  }add(ele){if(!this.has(ele)) {this.items[ele] = ele;returntrue;    }returnfalse;  }delete(ele){if(this.has(ele)) {deletethis.items[ele];returntrue;    }returnfalse;  }clear(){this.items = {};  }size(){returnObject.keys(this.items).length;  }theOtherOneSize(){letcount =0;for(constkeyinthis.items) {if(this.has(key)) {        count++;      }    }returncount;  }values(){returnObject.values(this.items);  }theOtherOneValues(){constarr = [];for(constkeyinthis.items) {if(this.has(key)) {        arr.push(key);      }    }returnarr;  }}复制代码

集合运算

并集

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

// 在Set类中添加方法union(otherSet){constunionSet =newSet();this.values().forEach((item) =>unionSet.add(item));    otherSet.values().forEach((item) =>unionSet.add(item));returnunionSet;}复制代码

测试代码

constsetA =newSet();constsetB =newSet();setA.add(1);setA.add(3);setA.add(5);setA.add(6);setB.add(2);setB.add(4);setB.add(6);constotherSetB = setA.union(setB);console.log(otherSetB.values());// [1, 2, 3, 4, 5, 6]复制代码

需要注意的是，在setA和setB中都添加了元素6，但是在下面打印出来的数据中只出现一个6。

交集

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

intersectionFn(otherSet){constintersection =newSet();

constvalues =this.values();for(leti =0; i < values.length; i++) {if(otherSet.has(values[i])) {        intersection.add(values[i]);      }    }returnintersection.values();}复制代码

首先创建一个Set实例，然后迭代当前Set实例中的所有值（values）。用has方法验证是否存在otherSet集合当中，如果存在，就添加到interseciton集合中。最后以数组的形式返回它。

测试代码

constsetA =newSet();

constsetB =newSet();

setA.add(1);

setA.add(3);

setA.add(5);

setA.add(6);

setB.add(2);

setB.add(4);

setB.add(6);

constotherSetB = setA.intersectionFn(setB);console.log(otherSetB);// [6]复制代码

改进版

假设现在有两个这样的集合：

setA的值是[1, 2, 3, 4, 5, 6];

setB的值是[2, 6];

用刚才的intersectionFn方法，就要迭代六次setA的值，然后还要用这个六个值和setB的两个值去作比较。那么换过来，只要用setB去和setA做比较的话，这样就减少了性能的消耗。因为只需要迭代两次setB。下面来修改之前的intersectionFn方法。

otherIntersection(otherSet){constintersection =newSet();

constvalues =this.values();

constotherVal = otherSet.values();

// 数组长度大的集合letbiggerSet = values;// 数组长度小的集合letsmallerSet = otherVal;/*

      如果传入的Set集合的元素个数比当前Set集合的元素个数多，那么就交换

      如果当前的集合元素个数比传入的Set集合的元素个数多，就不会走这一步

    */if(otherVal.length - values.length >0) {      biggerSet = smallerSet;      smallerSet = biggerSet;    }// 迭代较小的集合smallerSet.forEach((item) =>{if(biggerSet.includes(item)) {        intersection.add(item);      }    });returnintersection;}复制代码

差集

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

difference(otherSet){constdifferenceSet =newSet();this.values().

forEach((item) =>{if(!otherSet.has(item)) {        differenceSet.add(item);      }    });returndifferenceSet.values();}复制代码

difference方法会返回一个存在于集合setA中但不存在于集合setB的元素数组。首先创建结果集合，然后迭代集合中的所有值。检查当前值是否存在于给定集合中，存在的话，就把值添加到结果集合中。

测试代码

constsetA =newSet();

constsetB =newSet();

setA.add(1);

setA.add(3);

setA.add(5);

setA.add(6);

setB.add(2);

setB.add(4);

setB.add(6);

constotherSetB = setA.difference(setB);

console.log(otherSetB);// [1, 3, 5]复制代码

这里输出了[1, 3, 5]，因为[1, 3, 5]只存在于setA中。如果执行setB.difference(setA)，会输出[2, 4]，因为[2, 4]只存在于setB中。

这里不能像优化intersecton方法那样去优化difference方法，因为setA和setB之间的差集可能与setB和setA之间的差集不一样。

子集

验证一个集合是否是另一个集合的子集。

isSubsetOf(otherSet){if(this.size() > otherSet.size()) {returnfalse;   

}letisSubset =true;this.values().every((value) =>{if(!otherSet.has(value)) {        isSubset =false;returnfalse;      }returntrue;    });returnisSubset;}复制代码

首先验证当前Set实例的元素个数大小，如果当前实例中的元素比otherSet实例多，那就不是子集。直接返回false。记住，子集的元素个数始终小于或等于要比较的集合的。

上面的代码中，假如当前实例是给定集合的子集（isSubset = true）。就迭代当前集合中的所有元素，验证这些元素是否存在于otherSet中。如果都不存在，就说明它不是一个子集，返回false。如果都存在于otherSet中，那么isSubset的值就不会改变。返回true。

使用every方法的原因在于，一个值不存在于otherSet中时，可以停止迭代，表示这不是一个子集。只要回调函数返回true，就会执行下去。如果返回false，循环直接停止。

测试代码

constsetA =newSet();

constsetB =newSet()

;constsetC=newSet();

setA.add(1);

setA.add(2);

setA.add(3);

setB.add(1);

setB.add(2);

setB.add(3);

setB.add(4);

setC.add(2);

setC.add(3);

setC.add(4);

setC.add(5);

console.log(setA.isSubsetOf(setB));

// trueconsole.log(setA.isSubsetOf(setC));// false复制代码

这里有三个集合：setA是setB的子集，所以输出了true。setA不是setC的子集，因为setC中只包含了setA中的2，所以输出了false。

ES6中的Set类

下面我们用 ES6 的Set类来模拟并集、交集、差集、子集。

首先来定义两个集合，因为后面会用到。

constsetA =newSet();constsetB =newSet();setA.add(10);setA.add(20);setA.add(30);setB.add(20);setB.add(30);setB.add(40);setB.add(50);复制代码

模拟并集

constunion =(setA, setB) =>{letvalues =newSet();  setA.forEach((item) =>values.add(item));  setB.forEach((item) =>values.add(item));returnvalues.values();};console.log(union(setA, setB));// {10, 20, 30, 40, 50}复制代码

模拟交集

constintersection =(setA, setB) =>{letvalues =newSet();  setA.forEach((item) =>{if(setB.has(item)) {      values.add(item);    }  });returnvalues.values();};console.log(intersection(setA, setB));// {20, 30}复制代码

模拟差集

constdifference =(setA, setB) =>{constvalues =newSet();  setA.forEach((item) =>{if(!setB.has(item)) {      values.add(item);    }  });returnvalues.values();};console.log(difference(setA, setB));// {10}复制代码

模拟子集

constisSubsetOf =(setA, setB) =>{if(setA.size > setB.size) {returnfalse;  }letisSubset =true;letarr = [...setA];  arr.every((value) =>{if(!setB.has(value)) {      isSubset =false;returnfalse;    }returntrue;  });returnisSubset;};console.log(isSubsetOf(setA, setB));// false复制代码

结尾

如果文中出现错误，欢迎各位大佬指点。如果本章内容对你有收获，欢迎赞加关、私哦！