用 JavaScript 实现集合

发表于   |   分类于

集合是由一组无序且唯一（即不能重复）的项组成的，在数学中，集合是一组不同的对象（的集），包含并集、交集、差集等基本操作。

创建集合

在新的ECMAScript6中已经包括了Set类的实现，不过我们可以自己来实现它。

以下是我们Set类的骨架：

1
2
3
function Set(){
    var items = {};
}

我们使用对象而不是数组来表示集合，在JavaScript中的对象不允许一个键指向两个不同的属性，也保证了集合里的元素都是唯一的。

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

  • add(value):向集合添加一个新的项；
  • remove(value):从集合移除一个值；
  • has(value):如果值在集合中，返回true，否则返回false;
  • clear():移除集合中的所有项；
  • size():返回集合所包含元素的数量；
  • values():返回一个包含集合中所有值的数组。

实现代码如下：

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
function Set() {

    var items = {};

    this.add = function(value){
        if (!this.has(value)){
            items[value] = value;
            return true;
        }
        return false;
    };

    this.remove = function(value){
        if (this.has(value)){
            delete items[value];
            return true;
        }
        return false;
    };

    this.has = function(value){
        return items.hasOwnProperty(value);
        //return value in items;
    };

    this.clear = function(){
        items = {};
    };

   this.size = function(){
        return Object.keys(items).length;
    };

   
   this.values = function(){
        return Object.keys(items);
    };

集合操作

对集合可以进行如下操作：

  • 并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合。
  • 交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合。
  • 差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合。
  • 子集：验证一个给定集合是否是另一个集合的子集。

并集

Markdown

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
this.union = function(otherSet){
        var unionSet = new Set(); //{1}

        var values = this.values(); //{2}
        for (var i=0; i<values.length; i++){
            unionSet.add(values[i]);
        }

        values = otherSet.values(); //{3}
        for (var i=0; i<values.length; i++){
            unionSet.add(values[i]);
        }

        return unionSet;
    };

交集

Markdown

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
this.intersection = function(otherSet){
       var intersectionSet = new Set(); //{1}

       var values = this.values();
       for (var i=0; i<values.length; i++){ //{2}
           if (otherSet.has(values[i])){    //{3}
               intersectionSet.add(values[i]); //{4}
           }
       }

       return intersectionSet;
   };

差集

Markdown

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
this.difference = function(otherSet){
        var differenceSet = new Set(); //{1}

        var values = this.values();
        for (var i=0; i<values.length; i++){ //{2}
            if (!otherSet.has(values[i])){    //{3}
                differenceSet.add(values[i]); //{4}
            }
        }

        return differenceSet;
    };

子集

Markdown

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
this.subset = function(otherSet){

        if (this.size() > otherSet.size()){ //{1}
            return false;
        } else {
            var values = this.values();
            for (var i=0; i<values.length; i++){ //{2}
                if (!otherSet.has(values[i])){    //{3}
                    return false; //{4}
                }
            }
            return true;
        }
    };