用 JavaScript 學習資料結構和演算法：集合（Set）篇

什麼是集合（Set）？

集合是一個源自於數學理論中擁有不同元素的集合：

N = {0, 1, 2, 3, 4, 5, 6, …}

空集合：{}

其特性在於它是由一組無序且不重複的項目組成。你也可以想成是一個沒有重複元素和無順序的陣列。在這篇文章我們會介紹如何實作集合資料結構並使用交集、聯集、差集等集合操作方式。

集合初體驗

事實上，在 ES6 中就有原生的 Set，在這邊我們試著使用 JavaScript 物件模仿 ES6 的 Set 設計集合資料結構（使用物件好處是物件 key 是唯一）。

The Set object lets you store unique values of any type, whether primitive values or object references.

建立集合類別和方法

function Set() {
	var items = {};
	this.add(value) {};
	this.remove(value) {};
	this.has(value) {};
	this.clear() {};
	this.size() {};
	this.values() {};
}

has(value)：判斷是否元素在集合中，若有回傳 true，反之傳回 false

this.has = function(value) {
	return items.hasOwnProperty(value);
	// 由於我們是使用 JavaScript 物件實作所以也可以使用 value in items
}

add(value)：新增元素到集合

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

remove(value)：刪除元素

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

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

1
2
3

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

size()：回傳集合元素數量

使用類似於 Linked List 的 length 變數計算法，當新增、刪除元素時順便增減長度

1
2
3

this.size = function() {
	return length;
}

使用 JavaScript 內建 Object 類別的內建函數 keys

1
2
3

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

手動迭代判斷是否存在集合中並累加個數

this.size = function() {
	let count = 0;
	// 特別注意在 JavaScript 中 for in 會一起把繼承於 Object 類別和物件自身的所有相關非相關資料結構的屬性一起迭代出來
	for(let prop in items) {
		// 判斷是否屬於 items 的屬性
		if(items.hasOwnProperty(prop)) {
			++count;
		}
		return count;
	}
}

values()：回傳集合所有值，使用 JavaScript 內建 Object 類別的內建函數 keys 以陣列形式回傳

1
2
3

this.values = function() {
	return Object.keys(items);
}

另外一種瀏覽器相容性較高的寫法

this.value = function() {
	let keys = [];
	for(let key in items) {
		keys.push(key);
	}
	return keys;
}

使用集合類別

const set = new Set();
set.add(12);
console.log(set.values());
console.log(set.has(12));
console.log(set.size());
set.add(12);
set.add(7);
set.remove(12);
set.add(1);
console.log(set.has(12));
console.log(set.values());
console.log(set.size());

集合操作

用 JavaScript 學習資料結構和演算法：集合（Set）篇

參考數學上的集合概念，我們可以針對集合進行以下操作：

聯集
對於給定兩集合，回傳一個包含兩個集合中所有元素的新集合

this.union = function(otherSet) {
	// 首先建立代表聯集的新集合
	let unionSet = new Set();
	let values = this.values();
	for(var i = 0; i < values.length; i++) {
		unionSet.add(values[i]);
	}
	values = otherSet.values();
	for(let j = 0; j < values.length; j++) {
		unionSet.add(values[i]);
	}
	return unionSet;
}

在 console 測試：

let setA = new Set();
setA.add(1);
setA.add(4);
setA.add(2);

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

let unionSet = setA.unique(setB);
console.log(unionSet);

交集
對於給定兩集合，回傳一個包含兩個集合中共有元素的新集合

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;
}

在 console 測試：

let setA = new Set();
setA.add(1);
setA.add(4);
setA.add(2);

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

let intersectionSet = setA.intersection(setB);
console.log(intersectionSet);

差集
對於給定兩集合，回傳一個包含所有存在第一個集合但不存在於第二集合的元素集合

this.difference = function(otherSet) {
	let differenceSet = new Set();
	let values = this.values();
	for(let i = 0; i < values; i++) {
		if(!otherSet.has(values[i])) {
			differenceSet.add(values[i]);
		}
	}
	return differenceSet;
}

在 console 測試：

let setA = new Set();
setA.add(1);
setA.add(4);
setA.add(2);

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

let differenceSet = setA.difference(setB);
console.log(differenceSet);

子集
驗證給定集合是否為另一個集合的子集

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;
		}
	}
}

在 console 測試：

let setA = new Set();
setA.add(1);
setA.add(4);
setA.add(2);

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

let subSet = setA.subSet(setB);
console.log(subSet);

總結

在這篇文章中我們學會了：

什麼是集合（Set）？
建立集合類別和方法
集合操作（聯集、交集、差集、子集）

TechBridge 技術共筆部落格

var topics = ['Web前後端', '行動網路', '機器人/物聯網', '數據分析', '產品設計', 'etc.']

用 JavaScript 學習資料結構和演算法：集合（Set）篇

什麼是集合（Set）？

集合初體驗

集合操作

總結

延伸閱讀

訂閱 TechBridge Weekly 技術週刊，每週發送最精華的技術開發、產品設計的資訊給您

留言討論