JavaScript 数据结构之集合创建(1)

引言：

集合这一概念广为人知，多数人在编码之前便已了解。回顾高一数学教材，第一章即涉及此概念，定义如下：

通常，我们将考察的对象统称为元素，由若干元素构成的整体称为集合。

可见，集合与元素的概念与我们今日探讨的数据结构紧密相连。

一、集合的定义

集合由一组无序且互异（不可重复）的元素构成。在数据结构领域，集合对应数学中的有限集概念。

在数学表达中，若需展示城市集合，书写方式如下：

N = {北京, 上海, 深圳, 广州}
复制代码

映射至 JavaScript 语言，这等同于一个基础数组：

var cities = ['北京', '上海', '深圳', '广州']

数学中存在空集概念，以 {} 符号表示，对应 JavaScript 中的空数组 []。

集合的关键区别在于，此前学习的栈、队列及链表均属于有序集合，而集合则属于罕见的无序集合数据结构。

鉴于集合具备唯一性与无序性，无法通过下标定位元素。无序集合的唯一标识即元素自身的值。

JavaScript ES6 标准提供了对标集合的数据类型 Set。Set 支持存储任意类型的唯一值，这正是集合的具体实现。

数学集合包含交集、并集及差集等基本运算，本篇也将实现这些功能。

接下来，我们将手动实现一个 Set 类。

二、构建集合类

我们继续使用 class 语法构建基本框架：

class Set {
  constructor() {
    this.items = {};
  }
}

遵循栈与队列的设计原则，使用对象存储集合元素最为适宜。此外，基于元素的唯一性，对于基本类型元素，可直接以元素值作为对象 Key，而非使用 0,1,2...。

以下是需要声明的方法列表：

• add：向集合插入新元素
• delete：从集合移除指定元素
• has：判断元素是否存在于集合
• clear：清空集合内容
• size：获取集合元素数量
• values：返回包含集合所有元素的数组

1. has 方法实现

首先实现 has 方法，因为 add、delete 等方法均依赖此方法。

该方法用于检测指定元素是否存在，存在则返回 true，否则返回 false。

has(item) {
  return item in this.items;
}

如前所述，我们直接使用元素值作为对象 key，因此可直接利用 JavaScript ES6 提供的 in 运算符来检测属性是否存在。

另一种传统实现方式如下，效果与上述一致：

has(item) {
  return Object.prototype.hasOwnProperty.call(this.items, item);
}

2. add 方法实现

基于 has 方法，add 方法的实现较为直观：

add(item) {
  if(this.has(item)) {
    return false;
  }
  this.items[item] = item
  return true
}

为确保元素唯一性，添加前需判断元素是否已存在，若存在则跳过，不存在则执行添加。

3. delete 与 clear 方法实现

这两个方法均涉及元素删除，前者移除单个元素，后者移除全部元素。

// 删除
delete(item) {
  if(this.has(item)) {
    delete this.items[item]
    return true
  }
  return false
}
// 清空
clear(item) {
  this.item = {}
}

实现较为简单，直接删除或清空对象属性即可。

4. size 方法实现

size 方法旨在返回集合长度（元素个数），实现方式多样。

方式一：沿用栈、队列及链表的实现逻辑，使用属性 count 记录长度，并在添加或删除时更新该属性值。

方式二：直接调用 ES6 的 Object.keys 方法获取属性数组，进而获取数组长度：

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

鉴于第二种方法更为简洁，故采用此方案。

5. values 方法实现

与 size 方法类似，可直接获取对象属性值的数组：

values() {
  return Object.values(this.items)
}

三、集合的使用示例

前文已手动实现集合类，此处演示具体用法：

var set = new Set()
set.add('北京')
set.add('北京')
set.add('上海')
set.add('上海')
// 打印结果
console.log(set.size()) // 2
console.log(set.values()) // ['北京','上海']

添加功能检测无误，接下来验证删除功能：

console.log(set.has('上海')); // true
console.log(set.has('成都')); // false
set.delete('上海');
console.log(set.values()); ['北京']
console.log(set.has('上海')); // false

删除功能运行正常，实现完美！

总结

本篇手动实现了集合的基本功能，下一节将在此基础上实现集合的基本运算。

至此，关于 JavaScript 数据结构之集合创建的文章介绍完毕，更多相关 JavaScript 集合内容请查阅本站往期文章或继续浏览后续文章，希望大家日后多多支持本站！