集合(Set)

集合是一种无重复元素, 无顺序的数据结构。

ES6 引入的 Set 就是集合。

方法	描述
add	添加新元素
delete	移除元素
has	元素是否存在(Boolean)
clear	清除集合
size	集合数量
values	集合所有元素(Array)

实现

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

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

    has(value) {
        return Object.prototype.hasOwnProperty.call(this.items, value)
    }

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

    clear() {
        this.items = {}
    }

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

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

    data() {
        return this.items
    } 
}

并集

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

union(otherSet) {
    const 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;
}

const setA = new Set()
setA.add(1)
setA.add(2)
setA.add(3)

const setB = new Set()
setB.add(3)
setB.add(4)
setB.add(5)

const union = setA.union(setB)
console.log(union.values())
// [1, 2, 3, 4, 5]

注意元素3同时存在于setA和setB中，它在结果集合中只出现一次。

交集

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

intersection(otherSet) {
    const intersectionSet = new Set()

    const values = this.values()
    for (let i = 0; i < values.length; i++) {
        if (otherSet.has(values[i])) {
            intersectionSet.add(values[i])
        }
    }
    return intersectionSet
}

const setA = new Set()
setA.add(1)
setA.add(2)
setA.add(3)

const setB = new Set()
setB.add(3)
setB.add(4)
setB.add(5)

const intersection = setA.intersection(setB)
console.log(intersection.values())
// [3]

改进交集方法

假设我们有下面两个集合：

• setA的值为[1, 2, 3, 4, 5, 6, 7]
• setB的值为[4, 6]

使用我们创建的intersection方法，需要迭代七次setA的值，也就是setA中元素的个数，然后还要将这七个值和setB中的两个值进行比较。

如果我们只需要迭代两次setB就好了，更少的迭代次数意味着更少的过程消耗。那么就来优化代码，使得迭代元素的次数更少吧

intersection(otherSet) {
    const intersectionSet = new Set()

    const values = this.values()
    const otherValues = otherSet.values()

    let biggerSet = values;
    let smallerSet = otherValues;

    if (otherValues.length > values.length) {
        biggerSet = otherValues
        smallerSet = values
    }

    smallerSet.forEach(val => {
        if (biggerSet.includes(val)) {
            intersectionSet.add(val)
        }
    })
    
    return intersectionSet
}

差集

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

difference(otherSer) {
    const differenceSet = new Set()
    const values = this.values()

    values.forEach(val => {
        if (!otherSer.has(val)) {
            differenceSet.add(val)
        }
    })
    return differenceSet
}

const setA = new Set()
setA.add(1)
setA.add(2)
setA.add(3)

const setB = new Set()
setB.add(3)
setB.add(4)
setB.add(5)

const difference = setA.difference(setB)
console.log(difference.values())
// [1, 2]

子集

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

isSubsetOf(otherSet) {
    let isSubset = true

    this.values().forEach(val => {
        if (!otherSet.has(val)) {
            isSubset = false
            return false
        }
        return true
    })

    return isSubset
}

const setA = new Set()
setA.add(1)
setA.add(2)
setA.add(3)

const setB = new Set()
setB.add(1)
setB.add(2)
setB.add(3)

const setC = new Set()
setC.add(3)
setC.add(4)
setC.add(5)

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

我们有三个集合：setA是setB的子集（因此输出为true），然而setA不是setC的子集（setC只包含了setA中的2，而不包含1），因此输出为false。