javascript数据结构-Set集合与Map字典

本文最后更新于：8 个月前

本博客参考于洛伊安妮·格罗纳编著的javascript数据结构与算法第三版及codeWay老师视频或其他博客资料，在此对此表示感谢!
github仓库：https://github.com/hzx17/

集合

几乎每种编程语言中，都有集合结构。集合比较常见的实现方式是哈希表。

集合特点

  • 集合通常是由一组无序的、不能重复的元素构成。

  • 数学中常指的集合中的元素是可以重复的，但是计算机中集合的元素不能重复。

  • 集合是特殊的数组。

    • 特殊之处在于里面的元素没有顺序，也不能重复。
    • 没有顺序意味着不能通过下标值进行访问，不能重复意味着相同的对象在集合中只会存在一份。

封装集合

ES6 中的 Set 就是一个集合类，这里我们重新封装一个 Set 类，了解集合的底层实现。

Set集合的封装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
function Set() {
  // 集合属性,使用keys将其取出
    this.items = {}
  // 集合方法
  //添加方法
  Set.prototype.add = function(value) {
    // 判断当前集合中是否已经包含了该元素
    if(this.items.hasOwnProperty(value)){
      return false
    }else{
      this.items[value] = value
      return true
    }
  }
  // 元素是否存在于集合中
  Set.prototype.has = function(value) {
    return this.items.hasOwnProperty(value)
  }
  // remove方法
  Set.prototype.remove = function(value) {
    if(!this.items[value]){
      return false
    }
    // 使用delect操作符，删除元素
    delete this.items[value]
    return true
  }
  // 清除
  Set.prototype.clear = function () {
    this.items = {}
  }
  // 获取集合长度
  Set.prototype.size = function() {
    return Object.keys(this.items).length
  }
  // 获取集合中所有元素
  Set.prototype.values = function() {
    return Object.keys(this.items)
  }

  // 并集操作
  Set.prototype.union = function (otherSet) {
    // this:集合对象A
    // otherSet:集合对象B
    const unionSet = new Set()
    //将取出集合中所有元素,并放入集合A集合中
    let values = this.values()
    for(let i = 0 ;i < values.length ;i++) {
      unionSet.add(values[i])
    }
    values = otherSet.values()
    for(let i = 0;i<values.length ;i++) {
      unionSet.add(values[i])
    }
    return unionSet
  }
  //交集操作
  Set.prototype.intersection = function(otherSet) {
    // this: 为集合A
    // otherSet为集合B
    // 创建交集集合
    const intersectionSet = new Set()
    let valuesA = this.values()
    for(let i = 0;i<valuesA.length;i++) {
      if(otherSet.has(valuesA[i])){
        intersectionSet.add(valuesA[i])
      }
    }
    return intersectionSet
  }
  // 差集操作
  Set.prototype.difference = function(otherSet) {
    // 创建差集集合
    const differenceSet = new Set()
    // 将集合A（this)取出
    let values = this.values()
    for(let i= 0; i<values.length;i++) {
      if(!otherSet.has(values[i])){
        differenceSet.add(values[i])
      }
    }
    // 将集合B数据取出
    values = otherSet.values() 
    for(let i= 0; i<values.length;i++) {
      if(!this.has(values[i])){
        differenceSet.add(values[i])
      }
    }
    return differenceSet
  }
  // 判断一个集合是否属于另外一个集合
  Set.prototype.sub = function (otherSet) {
    if(this.size() < otherSet.size()){
      return false
    }
    let valuesB = otherSet.values()
    for(let i =0;i<valuesB.length ;i++) {
      if(!this.has(valuesB[i])){
        return false
      }
    }
    return true
  }
}

测试Set集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/* 测试Set集合类 */
// const set = new Set() //集合A
// const set1 = new Set() //集合B

// set1.add(4)
// set.add(1)
// set.add(2)
// // set.add("2")
// set.add(3)
// set.remove(3)
// // set.clear()
// console.log(set.union(set1).values()) //求并集
// console.log(set.values())
// console.log(set.size())

/* 测试交集 */
// const setA = new Set()
// const setB = new Set()

// setA.add('nba')
// setA.add('nbl')
// setA.add('cba')

// setB.add('nba')
// setB.add('cba')
// setB.add('dbba')
// setB.add('cuba')

// console.log(setA.values())
// console.log(setB.values())
// console.log(setA.intersection(setB))
/* 测试差集 */
// const setA = new Set()
// const setB = new Set()

// setA.add('nba')
// setA.add('nbl')
// setA.add('cba')

// setB.add('nba')
// setB.add('cba')
// setB.add('dbba')
// setB.add('cuba')

// console.log(setA.values())
// console.log(setB.values())
// console.log(setA.difference(setB))
/* 测试是否属于子集 */
const setA = new Set()
const setB = new Set()

setA.add('nba')
setA.add('nbl')
setA.add('cba')

setB.add('nba')

console.log(setA.values())
console.log(setB.values())
console.log(setA.sub(setB))

字典

字典特点

  • 字典存储的是键值对，主要特点是一一对应。
  • 比如保存一个人的信息
    • 数组形式：[19，"Tom", 1.65]，可通过下标值取出信息。
    • 字典形式：{"age": 19, "name": "Tom", "height": 165}，可以通过 key 取出 value。
  • 此外，在字典中 key 是不能重复且无序的，而 Value 可以重复。

字典和映射的关系

  • 有些编程语言中称这种映射关系为字典，如 Swift 中的 Dictonary，Python 中的 dict。
  • 有些编程语言中称这种映射关系为 Map，比如 Java 中的 HashMap 和 TreeMap 等。

在ES6中Map就是一个字典，可以尝试封装