集合，不允许值重复的顺序数据结构，类似Set数据结构。集合中主要关注点是值的本身。通过学习集合数据结构掌握增删查、交集、并集、差集等数学运算，学习ES6原生Set类，以及自己通过对象实现Set类

可以理解为ES6中的Set就是集合，存储形式是[值，值]

集合

集合是由一组无序且唯一（不能重复）的项组成的

模拟实现Set

构造函数声明

1
2
3
4
5
class Set {
    constructor () {
      this.items = {}
    }
}

判断元素是否存在has方法

1
2
3
has(element) {
  return Object.prototype.hasOwnProperty.call(this.items,element)
}

添加元素add方法

1
2
3
4
5
6
7
add(element) {
  if (!this.has(element)) {
    this.items[element] = element
    return true
  }
  return false
}

delete删除元素方法

1
2
3
4
5
6
7
8
delete (element) {
  if (this.has(element)) {
    delete this.items[element]
    return true
  }
  return false
}

clear清空方法、size返回元素长度、获取集合的所有values

1
2
3
4
5
6
7
8
9
10
11
12
clear () {
  this.items = {}
}
    
size() {
  return Object.keys(this.items).length
}

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

集合运算

集合是数学基础中的基础概念。在计算机领域主要的应用之一是数据库，比如我们去创建SQL查询命令时候，可以置顶去获取全部数据还是子集等，在SQL叫做连接，SQL连接的基础就是集合运算

并集

并集，同时保留A,B,但是相同部分只出现一次

1
2
3
let A = [1,2,3]
let B = [2,3,4]
A u B = [1,2,3,4] // 相同部分只出现一次

image
代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 实现并集，最关键的就是has方法，添加时候去重判断
union(otherSet) { // 接收一个其他集合，用来和当前的集合进行合并求并集
  // 新建一个集合用来保存返回结果
  const unionSet = new Set()
  // 通过values()获取当前元素所有的value,得到是一个数组，遍历数组，添加到新建的对象当中
  this.values().forEach(v => unionSet.add(v))
  // 传入的对象也一样,因为在添加时候实现了has方法，如果不存在才会被添加
  otherSet.values().forEach(v => unionSet.add(v))
  // 最后返回新建的这个集合
  return unionSet
}
// 测试并集
const setA = new Set()
setA.add(1)
setA.add(2)
setA.add(3)

const setB = new Set()
setB.add(2)
setB.add(3)
setB.add(4)
console.log(setA.union(setB))  // items: {1: 1, 2: 2, 3: 3, 4: 4}

交集

交集，只保留A和B中的公共相同部分。
和差集代码相反

1
2
3
4
let A = [1,2,3]
let B = [2,3,4]
A n B = [2,3] // 只保留相同部分

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
intersection (otherSet) {
  // 遍历元素,正常写法
  // const intersectionSet = new Set()
  // this.values().forEach((v) => {
  //   if (otherSet.has(v)) {
  //     intersectionSet.add(v)
  //   }
  // })
  // return intersectionSet
  // 优化写法,找到两个元素中长度较少的那一个去遍历
  const intersectionSet = new Set()
  let biggerSet = this.values()
  let smallerSet = otherSet.values()
  if (biggerSet.length < smallerSet.length) {
    biggerSet = otherSet.values()
    smallerSet = this.values()
  }
  smallerSet.forEach((v) => {
    if (biggerSet.includes(v)) {
      intersectionSet.add(v)
    }
  })
  return intersectionSet
}

差集

差集，元素只存在A，并且不存在B中。
和交集代码相反，多了一个取非

1
2
3
4
let A = [1,2,3]
let B = [2,3,4]
 A-B = [1] // 1只有A存在，并且不存在B中

image
代码实现

1
2
3
4
5
6
7
8
9
10
11
// 差集,元素只存在于A中，并且不存在B中
difference(otherSet) {
  const differenceSet = new Set()
  // 遍历元素A，找到B中不存在的
  this.values().forEach((v) => {
    if (!otherSet.has(v)) {
      differenceSet.add(v)
    }
  })
  return differenceSet
}

子集

子集，A ⊆ B,集合B包含集合A

1
2
3
4
let A = [1,2,3,4,5]
let B = [1,2,3]


代码实现

1
2
3
4
遍历短的.every



es6 Set

es6中的Set类似数组，所有成员的值都是唯一的，没有重复，本身就是是一个构造函数

Set常用方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const s = new Set()
s.add(1)
s.add(2) // 添加某个值
s.size // 2 返回成员总数
s.delete(value) // 删除某个值，表示是否删除成功
s.has(value) // 返回布尔值 表示是否为set成员
s.clear() // 清除所有成员。没有返回值

const s = new Set([1,2,3,4,5,6])
Array.from(s) //转化为数组

// 遍历操作
const s = new Set([9,8,7,6,5,4])
s.keys() // {9, 8, 7, 6, 5, …}
s.values() // 返回键值的遍历器 SetIterator {9, 8, 7, 6, 5, …}
s.entries() // 返回键值对遍历器 SetIterator {9 => 9, 8 => 8, 7 => 7, 6 => 6, 5 => 5, …}
s.forEach() // 遍历每一个成员

Set类实现模拟并集

1
2
3
4
5
6
7
8
9
// 实现并集
function union (setA,setB) {
    const unionAB = new Set()
    // 在之前模拟实现的那个Set，添加add时候已经做了has的判断
    setA.forEach(v => unionAB.add(v))
    setB.forEach(v => unionAB.add(v))
    return unionAB
}

Set类实现交集

1
2
3
4
5
6
7
8
9
10
// 实现交集
  function intersection (setA,setB) {
    const intersection = new Set()
    setA.forEach((v) => {
      if (setB.has(v)) {
        intersection.add(v)
      }
    })
    return intersection
  }

Set类实现差集

1
2
3
4
5
6
7
8
9
10
// 差集。元素只存在A，且不存在于B
  function difference (setA,setB) {
    const differenceSet = new Set()
    setA.forEach(v => {
      if (!setB.has(v)) {
        differenceSet.add(v)
      }
    })
    return differenceSet
  }

使用扩展运算符计算并集，交集，差集

1
2
3
4
console.log(new Set([...setA,...setB])) // 并集，因为会自动去重复，通过展开运算符展开
console.log(new Set([...setA]).filter(v => setB.has(v))) //并集
console.log(new Set([...setA]).filter(v => !setB.has(v))) // 差集