6 集合

集合是由一组无序且唯一（即不能重复）的项组成。该数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。

6.1 创建Set类

用下面的Set类以及它的构造函数声明作为开始

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

接下来我们需要声明一些集合可用的方法：

add(element)：向集合添加一个新的项
delete(element)：从集合里移除一个值
has(element)：如果值在集合中，返回true，否则返回false
clear()：移除集合中的所有项
size()：返回集合所包含元素的数量，与数组的length属性类似
values()：返回一个包含集合中所有值的数组

6.1.1 has(element)方法

由于has(element)方法会被add、delete等其它方法调用。它用来检验某个元素是否存在于集合中。所以我们先来实现它：

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

Object原型有hasOwnProperty方法。该方法返回一个表明对象是否具有特定属性的布尔值。

6.1.2 add(element)方法

1
2
3
4
5
6
7
add(element){
    if(!this.has(element)){
        this.items[element] = element;
        return true
    }
    return false;
}

对于给定的element，可以检查它是否存在于集合中。如果不存在，就把element添加到集合，返回true。如果集合已经有了这个元素就返回false不进行添加

6.1.3 delete()和clear()方法

1
2
3
4
5
6
7
delete(element){
    if(this.has(element)){
        delete this.items[element];
        return true;
    }
    return  false;
}

delete方法依旧要验证是否存在element。

1
2
3
clear(){
    this.items = {};
}

6.1.4 size()方法

该方法有三种实现方式。

第一种方式是使用一个length变量，每次使用add或者delete方法时就控制它。

第二种方式是使用JavaScript中Object类的一个内置方法

1
2
3
size(){
    return Object.keys(this.items).length
}

JavaScript的Object类有一个keys方法，它返回一个包含给定对象所有属性的数组。然后可以使用这个数组的length属性来返回items对象的属性个数。

第三种方式是手动提取items对象的每一个属性，记录属性的个数并返回这个数。

1
2
3
4
5
6
7
sizeLegacy(){
    let count = 0;
    for (let key in this.items){
        if(this.items.hasOwnProperty(key)) count++;
    }
    return count;
}

6.1.5 values()方法

要实现values()方法。有两种方式。

第一种是使用Object类的values()方法。

1
2
3
values(){
    return Object.values(this.items);
}

Object.values()方法返回一个包含给定对象所有属性值的数组。

第二种是矢代items对象的所有属性，把它们添加到一个数组中，并返回该数组。

1
2
3
4
5
6
7
valuesLegacy(){
    let values = [];
    for (let key in this.items){
        if(this.items.hasOwnProperty(key)) values.push(key);
    }
    return values;
}

下面是Set类的所有代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class Set {
    constructor() {
        this.items = {};
    }

    /**
     * 向集合添加一个新元素
     * @param element
     * @return {boolean}
     */
    add(element){
        if(!this.has(element)){
            this.items[element] = element;
            return true
        }
        return false;
    }

    /**
     * 从集合添加一个新元素
     * @param element
     * @return {boolean}
     */
    delete(element){
        if(this.has(element)){
            delete this.items[element];
            return true;
        }
        return  false;
    }

    /**
     * 返回一个包含集合中所有元素的数组
     * @return {unknown[]}
     */
    values(){
        return Object.values(this.items);
    }
    valuesLegacy(){
        let values = [];
        for (let key in this.items){
            if(this.items.hasOwnProperty(key)) values.push(key);
        }
        return values;
    }
    /**
     * 如果元素在集合中，返回true，否则返回false
     * @param element
     * @return {boolean}
     */
    has(element){
        return Object.prototype.hasOwnProperty.call(this.items,element);
    }

    /**
     * 移除集合中所有元素
     */
    clear(){
        this.items = {};
    }

    /**
     * 返回集合所包含元素的数量，与数组的length属性类似
     * @return {number}
     */
    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;
    }
}

6.1.6 使用Set类

我们来写几个测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let set = new Set();
set.add(1);
console.log(set.values());
console.log(set.has(1));
console.log(set.size());

set.add(3);
console.log(set.values());
console.log(set.has(3));
console.log(set.size());

set.delete(1);
console.log(set.values());

set.delete(3);
console.log(set.values());

下面是运行的结果：

Set类测试用例结果.png

6.2 集合运算

我们可以对集合进行如下运算。

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

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

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

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

6.2.1 并集

集合A和集合B的并集表现如下：
$$
A\cup B
$$

