Week 7: Lab Document, 10/11

In class, we studied hash tables and separate chaining as a mechanism to deal with collisions. This problem asks you to implement a "hash table" class. Problem: Using hashing with chaining, implement a class called Dictionary that provides the methods: insert, delete, and search. You may assume that the items to be inserted into the Dictionary class are strings. This makes it possible to use the StringLinkList class for the linked lists pointed to by each of the slots in the hash table. Use the following function headers:

To simplify the construction of the hash function assume that the given strings are composed entirely of lower case letters. Use tricks discussed in class such as (i) the use of Horner's Rule and (ii) bit-shifting as a way to multiply by powers of 2, to speed up the implementation of the function.