前言

上一篇JavaScript 數(shù)據(jù)結(jié)構(gòu) 之集合創(chuàng)建(1)我們介紹了什么是集合，并且手動(dòng)實(shí)現(xiàn)了一個(gè)集合的類。簡單總結(jié)，集合就是一組元素唯一，并且沒有順序的數(shù)據(jù)集，關(guān)鍵是元素唯一。

ES6 提供了原生的集合支持，就是新增的 Set 數(shù)據(jù)類型。其實(shí)在上篇我們幾乎已經(jīng)實(shí)現(xiàn)了 Set 的所有功能，如果還不了解集合，請看上篇內(nèi)容

但是我們也說到，Set 的基本功能中不包含數(shù)學(xué)運(yùn)算如 交集，并集，差集，事實(shí)上這也是集合的一部分。本篇我們就要介紹這類集合的運(yùn)算。

一、集合運(yùn)算

集合在計(jì)算機(jī)世界中主要的應(yīng)用之一就是數(shù)據(jù)庫。比如在一個(gè)關(guān)系型數(shù)據(jù)庫當(dāng)中，我們常用的查詢，基本都是對一個(gè)或多個(gè)數(shù)據(jù)集合進(jìn)行篩選，合并，過濾等運(yùn)算。

比如你寫一條 SQL 語句，它可能是要獲取表中的所有數(shù)據(jù)，也可能是根據(jù)條件獲取一部分?jǐn)?shù)據(jù)，還有可能是關(guān)聯(lián)查詢，要一次性獲取多個(gè)表的數(shù)據(jù)。

根據(jù)不同的需求來決定集合如何處理，這在 SQL 中叫做聯(lián)接。SQL 聯(lián)接的基礎(chǔ)就是集合運(yùn)算。

我們對集合的元算包含如下幾個(gè)：

• 并集：給定兩個(gè)集合，返回包含兩個(gè)集合中所有元素的新集合
• 交集：給定兩個(gè)集合，返回包含共有元素的新集合
• 差集：給定兩個(gè)集合，返回第一個(gè)集合有，第二個(gè)集合沒有的元素的新集合
• 子集：驗(yàn)證一個(gè)集合是否是另一個(gè)集合的子集（一部分）

我們看相應(yīng)的如何實(shí)現(xiàn)。

1.并集

并集說白了就是包含兩個(gè)集合的所有元素但是不重復(fù)的集合。

其實(shí)也很好理解，我們在 Set 類的基礎(chǔ)上實(shí)現(xiàn)一個(gè) union 方法。

union(otherSet) {
  let unionSet = new Set()
  this.values().forEach(value=> unionSet.add(value))
  otherSet.values().forEach(value=> unionSet.add(value))
  return unionSet;
}

如上的實(shí)現(xiàn)方式，首先實(shí)例化一個(gè)新集合，然后分別將兩個(gè)集合的全部元素加入到新集合。因?yàn)榧显谔砑釉貢r(shí)會(huì)做重復(fù)校驗(yàn)，所以全部添加后新集合包含了所有元素，且不重復(fù)。

2.交集

交集就是兩個(gè)集合共有的元素組成的一個(gè)新集合，這個(gè)集合肯定是兩個(gè)集合的子集。

我們來實(shí)現(xiàn) intersection 方法：

intersection(otherSet) {
  let inters = new Set()
  let values = this.values()
  for(let i = 0; i < values.length; i++) {
    if(otherSet.has(values[i])) {
      inters.add(values[i])
    }
  }
  return inters;
}

這個(gè)實(shí)現(xiàn)方式和并集一樣，首先定義新的集合。只不過是在一個(gè)集合元素的遍歷中，判斷元素是否在另一個(gè)集合中，如果在則添加到新集合，這樣新集合就是一個(gè)交集。

改進(jìn)交集

功能實(shí)現(xiàn)了，我們再看另外一種情況。假設(shè)兩個(gè)集合如下：

• 集合 A：[1, 2, 3, 4, 5, 6, 7]
• 集合 B：[4, 7]

