聊聊集合与数组的区别 | JS 集合的实现

数组与集合的区别

Set 是 ES6 的新增的数据结构，和数组一样，也用来存储值

大多数人认为二者最大的区别是集合存值的唯一性

但这其实远不足以使集合闻名，真正让集合成为一种新数据结构的是其另一优点

集合在检查值是否存在时要远超数组

下面这段代码对集合的 has 方法与数组的 includes 方法进行了测试

const fun = (n) => {
  const arr = new Array(n).fill(0).map((_, i) => i)
  const set = new Set(arr)

  console.time('set')
  for (let i = 0; i < n; i++) {
    set.has(n + 1)
  }
  console.timeEnd('set')

  console.time('arr')
  for (let i = 0; i < n; i++) {
    arr.includes(n + 1)
  }
  console.timeEnd('arr')
}
fun(10 ** 2)
// set: 0.012939453125 ms
// arr: 0.01904296875 ms
fun(10 ** 3)
// set: 0.058837890625 ms
// arr: 1.070068359375 ms
fun(10 ** 4)
// set: 0.38818359375 ms
// arr: 105.847900390625 ms
fun(10 ** 5)
// set: 5.6337890625 ms
// arr: 592.424072265625 ms

如果掘友复制上面的代码直接执行得到的结果可能与注释相差甚远。这是因为浏览器在频繁处理数组时，会对其进行优化。以上的数据每次仅执行一个 fun 时得出的，只是为了方便写在了一起。

基于以上优点，在不需要数字索引检索的场合，大多时候都是用集合来存储数据

然而集合是 ES6 才推出的数据结构，一些库为了兼容较老的浏览器，并不能直接使用集合，需要自己去实现

接下来介绍一下如何实现集合

集合的实现

我们知道，对象在检查其属性是否存在时也很快，而且对象的属性也具有唯一性

所以我们使用对象来实现集合，把集合的值作为对象的属性存储起来

因为对象的属性会被转换成字符串，1 与 '1' 应该是不同的，所以我们采用两个对象来区分数字值和字符串值，然后对 null 和 undefined 也做一下特殊的处理

下面代码实现了集合的功能

function MySet(iterator) {
  this.stringSet = {}
  this.numberSet = {}
  this.__undefined__ = false
  this.__null__ = false
  iterator.forEach((value) => {
    this.add(value)
  })
}
// 添加元素
MySet.prototype.add = function (value) {
  if (typeof value === 'string') {
    this.stringSet[value] = true
  } else if (typeof value === 'number') {
    this.numberSet[value] = true
  } else if (value === undefined) {
    this.__undefined__ = true
  } else if (value === null) {
    this.__null__ = true
  }
}
// 删除元素
MySet.prototype.delete = function (value) {
  if (typeof value === 'string') {
    this.stringSet[value] = false
  } else if (typeof value === 'number') {
    delete this.numberSet[value]
  } else if (value === undefined) {
    this.__undefined__ = false
  } else if (value === null) {
    this.__null__ = false
  }
}
// 检测元素是否存在
MySet.prototype.has = function (value) {
  if (typeof value === 'string') {
    return !!this.stringSet[value]
  } else if (typeof value === 'number') {
    return !!this.numberSet[value]
  } else if (value === undefined) {
    return this.__undefined__
  } else if (value === null) {
    return this.__null__
  }
}

有时也需要遍历集合，所以也实现一个 values 方法

MySet.prototype.values = function () {
  var arr = []
  if (this.__null__) arr.push(null)
  if (this.__undefined__) arr.push(undefined)
  for (var num in this.numberSet) {
    arr.push(parseFloat(num))
  }
  for (var str in this.stringSet) {
    arr.push(str)
  }
}

至此我们的集合就实现完成了

与 ES6 的集合有两点不同

• values 方法应该按元素的插入顺序返回元素的迭代器，为了方便我们就只返回了一个数组，也与插入顺序无关。
• 集合应该允许插入任何数据，我们的集合只能插入基础数据类型。