跳到主要内容

8. 字典和散列表

在集合中，我们感兴趣的是每个值本身，并把它当作主要元素。在字典（或映射）中，我们用[键，值]对的形式来存储数据。在散列表中也是一样（也是以[键，值]对的形式来存储数据）。但是两种数据结构的实现方式略有不同，例如字典中的每个键只能有一个值，

8.1 字典​

你已经知道，集合表示一组互不相同的元素（不重复的元素）。在字典中，存储的是[键，值]对，其中键名是用来查询特定元素的。字典和集合很相似，集合以[值，值]的形式存储元素，字典则是以[键，值]的形式来存储元素。字典也称作映射、符号表或关联数组。

在计算机科学中，字典经常用来保存对象的引用地址。例如，打开 Chrome | 开发者工具中的 Memory 标签页，执行快照功能，我们就能看到内存中的一些对象和它们对应的地址引用（用@<数>表示）。下面是该场景的截图。

image

本章，我们会介绍在现实问题中使用字典数据结构的例子：一个实际的字典（单词和它们的释义）以及一个地址簿。

8.1.1 创建字典类​

与 Set 类相似，ECMAScript 2015 同样包含了一个 Map 类的实现，即我们所说的字典。

本章将要实现的类就是以 ECMAScript 2015 中 Map 类的实现为基础的。你会发现它和 Set 类很相似，但不同于存储[值，值]对的形式，我们将要存储的是[键，值]对。

以下是我们的 Dictionary 类的骨架。

import { defaultToString } from "../util";

export default class Dictionary {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn; // {1}
    this.table = {}; // {2}
  }
}

与 Set 类类似，我们将在一个 Object 的实例而不是数组中存储字典中的元素（table 属性——行{2}）。我们会将[键，值]对保存为 table[key] = {key, value}。

JavaScript 允许我们使用方括号（[]）获取对象的属性，将属性名作为“位置”传入即可。这也是称它为关联数组的原因！

在字典中，理想的情况是用字符串作为键名，值可以是任何类型（从数、字符串等原始类型，到复杂的对象）。但是，由于 JavaScript 不是强类型的语言，我们不能保证键一定是字符串。我们需要把所有作为键名传入的对象转化为字符串，使得从 Dictionary 类中搜索和获取值更简单（同样的逻辑也可以应用在上一章的 Set 类上）。要实现此功能，我们需要一个将 key 转化为字符串的函数（行{1}）。默认情况下，我们会使用在 utils.js 文件中定义的 defaultToString 函数（可以在所创建的任何数据结构中复用该文件中的函数）。

defaultToString 函数声明如下。

export function defaultToString(item) {
  if (item === null) {
    return "NULL";
  } else if (item === undefined) {
    return "UNDEFINED";
  } else if (typeof item === "string" || item instanceof String) {
    return `${item}`;
  }
  return item.toString(); // {1}
}

请注意，如果 item 变量是一个对象的话，它需要实现 toString 方法，否则会导致出现异常的输出结果，如[object Object]。这对用户是不友好的。

如果键（item）是一个字符串，那么我们直接返回它，否则要调用 item 的 toString 方法。然后，我们需要声明一些映射/字典所能使用的方法。

  • set(key, value)：向字典中添加新元素。如果 key 已经存在，那么已存在的 value 会被新的值覆盖。
  • remove(key)：通过使用键值作为参数来从字典中移除键值对应的数据值。
  • hasKey(key)：如果某个键值存在于该字典中，返回 true，否则返回 false。
  • get(key)：通过以键值作为参数查找特定的数值并返回。
  • clear()：删除该字典中的所有值。
  • size()：返回字典所包含值的数量。与数组的 length 属性类似。
  • isEmpty()：在 size 等于零的时候返回 true，否则返回 false。
  • keys()：将字典所包含的所有键名以数组形式返回。
  • values()：将字典所包含的所有数值以数组形式返回。
  • keyValues()：将字典中所有[键，值]对返回。
  • forEach(callbackFn)：迭代字典中所有的键值对。callbackFn 有两个参数：key 和 value。该方法可以在回调函数返回 false 时被中止（和 Array 类中的 every 方法相似）。

1．检测一个键是否存在于字典中​

我们首先来实现 hasKey(key)方法。之所以要先实现这个方法，是因为它会被 set 和 remove 等其他方法调用。我们可以通过如下代码来实现。

    hasKey(key) {
      return this.table[this.toStrFn(key)] ! = null;
    }

JavaScript 只允许我们使用字符串作为对象的键名或属性名。如果传入一个复杂对象作为键，需要将它转化为一个字符串。因此我们需要调用 toStrFn 函数。如果已经存在一个给定键名的键值对（表中的位置不是 null 或 undefined），那么返回 true，否则返回 false。

2．在字典和 ValuePair 类中设置键和值​

下面，我们来实现 set 方法，代码如下。

    set(key, value) {
      if (key ! = null && value ! = null) {
        const tableKey = this.toStrFn(key); // {1}
        this.table[tableKey] = new ValuePair(key, value); // {2}
        return true;
      }
      return false;
    }

该方法接收 key 和 value 作为参数。如果 key 和 value 不是 undefined 或 null，那么我们获取表示 key 的字符串（行{1}），创建一个新的键值对并将其赋值给 table 对象上的 key 属性（tableKey）（行{2}）。如果 key 和 value 是合法的，我们返回 true，表示字典可以将 key 和 value 保存下来，否则返回 false。

该方法可以用于添加新的值，或是更新已有的值。

在行{2}，我们实例化了 ValuePair 类。ValuePair 类的定义如下。

class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
  toString() {
    return `[#${this.key}: ${this.value}]`;
  }
}

为了在字典中保存 value，我们将 key 转化为了字符串，而为了保存信息的需要，我们同样要保存原始的 key。因此，我们不是只将 value 保存在字典中，而是要保存两个值：原始的 key 和 value。为了字典能更简单地通过 toString 方法输出结果，我们同样要为 ValuePair 类创建 toString 方法。

3．从字典中移除一个值​

接下来，我们实现 remove 方法。它和 Set 类中的 delete 方法很相似，唯一的不同在于我们将先搜索 key（而不是 value）。

    remove(key) {
      if (this.hasKey(key)) {
        delete this.table[this.toStrFn(key)];
        return true;
      }
      return false;
    }

然后，可以使用 JavaScript 的 delete 运算符来从 items 对象中移除 key 属性。如果能够将 value 从字典中移除的话，就返回 true，否则将会返回 false。