如果按照上面的方式，我們需要循環(huán)七次，才能得到交集。那有沒有辦法選擇長度更小的集合循環(huán)，并實(shí)現(xiàn)功能呢？

有啊，假設(shè)遍歷集合 B，只需要循環(huán)兩次。我們看如何改進(jìn)：

intersection(otherSet) {
  let inters = new Set();
  let bigvals = this.values()
  let lessvals = otherSet.values();
  if(bigvals.length < lessvals.length) {
    bigvals = otherSet.values();
    lessvals =  this.values()
  }
  for(let i = 0; i < lessvals.length; i++) {
    if(bigvals.includes(lessvals[i])) {
      inters.add(lessvals[i])
    }
  }
  return inters;
}

這種方式是先判斷哪個(gè)集合的長度更短，然后遍歷更短的那個(gè)集合，再判斷元素是否在另一個(gè)集合里，這樣就避免了多余的循環(huán)。

3.差集

差集是指元素存在于集合 A 中，但不存在于集合 B 中，也就是計(jì)算 A - B 的部分。

我們來實(shí)現(xiàn) Set 類的 different 方法：

different(otherSet) {
  let diffSet = new Set();
  this.values().forEach(value=> {
    if(!otherSet.has(value)) {
      diffSet.add(value)
    }
  })
  return diffSet;
}

從代碼中能看出來，差集與交集的實(shí)現(xiàn)邏輯正好相反。

4.子集

在數(shù)學(xué)概念中，如果集合 A 包含于集合 B，也就是說集合 A 中所有的元素集合 B 中都存在，那我們認(rèn)為集合 A 是集合 B 的子集。

從程序的角度來看，集合 A 是從集合 B 中過濾出來的一部分，那么集合 A 就是一個(gè)子集。

我們來實(shí)現(xiàn)子集的 isSubsetOf 方法：

isSubsetOf(otherSet) {
  let isSubset = true
  let values = otherSet.values()
  for(let i = 0; i < values.length; i++) {
    if(!this.has(values[i])) {
      isSubset = false; break;
    }
  }
  return isSubset;
}

這個(gè)方法是檢測參數(shù)集合中，是否每個(gè)元素都在實(shí)例集合中存在。如果有一個(gè)不存在，則表示參數(shù)集合不是子集，終止循環(huán)并返回結(jié)果。

其實(shí)還有更簡單的方法：

isSubsetOf(otherSet) {
  return otherSet.values().every(value=> this.has(value))
}

every 方法可以判斷是否每個(gè)元素是否都符合條件。如果符合就返回 true，否則返回 false。

二、使用集合運(yùn)算

上面完成了集合基本運(yùn)算的實(shí)現(xiàn)，現(xiàn)在我們來使用一下吧：

let setA = new Set()
setA.add('北京')
setA.add('上海')
setA.add('廣州')

let setB = new Set()
setB.add('北京')
setB.add('南京')
setB.add('武漢')

首先添加了兩個(gè)集合，然后用它們來測試基本元算：

let sets = setA.union(setB);
console.log(sets.values()); // ['北京', '上海', '廣州', '南京', '武漢']

let inters = setA.intersection(setB);
console.log(inters.values()); // ['北京']

let diffs = setA.different(setB);
console.log(diffs.values()); // ['上海', '廣州']

最后再測試一下子集：

let issub = setA.isSubsetOf(setB);
console.log(issub); // false

let setC = new Set();
setC.add("上海");
issub = setA.isSubsetOf(setC);
console.log(issub); // true

測試通過，完美實(shí)現(xiàn)！

三、總結(jié)

通過兩篇文章介紹了集合的相關(guān)知識(shí)，你學(xué)會(huì)了嗎？雖然 ES6 提供了原生支持，但是對于我們學(xué)習(xí)者來說，手動(dòng)實(shí)現(xiàn)一次更有助于了解原理。

到此這篇關(guān)于JavaScript 數(shù)據(jù)結(jié)構(gòu)之集合創(chuàng)建(2)的文章就介紹到這了,更多相關(guān)JavaScript集合內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論