计算机科学导论：跨学科方法

4.4　符号表

符号表（symbol table）是一种数据结构，用于将数值与关键字关联。客户程序可以通过指定一个键值对将一个项目存储到（put）符号表中，然后从符号表中检索（get）对应于特定键的值。例如，一所大学可能把一个学生的姓名、家庭地址、成绩等（值）与该学生的社会安全号码（键）相关联，以便通过指定的社会安全号码来访问每个学生的记录信息（社会安全号码为美国社会的唯一标识，类似我国的身份证号码——译者注）。同样的方法适用于科学家组织数据、企业跟踪客户交易信息、Internet搜索引擎关联关键字和网页，或者其他许多应用场景。

在本节中，我们讨论符号表数据类型的基本API。除put和get操作外，我们的API还包括测试是否存在值与一个给定键相关联（contains）、移除键（以及相关联的值）、确定符号表中键值对的数量（size），以及对符号表中的键遍历访问的功能。我们也会讨论在各种应用中自然产生的符号表上的其他基于元素顺序的操作。

作为动力，我们讨论两个典型的客户程序——字典查找和索引，并简要地讨论它们在实际中的应用。类似的客户程序是基本的工具，它们经常以某种形式在每个计算环境中呈现，容易当成理所当然的而忽略其原理，也容易产生误用。同任何复杂的工具一样，想要高效地使用字典或者索引，必须了解它们是如何构建的。这就是我们在本节中详细研究符号表的原因。

由于其本质上的重要性，符号表自计算初期就被广泛使用和研究。我们讨论两个经典实现。第一个是散列操作，用于将键转换为数组索引下标以访问值。第二种是基于二叉搜索树（BST）的数据结构。两个实现都是非常简单的解决方案，在许多应用场景中性能良好，可以作为现代程序设计环境中工业级符号表实现的基础。我们认为散列和二叉搜索树的代码比我们讨论过的栈和队列中的链表代码稍微复杂一点，但它将会引领你进入一个具有深远影响的数据结构的新维度。 ...