Hash Table Experiment - HW-3
Due in class on April 18, 2002

The objective of this assignment is to implement a hash 
table object and conduct an experiment to help determine 
the proper size of the array relative to the expected 
amount of data to be stored.

The hash table object will contain an array of size N 
to be determined by the constructor call. It will also 
contain a counter.  You may use your elt class from 
the previous assignment as the hash table array will be 
an array of elt refs.  The collision resolution policy 
will be handled by a linked list at each index.  New 
insertions will take place at the far end of the list 
since the list must be searched to determine if the new 
elt is already in the structure.  No duplicates are 
allowed in the structure.  Your hash table class is an 
abstract class since the (virtual) hash function 
int h(elt-ref) must be supplied by the user of your 
class.  Users must inherit from your hash table class 
and supply the real hash function.  Users also inherit 
from your elt class for their data class.

For your concrete elt class, my_elt, store an integer 
value in a data member.

For your concrete class, my_hash, use the hash function 
h(elt-ref) returns the data member of my_elt mod N where 
N is the number chosen for the array size in the hash 
table constructor.

For the experiment you will need to determine the largest 
prime number less than 1500, 2000, 2500, and 3000.  Call 
these p1, p2, p3, and p4.  You may use the seive of 
Eratosthenes to determine these primes.

You will also need to generate three test files of random 
integers in the range 1 - 20000 with no duplicates.  This 
can be done as discussed in class.  Initialize an array A 
of 20000 ints as the sequence 1,2,3,...,20000.  Loop thru 
the array A and for each index i generate a random int j 
in the range 1 - 20000; then exchange A[i] and A[j].  Now, 
select the first 1000 values from A as your first data set.
Loop thru the array again doing the random exchanges and 
select the resulting first 1000 as your second data set.  
repeat a third time to obtain your last data set.

For each of the designated array sizes above (p1, p2, p3, 
p4) hash the data sets into your table.  Determine the 
following statistics for each data set and each array size:

average look-up in terms of number of compares.
worst case look-up in terms of number of compares.

record the average look-up, table-size pairs for analysis.
Formulate a hypothesis with regard to the proper array 
size relative to the expected amount of data.

hand in hard copy (2) of your source for the classes, 
your seive prog, and your test prog.  Also, a one page 
(max) analysis of your results.

include your data files and source code on diskette.