Symbol Tables

What are Symbol Tables? 

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

Three basic operations on symbol tables: searching, inserting, and deleting.
Example:
DNS lookup. Let us assume that the key in this case is the URL and the value is an IP address.

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

Symbol Table Implementations

Unordered Array Implementation:

With this method, just maintaining an array is enough. It needs O( n) time for searching, insertion and deletion in the worst case.

Ordered [Sorted] Array Implementation:

In this we maintain a sorted array of keys and values.

• Store in sorted order by key 
• keys[ i] = ith largest key 
• values[ i] = value associated with ith largest key

Unordered Linked List Implementation:

Just maintaining a linked list with two data values is enough for this method.

Ordered Linked List Implementation:

 In this method, while inserting the keys, maintain the order of keys in the linked list. Even if the list is sorted, in the worst case it needs O( n) time for searching, insertion and deletion.

Binary Search Trees Implementation:

The advantages of this method are: it does not need much code and it has a fast search [O( logn) on average].

Hashing Implementation:

 This method is important. For a complete discussion, refer to the Hashing chapter.

Comparison Of Implementation: