Programming Languages assignment VI

Assignment VI

Due date Tuesday April 17.


The hash-table is an important general-purpose data structure with constant-
time access, insertion and retrieval on the average. The purpose of this
exercise is to write a generic or template implementation of a hash-table, with
a few basic container operations for it.

A simple and effective implementation of a hash-table is as follows: we use
an array of headers, of fixed size, and we use one large array to store the
actual values that are held in the table. A header is an index into the storage
array. Each entry in the storage array has a link to the next entry with the
same hash code. The hash code of an object is used as an index into the
array of headers.

The table is parametrized by the type of the objects we store in it. In order
to enter objects in the table, or search the table for a particular object,
we need to have two operations defined on these objects:

a) We need a function Hash, that takes an object and returns an integer.

b) We need equality to be defined.

The first part of the assignment is to write the template for this data
structure, with a constructor, the operations Insert and Find, and
an  iterator class that iterates over the contents of the table.

Insert enter an element into the table. If the element is already present,
Insert is a noop.

Find determines whether an element is present in the table. 

The Iterator has the usual operations (Init, Next, Done), and produces
references to successive objects stored in the table, The easiest is to
implement the iterator as an iterator over the storage array, but it is
more interesting to have an iterator that delivers objects in order of
their hash-code. In that case the iterator needs to record the current
entry in the headers array, and the current object on the chain of objects
with that particular hash-code.

The second part of the assignment consists in testing your implementation
with three types: integers, character strings, and the large integers of the
previous assignments.

a) For integers, their value (modulo the size of the headers table) is
a convenient hash-code.

b) For strings, a reasonable hash-code is obtained by doing arithmetic
on successive bytes or words in the string. Adding up character values,
or successive word values, is a reasonable choice.

c) For large integers, some arithmetic combination of the words in the
mantissa can be used.

For your test program. generate 20 values of the proper type, insert them
into the table, and use the iterator to print the contents of the table.
You can create the input by hand. Make sure that there are some duplicates
among those 20, so that the output contains fewer than 20 elements (to
verify that Insert does not produce duplicates).