数据结构（四）集合

一种无序且唯一的数据结构

es6中有集合Set

集合的常见操作：去重、判断某元素是否在集合中、求交集

1. 定义

集合是由一组无序且唯一（即不能重复）的项组成的

2. 具体操作

创建

1
2
3
4
5
class Set {
	constructor() {
		this.items = {};  //使用对象来模拟
	}
}

方法

  • has(element)：如果元素在集合中，返回true，否则返回false

    1
    2
    3
    has(element) {
        return element in items;
    }
    1
    2
    3
    has(element) {
        return Object.prototype.hasOwnProperty.call(this.item, element);
    }

  • add(element)：向集合添加一个新元素

    1
    2
    3
    4
    5
    6
    7
    add(element) {
        if(!this.has(element)) {
            this.items[element] = element;
            return true;
        }
        return false;
    }

  • delete(element)：从集合移除一个元素

    1
    2
    3
    4
    5
    6
    7
    detele(element) {
        if(this.has(element)) {
            detele this.items[element];
            return true;
        }
        return false;
    }

  • clear()：移除集合中的所有元素

    1
    2
    3
    clear() {
        this.items = {};
    }

  • size()：返回集合所包含元素的数量。它与数组的length 属性类似

    方法一：和其他数据结构一样，直接使用length

    方法二：

    1
    2
    3
    size() {
        return Object.keys(this.items).length;
    }

    方法三：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    sizeLegacy() {
        let count = 0;
        for(let key in this.items) {
            if(this.items.hasOwnProperty(key)){
                count++;
            }
        }
        return count;
    }

  • values()：返回一个包含集合中所有值（元素）的数组

    1
    2
    3
    values() {
        return Object.values(this.items);
    }

    but Object.values()是ECMAScript 2017添加的，适用于现代浏览器中，等价于：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    valuesLegacy() {
        let values = [];
        for(let key in this.items) {
            if(this.items.hasOwnProperty(key)) {
                values.push(key);
            }
        }
        return values;
    }

3. 使用

1
2
3
4
5
6
7
8
9
10
11
12
13
const set = new Set();
set.add(1);
console.log(set.values()); // [1]
console.log(set.has(1)); // true
console.log(set.size()); // 1
set.add(2);
console.log(set.values()); // [1, 2]
console.log(set.has(2)); // true
console.log(set.size()); // 2
set.delete(1);
console.log(set.values()); // [2]
set.delete(2);
console.log(set.values()); // []
1
2
3
//去重
const arr = [1,1,2,2];
const arr2 = [...new Set(arr)];

4. 集合的运算

并集

1
2
3
4
5
6
union(otherSet) {
    const unionSet = new Set();
    this.values().forEach(value => unionSet.add(value));
    otherSet.values().forEach(value => unionSet.add(value));
    return unionSet;
}

交集

1
2
3
4
5
6
7
8
9
10
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;
}

优化一下，迭代AB集合中元素较少的那个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 > 0) { 
        biggerSet = otherValues;
        smallerSet = values;
    }
    smallerSet.forEach(value => { // 元素少的迭代次数少
        if (biggerSet.includes(value)) {
            intersectionSet.add(value);
        }
    });
    return intersectionSet;
}

差集

1
2
3
4
5
6
7
8
9
difference(otherSet) {
    const differenceSet = new Set();
    this.values().forEach(value => {
        if(!otherSet.has(value)) {
            differenceSet.add(value);
        }
    });
    return differenceSet;
}

子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
isSubsetOf(otherSet) {
    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;
}

5. 前端与集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
let mySet = new Set();

let o = {a:1, b:2};
mySet.add(o)
mySet.add({a:1, b:2});
mySet.add('text');

const has = mySet.has(o);

mySet.delete(o)

for(let item of mySet.keys()) console.log(item);
for(let item of mySet.value()) console.log(item);
for(let [key, value] of mySet.keys()) console.log(key, value);

const myArr =[...mySet];
const myArr = Array.from(mySet);

const mySet2 = new Set([1,2,3,4]);
const intersection = new Set([..mySet].filter(x => mySet2.has(x)));
const difference = new Set([..mySet].filter(x => !mySet2.has(x)));