Programming assignment - you may use C, C++, or Java

Implement insertion, deletion and search for a hash table by using the double hashing method as defined in class. Suppose your double hashing is h(k) = i + jd(k) mod N and d(k) = q k mod q, then pick q the largest prime less than N.

Input:

A sequence of integers to be randomly generated (file input)

Sample input format: 13 7 1.in 3.in 5.in 3.del 7.in 9.in 11.in 12.in 2.in 1.sch 15.in

The first and second integers are, N and q values, respectively.

Note that stop your input once the hash table is full.

Output:

Two sets of outputs to be displayed, one for before the operation, another for after the operation.

In each set of output, each entry to be displayed on a new line possibly with more than one key.

Note that output of a sch is to be found or not found.

If a duplicate is inserted display duplicate key.

Sample output format (in case of the chaining):

0:

1: 1

2: 2 15

3:

4:

5: 5

6:

7: 7

8:

9:

10:

11: 11

12: 12

Note that 2.in will output duplicate on the screen and 1.sch will output found.

A command line user interface has to be provided as follows:

Enter your input file name:

Display the input before: /* display the input integers following a statement */

Display the output after the operation: /* display the resulting output on the screen */

Double Hashing o Double hashing uses a secondary hash function d(k) and handles collisions by placing an item in the first available cell of the series Common choice of compression function for the secondary hash function: d2(k)-q-k mod q (i +jd(k)) mod N where for j-0, 1,... , N- 1 o The secondary hash qisa prime function d(k) cannot have zero values o The possible values for oThe table size N must be a prime to allow probing of all the cells Double Hashing o Double hashing uses a secondary hash function d(k) and handles collisions by placing an item in the first available cell of the series Common choice of compression function for the secondary hash function: d2(k)-q-k mod q (i +jd(k)) mod N where for j-0, 1,... , N- 1 o The secondary hash qisa prime function d(k) cannot have zero values o The possible values for oThe table size N must be a prime to allow probing of all the cells