该集合定义如下：
$$
A \cup B {x|x \in A \lor x \in B}
$$
意思是x（元素）存在于A中，或者x存在于B中。下图展示了并集运算：

并集.png

现在来实现Set类的union()方法

1
2
3
4
5
6
union(otherSet){
    let unionSet = new Set();
    this.values().forEach(value => unionSet.add(value));
    otherSet.values().forEach(value => unionSet.add(value));
    return unionSet;
}

以上使用的为forEach方法来矢代数组的元素，但它是ECMAScript2015中才引入的。也可以把union方法写成下面这样，不适用forEach和箭头函数：

1
2
3
4
5
6
7
8
9
10
11
12
unionLegacy(otherSet){
    let unionSet = new Set();
    let values = this.values();
    for (let i = 0;i < values.length;i++){
        unionSet.add(values[i]);
    }
    values = otherSet.values();
    for (let i = 0;i < values.length;i++){
        unionSet.add(values[i]);
    }
    return unionSet;
}

我们来写测试用例：

1
2
3
4
5
6
7
8
9
10
11
12
13
let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

let setB = new Set();
setB.add(3);
setB.add(4);
setB.add(5);
setB.add(6);

let unionSet = setA.union(setB);
console.log(unionSet.values())

运行结果为[ 1, 2, 3, 4, 5, 6 ]。注意元素3同时存在于setA和setB中，它在结果集合中只出现一次。

6.2.2 交集

集合A和集合B的交集表示如下：
$$
A \cap B
$$
该集合定义如下：
$$
A \cap B {x|x \in A \land x \in B}
$$
意思是x（元素）存在于A中，且x存在于B中。下图展示了交集运算：

交集.png

现在来实现Set类的intersection方法

1
2
3
4
5
6
7
8
9
10
11
intersection(otherSet) {
    let intersectionSet = new Set();
    let values = this.values();
    for (let i = 0; i < values.length; i++) {
        //验证是否存在otherSet中,存在则添加
        if (otherSet.has(values[i])) {
            intersectionSet.add(values[i]);
        }
    }
    return intersectionSet;
}

来写个测试用例：

1
2
3
4
5
6
7
8
9
10
11
12
let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

let setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);

let intersectionAB = setA.intersection(setB);
console.log(intersectionAB.values());

运行结果为[ 2, 3 ]，因为2和3同时存在于两个集合中。

6.2.3 差集

集合A和集合B的差集表示为 A - B，定义如下：
$$
A - B = {x|x \in A \land x \not \subset B}
$$
意思是x（元素）存在于A中，且x不存在于B中。下图展示了集合A和集合B的差集运算。

差集.png

现在来实现Set类的difference方法

1
2
3
4
5
6
7
8
9
difference(otherSet){
    let differenceSet = new Set();
    this.values().forEach(value => {
        if(!otherSet.has(value)){
            differenceSet.add(value);
        }
    });
    return differenceSet;
}

写个测试用例来测试以上方法：

1
2
3
4
5
6
7
8
9
10
11
12
let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

let setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);

let differenceAB = setA.difference(setB);
console.log(differenceAB.values());

输出结果为[ 1 ]，因为1是唯一一个仅存在于setA的元素。如果我们执行setB.difference(setA),会得到[ 4 ]作为输出结果，因为4是只存在于setB中的元素

6.2.4 子集

子集的数学概念是集合A是集合B的子集，表示如下：
$$
A \subseteq B
$$
该集合的定义如下：
$$
{x|\forall x \in A \Rightarrow x \in B}
$$
意思是集合A中的每一个x（元素），也需要存在于集合B中。下图展示了集合A是集合B的子集：

子集.png

现在来实现Set类的isSubsetOf()方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
isSubsetOf(otherSet) {
    //当前set类的大小必须要大于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;
}

在isSubsetOf()方法中，我们不像并集、交集和差集中使用forEach方法。我们使用every()方法代替，这个方法的回调函数只要返回false，那么循环就会停止。不需要再往下循环。

写个测试检验一下上面的代码效果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let setA = new Set();
setA.add(1);
setA.add(2);

let setB = new Set();
setB.add(1);
setB.add(2);
setB.add(3);

let setC = new Set();
setC.add(2);
setC.add(3);
setC.add(4);

console.log(setA.isSubsetOf(setB)); // true
console.log(setA.isSubsetOf(setC)); // false