集合

本篇博客的所有代码都整理到自己的github库中，以便大家查看及学习。

这篇文章主要介绍了集合，会从以下几个方面展开学习

• 构建数据集合
• 创建集合类
• 集合运算
• Set类
• 多重集或袋

1. 构建数据集合

集合时一组无序且唯一(即不能重复)的项组成。使用了数学概念中的有序集合，应用到计算机科学的数据结构中。

2. 创建集合类

ECMA2015中介绍了Set类是JS API的一部分，我们会继承ECMA2015中的Set类实现自己的Set类
首先声明Set类及构造函数

class Set{
    constructor(){
        this.items = {}
    }
}

接下来我们需要注意的是我们使用对象而不是数组来表示集合(items)；接下来需要声明一些集合可用的方法。

• add(element)：向集合中添加一个新的元素
• delete(element) ：从集合中移除一个元素
• has(element) ：判断几个钟是否含有该元素
• clear() ： 移除集合中所有元素
• size() ： 返回集合所包含的元素数量
• values() ：返回一个包含集合中所有值（元素）的数据

接下来我们先实现has(element),因为该方法在好几个方法中都会被引用

class Set{
    constructor(){
        this.items = {}
    }
    has(element){
        return Object.prototype.hasOwnProperty.call(this.items,element)
    }
    add(element){
        if (this.has(element)) {
            return false
        }
        this.items[element] = element
        return true
    }
    delete(element){
        if (this.has(element)) {
            const result =  this.items[element]
            delete this.items[element]
            return result
        }
        return undefined
    }
    clear(){
        this.items = {}
    }
    size(){
        return Object.keys(this.items).length
    }
    values(){
        let result = []
        if (this.size() > 0) {
            for (const key in this.items) {
                result.push(this.items[key])
            }
        }
       return result
    }
}


var set = new Set()
set.add(1)
set.add(2)
set.add(3)
set.add(4)
console.log(set) // Set { items: { '1': 1, '2': 2, '3': 3, '4': 4 } }
set.delete(3)
console.log(set) // Set { items: { '1': 1, '2': 2, '4': 4 } }
console.log(set.size()) // 3
console.log(set.values()) // [1,2,4]
console.log(set) // Set { items: {} }

3. 集合运算

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

1. 并集

基于封装的Set类的union方法

union(otherSet){
    let resultSet = new Set()
    this.values().forEach((item) => {
        resultSet.add(item)
    })
    otherSet.values().forEach((item) => [
        resultSet.add(item)
    ])
    return resultSet
}

2. 交集

我们通过了解交集的数学概念，可以实现Set类的intersection方法

intersection(otherSet){ // 交集
    const intersection = new Set() // 创建一个新的变量，获取当前集合的值
    const values = this.values
    for (let i = 0; i < values.length; i++) {
        if (otherSet.has(values[i])) { // 判断传入的集合中是否含有该值，将两个集合都含有的值放到新的集合中，并返回
            intersection.add(values[i])
        }
    }
    return intersection
}

上述代码中，我们可以看到如果SetA的值是[2,3] ,SetB 的值是[1,2,3,4,5,6,7],按照上述的方法，我们需要遍历SetB值的长度。所以我们可以将上述的方法改进一下，遍历集合长度小的，减少遍历次数

intersection(otherSet){ // 交集
    const intersection = new Set()
    const values = this.values
    const otherSetValues = otherSet.values 
    let bigSet = values
    let smallSet = otherSetValues
    if (otherSetValues.length - values.length > 0) { // 传入的集合大
        bigSet = otherSetValues
        smallSet = values
    }
    smallSet.forEach(item => {
        if (bigSet.has(item)) {
            intersection.add(item)
        }
    })
    return intersection
}

3. 差集

差集是集合A中的元素只属于它自己。
如果在差集中还是采用上述交集的方式，代码就会变得冗余

 difference(otherSet){ 
    const differenceSet = new Set()
    this.values.forEach(item => {
        if (!otherSet.has(item)) {
            differenceSet.add(item)
        }
    })
    return differenceSet
}

4. 子集

判断当前集合是否为传入集合的子集，返回值为Boolean

isSubsetOf(otherSet){
    if (this.size() > otherSet.size()) { // 当前的集合大
        return false
    } 
    let isSubset = true
    this.values().every(values => {
        if (!otherSet.has(values)) {
            isSubset = false
            return false
        }
        return true
    })
    return isSubset
}