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 时被中止。

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(',');
  }
}

下一篇来分析 散列表。

---

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

---