Symbol table data structure

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, Stringand 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 nullif 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 Iterableand 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](http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html)and [java.util.HashMap](http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html)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/](http://introcs.cs.princeton.edu/java/44st/)