JavaScript資料結構——集合的實作與應用

　　與數學中的集合概念類似，集合由一組無序的元素組成，且集合中的每個元素都是唯一存在的。可以回顧一下中學數學中集合的概念，我們這裡所要定義的集合也具有空集（即集合的内容為空）、交集、并集、差集、子集的特性。

　　在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來實作字典和散清單。