This assignment is to study and implement hash table.
Alice has a fixed number of closed empty boxes (lined up and indexed from ‘0’ like an array) and some numbered cubes. Each empty box can fit only one cube. Alice opens a box and puts the numbered cube in and closes the box. Alice could put the numbered cubes into random boxes, but if done so Alice was not able to tell which numbered cube was in which box without looking into the box. If Alice has used any hashing algorithm to place the numbered cubes in the empty boxes, after putting all the cubes Alice will be able to tell which cube is in which box without looking into the box by using the same hashing algorithm that was used earlier. Alice has implemented three different hashing algorithms to places the numbered cubes in the empty boxes. Implement as detailed below.
1. Implement insertion, deletion and search for a hash table by using the chaining method as defined in class.
Input format: <#EmptyBoxes <NumberedCube.command <NumberedCube.command
Sample input: 13 1.in 2.in 15.in 5.in 7.in 2.del 11.in 12.in
Sample output:
0:
1: 1
2: 15
3:
4:
5: 5
6:
7: 7
8:
9:
10:
11: 11
12: 12
2. Implement insertion, deletion and search for a hash table by using the single linear probing method as defined in class.
Input format: <#EmptyBoxes <NumberedCube.command <NumberedCube.command
Sample input: 13 1.in 2.in 15.in 5.in 7.in 2.del 11.in 12.in
Sample output:
0:
1: 1
2:
3: 15
4:
5: 5
6:
7: 7
8:
9:
10:
11: 11
12: 12
3. 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 format: <#EmptyBoxes <primeNumber <NumberedCube.command …
Sample Input: 13 7 18.in 41.in 18.sch 22.in 44.in 45.sch 59.in 32.in 41.del 31.in 73.in
The first and second integers are, N and q values, respectively.
Note to 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:
0:31
1:
2:
3:
4:
5:18
6:32
7:59
8:73
9:22
10:44
11:
12:
Write a separate program for each question. Total 3 programs are to be submitted to the same directory un “handin”.
