Symbol Tables

Since childhood, we have all used a dictionary, and many of us have used a word processor (say Microsoft WORD) which comes with a spell checker. The spell checker is also a dictionary but limited. There are many real time examples for dictionaries and few of them are:-

• Spelling checker
• The data dictionary found in database management applications
• Symbol tables generated by loaders, assemblers, and compilers
• Routing tables in networking companies (DNS Lookup)

In computer science, we generally use the term symbol table rather than dictionary, when referring to the ADT (Abstract Data Type).

What are Symbol Tables?

From the above discussion, we can define the symbol table as a data structure that associates a value with a key. It supports the following operations:

• Search whether a particular name is in the table
• Get the attributes of that name
• Modify the attributes of that name
• Insert a new name and its attributes
• Delete a name and its attributes

There are only three basic operations on symbol tables: searching, hashing and deleting.

Example: DNS Lookup. Let us assume that the key in this case is URL and value is an IP address.

• Insert URL, with specified IP address
• Given URL, find corresponding IP address

Read about symbol table implementations.