本系列所有文章：

第一篇文章：

第二篇文章：

第三篇文章：

第四篇文章：

第五篇文章：

集合简介

记得高一数学第一节课学的就是集合，现在快大四了再看到它有种见了老朋友的感觉。哈哈，闲话不多扯，进入正题。

集合是由一组无序且不重复的项组成的数据结构。这里集合的概念和高中数学类似，也有空集，交集，并集，子集等概念，只不过在这里就没有那么复杂的证明题了。那么接下来就用JavaScript实现一下集合。

用JavaScript实现集合

老规矩，先弄一个构造函数出来

function Set () {  // 这里用对象来模拟集合  var items = {}}

集合要实现以下方法：

• add(value)：向集合添加新的项
• remove(value)：从集合删除一项
• has(value)：如果集合中存在该项则返回true，否则返回false
• clear()：清除集合中的所有项
• size()：返回集合包含元素的数量
• values()：返回集合中所有值的数组

实现has

根据hasOwnProperty判断该元素是否属于集合，注意：hasOwnProperty可以检查属性是否属于对象，对于原型链上的属性hasOwnProperty会返回false

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

实现add

这里添加新的元素到集合中时，首先要保证该元素不存在于集合中。

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

实现remove

删除前也要先判断元素是否存在

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

实现values

Object.keys的作用是返回对象中所有可枚举属性组成的数组（不包括原型链上的属性）。当然，你也可以用for...in 来实现。

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

实现clear和size

比较简单，就直接贴源码了

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

实现集合操作

集合有以下操作：

• 并集
• 交集
• 差集
• 子集

具体的就不多解释了，请看代码

实现并集

创建一个新集合unionSet表示两个集合的并集，之后分别遍历两个集合添加进unionSet，最后返回集合

this.union = function (otherSet) {  var unionSet = new Set()    var values = this.values()  for (var i = 0; i < values.length; i++) {    unionSet.add(values[i])  }    values = otherSet.values()  for (var i = 0; i < values.length; i++) {    unionSet.add(values[i])  }  return unionSet}

实现交集

交集是两者都有的属性的集合，实现思路与上面类似，只要判断元素是否同时存在与两个集合就行了

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

实现差集

差集A-B的意思是：元素只在集合A中存在，集合B中不存在，因此实现也很简单。

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

实现子集

数学中A是B的子集意味着A中的所有元素都存在于B中，按照这个思路实现代码如下

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

放上源代码，有兴趣的可以看看：

小结

到目前为止，比较简单的数据结构基本都掌握了，后面就是字典、散列表、树、图以及排序算法了，都是难啃的骨头，但是必须要啃下来。继续加油～