集合的实现-灵析社区

前言

集合是一种不允许值重复的顺序数据结构。

本文将详解集合的实现思路并使用TypeScript实现类似于ES6中的Set集合以及集合的基本运算，欢迎各位感兴趣的开发者阅读本文。

实现思路

集合有一个很重要的特点：它的内部元素不会重复，因此我们可以使用JavaScript中对象来描述结合。

基础集合的实现

一个较为完善的集合类必须具备：判断元素是否在集合中、向集合中添加元素、删除集合中的元素等基础函数，接下来我们来分析下这些函数的实现思路。

判断元素是否在集合中(has)
集合中添加元素(add)
删除集合中的元素(delete)
清空集合(clear)，将集合指向空对象即可。
获取集合大小(size)，声明一个变量来存储集合大小，遍历集合，集合大小自增，结束遍历返回集合大小。
获取集合中的所有元素

集合运算的实现

集合是数学中基础的概念，在计算机领域也非常重要。接下来我们来看看集合相关运算的实现思路，实现之前我们先用图解的形式描述下常用的几个集合运算。

数学公式图解

并集(A∪B)，将给定集合中的元素进行合并，存进一个新集合中，返回这个新集合，该集合定义如下，意思为:X（元素）存在于A中，或X存在于B中。
交集(A∩B)，找出给定集合中的相同的元素，将找到的相同元素存进一个新集合中，返回这个新集合，该集合定义如下，意思为：X（元素）存在于A中，且X存在于B中。
差集(A - B)，给定两个集合，找出集合中不存在于另一个集合中的元素将其存进一个新集合里，返回这个新集合，该集合定义如下：意思为：X（元素）存在于A中，且X不存在于B中。
子集(A⊆B)，给定了两个集合，判断其中一个集合中的元素是否都存在于另一个集合中，如果又一个不存在则返回false，该集合定义如下：集合A中的每一个X（元素），也需要存在于集合B中。

实现思路解析

并集运算(union)，给定两个集合，返回一个包含两个集合中所有元素的新集合。声明并集集合变量，值为Set类型遍历当前实例集合中的所有元素，将其放进并集变量集合中遍历传进来的集合参数，将其放进并集变量集合中返回并集变量集合
交集运算(intersection)，给定两个集合，返回一个包含两个集合中共有元素的新集合声明交集集合变量，值为Set类型获取当前实例集合中的所有元素存进当前集合数组变量中，获取参数集合中的所有元素存进参数结合数组中假设当前集合数组中的元素最多将其放到一个变量里，假设参数集合中的元素最少将其放到一个变量里。如果参数集合中的元素个数比当前元素集合中的个数多，则交换两个变量存储的集合元素数组遍历参数最少的集合变量数组，判断当前遍历到的元素是否在参数最多的集合元素数组里，如果存在则向交集变量中添加当前元素返回交集集合变量集合
差集运算(difference)，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合。声明差集集合变量，值为Set类型遍历当前实例集合中的元素，判断参数集合中是否包含当前遍历到的元素，如果不包含，则向差集集合里添加当前元素返回差集集合变量
子集运算，验证一个给定集合是否是另一个集合的子集声明一个子集判断变量，用于判断参数集合是否在当前集合中，默认值为true遍历当前实例集合中的元素，判断当前遍历到的元素是否都存在于参数集合中，如果遍历到的元素有一个不存在于参数集合中则将子集判断变量设为false返回子集判断变量

实现代码

我们捋清实现思路后，接下来我们将上述实现思路转换为代码：

新建一个Set.ts文件，用于实现集合类
在集合类中声明一个class，用于存放我们需要实现的集合函数

export default class Set<T>{

}

在class类中声明构造器以及实现集合函数需要的变量

interface setItemsType<T> {
    [propName: string]: T;
}

private items: setItemsType<T>;
constructor() {
    this.items = {};
}

实现判断元素是否存在于集合中函数(has)

    has(element: any){
        // Object原型有hasOwnProperty方法用于判断对象是否有特定属性
        return Object.prototype.hasOwnProperty.call(this.items,element);
    }

实现向集合中添加元素函数（add）

    add(element: any){
        if(!this.has(element)){
            this.items[element] = element;
            return true;
        }
        return false;
    }

实现删除集合中元素函数(delete)

    delete(element: any){
        if(this.has(element)){
            delete this.items[element];
            return true;
        }
        return false;
    }

清空集合(clear)

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

获取集合大小(size)

    size(){
        let count = 0;
        for (let key in this.items){
            if(this.items.hasOwnProperty(key)){
                count++;
            }
        }
        return count;
    }

获取集合中的所有元素（values）

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

并集运算(union)

    union(otherSet: Set<T>){
        // 声明并集变量
        const unionSet = new Set();
        this.values().forEach(value => unionSet.add(value));
        otherSet.values().forEach(value => unionSet.add(value));
        return unionSet;
    }

交集运算（intersection）

    intersection(otherSet: Set<T>) {
        // 声明交集变量
        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）

    difference(otherSet: Set<T>) {
        // 声明差集变量
        const differenceSet = new Set();
        // 遍历当前实例中的集合
        this.values().forEach(value => {
            // 如果当前遍历到元素不存在与另一个集合中，则将档当前元素添加进差集变量里
           if(!otherSet.has(value)){
               differenceSet.add(value);
           }
        });
        // 返回差集变量
        return differenceSet;
    }    isSubsetOf(otherSet: Set<T>) {
        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）

    isSubsetOf(otherSet: Set<T>) {
        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;
    }

完整代码请移步：Set.ts

编写测试代码

接下来，我们对上述实现的Set类进行测试，确保每个函数都正常工作。

const set = new Set();
set.add(11);
set.add(12);
set.add(13);
set.delete(11);
console.log(set.size())
console.log("获取集合中的元素",set.values());
set.clear();
console.log("获取集合大小",set.size());

// 集合运算
const A = new Set();
A.add(10);
A.add(11);
A.add(12);
A.add(13);
A.add(1);
A.add(2);
const B = new Set();
B.add(1);
B.add(2);
B.add(3);
// 求A和B的并集
console.log("A和B的并集",A.union(B).values());
// 求A和B的交集
console.log("A和B的交集",A.intersection(B).values());
//求A和B的差集
console.log("A和B的差集",A.difference(B).values());

// 求C是否为D的子集
const C = new Set();
C.add(1);
C.add(2);
C.add(3);
C.add(4);
C.add(5);
const D = new Set();
D.add(1);
D.add(2);
D.add(3);
D.add(9)
console.log(D.isSubsetOf(C));

完整代码请移步：SetTest.js