CSE 100: Data Structures (Fall 1996)


		Programming Assignment #4
		Hashing
		Due Date: DEC 3  (NO EXTENSION)



In this programming assignment you will experiment with various hash table
designs, and evaluate your designs using measurements obtained from large
randomized data sets.  An important part of this assignment are the
measurements themselves, so be sure to allow plenty of time for
experiments.


You will implement 3 strategies:
	a) linear probing
	b) double hashing
	c) buckets with secondary hash tables


You'll look at random integer data sets.  We'll provide you with functions
to generate the required data sets and the search keys.

Try and make  your hash tables as efficient as possible, taking into
account both the cost of managing as well as accessing the tables.  Use
fixed size hash tables, but permit the user to input the size of the hash
table at run time.

For buckets with secondary hash tables (c) each bucket is itself a hash
table.  The size of the secondary tables may be different from the size of
the primary table, and need not all be the same size. You can experiment
with the table sizes and note the effect on performance.  Note: that for
(c) you should use double hashing for the secondary hash tables.  You can
use linear probing for the top level hash table.  Consider a top-level
hash table entry to be full if the secondary table it points to is full.

Don't forget to make your hash tables a prime number in length.  The
procedure for generating prime numbers---Euclid's Algorithm---will be
provided on-line as described below.

Performance

There are two performance measurements:
	1. number of probes
	2. running time.

Report on both performance metrics for
the three hash table designs (a)-(c) above:

    1.  The average number of probes for insertion

    2.  The average number of probes for a successful and
	unsuccessful searches as a function of the load factor Alpha,
	for the following values of Alpha:

		Alpha = 0.1, 0.2, 0.5, 0.75, 0.8, 0.9, 0.95, 1.0

    3.  The time to construct a table for a given set of keys,
	and the time to perform the searches.


The first two measurements imply that you will need to maintain the
cumulative number of probes incurred in managing a hash table.
Encapsulate this information appropriately.  You may want to keep a set of
counters, with procedures for clearing the counters.

Note that when performing timings, you should NOT include the time to read
in the keys and the queries.  Instead, read these data into an array, and
deliver the inputs directly from the array.

To measure the effect that a growing Alpha has on performance, we
recommend the following procedure.  Fill the hash table in stages; at each
stage fill the table up to the appropriate fraction, then perform the
searches.  So, first fill the table to 10% full, collect statistics,
perform searches, collect more statistics, then fill to 20%, perform more
searches, and so on.

Your inputs will be randomly generated NON-ZERO integers.  Use the code
provided in the file Rand.[Ch].  It will probably be easier for you to
perform successful and unsuccessful searches separately.  For the
successful searches you will need to  guarantee that the search keys are
in the hash table.  An easy way to do this is to simply make a copy of the
keys from the hash table in the order they appear (why is this
reasonable?) For the unsuccessful search you will need to guarantee that
the search keys will NOT be found in the hash table. The random number
generator makes this easy since you can generate random integers over a
given range.


The size of your samples should be large.  Assume that you will read in
N=20,000 keys to go into the hash table.  Your search samples should be on
the order of the number of entries currently in the table.  So, if your
table is 10% full, then you should search for approximately 2,000 values.
Note that you will get some duplicates; these should be discarded.  So
long as the number of duplicates is small (e.g. on the order of less than
0.1% of the total number of keys) you may ignore them in your
computation.