摘要：至于這三個(gè)的具體概念，可以看圖中集合的實(shí)現(xiàn)首先，創(chuàng)建一個(gè)構(gòu)造函數(shù)。前端路漫漫，且行且歌的前端樂(lè)園原文鏈接寒假前端學(xué)習(xí)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法三集合

本系列的第一篇文章: 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（一），棧與隊(duì)列
第二篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（二）：鏈表
第三篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（三）：集合
第四篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（四）：二叉搜索樹(shù)

說(shuō)起集合，就想起剛進(jìn)高中時(shí)，數(shù)學(xué)第一課講的就是集合。因此在學(xué)習(xí)集合這種數(shù)據(jù)結(jié)構(gòu)時(shí)，倍感親切。
集合的基本性質(zhì)有一條: 集合中元素是不重復(fù)的。因?yàn)檫@種性質(zhì)，所以我們選用了對(duì)象來(lái)作為集合的容器，而非數(shù)組。
雖然數(shù)組也能做到所有不重復(fù)，但終究過(guò)于繁瑣，不如集合。

集合的基本操作有交集、并集、差集等。這兒我們介紹JavaScipt集合中交集、并集、差集的實(shí)現(xiàn)。至于這三個(gè)的具體概念，可以看圖:

首先，創(chuàng)建一個(gè)構(gòu)造函數(shù)。

/**
 * 集合的構(gòu)造函數(shù)
 */
function Set() {
  /**
   * 集合元素的容器，以對(duì)象來(lái)表示
   * @type {Object}
   */
  var items = {};
}

集合需要有如下方法:

has(value): 檢測(cè)集合內(nèi)是否有某個(gè)元素

add(value): 給集合內(nèi)添加某個(gè)元素

remove(value): 移除集合中某個(gè)元素

clear(value): 清空集合

size(): 返回集合長(zhǎng)度

values(): 返回集合轉(zhuǎn)換的數(shù)組

union(otherSet): 返回兩個(gè)集合的并集

intersection(otherSet): 返回兩個(gè)集合的交集

difference(otherSet): 返回兩個(gè)集合的差集

subset(otherSet): 判斷該集合是否為傳入集合的子集

說(shuō)明:集合中元素是不重復(fù)的。所以在其它任何操作前，必須用has方法確認(rèn)集合是否有某個(gè)元素。這兒使用了hasOwnProperty方法來(lái)檢測(cè)。
實(shí)現(xiàn):

/**
 * 檢測(cè)集合內(nèi)是否有某個(gè)元素
 * @param  {Any}  value    要檢測(cè)的元素
 * @return {Boolean}       如果有，返回true
 */
this.has = function(value) {
  // hasOwnProperty的問(wèn)題在于
  // 它是一個(gè)方法，所以可能會(huì)被覆寫(xiě)
  return items.hasOwnProperty(value)
};

說(shuō)明: 給集合內(nèi)添加某個(gè)元素。
實(shí)現(xiàn):

/**
 * 給集合內(nèi)添加某個(gè)元素
 * @param {Any} value 要被添加的元素
 * @return {Boolean}       添加成功返回True。
 */
this.add = function(value) {
  //先檢測(cè)元素是否存在。
  if (!this.has(value)) {
    items[value] = value;
    return true;
  }
  //如果元素已存在則返回false
  return false;
};

說(shuō)明: 移除集合中某個(gè)元素
實(shí)現(xiàn):

/**
 * 移除集合中某個(gè)元素
 * @param  {Any} value 要移除的元素
 * @return {Boolean}       移除成功返回True。
 */
this.remove = function(value) {
  //先檢測(cè)元素是否存在。
  if (this.has(value)) {
    delete items[value];
    return true;
  }
  //如果元素不存在，則刪除失敗返回false
  return false;
};

說(shuō)明: 清空集合
實(shí)現(xiàn):

/**
 * 清空集合
 */
this.clear = function() {
  this.items = {};
};

說(shuō)明: 返回集合長(zhǎng)度，這兒有兩種方法。第一種方法使用了Object.keys這個(gè)Api，但只支持IE9及以上。第二種則適用于所有瀏覽器。
實(shí)現(xiàn):

/**
 * 返回集合長(zhǎng)度，只可用于IE9及以上
 * @return {Number} 集合長(zhǎng)度
 */
this.size = function() {
  // Object.keys方法能將對(duì)象轉(zhuǎn)化為數(shù)組
  // 只可用于IE9及以上，但很方便
  return Object.keys(items).length;
}

/**
 * 返回集合長(zhǎng)度，可用于所有瀏覽器
 * @return {Number} 集合長(zhǎng)度
 */
this.sizeLegacy = function() {
  var count = 0;
  for (var prop in items) {
    if (items.hasOwnProperty(prop)) {
      ++count;
    }
  }
  return count;
}

說(shuō)明: 返回集合轉(zhuǎn)換的數(shù)組，這兒也有兩種方法。理由同上。使用了Object.keys，只能支持IE9及以上。
實(shí)現(xiàn):

/**
 * 返回集合轉(zhuǎn)換的數(shù)組，只可用于IE9及以上
 * @return {Array} 轉(zhuǎn)換后的數(shù)組
 */
this.values = function() {
  return Object.keys(items);
};

