JavaScript 集合

[Checkson]

前言

集合（set）是一种包含不同元素的数据结构。集合中的元素称为成员。集合的两个最重要特性是：

• 集合中的成员是无序的
• 集合中不允许相同成员存在

集合在计算机科学中扮演了非常重要的角色，然而在很多编程语言中，并不把集合当成一种数据类型。当你想要创建一个数据结构，用来保存一些独一无二的元素时，比如一段文本中用到的单词，集合就变得非常有用。ES6中已经实现了Set类，那么这里，我们尝试自己去实现一个类似ES6中Set类。

定义

集合是由一组无序但彼此之间又有一定相关性的成员构成的，每个成员在集合中只能出现一次。在数学上，用大括号将一组成员括起来表示集合，比如 {0,1,2,3,4,5,6,7,8,9}。集合中成员的顺序是任意的，因此前面的集合也可以写做 {9,0,8,1,7,2,6,3,5,4}，或者其他任意形式的组合，但是必须保证每个成员只能出现一次。

另外，下面是一些使用集合时必须了解的定义：

• 不包含任何成员的集合称为 空集，全集 则是包含一切可能成员的集合。
• 如果两个集合的成员完全相同，则称两个集合相等。
• 如果一个集合中所有的成员都属于另外一个集合，则前一集合称为后一集合的 子集。

而对集合的基本操作有下面几种：

• 并集：将两个集合中的成员进行合并，得到一个新集合。
• 交集：两个集合中共同存在的成员组成一个新的集合。
• 补集：属于一个集合而不属于另一个集合的成员组成的集合。

集合（Set）类实现

1. 构造函数

完整代码地址。

function Set (arr) {
    if (arr && !Array.isArray(arr)) {
        throw new Error('传入的参数是非数组类型！');
    }
    this.dataStore = [];
    if (arr.length) {
        var _this = this;
        arr.forEach(function (item) {
            _this.add(item);
        });
    }
}

2. add：向集合中添加元素

Set.prototype.add = function (data) {
    if (!this.has(data)) {
        this.dataStore.push(data);
        return true;
    }
    return false;    
}

3. has：判断某个元素是否在集合中存在

Set.prototype.has = function (data) {
    return this.dataStore.indexOf(data) > -1;
}

4. remove：删除集合中的某个元素

Set.prototype.remove = function (data) {
    var pos = this.dataStore.indexOf(data);
    if (pos > -1) {
        this.dataStore.splice(pos, 1);
        return true;
    }
    return false;
}

5. clear：清除集合中的所有成员

Set.prototype.clear = function () {
    delete this.dataStore;
    this.dataStore = [];
}

6. size：获取集合中的元素个数

Set.prototype.size = function () {
    return this.dataStore.length;
}

7. show：返回集合中的元素

Set.prototype.show = function () {
    return this.dataStore;
}

8. union：求集合的并集

Set.prototype.union = function (set) {
    var tempSet = new Set();
    this.dataStore.forEach(function (item) {
        tempSet.add(item);
    });
    set.show().forEach(function (item) {
        if (!tempSet.has(item)) {
            tempSet.add(item);
        }
    });
    // 返回集合并集
    return tempSet;
}

9. intersect：求集合的交集

Set.prototype.intersect = function (set) {
    this.dataStore.forEach(function (item) {
        if (set.has(item)) {
            tempSet.add(item);
        }
    });
    return tempSet;
}

10. subSet：判断一个集合是否是另一个集合的子集

Set.prototype.subSet = function (set) {
    if (this.size() > set.size()) {
        return false;
    } 
    this.dataStore.forEach(function (item) {
        if (!set.has(item)) {
            return false;
        }
    });
    return true;
}

11. difference:：求集合与另一个集合的补集

Set.prototype.difference = function (set) {
    var tempSet = new Set();
    this.dataStore.forEach(function (item) {
        if (!set.has(item)) {
            tempSet.add(item);
        }
    });
    return tempSet;
};

集合（Set）类测试

var set = new Set([1, 2, 3])
console.log(set.show());
set.remove(3);
console.log(set.show());
set.clear();
console.log(set.show());
var set1 = new Set([1, 2, 3, 4]);
var set2 = new Set([3, 4, 5, 6]);
var unionSet = set1.union(set2);
console.log(unionSet.show());
var intersectSet = set1.intersect(set2);
console.log(intersectSet.show());
console.log(set.subSet(set1));
set.add(1);
set.add(2);
set.add(3);
var diffSet = set.difference(set2);
console.log(diffSet.show());

运行结果：

[ 1, 2, 3 ]
[ 1, 2 ]
[]
[ 1, 2, 3, 4, 5, 6 ]
[ 3, 4 ]
true
[ 1, 2 ]

集合应用

据我所知，集合在生产环境中，大多时候的作用是辅助去重的功能。

参考地址

• Set 和 Map 数据结构
• 学习javascript数据结构(三)——集合
• JavaScript数据结构-集合