Repeat Programming Problem 7, but use the class Hashed Dictionary, as described in Section 18.4.6, which uses separate chaining to resolve collisions. Use the hash function h(x) = x mod table Size and the algorithm that involves Horner's rule, as described in Section 18.4.1about hash functions, to convert a variable into an integer x. Because you add an item to the dictionary only if its search key is not already present, does the time required for an insertion increase?
Programming Problem 7:
Implement the symbol table described in Exercise 5 by reusing the class Tree Dictionary , as described in Section 18.2.2 of this chapter.
Exercise 5:
A C++ compiler uses a symbol table to keep track of the identifiers that a program uses. When the compiler encounters an identifier, it searches the symbol table to see whether that identifier has already been encountered. If the identifier is new, it is inserted into the table. Thus, the symbol table needs only insertion and retrieval operations. Which implementation of the ADT dictionary would be most efficient as a symbol table?