Symbol table 和 Hash map 数据结构的区别

Question

在阅读不同的数据结构时，发现编译器使用的 Symbol table 被归类为数据结构。

谁能解释一下 Symbol table 数据结构和 Hash map 之间的区别？

Answer 1

符号 Table 本身不是 a 数据结构。大多数编译器将需要一个或多个符号 table，但它们的 exact 形式不限于一种特定的数据结构。 一些 编译器可能会选择将他们的符号 table 实现为哈希映射，如果这符合他们的目的的话。

所以我想说区别是概念上的。 "Symbol Table" 通过其 用途 描述数据结构。 "Hash Map" 通过其 实现 描述数据结构。

Wikipedia page还不错

Answer 2

tl;dr 符号 table 是 不是 数据结构。所以不能和hash map相提并论，因为hash map是一种数据结构。但他们有着亲密的关系。

详情： 首先Symbol table是不是一个数据结构。 Symbol table 是计算机科学中的抽象数据类型（ADT）。这个ADT就是俗称的字典。

ADT 的实现称为数据结构。有许多实现 Symbol Table ADT 的数据结构。一种这样的数据结构是哈希映射。实现Symbol Table ADT的各种其他可能的数据结构如下：

• 无序数组实现
• 有序（排序）数组实现
• 无序链表实现
• 有序链表实现
• 基于二叉搜索树的实现
• 基于平衡二叉搜索树的实现
• 三元搜索实现
• 基于哈希的实现 - 例如哈希图

请记住，以上列表并非详尽无遗。这个 ADT 可以有更多的实现。

注意：您可能想阅读this线程以了解ADT和数据结构之间的区别。

Answer 3

"符号 table 的主要目的是将值与键相关联。Symbol-table 实现通常以其底层数据结构及其 get 实现为特征() 和放置 ()。 使用哈希的搜索算法由两个独立的部分组成。第一部分是计算将搜索键转换为数组索引的哈希函数。 散列搜索的第二部分是 collision-resolution 过程