学习《JavaScript 数据结构与算法》读书笔记

6 集合

6.1 构建数据集合

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

6.2 创建集合

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

这里我们使用对象而不是数组来表示集合（items），但也可以使用数组实现。
JavaScript 的对象不允许一个键指向两个不同的属性，也保证了集合里的元素都是唯一的。

接下来，需要声明一些集合可用的方法（我们会尝试模拟与 ECMAScript6 实现相同的 Set 类）

6.2.1 has(value) 方法

1
2
3
this.has = function(value) {
	return value in items;
};

既然我们使用对象来存储集合的值，就可以用JavaScript的 in 操作符来验证给定的值是否是 items 对象的属性

1
2
3
this.has = function(value) {
	return items.hasOwnProperty(value);
};

6.2.2 add方法

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

添加一个值的时候，把它同时作为键和值保存，因为这样有利于查找这个值。

6.2.3 remove 和 clear 方法

1
2
3
4
5
6
7
8
9
10
11
this.remove = function(value) {
	if (this.has(value)) {
		delete items[value];
		return true;
	}
	return false;
};

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

6.2.4 size 方法

这种方法有三种实现方式

第一种方法

使用一个 length 变量，每次使用 add 或 remove 方法时控制它。

第二种方法

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

第三种方法

遍历 items 对象的所有属性，检查它们是否是对象自身的属性（避免重复计数）。

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

不能简单地使用 for-in 语句遍历 items 对象的属性，还需要使用 hasOwnProperty 方法。因为对象的原型包含了额外的属性（属性既有继承自JavaScript的 Object 类的，也有属于对象自身的，未用于数据结构的）。

6.2.5 values 方法

1
2
3
4
5
6
7
this.values = function() {
	let values = [];
	for (let i = 0, key = Object.keys(items); i < keys.length; i++) {
		values.push(items[keys[i]]);
	}
	return values;
};
1
2
3
4
5
6
7
8
9
this.valuesLegacy = function() {
	let values = [];
	for (let key in items) {
		if (items.hasOwnProperty(key)) {
			values.push(items[key]);
		}
	}
	return values;
}

6.2.6 使用 Set 类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let 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.remove(1);
console.log(set.values()); /* ["2"] */

set.remove(2);
console.log(set.values()); /* [] */

6.3 集合操作

6.3.1 并集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
this.union = function(otherSet) {
	let 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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

let setB = new Set();
setB.add(3);
setB.add(4);
setB.add(5);
setB.add(6);

let unionAB = setA.union(setB);
console.log(unionAB.values()); /* ["1", "2", "3", "4", "5", "6"] */

6.3.2 交集

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

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

	return intersectionSet;
}
1
2
3
4
5
6
7
8
9
10
11
12
let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

let setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);

let intersectionAB = setA.intersection(setB);
console.log(intersectionAB.values()); /* ["2", "3"] */

6.3.3 差集

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

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

	return differenceSet;
}
1
2
3
4
5
6
7
8
9
10
11
12
let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

let setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);

let differenceAB = setA.difference(setB);
console.log(differenceAB); /* ["1"] */

6.3.4 子集

1
2
3
4
5
6
7
8
9
10
11
12
13
this.subset = function(otherSet) {
	if (this.size() > otherSet.size()) {
		return false;
	} else {
		let values = this.values();
		for (let i = 0; i < values.length; i++) {
			if (!otherSet.has(values[i])) {
				return false;
			}
		}
		return true;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let setA = new Set();
setA.add(1);
setA.add(2);

let setB = new Set();
setB.add(1);
setB.add(2);
setB.add(3);

let setC = New Set();
setC.add(2);
setC.add(3);
setC.add(4);

console.log(setA.subset(setB)); /* true */
console.log(setA.subset(setC)); /* false */

6.4 ES6 Set 类

1
2
3
4
5
let set = new Set();
set.add(1);
console.log(set.values()); /* @Iterator */
console.log(set.has(1)); /* true */
console.log(set.size); /* 1 */

和之前写的 Set 不同， ES6的 Set 的 values 方法返回 Iterator ，而不是值构成的数组。另一个区别是，我们的 size 方法返回 set 中存储的值的个数，而ES6的 Set 则有一个 size 属性。

ES6 Set 类的操作

1
2
3
4
5
6
7
8
9
let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

let setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);

1. 模拟并集操作

1
2
3
let unionAB = new Set();
for (let x of setA) unionAB.add(x);
for (let x of setB) unionAB.add(x);

2.模拟交集操作

1
2
3
4
5
6
7
8
9
10
let intersection = function(setA, setB) {
	let intersectionSet = new Set();
	for (let x of setA) {
		if (setB.has(x)) {
			intersectionSet.add(x);
		}
	}
	return intersectionSet;
};
let intersectionAB = intersection(setA, setB);

也可以使用更简单的语法实现

1
intersectionAB = new Set([x for (x of setA) if (setB.has(x))]);

3.模拟差集操作

1
2
3
4
5
6
7
8
9
10
let difference = function(setA, setB) {
	let differenceSet = new Set();
	for (let x of setA) {
		if (!setB.has(x)) {
			differenceSet.add(x);
		}
	}
	return differenceSet;
};
let differenceAB = difference(setA, setB);

依然可以使用更简单的语法实现

1
differenceAB = new Set([x for (x of setA) if (!setB.has(x))]);

原书备注“目前只有Firefox支持简化语法，但在所有支持ES6的现代浏览器中都以执行普通函数”

但是我在以下浏览器全部运行失败

Google Chrome Version 74.0.3729.169 (Official Build) (64-bit)

Google Chrome Version 76.0.3809.2 (Official Build) canary (64-bit)

Firefox Developer Edition Version 68.0b6 (64-bit)