『資料結構』集合 Set

前言

這週要帶各位認識的資料結構是「集合 Set」。在深入探索它之前先讓我們看一下他的數學概念，在裡頭集合是一組不同的物件（的集合）。

比如說，一個由大於或等於零的整數組成的自然數集合：Ｎ = {0, 1, 2, 3, 4, 5, …}。集合中的物件列表用{}包圍起來。

另一個概念為「空集」，不包含任何元素的集合。比如說： 20, 23 這兩個數字之間的質數集合，由於這兩數之間沒有質數（除了 1 和本身，沒有其他正因數的大於一的自然數），這個集合就是空集合。用 { } 表示。個人覺得本章節在資料結構中蠻重要的，特別是對於後端在資料庫存取時常用到這一個概念。

什麼是集合？

集合是由一組無序且唯一的項目組成的。這個資料結構使用了與有限集合相同的概念，但應用在電腦科學的資料結構中。你也可以把集合想成一個既沒有元素，也沒有順序的陣列。在數學中，集合也有聯集、焦急、差集，在接下來也會一一介紹操作。

建立一個集合

在 ES6 中，已經有 Set 的類別，~~終於遇到原生的資料結構了~~QAQ
不過以下我們還是自己寫一個會比較印象深刻！

這是我們的 Set 類別骨架：

1
2
3

function Set(){
  var items = {};
}

這裡有一個細節，我們使用的不是陣列而是物件，原因是 Java Script 的物件是不允許一個鍵指向兩個不同屬性，保證了元素都是唯一的。

開始宣告一些集合可用的方法：

add(value)：向集合添加一個新的項目。
remove(value)：從一個集合移除一個值。
has(value)：如果值在集合中，返回 true，反之 false。
clear()：移除集合中所有項目。
size()：返回集合所包含元素的數量。與陣列 length 相同。
values()：返回一個包含集合中所有值的陣列。

has(value)

1
2
3

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

既然我們用物件來存放集合的值，就可以使用 JS 的 in 運算子來驗證是否是物件的屬性。

==補充一個方法 obj.hasOwnProperty(prop)，它會返回一個布林值，指示物件自身屬性中（非繼承屬性）是否具有指定的屬性。==

add(value)

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

新增項目時，先檢查它是否存在於集合中。

==添加一個值的時候，把它同時當作鍵和值儲存，因為這樣有利於尋找這個值==

remove(value) & clear()

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

remove 方法中，我們會驗證給定的 value 是否存在於集合中。如果存在，就從集合中移除 value，返回 true，表示值被移除；否則返回 false。

既然用物件來存放集合的 items 物件，就可以使用 delete 運算子從 items 物件中移除屬性。

使用 Set 類別的範例如下：

1
2
3

var set = new Set();
set.add(1);
set.add(2);

出於好奇，如果執行以上程式碼之後，在主控台（ console.log ）輸出 items 變數，Google Chrome 就會輸出如下內容：
Object{ 1: 1, 2: 2 }
可以看到，這是一個有兩個屬性的物件。屬性名就是添加到集合的值同時它也是屬性值

如果想移除集合中的所有值，可以用 clear 方法：

1
2
3

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

要重設 items 物件，需要做的只是把一個空物件重新賦值給它。

size()

這裡會有三種實作方法。

第一種是使用一個 length 變數，每當使用 add 或 remove 方法時控制它。

第二種方法，使用 JavaScript 內建的 Object 類別的一個內建函數（ ECMAScript 5 以上版本）：

1
2
3

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

第三種方法是手動提取 items 物件的每一個屬性，紀錄屬性的個數並返回這個數字。這可以運行在每個瀏覽器，和之前的程式碼是等價的：

this.sizeLegacy = function(){
  var count = 0;
  for(var prop in items){
    if(items.hasOwnProperty(prop)){
      ++count;
    }
  }
  return count;
};

遍歷 items 物件的所有屬性，檢查它們是否是物件本身的屬性。如果是，就遞增 count 值，最後在方法結束再返回這數字。

不能簡單地使用 for-in 語句遍歷 items 物件的屬性，遞增 count 變數的值。還需要使用 has 方法，因為物件的原型包含了額外的屬性。

values()

1
2
3

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

使用 Set 類別

資料結構已經完成囉，看看怎麼使用它吧！

var 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"]

集合操作

對集合可以進行的操作如下：

聯集：給定的兩集合，返回一個包含兩個集合中所有元素的新集合。
交集：給定的兩集合，返回一個包含兩個集合中共有元素的新集合。
差集：給定的兩集合，返回一個包含所有存在於第一個集合且不存在於第二個集合的元素的新集合。
子集：驗證一個給定集合是否是另一集合的子集。

聯集

集合 A 和 B 的聯集，表示為 $ A\bigcup B $ ，定義如下：

$$ A\bigcup B = { x | x \in A \bigvee x \in B } $$

意思是 x （元素）存在於 A 中，或 x 存在於 B 中。

this.union = function(otherSet){
  var unionSet = new Set();

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

交集

意思是 x （元素）存在於 A 中，且 x 存在於 B 中。

this.intersection = function(otherSet){
  var intersectionSet = new Set();

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

差集

意思是 x （元素）存在於 A 中，且 x 不存在於 B 中。

this.difference = function(otherSet){
  var differenceSet = new Set();

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

子集

意思是集合 A 中的每一個 x （元素），也需要存在於 B 中。

this.subset = function(otherSet){
  if(this.size() > otherSet.size()){
    return false;
  } else {
    var values = this.values();
    for(let i=0; i<values.length; i++){
      if(!otherSet.has(values[i])){
        return false;
      }
    }
    return true;
  }
};

小結

這章學習了如何從頭實作與 ES6 中定義的類似的 Set 類別。我們還介紹了在其他程式語言的集合結構的實作中不常見的一些方法，例如：連擊、交集、差集..等。相較於前幾個主題，我們完成了較完善的實例！給自己一個掌聲 👏🏻