JavaScript數據結構——集合的實現與應用
- 2019 年 10 月 3 日
- 筆記
與數學中的集合概念類似，集合由一組無序的元素組成，且集合中的每個元素都是唯一存在的。可以回顧一下中學數學中集合的概念，我們這裡所要定義的集合也具有空集（即集合的內容為空）、交集、並集、差集、子集的特性。
在ES6中，原生的Set類已經實現了集合的全部特性，稍後我們會介紹它的用法。
我們使用JavaSctipt的對象來表示集合，下面是集合類的主要實現方法：
class Set { constructor () { this.items = {}; } add (value) { // 向集合中添加元素 if (!this.has(value)) { this.items[value] = value; return true; } return false; } delete (value) { // 從集合中刪除對應的元素 if (this.has(value)) { delete this.items[value]; return true; } return false; } has (value) { // 判斷給定的元素在集合中是否存在 return this.items.hasOwnProperty(value); } clear() { // 清空集合內容 this.items = {}; } size () { // 獲取集合的長度 return Object.keys(this.items).length; } values () { // 返回集合中所有元素的內容 return Object.values(this.items); } }
在使用JavaScript對象{ }來表示集合時，我們可以像操作數組一樣通過[ ]來設置和獲取集合內元素的值。通過這種方式，在設置集合元素的值時，如果元素不存在，則創建一個新元素，如果元素存在，則修改對應的值；在獲取集合元素的值時，如果元素存在，則返回對應的值，如果元素不存在，則返回undefined。此外，JavaScript對象還提供了一些基礎方法以方便我們對集合進行一些操作，例如hasOwenProperty()方法返回一個表明對象是否具有特定屬性的布爾值，Object.keys()方法返回指定對象的所有屬性名稱的數組，Object.values()方法方法指定對象的所有屬性值的數組。
上述程式碼很簡單，這裡就不再詳細解釋了。下面是一些測試用例和測試結果：
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.delete(1); console.log(set.values()); // [ 2 ] set.delete(2); console.log(set.values()); // []
下面我們來看看集合的數學運算：並集、交集、差集、子集。
並集
對於給定的兩個集合，並集返回一個包含兩個集合中所有元素的新集合。示意圖如下：
並集的實現程式碼：
union (otherSet) { // 並集 let unionSet = new Set(); this.values().forEach(value => unionSet.add(value)); otherSet.values().forEach(value => unionSet.add(value)); return unionSet; }
首先遍歷第一個集合，將所有的元素添加到新集合中，然後再遍歷第二個集合，將所有的元素添加到新集合中。然後返回新集合。不用擔心會添加重複的元素，因為集合的add()方法會自動排除掉已添加的元素。
測試用例及結果：
let setA = new Set(); setA.add("first"); setA.add("second"); setA.add("third"); let setB = new Set(); setB.add("third"); setB.add("fourth"); setB.add("fifth"); setB.add("sixth"); console.log(setA.union(setB).values()); // [ 'first', 'second', 'third', 'fourth', 'fifth', 'sixth' ]
交集
對於給定的兩個集合，交集返回一個包含兩個集合中共有元素的新集合。示意圖如下：
交集的實現程式碼：
intersection (otherSet) { // 交集 let intersectionSet = new Set(); this.values().forEach(value => { if (otherSet.has(value)) intersectionSet.add(value); }); return intersectionSet; }
遍歷第一個集合，如果元素出現在第二個集合中，則將它添加到新集合。然後返回新集合。
測試用例及結果：
let setA = new Set(); setA.add("first"); setA.add("second"); setA.add("third"); let setB = new Set(); setB.add("second"); setB.add("third"); setB.add("fourth"); console.log(setA.intersection(setB).values()); // [ 'second', 'third' ]
差集
對於給定的兩個集合，差集返回一個包含所有存在於第一個集合且不存在於第二個集合的元素的新集合。示意圖如下：
差集的實現程式碼：
difference (otherSet) { // 差集 let differenceSet = new Set(); this.values().forEach(value => { if (!otherSet.has(value)) differenceSet.add(value); }); return differenceSet; }
遍歷第一個集合，如果元素沒有出現在第二個集合中，則將它添加到新集合。然後返回新集合。
測試用例及結果：
let setA = new Set(); setA.add("first"); setA.add("second"); setA.add("third"); let setB = new Set(); setB.add("second"); setB.add("third"); setB.add("fourth"); console.log(setA.difference(setB).values()); // [ 'first' ]
子集
驗證一個給定集合是否是另一個集合的子集，即判斷給定的集合中的所有元素是否都存在於另一個集合中，如果是，則這個集合就是另一個集合的子集，反之則不是。示意圖如下：
子集的實現程式碼：
subset (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; }
如果集合A比集合B的長度大，則直接返回false，因為這種情況A不可能是B的子集。然後使用every()函數遍歷集合A的所有元素，一旦碰到其中的元素沒有在集合B中出現，則直接返回false，並終止遍歷。這裡我們沒有使用forEach來遍歷集合A，是因為你無法根據某個條件來終止forEach循環。考慮下面這種情況：
var arr = ["first", "second", "third", "fourth"]; arr.forEach(item => { if(item === "third") return true; console.log(item); });
輸出結果是：
first second fourth
很顯然，這裡的return true語句並不能退出forEach循環，它只能保證本次循環中餘下的語句不被執行，而接下來其它的元素還是會被遍歷到。
在我們的subset()方法中，如果使用forEach語句，每一次都會遍歷集合中的所有元素，如果遇到其中的元素沒有在集合B中出現，就將isSubset變數的值設置為false，但並不能退出forEach，isSubset變數的值可能會被多次覆蓋。為了提高執行效率，推薦使用every()函數，它會遍歷集合中的元素，直到其中一個返回結果為false，就終止遍歷，並返回false，否則就遍歷所有的元素並返回true。有關every()函數的詳細介紹可以看這裡。與every()函數功能相似還有一個some()函數，它在遍歷集合的過程中，遇到返回結果為true時就終止遍歷，具體內容可以看這裡。
差集的測試用例及結果：
let setA = new Set(); setA.add("first"); setA.add("second"); let setB = new Set(); setB.add("first"); setB.add("second"); setB.add("third"); let setC = new Set(); setC.add("second"); setC.add("third"); setC.add("fourth"); console.log(setA.subset(setB)); // true console.log(setA.subset(setC)); // false
文章的開頭說過，ES6提供了原生的Set類，讓我們來看看它的一些使用方法：
let set = new Set(); set.add(1); set.add(2); set.add(3); console.log(set.values()); // [Set Iterator] { 1, 2, 3 } console.log(set.has(1)); // true console.log(set.size); // 2 set.delete(1); console.log(set.values()); // [Set Iterator] { 2, 3 } set.clear(); console.log(set.values()); // [Set Iterator] { }
和前面我們自定義的Set類稍微有一點不同，values()方法返回的不是一個數組，而是Iterator迭代器。另一個就是這裡的size是一個屬性而不是方法，其它部分都和我們前面定義的Set類相同。由於ES6的Set類不包含對集合的數學運算，我們可以按照前面我們提供的方法來對其進行擴充。有關ES6的Set類的詳細介紹可以看查看這裡。
下一章我們將介紹如何用JavaScript來實現字典和散列表。
