爱囡囡，爱前端

0%

TypeScript数据结构与算法：字典

发表于 分类于 ， ，

上一篇《TypeScript 数据结构与算法：集合》实现了 Typescript 中集合的数据结构与算法，本篇继续实现 字典。

上一篇中实现的集合是表示一组互不相同的元素（不重复的元素）。但是在字典（Dictionary）中，存储的是键值对，其中键名是用来查询特定元素的，值就是被查询的特定元素。字典也称作映射、符号表或关联数组。在计算机科学中，字典经常用来保存对象的引用地址。

数据结构

其实字典和 JS 中的 Object 数据类型非常类似，所以可以用 Object 来封装一个 Dictionary。但是在 ES2015 中，已经原生实现了更先进和专用的 Map 数据结构，所以可以通过 Map 来封装 Dictionary 类。

一个字典中，应该有以下方法：

  • set(key,value)：向字典中添加键值对。
  • remove(key)：从字典中删除键值对。
  • hasKey(key)：返回某个键是否存在。
  • get(key)：返回字典中键对应的值。
  • clear()：清空字典。
  • size()：返回字典中键值对的数量。
  • isEmpty()：返回字典是否为空。
  • keys()：返回字典的键数组。
  • values()：返回字典的值数组。
  • keyValues()：返回字典的 [键, 值] 数组。
  • forEach(callbackFn)：迭代字典中所有的键值对。callbackFn 有两个参数：key 和 value。该方法可以在回调函数返回 false 时被中止。
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
export default class Dictionary<K, V> {
  private table: Map<K, V>;

  constructor() {
    this.table = new Map();
  }

  /**
   * @description: 设置键值对
   * @param {K} key
   * @param {V} value
   * @return {boolean}
   */
  set(key: K, value: V): boolean {
    this.table.set(key, value);
    return true;
  }

  /**
   * @description: 根据键取值
   * @param {K} key
   * @return {V}
   */
  get(key: K): V {
    return this.table.get(key);
  }

  /**
   * @description: 返回是否有此键
   * @param {K} key
   * @return {boolean}
   */
  hasKey(key: K): boolean {
    return this.table.has(key);
  }

  /**
   * @description: 移除键值对
   * @param {K} key
   * @return {boolean}
   */
  remove(key: K): boolean {
    return this.table.delete(key);
  }

  /**
   * @description: 返回值数组
   * @return {Array<V>}
   */
  values(): V[] {
    return Array.from(this.table.values());
  }

  /**
   * @description: 返回键数组
   * @return {Array<K>}
   */
  keys(): K[] {
    return Array.from(this.table.keys());
  }

  /**
   * @description: 返回键值对数组
   * @return {Array<K, V>}
   */
  keyValues(): [K, V][] {
    return Array.from(this.table.entries());
  }

  /**
   * @description: 迭代整个字典
   * @param {function} callbackFn
   */
  forEach(callbackFn: (key: K, value: V) => any) {
    const valuePairs = this.keyValues();
    for (let i = 0; i < valuePairs.length; i++) {
      // callbackFn 返回 false 时要终止迭代
      if (callbackFn(valuePairs[i][0], valuePairs[i][1]) === false) {
        break;
      }
    }
  }

  /**
   * @description: 是否为空
   * @return {boolean}
   */
  isEmpty(): boolean {
    return this.size() === 0;
  }

  /**
   * @description: 字典的大小
   * @return {number}
   */
  size(): number {
    return this.table.size;
  }

  /**
   * @description: 清空字典
   */
  clear() {
    this.table.clear();
  }

  /**
   * @description: 替代默认toString
   * @return {string}
   */
  toString(): string {
    if (this.isEmpty()) {
      return '';
    }

    let objStringList = [];
    // 迭代 table
    for (const [key, value] of this.table) {
      objStringList.push(`[${key}: ${value}]`);
    }
    return objStringList.join(',');
  }
}

下一篇来分析 散列表。

前端记事本，不定期更新，欢迎关注！

👆 全文结束，棒槌时间到 👇