In this lab, you will be using a vector (or array) of linked lists to implement a hash table.

A hash table is a data structure in which the location of an item is determined directly as a function of the item rather than by a sequence of trial-and-error comparisons and is used when fast searching is needed. Ideally, search time is O(1); i.e., it is constant and independent of the number of items to be searched. Here we will use the method known as chaining, in which the hash table is implemented using a vector (or array) of linked lists.

When an item is to be inserted into the table, a hashing function h is applied to the item to determine where it is to be placed in the table; for example, a common one is

h(item) = item % table-size

where the table-size is usually taken to be a prime number (to scatter ("hash") the items throughout the table. For non-numeric items, numeric codes e,g., ASCII are used. The linked list at location h(item) is searched for the item. If it is not found, the item is inserted into the linked list at this location.

Design a HashTable class for processing hash tables. Use a small prime number such as 11 or 13 for the table size. Two of the basic operations it must provide are:

1. Insert an item into the hash table as just described. It doesn't matter where in the linked list it is inserted.

2. Display each index in the hash table and a list of all the items stored at that location.

For this particular problem, the hash table is to store strings and use the following hash function:

h(str) = (sum of the ASCII codes of the first 3 characters of str) % table_size.

For strings with fewer than 3 characters, just use whatever characters there are in the string.

Assignment: Use a vector (or array) of linked lists to implement a hash table. You are only allowed to use the linklist that we learned in this Chapter. You are not allowed to use STL list library.

Write a driver program to test your class. It should read several strings, storing each in the hash table. After all the strings are input, it should display the hash table by listing the indices and for each index, a list of all the words in the linked list at that location (sort of like the diagram above).

After you have thoroughly tested your class, then use it to process the strings in the piece of text:

DEAR MARLIN

THE AARDVARKS AND THE CAMELS WERE MISTAKENLY SHIPPED TO THE AZORES

SORRY ABOUT THAT

SINCERELY JIM

PS ANTS AND BATS AND COWS AND CATS ARE ANIMALS

COWS ARE BIG BUT ANTS ARE SMALL AND BATS AND CATS ARE IN BETWEEN