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

First of all Symbol table is not a data structure. Symbol table is an Abstract Data Type (ADT) in computer science. Another common name of this ADT is dictionary.

Implementation of an ADT is called a Data Structure. There are many implementations (aka Data structures) of Symbol Table ADT. One such implementation is hash map. Various possible implementations of Symbol Table but not limited to 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

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

Answer 2

"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"