聊聊集合与数组的区别 | 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' 应该是不同的,所以我们采用两个对象来区分数字值和字符串值,然后对 nullundefined 也做一下特殊的处理

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

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

我们使用集合很少会依赖他按序遍历的功能,当我们的遍历需要依赖一定顺序时,理应换用数组来操作。真要实现按序遍历也就是再内置一个数组记录顺序,但在删除元素时就会更加耗时。

至于集合存放对象的功能,想要实现一个通用的 转换对象为基础类型的方法 非常麻烦,使用 JSON.stringify 又会出现正则、时间、克隆对象的问题,索性就不实现了。

取而代之我们建议在使用时应该为每个对象定义一个自增的 id 属性,集合仅存储操作 id

至于 ES6 的集合是如何实现以上功能的,我们知道 js 的底层是 C++
C++ 中有一个取地址操作,可以轻易的将任何数据类型与数字地址互转,同时还确保了唯一性。
对于数字的添加删除,可以轻松实现按序遍历的要求

结语

如果文中有不理解或不严谨的地方,欢迎评论提问。

如果喜欢或有所帮助,希望能点赞关注,鼓励一下作者。

你可能感兴趣的