9.3　字典、散列、关联数组

本节我们来看另一种诸多语言都支持的容器，它被称作字典、散列或关联数组等 10。

10在脚本语言中常用散列一词来指代这种容器。它源自于字典实现方式之一的散列表，因此严格来讲把它和字典并列起来并不合适。为了使本章内容易于理解，暂且这样处理。

本章使用字典这个词。字典和上一节中学习的数组有什么区别呢？数组是整数和值的对应。当被问到第 10 个数值是多少时，它能告知第 10 个数值是 3。与之相对应，字典是字符串和数值的对应。当被问到 "age" 的值是多少时，它能告知 "age" 的值是 31（图 9.6)。这里的字符串被称作字典的“键”11。笔者认为字典这一名称很自然就能让人想起字符串和值的对应关系 12。

11在实现中，字典中的键也可以是字符串以外的东西，像 Python 语言中就可以。这一点跟此处论述的主题无关，因此不多赘述。

12敏锐的读者可能一下子想起了第 7 章中出现的名字和内容的对照表，两者颇为相似。的确如此，对照表（命名空间）和字典在功能上是等价的。“Python Reference Manual”(http://docs.python.org/release/1.6/ref/execframes.html)中有如下论述：Namespaces are functionally equivalent to dictionaries (and often implemented as dictionaries).

图 9.6　数组与字典

我们来看一个具体的例子。有三个小孩，名字分别是 Ichiro、Hanako 和 Jiro，年龄分别为 5 岁、4 岁和 3 岁。我们来考虑一下如何在内存上记录他们名字和年龄的对应情况。实现存放多个数值的目的的方法有数组和链表这两种。同样地，实现字符串和值对应存储的也有多种实现方法。常用的方法是散列表和树。

散列表

散列表使用以字符串为参数返回整数的散列函数，实现了字符串与值的对应。存放值之前首先准备一个大的数组，然后使用散列函数（分散函数 13）将字符串转换成适当分散的整数，用来决定这个值在数组中存放的位置。

13分散函数这个名称最早出现于 1980 年的《信息处理手册》（日本信息处理学会编）。这个词非常直观地表达了函数的目的，但目前最为广泛的称呼还是散列函数。

首先使用散列函数把键转换为整数 n。比如 Ichiro 是 434，Hanako 是 522，Jiro 是 110. 经过这样的转换后，再把值存入数组的第 n 个位置 中（图 9.7）14。

14这里仅仅介绍了概要，在实际的实现过程中会碰到几个棘手的问题。比如，不同的键传递给散列函数碰巧得到相同的内存地址该怎么办？又如，为了得到分散的整数返回值该选用怎样的散列函数？再如，事先准备好的数组多大才合适？对这些问题感兴趣的读者可以阅读一些与散列表实现相关的文献。

图 9.7　散列表

树

如图 9.8 所示，树是一种数据结构。链表中用箭头连接了下一个值，而树用箭头连接了右边子树和左边子树两处 15。因为在制作图表时一般会习惯性地向下描绘，所以与其说是树不如说更像是树根。

15树最上面的节点叫根，箭头的尾端叫父节点，尖端叫子节点。子节点最多两个的树被称为二叉树。一般的树也可能有三个以上的子节点。第 3 章中我们曾经讲到过结构树，本章讲的是二叉树。

图 9.8　树的结构

我们来看一下树的构造过程。首先把 Ichiro 作为根节点，如图 9.9。

图 9.9　以 Ichiro 为根节点

再追加 Hanako 这个元素。基本原则是键小的放在左边，键大的放在右边。把 Ichiro 和 Hanako 这两个键按照字典序比较，可知 H 在 I 的前面，因此 Hanako 要比 Ichiro 小，在其左边（图 9.10）。

图 9.10　Hanako 在 Ichiro 的左边

然后追加 Jiro 这个元素。Jiro 因为比 Ichiro 更靠后，因此在其右边（图 9.11）。

图 9.11　Jiro 在 Ichiro 的右边

然后追加 Saburo 这个元素。首先比较 Saburo 和 Ichiro，S 在 I 后面，因此往右前进。右边已经有了 Jiro。比较 Jiro 和 Saburo，S 在 J 的后面，因此放在其右边。

读取数值时，也要做同样的比较。比如要把 Jiro 这个键对应的值读取出来，首先要比较 Ichiro 和 Jiro。Jiro 在后面，因此顺着右边的箭头前进。然后比较 Jiro 和 Jiro，他们是相同的，从而得到此处记录的 3 就是和 Jiro 相对应的数值 16。

16这里仅仅介绍了概要，在实际的实现过程中会碰到几个棘手的问题。这种方法中如果没有很好地平衡树的左右两边，则可能产生性能问题。比如，对于一个对键按降序排序好了的树，它只会往左边一个方向成长。怎么保持左右两边的平衡呢？有兴趣的读者可以通过关键字平衡二叉树或是红黑树查找相关文献。

元素的读取时间

不搞这么复杂，使用两个数组不也行吗？或者说，在数组里按键－值－键－值这种方式存放数据不也可以吗？抱有这种想法的人应该不在少数吧。

元素的数量较少时这样做是没有问题的。至于给定键读取对应的值时所需时间是多少，我们从大 O 表示法的角度来探讨一下。在数组里存放键和值的这种方式中，要读取特定键对应的值时，因为不知道键存放的位置，所以要从数组的开头位置按顺序往后读。或许在一开始很快就能找到，或许要到最后才能找到，平均需要进行 n/2 次的检查。因此，数量级为 O(n)17。

17可能有读者会说，将数组按照键的升序先排序好，采用二分查找的办法，时间复杂度就可以降为 O(log n) 了。的确如此。但是考虑到元素添加的过程，如何才能保持数组的已排序状态呢？这又会回到平衡二叉树的话题。

对于树

从树中读取元素是什么情况呢？在前面的例子中我们构造了一个带有 3 个元素的树。从这棵树中读取 1 个所需数据，最多需要比较两次。比如要把 Hanako 对应的值读取出来，首先把 Hanako 和根部的 Ichiro 进行比较，这是第一次。接下来，因为 Hanako 比 Ichiro 要小，于是沿着左边的箭头找到下一个，再和 Hanako 做比较，这是第二次。高度为 2 的树中最多有 3 个元素 18。

18本章讲的不是一般的树，而是子节点最多为两个的二叉树。

比较次数增加 1 次，能最多从多少个元素中读取某个元素呢？高度为 3 的树中最多能有多少个元素呢？答案是 1+3*2＝7 个。把它想象为一个根部左右两边都是一棵高度为 2 的树的树。那这棵树的元素就是由根部的 1 个，加上高度为 2 的树中的 3 个，再加上左边高度为 2 的树中的 3 个，总共 7 个。

那么，高度为 4 的树最多又能有多少个元素呢？答案是 1+7*2＝15 个。假设一棵树它的根部左右两边都是一棵高度为 3 的树。它的元素个数就是由根部的 1 个，加上高度为 3 的树中的 7 个，再加上左边高度为 3 的树中的 7 个，总共 15 个（图 9.12）。

图 9.12　比较 4 次，可以从 15 个元素中读取出某个特定的元素

像这样，树的高度每增加 1，元素的数量就大致变成 2 倍。反之，每当数据量翻倍时，所需的比较次数就增加 1 次。也就是说，从树中读取元素的所需时间是 O(log n)19。

19要获得 O(logn) 的性能，必须保证树的左右两边的平衡。如果向一边偏移，最坏的情况性能可能降为 O(n)。

对于散列表

在散列表中又是什么情况呢？要把键对应的值读取出来，首先要经过散列函数把键转换成数组中的位置信息，再把该位置上的值读取出来。这个操作与数据的量没有关系，也就是 O(1) 的数量级 20。

20然而，如果散列函数的结果分散度比较差，或者为值准备的数组太小，那么不同的键的散列值碰巧落入一个内存地址的概率就会增高。这时为了不返回错误的值，就要额外花费更多的时间。

所以散列表所需时间数量级是最小的。正因为如此，很多语言中在制作字典时都会使用散列表。从内存的占用量来看，借助数组的方法所需内存最少，而散列表为了存放值需要很大的数组，因此内存的占用量是最大的。

没有万能的容器

也许有人要问，那到底用什么容器好呢。事实上，万能的容器是不存在的。根据容器的使用目的、使用方式和操作类型的不同，最适宜的容器类型也会相应地变化。是想要节约内存、节约计算时间，还是两样都没有必要节约。没有绝对的正确答案，而是需要根据当时的状况仔细分析，寻求最佳平衡。这是非常重要的。

比如你需要写一个针对用户操作做出响应的程序。如果在不考虑处理速度的情况下 0.01 秒可以处理完毕，那么对于这个程序还有必要做高速化处理吗？

要回答这个问题，需要重点考虑两点：什么有增加的可能性，以及其时间复杂度是什么数量级。比如开发环境中只有 10 个数据，用户实际使用的环境中有 10 万个数据。如果你写的程序的处理时间复杂度是 O(1)，那么即使数据有 10 万个，你也能在 0.01 秒内处理完毕。这种情况下，即使花费精力把处理速度提升两倍，时间缩短到 0.005 秒，在用户满意度提升方面带来的效益也十分有限。但是如果你写的程序的处理时间复杂度是 O(n)，那么数据量变为 10 万个时，处理时间就要 100 秒。耗时 100 秒用户能接受么？如果不能，那就有进行高速化处理的必要了 21。

21即使不能做高速化处理，至少也要花点工夫显示一个进度条。