/**
 * 返回集合轉(zhuǎn)換的數(shù)組，可用于所有瀏覽器
 * @return {Array} 轉(zhuǎn)換后的數(shù)組
 */
this.valuesLegacy = function() {
  var keys = [];
  for (var key in items) {
    keys.push(key)
  };
  return keys;
};

說(shuō)明: 返回兩個(gè)集合的并集
實(shí)現(xiàn):

/**
 * 返回兩個(gè)集合的并集
 * @param  {Set} otherSet 要進(jìn)行并集操作的集合
 * @return {Set}          兩個(gè)集合的并集
 */
this.union = function(otherSet) {
  //初始化一個(gè)新集合，用于表示并集。
  var unionSet = new Set();
  //將當(dāng)前集合轉(zhuǎn)換為數(shù)組，并依次添加進(jìn)unionSet
  var values = this.values();
  for (var i = 0; i < values.length; i++) {
    unionSet.add(values[i]);
  }

  //將其它集合轉(zhuǎn)換為數(shù)組，依次添加進(jìn)unionSet。
  //循環(huán)中的add方法保證了不會(huì)有重復(fù)元素的出現(xiàn)
  values = otherSet.values();
  for (var i = 0; i < values.length; i++) {
    unionSet.add(values[i]);
  }

  return unionSet;
};

說(shuō)明: 返回兩個(gè)集合的交集
實(shí)現(xiàn):

/**
 * 返回兩個(gè)集合的交集
 * @param  {Set} otherSet 要進(jìn)行交集操作的集合
 * @return {Set}          兩個(gè)集合的交集
 */
this.intersection = function(otherSet) {
  //初始化一個(gè)新集合，用于表示交集。
  var interSectionSet = new Set();
  //將當(dāng)前集合轉(zhuǎn)換為數(shù)組
  var values = this.values();
  //遍歷數(shù)組，如果另外一個(gè)集合也有該元素，則interSectionSet加入該元素。
  for (var i = 0; i < values.length; i++) {

    if (otherSet.has(values[i])) {
      interSectionSet.add(values[i])
    }
  }

  return interSectionSet;
};

說(shuō)明: 返回兩個(gè)集合的差集
實(shí)現(xiàn):

/**
 * 返回兩個(gè)集合的差集
 * @param  {Set} otherSet 要進(jìn)行差集操作的集合
 * @return {Set}          兩個(gè)集合的差集
 */
this.difference = function(otherSet) {
  //初始化一個(gè)新集合，用于表示差集。
  var differenceSet = new Set();
  //將當(dāng)前集合轉(zhuǎn)換為數(shù)組
  var values = this.values();
  //遍歷數(shù)組，如果另外一個(gè)集合沒(méi)有該元素，則differenceSet加入該元素。
  for (var i = 0; i < values.length; i++) {

    if (!otherSet.has(values[i])) {
      differenceSet.add(values[i])
    }
  }

  return differenceSet;
};

說(shuō)明: 判斷該集合是否為傳入集合的子集。這段代碼在我自己寫(xiě)完后與書(shū)上一比對(duì)，覺(jué)得自己超級(jí)low。我寫(xiě)的要遍歷數(shù)組三次，書(shū)上的只需要一次，算法復(fù)雜度遠(yuǎn)遠(yuǎn)低于我的。
實(shí)現(xiàn):

/**
 * 判斷該集合是否為傳入集合的子集
 * @param  {Set} otherSet 傳入的集合
 * @return {Boolean}      是則返回True
 */
this.subset = function(otherSet) {
  // 第一個(gè)判定,如果該集合長(zhǎng)度大于otherSet的長(zhǎng)度
  // 則直接返回false
  if (this.size() > otherSet.size()) {
    return false;
  } else {
    // 將當(dāng)前集合轉(zhuǎn)換為數(shù)組
    var values = this.values();

    for (var i = 0; i < values.length; i++) {

      if (!otherSet.has(values[i])) {
        // 第二個(gè)判定。只要有一個(gè)元素不在otherSet中
        // 那么則可以直接判定不是子集，返回false
        return false;
      }
    }

    return true;
  }
};

源代碼在此~

集合-源代碼

ES6也提供了集合，但之前看ES6的集合操作一直迷迷糊糊的。實(shí)現(xiàn)一遍后再去看，感覺(jué)概念清晰了很多。
具體的我掌握的不是很好，還在學(xué)習(xí)中，就不寫(xiě)出來(lái)啦~推薦看阮一峰老師的《ECMAScript 6入門(mén)》中對(duì)ES6 Set的介紹。

《ECMAScript 6入門(mén)》-- Set和Map數(shù)據(jù)結(jié)構(gòu)

到了這兒，已經(jīng)掌握了一些基本的數(shù)據(jù)結(jié)構(gòu)。剩下的都是難啃的骨頭了(對(duì)我而言)。

字典的散列表、圖、樹(shù)、排序算法。算是四大金剛，所以近期關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法系列的文章，可能會(huì)更新的很慢。對(duì)我來(lái)說(shuō)，也算是一個(gè)坎。希望這個(gè)寒假，能跨過(guò)這個(gè)坎。

前端路漫漫，且行且歌~

Lxxyx的前端樂(lè)園
原文鏈接：寒假前端學(xué)習(xí)(5)——學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（三）：集合