In a chained hash table, each table entry is a pointer to a collection of elements. It can be any collection that supports insert, remove, and find, but is commonly a linked list. The elements in the list can be stored by key value order, by frequency of access or by insertion time. Each list forms a bucket in which we place elements hashing to a specific position in the array. Because each bucket is a linked list, an unlimited number of elements can be inserted. However, performance degrades if the table becomes full.

"Chained hash tables have a simple solution for resolving collisions: elements are simply placed in the bucket where the collision occurs. One problem with this, however, is that if an excessive number of collisions occur at a specific position, a bucket becomes longer and longer. Thus, accessing its elements takes more and more time. Ideally, we would like all buckets to grow at the same rate so that they remain nearly the same size and as small as possible. In other words, the goal is to distribute elements about the table in as uniform and random a manner as possible. This theoretically perfect situation is known as uniform hashing; however, in practice it usually can only be approximated.

Even assuming uniform hashing, performance degrades significantly if we make the number of buckets in the table small relative to the number of elements we plan to insert. In this situation, all of the buckets become longer and longer. Thus, it is important to pay close attention to a hash table's load factor. The load factor of a hash table is defined as: where n is the number of elements in the table and m is the number of positions into which elements may be hashed. The load factor of a chained hash table indicates the maximum number of elements we can expect to encounter in a bucket, assuming uniform hashing.

For example, in a chained hash table with m = 1699 buckets and a total of n = 3198 elements, the load factor of the table is a = 3198/1699 = 2. Therefore, in this case, we can expect to encounter no more than two elements while searching any one bucket. When the load factor of a table drops below 1, each position will probably contain no more than one element. Of course, since uniform hashing is only approximated, in actuality we end up encountering somewhat more or less than what the load factor suggests. How close we come to uniform hashing ultimately depends on how well we select our hash function."

Problem

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

You will use the table to compare two Shakespeare plays: Hamlet and As You Like It. You will report the number of words that Shakespeare used in both plays. Have your program read the file hamlet.txt and insert each word into the table. For this assignment, a word will be delimited by a white space, so simple input with >> can be used. Some of the words will, of course, be nonsense, but we will ignore this. After inserting all the words from Hamlet, do a lookup for words from the file asyoulikeit.txt. Store and count the words that are duplicated in the two plays (i.e. words for which the search is successful). Your count may be slightly less than accurate in reality, since we will not strictly parse the words. However, each student should come up with the same list of words and the same count. For each word you insert, compute the number of elements in the bucket that are searched. Likewise, compute the number of unsuccessful searches. Report the average number of elements inspected during a search (average number per bucket). Determine if this is close to the expected size based on the load factor after all words have been inserted.