3.1   Elementary Symbol Tables


Symbol table.

The primary purpose of a symbol table is to associate a value with a key. The client can insert key–value pairs into the symbol table with the expectation of later being able to search for the value associated with a given key.

Typical symbol-table applications

API.

Here is the API.

Symbol-table API
We consider several design choices for our implementations to make our code consistent, compact, and useful.

Ordered symbol tables.

In typical applications, keys are Comparable objects, so the option exists of using the code a.compareTo(b) to compare two keys a and b. Several symbol-table implementations take advantage of order among the keys that is implied by Comparable to provide efficient implementations of the put() and get() operations. More important, in such implementations, we can think of the symbol table as keeping the keys in order and consider a significantly expanded API that defines numerous natural and useful operations involving relative key order. For applications where keys are Comparable, we implement the following API:

Ordered Symbol-table API
Examples of ordered symbol table operations

Sample clients.

We consider two clients: a test client that we use to trace algorithm behavior on small inputs and a performance client.

Sequential search in an unordered linked list.

Program SequentialSearchST.java implements a symbol table with a linked list of nodes that contain keys and values. To implement get(), we scan through the list, using equals() to compare the search key with the key in each node in the list. If we find the match, we return the associated value; if not, we return null. To implement put(), we also scan through the list, using equals() to compare the client key with the key in each node in the list. If we find the match, we update the value associated with that key to be the value given in the second argument; if not, we create a new node with the given key and value and insert it at the beginning of the list. This method is known as sequential search.

Sequential search

Proposition A.

Unsuccessful search and insert in an (unordered) linked-list symbol table both use N compares, and successful search uses N compares in the worst case. In particular, inserting N keys into an initially empty linked-list symbol table uses ~N^2/2 compares.

Binary search in an ordered array

. Program BinarySearchST.java implements the ordered symbol table API. The underlying data structure is two parallel array, with the keys kept in order. The heart of the implementation is the rank() method, which returns the number of keys smaller than a given key. For get(), the rank tells us precisely where the key is to be found if it is in the table (and, if it is not there, that it is not in the table). For put(), the rank tells us precisely where to update the value when the key is in the table, and precisely where to put the key when the key is not in the table. We move all larger keys over one position to make room (working from back to front) and insert the given key and value into the proper positions in their respective arrays.

Binary search symbol table

Proposition B.

Binary search in an ordered array with N keys uses no more than lg N + 1 compares for a search (successful or unsuccessful) in the worst case.

Proposition C.

Inserting a new key into an ordered array uses ~ 2N array accesses in the worst case, so inserting N keys into an initially empty table uses ~ N^2 array accesses in the worst case.


Exercises

  1. Write a client program GPA.java that creates a symbol table mapping letter grades to numerical scores, as in the table below, then reads from standard input a list of letter grades and computes and prints the GPA (the average of the numerical scores of the corresponding grades).
    A+    A     A-    B+    B     B-    C+    C     C-    D     F
    4.33  4.00  3.67  3.33  3.00  2.67  2.33  2.00  1.67  1.00  0.00
    
  2. Develop a symbol-table implementation ArrayST.java that uses an (unordered) array as the underlying data structure to implement our basic symbol table API.
  3. Implement size(), delete(), and keys() for SequentialSearchST.java.
  4. Implement the delete() method for BinarySearchST.java.
  5. Implement the floor() method for BinarySearchST.java.

Creative Problems

  1. Test client. Write a test client TestBinarySearchST.java for use in testing the implementations of min(), max(), floor(), ceiling(), select(), rank(), deleteMin(), deleteMax(), and keys().
  2. Certification. Add assert statements to BinarySearchST.java to check algorithm invariants and data structure integrity after every insertion and deletion. For example, every index i should always be equal to rank(select(i)) and the array should always be in order.

Web Exercises

  1. Phone number data type. Write a data type PhoneNumber.java that implements US phone numbers. Include an equals() method.
  2. Student data type. Write a data type Student.java that implements a student with a name and section. Include an equals() method.