3.1 符号表
Robert Sedgewick Kevin Wayne
符号表最主要的目的就是将一个键和一个值联系起来。用例能够将一个键值对插入符号表并希望在之后能够从符号表的所有键值对中按照键直接找到相对应的值。本章会讲解多种构造这样的数据结构的方法,它们不光能够高效地插入和查找,还可以进行其他几种方便的操作。要实现符号表,我们首先要定义其背后的数据结构,并指明创建并操作这种数据结构以实现插入、查找等操作所需的算法。
查找在大多数应用程序中都至关重要,许多编程环境也因此将符号表实现为高级的抽象数据结构,包括 Java——我们会在 3.5 节中讨论 Java 的符号表实现。表 3.1.1 给出的例子是在一些典型的应用场景中可能出现的键和值。我们马上会看到一些参考性的用例,3.5 节的目的就是向你展示如何在程序中有效地使用符号表。本书中我们还会在其他算法中使用符号表。
定义。符号表是一种存储键值对的数据结构,支持两种操作:插入(put),即将一组新的键值对存入表中;查找(get),即根据给定的键得到相应的值。
表 3.1.1 典型的符号表应用
公开
同步至部落
取消
完成
0/2000
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
![](https://static001.geekbang.org/resource/image/d0/e4/d0880927e2a522a038be2d04bf19dfe4.png)
本文深入介绍了符号表的概念、用途以及在不同应用场景中的典型应用。文章提供了简单的泛型符号表API,包括创建符号表、插入键值对、获取键对应的值、删除键值对等操作。此外,还介绍了符号表的一些设计决策,如泛型处理、重复的键处理、空键和空值的规定,以及删除操作的实现方式。强调了符号表在各种应用中的重要性,如字典、图书索引、文件共享、账户管理、网络搜索和编译器等领域的应用。通过这些典型应用的介绍,读者可以更好地理解符号表在实际编程中的作用和意义。此外,还介绍了有序符号表的概念和API,以及对于Comparable键的操作。文章还讨论了符号表的性能问题,特别是在处理大型文本时的性能考量。总体而言,本文通过简洁清晰的语言和具体的示例,为读者提供了对符号表的全面了解和使用指南。文章内容深入浅出,适合对符号表感兴趣的读者阅读学习。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《算法(第 4 版)》
《算法(第 4 版)》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论