Difference between Symbol table and Hash map data structures

Question

While reading about different data structures, found that the Symbol table used by compilers is classified as a data structure.

Can someone explain what is the difference between Symbol table data structure and a Hash map?

Answer 1

TL;DR: Symbol table is not a data structure. Symbol table is an abstract data type (ADT). So it can't be compared with hash map which is a data structure. But they are very closely related.

Detailed Explanation: First of all, Symbol table is not a data structure. Symbol table is an Abstract Data Type (ADT) in computer science. ADT is more commonly known as dictionary.

Implementation of an ADT is called a Data Structure. There are many data structures which implement Symbol Table/dictionary ADT. One such data structure is hash map. Various other possible data structures which implement Symbol Table/dictionary ADT are as below:

• Unordered array implementation
• Ordered (sorted) array implementation
• Unordered linked list implementation
• Ordered linked list implementation
• Binary search tree based implementation
• Balanced binary search tree based implementation
• Ternary search implementation
• Hashing based implementation - e.g. Hash Map

Please remember that above list is not exhaustive in nature. There can be more implementations of this ADT.

Note: You might want to read this thread to understand the difference between ADT and data structure.

Answer 2

A Symbol Table isn't a data structure per se. Most compilers will require one or more symbol tables but their exact form isn't limited to one particular data structure. Some compilers may choose to implement their symbol table as a hash map, if that's suitable for their purposes.

So I'd say the difference is conceptual. "Symbol Table" describes a data structure by its purpose. "Hash Map" describes a data structure by its implementation.

The Wikipedia page isn't too bad

Answer 3

"The primary purpose of a symbol table is to associate a value with a key. Symbol-table implementations are generally characterized by their underlying data structures and their implementations of get() and put(). Search algorithms that use hashing consist of two separate parts. The first part is to compute a hash function that transforms the search key into an array index. the second part of a hashing search is a collision-resolution process"