算法技术手册（原书第2 版）

102

｜

第

5

章

如果使用

Java

的

String

类，那么还会需要额外的存储费用——每个字符串有

12B

的费

用。因此还需要增加

213 557

×

12 = 2 562 684

个额外字节，所以，例子中的实现需要

7 568 172B

的内存来正常运行。单词表中字符串的实际字符数量只有

2 099 075

。所以我

们的实现需要大约是字符数量的

3.6

倍的存储空间。

大多数的存储费用都是由于使用了

Java

类而导致的。在实现散列表时，必须在易用且略

有浪费与难于实现却可实现最大优化之间做出选择。当内存价格高高在上时，可以选择

后者来优化内存使用从而节省开支。但是，如果内存充足，散列函数不会产生太多冲突，

且有一个可以立即使用的链表实现，我们通常都会选择

JDK

提供的解决方案。

影响实现算法的一个主要因素是数据集合是否会改变。在上述例子中，单词表是固定的，

且其大小是预先知道的，并且我们不会在单词表中添加或者删除单词。但是，如果这个

数据集合是动态的，会有很多元素插入或者删除，那么就必须选择一个合适的数据结构

来优化性能。在上述例子中，冲突处理策略之所以工作得非常好，是因为在链表中插入

元素只需要常数时间，删除元素的时间和链表长度成比例。如果散列函数能够更加均匀

地分布元素，那么得到的每一个链表的长度会相对更短。

5.3.3 解决方案

除了设计散列函数，

散列搜索算法

还包括两个步骤：第一步是创建散列表。例

5-6

的代

码展示了如何使用链表将元素散列到特定的表元素中。我们使用迭代器来从集合

C

中来

读取输入元素。

例

5-6

：加载散列表

public ...