CMIS 250  Data Access and Organization
Term 2  Wiesbaden Lindsey Air Station
Programming Assignment #4
Due 19 Dec.


Write a program that will generate the number of key
comparisons needed by the hashing collision handling
techniques of linear probing and chaining.

Allow the user freedom to conduct his own experiments.  So,
include user specification of hash table size, load factor
alpha, number of tables to generate and fill with keys up to
alpha percent, and the number of simulated insertions that
will be used to derive the average number of key comparisons
needed to insert a key into the table when it is alpha-percent
full.

As an example, user specifies table size of 91 (some prime
number), alpha as .5, 50 tables, 50 insertions each.  Program
will insert about 45 random keys into a table, then will
generate 50 random keys and see where they would be inserted
into the half-full table (the average of the number of key
comparisons needed to insert a key into a half-full table of
this size can be computed this way) but do not insert them
into the table (if you do, the table will no longer be at
alpha of .5).  Just as in our sorting and searching programs
we did not use just one array to derive our average number of
key comparisons, we won't trust the results of simulated
insertions into just one table (it might be a very good or
very bad table) but will use many tables, hence the number of
tables parameter.  (Re-use the same table, clearing it and
then inserting new keys.  Don't worry about Disposing nodes.) 
 
As usual, use random keys.  Since in hashing applications the
key range is large compared with the hash table range, the
keys can be integers up to Maxint.  The hashing function to
use might as well be MOD TableSize.

You should get numbers similar to the textbook's.  

Debugging hints: to see that keys are hashing to where they
should be, use an array size of a power of ten, then the last
digits of the key will be its table index.
To see that the chaining is correct, have a procedure that
displays lists.