Symbol table data structure

Definition

A symbol table is a data type that we use to associate values with keys. Clients can store (put) an entry into the symbol table by specifying a key-value pair and then can retrieve (get) the value corresponding to a particular key from the symbol table.

Operations

Symbol table is key value abstraction. Operations supported

• Insert - Insert a value with specified key
• Search - Given key, search for the corresponding value

Application

Application	Action	Key	Value
Internet DNS	Look up website by IP address	website	IP address
Reverse DNS	Look up IP address by web site	IP address	Website
genomics	amino acid dictionary	codon	amino acid
Java compiler	Find properties of variable	Variable name	Value and type
stock quote	Look up price of stock	stock symbol	price
file share	find song to download	song name	machine
file system	find file on hard drive	file name	location on hard drive

Implementation and ADT

Here is basic idea of simple table : 

public class *ST, Value>
             *ST()                  // create a symbol table
       void  put(Key key, Value v)  // put key-value pair into the table
      Value  get(Key key)           // return value paired with key
                                    // or null if no such value
    boolean  contains(Key key)      // is there a value paired with key?

This API reflects several design decisions, which we now enumerate:

• Comparable keys. We take advantage of key ordering to develop efficient implementations of put and get. We also assume the keys do not change their value while in the symbol table. The simplest and most commonly used types of keys, String and built-in wrapper types like Integer and Double, are immutable.
• Replace-the-old-value policy. If when a key-value pair is inserted into the symbol table that already associates another value with the given key, we adopt the convention that the new value replaces the old one (just as with an array assignment statement).
• Not found. The method get() returns null if no entry with the given key has previously been put into the table. This choice has two implications, discussed next.
• Null keys and values. Clients are not permitted to use null as a key or value. This convention enables us to implement contains() as follows:
  

  public boolean contains(Key key) {
     return get(key) != null;
  } 
  

• Remove. We do not include a method for removing keys from the symbol table. Many applications do require such a method, but we leave implementations as an exercise or for more advanced courses in data structures in algorithms. Since clients cannot associate null with a key, one simple interface is to take a put command with null as the value to mean remove.
• Iterable. As with most collections, it is best to implement Iterable and to provide an appropriate iterator that allows clients to visit the contents of the table. The natural order of iteration is in order of the keys, so we implement Iterable and use get to get values, if desired.
• Variations. Numerous other useful operations on symbol tables have been identified, and APIs based on various subsets of them have been widely studied. We will consider several of these at the end of this section.

Java implementation of symbol table:
Now that you understand how a symbol table works, you are certainly welcome to use the industrial strength versions java.util.TreeMap and java.util.HashMap They follow the same basic API as BST, but they allow null keys and use the names containsKey() and keySet() instead of contains() and iterator(), respectively. They also contain additional methods such as remove(), but they do not provide any efficient way to add some of the additional methods that we mentioned, such as order statistics. You can also use java.util.TreeSet and java.util.HashSet which implement an API like our SET.

Whole example is taken from the URL in reference. Thanks.

References

• http://introcs.cs.princeton.edu/java/44st/