In all of the procedures below, assume that the keys to be stored in your hash table (by chaining in the former item, or by open addressing in the latter two items) are natural numbers in the range [0, 100]. You need to implement the following procedures, whose description and pseudocode were given in class:

Chained-Hash-Insert and Chained-Hash-Search, using the hash function h(k) = k mod p, and chaining for resolving conflicts on a hash table of size p.

Hash-Search-Linear and Hash-Insert-Linear, using open addressing for resolving conflicts on a hash table of size p, and linear probing with h(k) = p(( k) mod 1) where is a real number. (therefore the probe sequence will be defined by h(k, i) = (h(k) + i) mod p, for all 0 i < p).

Hash-Search-Double and Hash-Insert-Double, using open addressing for resolving conflicts on a hash table of size p, and double hashing with h1(k) = k mod p and h2(k) = 1+(k mod (p2)) (the probe sequence will then be defined by h(k, i) = (h1(k) + i h2(k)) mod p, for all 0 i < p).

In each of the items below, you will insert the sequence of keys in the order that they appear in the input file into an initially empty hash table and store it in a separate output file.

Chained-Hash-Insert. Print out the linked lists headed by each slot of the table (one linked list per line, with space between consecutive elements of the list), in increasing order of the indices of the slots, right after you have finished inserting the sequence of keys. Indicate at the beginning of each list to which slot it corresponds to. Now search for the key k1 (read from the input file) in your table and print out the index of the slot that heads the linked list where this key was found.

Hash-Insert-Linear. Print out the contents of each slot in your hash table in increasing order of the indices of the slots, right after you have finished inserting the sequence of keys. Now search for the key k1 (read from the input file) in your table and print out the sequence of slots probed in the search until you find this key.

Hash-Insert-Double. Print out the contents of each slot in your hash table in increasing order of the indices of the slots, right after you have finished inserting the sequence of keys. Now search for key k1 (read from the input file) in your table and print out the sequence of slots probed in the search until you find this key.

Following is the format of the input and output files you should use for your program. One way of checking whether your program is working correctly is to test it on the sample input file on the blackboard and compare your output files with the corresponding output files on the blackboard.

Your program should be well documented. At the start of each function, you should inform the reader what this function is about and what algorithm(s) you are using.

1

HW 03: Programming assignment-Hashing 2

Format of the Input File: This file will be given as a parameter to the program. There will be a single value in each line of the input file. The first line will contain the value for p and the second line will contain the value for (the real number used in linear hashing). The next line will be the number of keys that need to be inserted into the hash table which we will call n. The subsequent n lines will contain the actual keys. Finally the last line will contain the value for k1 which is the key that your program should be searching for after it has inserted all of the n elements into the hash table.

Format of the Output Files:

Chained Hash: The first p lines of this output file will represent the p slots of the hash table. In the beginning of each line will be the index of that slot (0 through p 1) followed by a :. Then for each slot, output the elements according to the order they appear on the linked list. (New elements will be inserted at the head of the linked list.)

Next, output the slot that contains key k1.

Linear Hash: The first p lines of this output file will represent the p slots of the hash table. In the beginning of each line will be the index of that slot (0 through p 1) followed by a :. Then for each slot, print out the element in that slot, if there exists one.

Next, print the sequence of probes made for key k1 in a single line with space delimiters.

Double Hash The first p lines of this output file will represent the p slots of the hash table. In the beginning of each line will be the index of that slot (0 through p 1) followed by a :. Then for each slot, print out the element in that slot if there exists one.

Next, print the sequence of probes made for key k1 in a single line with space delimiter. You should also prepare a Makefile which will compile your program and make sure your executable file is

named Hashtable.